The C++ Standard Template Library (STL)

Douglas C. Schmidt
[email protected]
www.dre.vanderbilt.edu/~schmidt

Professor of Computer Science

Institute for Software
Integrated Systems

Vanderbilt University
Nashville, Tennessee, USA
The C++ STL Douglas C. Schmidt

The C++ Standard Template Library: Presentation Outline

• What is STL?
• Generic programming: Why use STL?
• Overview of STL concepts & features
– e.g., helper class & function templates, ,
containers, iterators, generic algorithms,
function objects, adapters
• A complete STL example
• References for more information on STL

Vanderbilt University 1
The C++ STL Douglas C. Schmidt

What is the C++ Standard Template Library (STL)?

STL is a subset of the Standard
C++ library that provides a set
of well-structured generic C++
components that work together
in a seamless way

2
See en.wikipedia.org/wiki/Standard_Template_Library
The C++ STL Douglas C. Schmidt

What is the C++ Standard Template Library (STL)?

• A collection of composable class Iterators are Iterators are

passed to perform Container passed to perform
& function templates a function of data an algorithm
elements
– Helper class & function
templates: operators, pair Functors acts on Algorithm
elements, holds acts on
– Container & iterator class data & does actions elements
templates on them
– Generic algorithms that Functors are sometimes passed
operate over iterators to algorithms & containers to
direct their actions
– Functors (function objects)
– adapters

Vanderbilt University 3
The C++ STL Douglas C. Schmidt

What is the C++ Standard Template Library (STL)?

• Enables generic programming in C++

3
See en.wikipedia.org/wiki/Generic_programming
The C++ STL Douglas C. Schmidt

What is the C++ Standard Template Library (STL)?

• Enables generic programming in C++ template <typename InputIterator,
typename T>
– A programming paradigm in which InputIterator find
algorithms are written in terms of (InputIterator first,
generic types, which are instantiated InputIterator last,
when needed for specific types const T& value) {
provided as parameters while (first != last
&& *first != value)
++first;
return first;
}
...
vector<int> v {1, 2, 3, 4};
auto i = find(v.begin(),
v.end(),
3);

3
The C++ STL Douglas C. Schmidt

What is the C++ Standard Template Library (STL)?

• Enables generic programming in C++ template <typename InputIterator,
typename T>
– A programming paradigm in which InputIterator find
algorithms are written in terms of (InputIterator first,
generic types, which are instantiated InputIterator last,
when needed for specific types const T& value) {
provided as parameters while (first != last
– Each generic algorithm can operate over && *first != value)
++first;
any iterator for which the necessary
return first;
operations are provided }
...
int a[] = {1, 2, 3, 4};
int *e = a + sizeof(a)/sizeof(*a);
auto i = find(a, e, 3);

3
The C++ STL Douglas C. Schmidt

What is the C++ Standard Template Library (STL)?

• Enables generic programming in C++
– A programming paradigm in which
algorithms are written in terms of
generic types, which are instantiated
when needed for specific types
provided as parameters
– Each generic algorithm can operate over
any iterator for which the necessary
operations are provided
– Extensible: can support new algorithms,
containers, iterators

3
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Reuse: “write less, do more”

Vanderbilt University 4
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Reuse: “write less, do more”

– STL hides complex, tedious, & error-
prone details
• e.g., dynamic memory management,
complex data structures & algorithms,
many optimizations, etc.

4
Programmers can thus focus on the (business) problem at hand
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Reuse: “write less, do more” vector<int> v{2, 4, 3, 5, 1};

list<int> l{5, 2, 1, 2, 3};
– STL hides complex, tedious, & error-
prone details sort(v.begin(), v.end()); // Ok
– Ensures type-safe plug compatibility sort(l.begin(), l.end()); // Error
between STL components

4
C++ STL performs static type checking to enhance correctness & performance
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Flexibility

Vanderbilt University 4
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Flexibility vector<int> v{1, 2, 3, 4, 5};

list<int> l{5, 4, 3, 2, 1};
– Iterators decouple algorithms
from containers auto vi = find(v.begin(),
v.end(),
5);

auto li = find(l.begin(),
l.end(),
5);

Vanderbilt University 4
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Flexibility vector<int> v{1, 2, 3, 4, 5};

list<int> l{5, 4, 3, 2, 1};
– Iterators decouple algorithms
from containers template<typename T>
– Unanticipated combinations struct greater_than_5 {
easily supported bool operator()(const T &i)
• e.g., via adapters { return i > 5; }
};

auto i = find_if(v.begin, v.end(),

greater_than_5<>());
auto vi = find_if(v.begin(), v.end(),
bind(greater<>, _1, 5));
auto li = find_if(l.begin(), l.end(),
not_fn(bind(greater<>, _1, 5));

Vanderbilt University 4
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Efficiency

Vanderbilt University 4
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Efficiency vector<int> v{2, 4, 3, 5, 1};

list<int> l{5, 2, 1, 2, 3};
– Templates & inlining avoids
virtual function overhead sort(v.begin(), v.end());
l.sort();

Vanderbilt University 4
The C++ STL Douglas C. Schmidt

Generic Programming: Why Use STL?

• Efficiency
– Templates & inlining avoids
virtual function overhead
– Strict attention to time
complexity of algorithms

Vanderbilt University 4
The C++ STL Douglas C. Schmidt

Generic Programming with C++ Function & Class Templates

• C++ STL makes heavy use of
function templates & class templates

5
See en.wikipedia.org/wiki/Template_(C++)
The C++ STL Douglas C. Schmidt

Generic Programming with C++ Function & Class Templates

• C++ STL makes heavy use of template <typename InputIterator,
function templates & class templates typename T>
InputIterator find
• Function templates are C++ (InputIterator first,
functions that can operate on InputIterator last,
different data types without const T& value) {
separate code for each of them while (first != last
&& *first != value)
++first;
return first;
}

5
The C++ STL Douglas C. Schmidt

Generic Programming with C++ Function & Class Templates

• C++ STL makes heavy use of template <typename T,
function templates & class templates typename Container =
deque<T>>
• Function templates are C++ class stack {
functions that can operate on public:
different data types without explicit stack(const Container&);
separate code for each of them bool empty() const;
• Class templates define a family size_type size() const;
value_type& top();
of classes parameterized by type
const value_type& top() const;
or values void push(const value_type& t);
• If a set of functions have the void pop();
same functionality for different private :
data types, this becomes a Container container_ ;
good class template // …
};