The C++ Standard Template Library

Douglas C. Schmidt
Professor Department of EECS
[email protected] Vanderbilt University
www.dre.vanderbilt.edu/∼schmidt/ (615) 343-8197

February 12, 2014

The C++ STL Douglas C. Schmidt

The C++ Standard Template Library

• 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, adaptors
• A Complete STL Example
• References for More Information on STL

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

What is STL?

The Standard Template Library provides a set of well structured

generic C++ components that work together in a seamless way.

–Alexander Stepanov & Meng Lee, The Standard Template Library

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

What is STL (cont’d)?

• A collection of composable class & function templates

– Helper class & function templates: operators, pair
– Container & iterator class templates
– Generic algorithms that operate over iterators
– Function objects
– Adaptors
• Enables generic programming in C++
– Each generic algorithm can operate over any iterator for which the
necessary operations are provided
– Extensible: can support new algorithms, containers, iterators

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

Generic Programming: Why Use STL?

• Reuse: “write less, do more”

– STL hides complex, tedious & error prone details
– The programmer can then focus on the problem at hand
– Type-safe plug compatibility between STL components
• Flexibility
– Iterators decouple algorithms from containers
– Unanticipated combinations easily supported
• Efficiency
– Templates avoid virtual function overhead
– Strict attention to time complexity of algorithms

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

STL Features: Containers, Iterators, & Algorithms

• Containers
– Sequential: vector, deque, list
– Associative: set, multiset, map, multimap
– Adapters: stack, queue, priority queue
• Iterators
– Input, output, forward, bidirectional, & random access
– Each container declares a trait for the type of iterator it provides
• Generic Algorithms
– Mutating, non-mutating, sorting, & numeric

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

STL Container Overview

• STL containers are Abstract Data Types (ADTs)

• All containers are parameterized by the type(s) they contain
• Each container declares various traits
– e.g., iterator, const iterator, value type, etc.
• Each container provides factory methods for creating iterators:
– begin()/end() for traversing from front to back
– rbegin()/rend() for traversing from back to front

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

Types of STL Containers

• There are three types of containers
– Sequential containers that arrange the data they contain in a
linear manner
∗ Element order has nothing to do with their value
∗ Similar to builtin arrays, but needn’t be stored contiguous
– Associative containers that maintain data in structures suitable
for fast associative operations
∗ Supports efficient operations on elements using keys ordered
by operator<
∗ Implemented as balanced binary trees
– Adapters that provide different ways to access sequential &
associative containers
∗ e.g., stack, queue, & priority queue

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

STL Vector Sequential Container

• A std::vector is a dynamic #include <iostream>
array that can grow & shrink #include <vector>
#include <string>
at the end
int main (int argc, char *argv[])
– e.g., it provides {
(pre—re)allocation, std::vector <std::string> projects;

indexed storage, std::cout << "program name:"

push back(), << argv[0] << std::endl;
pop back() for (int i = 1; i < argc; ++i) {
projects.push_back (argv [i]);
• Supports random access std::cout << projects [i - 1]
iterators << std::endl;
}
• Similar to—but more
return 0;
powerful than—built-in }
C/C++ arrays

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

STL Deque Sequential Container

• A std::deque (pronounced #include <deque>
“deck”) is a double-ended #include <iostream>
#include <iterator>
queue #include <algorithm>

• It adds efficient insertion & int main() {

removal at the beginning & std::deque<int> a_deck;
a_deck.push_back (3);
end of the sequence via a_deck.push_front (1);
push front() & a_deck.insert (a_deck.begin () + 1, 2);
a_deck[2] = 0;
pop front() std::copy (a_deck.begin (), a_deck.end (),
std::ostream_iterator<int>
(std::cout, " "));
return 0;
}

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

STL List Sequential Container

• A std::list has #include <list>
constant time #include <iostream>
#include <iterator>
insertion & deletion at #include <string>
any point in the int main() {
std::list<std::string> a_list;
sequence (not just at a_list.push_back ("banana");
the beginning & end) a_list.push_front ("apple");
a_list.push_back ("carrot");
– performance
std::ostream_iterator<std::string> out_it
trade-off: does not (std::cout, "\n");
offer a random
access iterator std::copy (a_list.begin (), a_list.end (), out_it);
std::reverse_copy (a_list.begin (), a_list.end (),
• Implemented as out_it);
std::copy (a_list.rbegin (), a_list.rend (), out_it);
doubly-linked list return 0;
}

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

STL Associative Container: Set

• An std::set is an #include <iostream>
ordered collection #include <iterator>
#include <set>
of unique keys
int main () {
– e.g., a set of std::set<int> myset;
student id
for (int i = 1; i <= 5; i++) myset.insert (i*10);
numbers std::pair<std::set<int>::iterator,bool> ret =
myset.insert (20);
assert (ret.second == false);

int myints[] = {5, 10, 15};

myset.insert (myints, myints + 3);

std::copy (myset.begin (), myset.end (),

std::ostream_iterator<int> (std::cout, "\n"));
return 0;
}

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

STL Pair Helper Class

• This template group is the template <typename T, typename U>
basis for the map & set struct pair {

associative containers because // Data members

it stores (potentially) T first;
U second;
heterogeneous pairs of data
together // Default constructor
pair () {}
• A pair binds a key (known as
// Constructor from values
the first element) with an pair (const T& t, const U& u)
associated value (known as the : first (t), second (u) {}
second element) };

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

STL Pair Helper Class (cont’d)

// Pair equivalence comparison operator
template <typename T, typename U>
inline bool
operator == (const pair<T, U>& lhs, const pair<T, U>& rhs)
{
return lhs.first == rhs.first && lhs.second == rhs.second;
}

// Pair less than comparison operator

template <typename T, typename U>
inline bool
operator < (const pair<T, U>& lhs, const pair<T, U>& rhs)
{
return lhs.first < rhs.first ||
(!(rhs.first < lhs.first) && lhs.second < rhs.second);
}

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

STL Associative Container: Map

• An std::map associates #include <iostream>
a value with each unique #include <map>
#include <string>
key #include <algorithm>

– a student’s id number typedef std::map<std::string, int> My_Map;

• Its value type is struct print {

void operator () (const My_Map::value_type &p)
implemented as { std::cout << p.second << " "
pair<const Key, << p.first << std::endl; }
Data> };

int main() {
My_Map my_map;
for (std::string a_word;
std::cin >> a_word; ) my_map[a_word]++;
std::for_each (my_map.begin(),
my_map.end(), print ());
return 0;
}

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

STL Associative Container: MultiSet & MultiMap

• An std::multiset or an std::multimap can support multiple

equivalent (non-unique) keys
– e.g., student first names or last names
• Uniqueness is determined by an equivalence relation
– e.g., strncmp() might treat last names that are distinguishable
by strcmp() as being the same

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

STL Associative Container: MultiSet Example

#include <set>
#include <iostream>
#include <iterator>

int main() {
const int N = 10;
int a[N] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};
int b[N] = {4, 4, 2, 4, 2, 4, 0, 1, 5, 5};

std::multiset<int> A(a, a + N);

std::multiset<int> B(b, b + N);
std::multiset<int> C;
std::cout << "Set A: ";
std::copy(A.begin(), A.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

std::cout << "Set B: ";

std::copy(B.begin(), B.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

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

STL Associative container: MultiSet Example (cont’d)

std::cout << "Union: ";
std::set_union(A.begin(), A.end(), B.begin(), B.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

std::cout << "Intersection: ";

std::set_intersection(A.begin(), A.end(), B.begin(), B.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
std::set_difference(A.begin(), A.end(), B.begin(), B.end(),
std::inserter(C, C.end()));
std::cout << "Set C (difference of A and B): ";
std::copy(C.begin(), C.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
return 0;
}

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

STL Iterator Overview

• STL iterators are a C++ implementation of the Iterator pattern

– This pattern provides access to the elements of an aggregate
object sequentially without exposing its underlying representation
– An Iterator object encapsulates the internal structure of how the
iteration occurs
• STL iterators are a generalization of pointers, i.e., they are objects
that point to other objects
• Iterators are often used to iterate over a range of objects: if an
iterator points to one element in a range, then it is possible to
increment it so that it points to the next element

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

STL Iterator Overview (cont’d)

• Iterators are central to generic programming because they are an

interface between containers & algorithms
– Algorithms typically take iterators as arguments, so a container
need only provide a way to access its elements using iterators
– This makes it possible to write a generic algorithm that operates
on many different kinds of containers, even containers as different
as a vector & a doubly linked list

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

Simple STL Iterator Example

#include <iostream>
#include <vector>
#include <string>

int main (int argc, char *argv[]) {

std::vector <std::string> projects; // Names of the projects

for (int i = 1; i < argc; ++i)

projects.push_back (std::string (argv [i]));

for (std::vector<std::string>::iterator j = projects.begin ();

j != projects.end (); ++j)
std::cout << *j << std::endl;
return 0;
}

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

STL Iterator Categories

• Iterator categories depend on type parameterization rather than on
inheritance: allows algorithms to operate seamlessly on both native
(i.e., pointers) & user-defined iterator types
• Iterator categories are hierarchical, with more refined categories
adding constraints to more general ones
– Forward iterators are both input & output iterators, but not all input
or output iterators are forward iterators
– Bidirectional iterators are all forward iterators, but not all forward
iterators are bidirectional iterators
– All random access iterators are bidirectional iterators, but not all
bidirectional iterators are random access iterators
• Native types (i.e., pointers) that meet the requirements can be used
as iterators of various kinds

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

STL Input Iterators

• Input iterators are used to read values from a sequence

• They may be dereferenced to refer to some object & may be
incremented to obtain the next iterator in a sequence
• An input iterator must allow the following operations
– Copy ctor & assignment operator for that same iterator type
– Operators == & != for comparison with iterators of that type
– Operators * (can be const) & ++ (both prefix & postfix)

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

STL Input Iterator Example

// Fill a vector with values read from standard input.
std::vector<int> v;
for (istream_iterator<int> i = cin;
i != istream_iterator<int> ();
++i)
v.push_back (*i);

// Fill vector with values read from stdin using std::copy()

std::vector<int> v;
std::copy (std::istream_iterator<int>(std::cin),
std::istream_iterator<int>(),
std::back_inserter (v));

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

STL Output Iterators

• Output iterator is a type that provides a mechanism for storing (but

not necessarily accessing) a sequence of values
• Output iterators are in some sense the converse of Input Iterators,
but have a far more restrictive interface:
– Operators = & == & != need not be defined (but could be)
– Must support non-const operator * (e.g., *iter = 3)
• Intuitively, an output iterator is like a tape where you can write a value
to the current location & you can advance to the next location, but you
cannot read values & you cannot back up or rewind

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

STL Output Iterator Example

// Copy a file to cout via a loop.
std::ifstream ifile ("example_file");
int tmp;
while (ifile >> tmp) std::cout << tmp;

// Copy a file to cout via input & output iterators

std::ifstream ifile ("example_file");
std::copy (std::istream_iterator<int> (ifile),
std::istream_iterator<int> (),
std::ostream_iterator<int> (std::cout));

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

STL Forward Iterators

• Forward iterators must implement (roughly) the union of

requirements for input & output iterators, plus a default ctor
• The difference from the input & output iterators is that for two
forward iterators r & s, r==s implies ++r==++s
• A difference to the output iterators is that operator* is also valid
on the left side of operator= (*it = v is valid) & that the number
of assignments to a forward iterator is not restricted

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

STL Forward Iterator Example

template <typename ForwardIterator, typename T>
void replace (ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value) {
for (; first != last; ++first)
if (*first == old_value) *first = new_value;
}

// Iniitalize 3 ints to default value 1

std::vector<int> v (3, 1);
v.push_back (7); // vector v: 1 1 1 7
replace (v.begin(), v.end(), 7, 1);
assert (std::find (v.begin(), v.end(), 7) == v.end());

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

STL Bidirectional Iterators

• Bidirectional iterators allow algorithms to pass through the elements

forward & backward
• Bidirectional iterators must implement the requirements for forward
iterators, plus decrement operators (prefix & postfix)
• Many STL containers implement bidirectional iterators
– e.g., list, set, multiset, map, & multimap

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

STL Bidirectional Iterator Example

template <typename BidirectionalIterator, typename Compare>
void bubble_sort (BidirectionalIterator first, BidirectionalIterator last,
Compare comp) {
BidirectionalIterator left_el = first, right_el = first;
++right_el;
while (first != last)
{
while (right_el != last) {
if (comp(*right_el, *left_el)) std::swap (left_el, right_el);
++right_el;
++left_el;
}
--last;
left_el = first, right_el = first;
++right_el;
}
}

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

STL Random Access Iterators

• Random access iterators allow algorithms to have random access to

elements stored in a container that provides random access iterators
– e.g., vector & deque
• Random access iterators must implement the requirements for
bidirectional iterators, plus:
– Arithmetic assignment operators += & -=
– Operators + & - (must handle symmetry of arguments)
– Ordering operators < & > & <= & >=
– Subscript operator [ ]

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

STL Random Access Iterator Example

std::vector<int> v (1, 1);
v.push_back (2); v.push_back (3); v.push_back (4); // vector v: 1 2 3 4

std::vector<int>::iterator i = v.begin();
std::vector<int>::iterator j = i + 2; cout << *j << " ";
i += 3; std::cout << *i << " ";
j = i - 1; std::cout << *j << " ";
j -= 2;
std::cout << *j << " ";
std::cout << v[1] << endl;

(j < i) ? std::cout << "j < i" : std::cout << "not (j < i)";
std::cout << endl;
(j > i) ? std::cout << "j > i" : std::cout << "not (j > i)";
std::cout << endl;
i = j;
i <= j && j <= i ? std::cout << "i & j equal" :
std::cout << "i & j not equal"; std::cout << endl;

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

Implementing Iterators Using STL Patterns

• Since a C++ iterator provides a familiar, standard interface, at some

point you will want to add one to your own classes so you can
“plug-&and-play with STL algorithms
• Writing your own iterators is a straightforward (albeit tedious
process, with only a couple of subtleties you need to be aware of,
e.g., which category to support, etc.
• Some good articles on using & writing STL iterators appear at
– http://www.oreillynet.com/pub/a/network/2005/10/
18/what-is-iterator-in-c-plus-plus.html
– http://www.oreillynet.com/pub/a/network/2005/11/
21/what-is-iterator-in-c-plus-plus-part2.html

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

STL Generic Algorithms

• Algorithms operate over iterators rather than containers
• Each container declares an iterator & const iterator as a
trait
– vector & deque declare random access iterators
– list, map, set, multimap, & multiset declare bidirectional
iterators
• Each container declares factory methods for its iterator type:
– begin(), end(), rbegin(), rend()
• Composing an algorithm with a container is done simply by invoking
the algorithm with iterators for that container
• Templates provide compile-time type safety for combinations of
containers, iterators, & algorithms

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

Categorizing STL Generic Algorithms

• There are various ways to categorize STL algorithms, e.g.:
– Non-mutating, which operate using a range of iterators, but don.t
change the data elements found
– Mutating, which operate using a range of iterators, but can
change the order of the data elements
– Sorting & sets, which sort or searches ranges of elements & act
on sorted ranges by testing values
– Numeric, which are mutating algorithms that produce numeric
results
• In addition to these main types, there are specific algorithms within
each type that accept a predicate condition
– Predicate names end with the if suffix to remind us that they
require an “if” test.s result (true or false), as an argument; these
can be the result of functor calls

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

Benefits of STL Generic Algorithms

• STL algorithms are decoupled from the particular containers they

operate on & are instead parameterized by iterators
• All containers with the same iterator type can use the same
algorithms
• Since algorithms are written to work on iterators rather than
components, the software development effort is drastically reduced
– e.g., instead of writing a search routine for each kind of container,
one only write one for each iterator type & apply it any container.
• Since different components can be accessed by the same iterators,
just a few versions of the search routine must be implemented

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

Example of std::find() Algorithm

Returns a forward iterator positioned at the first element in the given
sequence range that matches a passed value
#include <vector>
#include <algorithm>
#include <assert>
#include <string>

int main (int argc, char *argv[]) {

std::vector <std::string> projects;
for (int i = 1; i < argc; ++i)
projects.push_back (std::string (argv [i]));

std::vector<std::string>::iterator j =
std::find (projects.begin (), projects.end (), std::string ("Lab8"));

if (j == projects.end ()) return 1;

assert ((*j) == std::string ("Lab8"));
return 0;
}

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

Example of std::find() Algorithm (cont’d)

STL algorithms can work on both built-in & user-defined types
int a[] = {10, 30, 20, 15}; int A[] = {10, 30, 20, 15};
int *ibegin = a; std::set<int> int_set
int *iend = (A, A + (sizeof (A)/ sizeof (*A)));
a + (sizeof (a)/ sizeof (*a));
int *iter = std::set<int>::iterator iter =
std::find (ibegin, iend, 10); // int_set.find (10) will be faster!
if (iter == iend) std::find (int_set.begin (),
std::cout << "10 not found\n"; int_set.end (), 10);
else if (iter == int_set.end ())
std::cout << *iter << " found\n"; std::cout << "10 not found\n";
else
std::cout << *iter << " found\n";

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

Example std::adjacent find() Algorithm

Returns the first iterator i such that i & i + 1 are both valid iterators
in [first, last), & such that *i == *(i+1) or binary pred
(*i, *(i+1)) is true (it returns last if no such iterator exists)
// Find the first element that is greater than its successor:
int A[] = {1, 2, 3, 4, 6, 5, 7, 8};
const int N = sizeof(A) / sizeof(int);

const int *p = std::adjacent_find(A, A + N, std::greater<int>());

std::cout << "Element " << p - A << " is out of order: "
<< *p << " > " << *(p + 1) << "." << std::endl;

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

Example of std::copy() Algorithm

Copies elements from a input iterator sequence range into an output
iterator
std::vector<int> v;
std::copy (std::istream_iterator<int>(std::cin),
std::istream_iterator<int>(),
std::back_inserter (v));

std::copy (v.begin (),

v.end (),
std::ostream_iterator<int> (std::cout));

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

Example of std::fill() Algorithm

Assign a value to the elements in a sequence
int a[10];
std::fill (a, a + 10, 100);
std::fill_n (a, 10, 200);

std::vector<int> v (10, 100);

std::fill (v.begin (), v.end (), 200);
std::fill_n (v.begin (), v.size (), 200);

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

Example of std::replace() Algorithm

Replaces all instances of a given existing value with a given new value,
within a given sequence range
std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(1);

std::replace (v.begin (), v.end (), 1, 99);

assert (V[0] == 99 && V[3] == 99);

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

Example of std::remove() Algorithm

Removes from the range [first, last) the elements with a value
equal to value & returns an iterator to the new end of the range, which
now includes only the values not equal to value
#include <iostream>
#include <algorithm>
#include <iterator>

int main () {
int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};
int *pbegin = myints, *pend = myints + sizeof myints / sizeof *myints;
std::cout << "original array contains:";
std::copy (pbegin, pend, std::ostream_iterator<int> (std::cout, " "));
int *nend = std::remove (pbegin, pend, 20);
std::cout << "\nrange contains:";
std::copy (pbegin, nend, std::ostream_iterator<int> (std::cout, " "));
std::cout << "\ncomplete array contains:";
std::copy (pbegin, pend, std::ostream_iterator<int> (std::cout, " "));
std::cout << std::endl;
return 0;
}

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

Example of std::remove if() Algorithm

Removes from the range [first, last) the elements for which
pred applied to its value is true, & returns an iterator to the new end of
the range, which now includes only the values for which pred was false.
#include <iostream>
#include <algorithm>

struct is_odd { // Could also be a C-style function.

bool operator () (int i) { return (i%2)==1; }
};

int main () {
int myints[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int *pbegin = myints;
int *pend = myints + sizeof myints / sizeof *myints;
pend = std::remove_if (pbegin, pend, is_odd ());
std::cout << "range contains:";
std::copy (pbegin, pend, std::ostream_iterator<int> (std::cout, " "));
std::cout << std::endl;
return 0;
}

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

Example of std::transform() Algorithm

Scans a range & for each use a function to generate a new object put
in a second container or takes two intervals & applies a binary
operation to items to generate a new container
#include <iostream> std::string lower (const std::string &str) {
#include <algorithm> std::string lc;
#include <ctype.h> std::transform (str.begin (), str.end (),
#include <functional> std::back_inserter (lc),
to_lower ());
class to_lower { return lc;
public: }
char operator() (char c) const
{ int main () {
return isupper (c) std::string s = "HELLO";
? tolower(c) : c; std::cout << s << std::endl;
} s = lower (s);
}; std::cout << s << std::endl;
}

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

Another Example of std::transform() Algorithm

#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <iterator>

int main() {
std::vector<float> v (5, 1); // a vector of 5 floats all initialized to 1.0.
std::partial_sum (v.begin(), v.end(), v.begin());

std::transform(v.begin(), v.end(), v.begin(),

v.begin(), std::multiplies<float>());
std::copy (v.begin (), v.end (), std::ostream_iterator<float> (std::cout, "\n"));

std::transform(v.begin(),v.end(), v.begin (),

std::bind2nd(std::divides<float>(), 3));
std::copy (v.begin (), v.end (), std::ostream_iterator<float> (std::cout, "\n"));
return 0;
}

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

Example of std::for each() Algorithm

Applies the function object f to each element in the range [first,
last); f’s return value, if any, is ignored
template<class T>
struct print {
print (std::ostream &out): os_(out), count_(0) {}
void operator() (const T &t) { os << t << ’ ’; ++count_; }
std::ostream &os_;
int count_;
};

int main() {
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);

// for_each() returns function object after being applied to each element

print<int> f = std::for_each (A, A + N, print<int>(std::cout));
std::cout << std::endl << f.count_ << " objects printed." << std::endl;
}

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

STL Function Objects

• Function objects (aka functors) declare & define operator()

• STL provides helper base class templates unary function &
binary function to facilitate user-defined function objects
• STL provides a number of common-use function object class
templates:
– Arithmetic: plus, minus, times, divides, modulus, negate
– comparison: equal to, not equal to, greater, less,
greater equal, less equal
– logical: logical and, logical or, logical not
• A number of STL generic algorithms can take STL-provided or
user-defined function object arguments to extend algorithm behavior

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

STL Function Objects Example

#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
#include <string>

int main (int argc, char *argv[])

{
std::vector <std::string> projects;

for (int i = 0; i < argc; ++i)

projects.push_back (std::string (argv [i]));

// Sort in descending order: note explicit ctor for greater

std::sort (projects.begin (), projects.end (),
std::greater<std::string> ());

return 0;
}

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

STL Adaptors

• STL adaptors implement the Adapter design pattern

– i.e., they convert one interface into another interface clients expect
• Container adaptors include stack, queue, priority queue
• Iterator adaptors include reverse iterators &
back inserter() iterators
• Function adaptors include negators & binders
• STL adaptors can be used to narrow interfaces (e.g., a stack
adaptor for vector)

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

STL Container Adaptors

• The stack container adaptor is an ideal choice when one need to

use a “Last In, First Out” (LIFO) data structure characterized by
having elements inserted & removed from the same end
• The queue container adaptor is a “First In, First Out” (FIFO) data
structure characterized by having elements inserted into one end &
removed from the other end
• The priority queue assigns a priority to every element that it
stores
– New elements are added to the queue using the push() function,
just as with a queue
– However, its pop() function gets element with the highest priority

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

STL stack & queue Container Adaptor Definitions

template <typename T, template <typename T,
typename ST = deque<T> > typename Q = deque<T> >
class stack class queue
{ {
public: public:
explicit stack(const ST& c = ST()); explicit queue(const Q& c = Q());
bool empty() const; bool empty() const;
size_type size() const; size_type size() const;
value_type& top(); value_type& front();
const value_type& top() const; const value_type& front() const;
void push(const value_type& t); value_type& back();
void pop(); const value_type& back() const;
void push(const value_type& t);
private : void pop();
ST container_ ;
//. private:
}; Q container_;
// .
};

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

STL stack & queue Container Adaptor Examples

// STL stack // STL queue
#include <iostream> #include <iostream>
#include <stack> #include <queue>
#include <string>
int main() { int main() {
std::stack<char> st; std::queue<string> q;
st.push (’A’); std::cout << "Pushing one two three \n";
st.push (’B’); q.push ("one");
st.push (’C’); q.push ("two");
st.push (’D’); q.push ("three");

for (; !st.empty (); st.pop ()) { for (; !q.empty (); q.pop ()) {
cout << "\nPopping: "; std::cout << "\nPopping ";
cout << st.top(); std::cout << q.front ();
} }
return 0; return 0;
} }

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

STL priority queue Container Adaptor Example

#include <queue> // priority_queue
#include <string>
#include <iostream>

struct Place {
unsigned int dist; std::string dest;
Place (const std::string dt, size_t ds) : dist(ds), dest(dt) {}
bool operator< (const Place &right) const { return dist < right.dist; }
};

std::ostream &operator << (std::ostream &os, const Place &p)

{ return os << p.dest << " " << p.dist; }

int main () {
std::priority_queue <Place> pque;
pque.push (Place ("Poway", 10));
pque.push (Place ("El Cajon", 20));
pque.push (Place ("La Jolla", 3));
for (; !pque.empty (); pque.pop ()) std::cout << pque.top() << std::endl;
return 0;
}

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

STL Iterator Adaptors

• STL algorithms that copy elements are passed an iterator that
marks the position within a container to begin copying
– e.g., copy(), unique copy(), copy backwards(),
remove copy(), & replace copy()
• With each element copied, the value is assigned & the iterator is
incremented
• Each copy requires the target container is of a sufficient size to hold
the set of assigned elements
• We can use iterator adapters to expand the containers as we
perform the algorithm
– Start with an empty container, & use the inserter along with the
algorithms to make the container grow only as needed

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

STL back inserter() Iterator Adaptor Example

• back inserter() causes // Fill vector with values read
the container’s push back() // from stdin using std::copy()
operator to be invoked in place std::vector<int> v;
std::vector<int>::iterator in_begin =
of the assignment operator
std::istream_iterator<int>(std::cin)
• The argument passed to std::vector<int>::iterator in_end =
back inserter() is the std::istream_iterator<int>(),
std::copy (in_begin,
container itself
in_end,
std::back_inserter (v));

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

STL Function Adaptors

• STL has predefined functor adaptors that will change their functors
so that they can:
– Perform function composition & binding
– Allow fewer created functors
• These functors allow one to combine, transform or manipulate
functors with each other, certain values or with special functions
• STL function adapters include
– Binders (bind1st() & bind2nd()) bind one of their arguments
– Negators (not1 & not2) adapt functors by negating arguments
– Member functions (ptr fun & mem fun) allow functors to be
class members

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

STL Binder Function Adaptor

• A binder can be used to transform a binary functor into an unary one

by acting as a converter between the functor & an algorithm
• Binders always store both the binary functor & the argument
internally (the argument is passed as one of the arguments of the
functor every time it is called)
– bind1st(Op, Arg) calls ’Op’ with ’Arg’ as its first parameter
– bind2nd(Op, Arg) calls ’Op’ with ’Arg’ as its second parameter

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

STL Binder Function Adaptor Example 1

#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>

int main (int argc, char *argv[]) {

std::vector<int> v (10, 2);
std::partial_sum (v.begin (), v.end (), v.begin ());
std::random_shuffle (v.begin (), v.end ());
std::copy (v.begin (), v.end (), std::ostream_iterator<int> (std::cout, "\n"));
std::cout << "number greater than 10 = "
<< count_if (v.begin (), v.end (),
std::bind2nd (std::greater<int>(), 10)) << std::endl;
return 0;
}

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

STL Binder Function Adaptor Example 2

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <functional>
#include <cstdlib>
#include <ctime>

int main (int argc, char *argv[]) {

srand (time(0));
std::vector<int> v, v2 (10, 20);
std::generate_n (std::back_inserter (v), 10, rand);
std::transform (v.begin (), v.end (), v2.begin (), v.begin (), std::modulus<int>());
std::copy (v.begin (), v.end (), std::ostream_iterator<int> (std::cout, "\n"));
std::cout << std::endl;
int factor = 2;
std::transform (v.begin (), v.end (),
v.begin(), std::bind2nd (std::multiplies<int> (), factor));
std::copy (v.begin (), v.end (), std::ostream_iterator<int> (std::cout, "\n"));
return 0;
}

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

STL Binder Function Adaptor Example 3

This example removes spaces in a string that uses the equal to and
bind2nd functors to perform remove if when equal to finds a
blank char in the string
#include <iostream>
#include <string>

int main() {
std::string s = "spaces in text";
std::cout << s << std::endl;
std::string::iterator new_end =
std::remove_if (s.begin (), s.end (), std::bind2nd (std::equal_to<char>(), ’ ’));

// remove_if() just moves unwanted elements to the end and returns an iterator
// to the first unwanted element since it’.s a generic algorithm & doesn’t "know"
// whether the container be changed. s.erase() *does* know this, however..
s.erase (new_end, s.end ());
std::cout << s << std::endl;
return 0;
}

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

STL Binder Function Adaptor Example 4

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>

int main() { // Contrasts std::remove_if() & erase().

std::vector<int> v;
v.push_back (1); v.push_back (4); v.push_back (2);
v.push_back (8); v.push_back (5); v.push_back (7);
std::copy (v.begin (), v.end (), std::ostream_iterator<int> (std::cout, " "));
int sum = std::count_if (v.begin (), v.end (),
std::bind2nd (std::greater<int>(), 5));
std::cout << "\nThere are " << sum << " number(s) greater than 5" << std::endl;
std::vector<int>::iterator new_end = // "remove" all the elements less than 4.
std::remove_if (v.begin (), v.end (), std::bind2nd (std::less<int>(), 4));
v.erase (new_end, v.end ());
std::copy (v.begin (), v.end (), std::ostream_iterator<int> (std::cout, " "));
std::cout << "\nElements less than 4 removed" << std::endl;
return 0;
}

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

STL Negator Adapters & Function Adaptors

• A negator can be used to store the opposite result of a functor

– not1(Op) negates the result of unary ’Op’
– not2(Op) negates result of binary ’Op’
• A member function & pointer-to-function adapter can be used to
allow class member functions or C-style functions as arguments to
STL predefined algorithms
– mem fun(PtrToMember mf) converts a pointer to member to a
functor whose first arg is a pointer to the object
– ptr fun() converts a pointer to a function & turns it into a
functor

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

STL Negator Function Adaptor Example

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>

int main() {
std::vector<int> v1;
v1.push_back (1); v1.push_back (2); v1.push_back (3); v1.push_back (4);
std::vector<int> v2;
std::remove_copy_if (v1.begin(), v1.end(), std::back_inserter (v2),
std::bind2nd (std::greater<int> (), 3));
std::copy (v2.begin(), v2.end (),
std::ostream_iterator<int> (std::cout, "\n"));
std::vector<int> v3;
std::remove_copy_if (v1.begin(), v1.end(), std::back_inserter (v3),
std::not1 (std::bind2nd (std::greater<int> (), 3)));
std::copy (v3.begin(), v3.end (),
std::ostream_iterator<int> (std::cout, "\n"));
return 0;
}

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

STL Pointer-to-MemFun Adaptor Example

class WrapInt {
public:
WrapInt (): val_ (0) {}
WrapInt(int x): val_ (x) {}

void showval() {
std::cout << val_ << " ";
}

bool is_prime() {
for (int i = 2; i <= (val_ / 2); i++)
if ((val_ % i) == 0)
return false;
return true;
}
private:
int val_;
};

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

STL Pointer-to-MemFun Adaptor Example (cont’d)

int main() {
std::vector<WrapInt> v (10);

for (int i = 0; i <10; i++)

v[i] = WrapInt (i+1);

std::cout << "Sequence contains: ";

std::for_each (v.begin (), v.end (),
std::mem_fun_ref (&WrapInt::showval));
std::cout << std::endl;

std::vector<WrapInt>::iterator end_p = // remove the primes

std::remove_if (v.begin(), v.end(),
std::mem_fun_ref (&WrapInt::is_prime));

std::cout << "Sequence after removing primes: ";

for_each (v.begin (), end_p, std::mem_fun_ref (&WrapInt::showval));
std::cout << std::endl;

return 0;
}

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

STL Pointer-to-Function Adaptor Example

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>

int main () {
std::vector<char *> v;
v.push_back ("One"); v.push_back ("Two"); v.push_back ("Three"); v.push_back ("Four");

std::cout << "Sequence contains:";

std::copy (v.begin (), v.end (), std::ostream_iterator<char *> (std::cout, " "));
std::cout << std::endl << "Searching for Three.\n";
std::vector<char *>::iterator it = std::find_if (v.begin (), v.end (),
std::not1 (std::bind2nd (std::ptr_fun (strcmp), "Three")));
if (it != v.end ()) {
std::cout << "Found it! Here is the rest of the story:";
std::copy (it, v.end (), std::ostream_iterator<char *> (std::cout, "\n"));
}
return 0;
}

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

STL Utility Operators

template <typename T, typename U>

inline bool
operator != (const T& t, const U& u)
{
return !(t == u);
}

template <typename T, typename U>

inline bool
operator > (const T& t, const U& u)
{
return u < t;
}

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

STL Utility Operators (cont’d)

template <typename T, typename U>

inline bool
operator <= (const T& t, const U& u)
{
return !(u < t);
}

template <typename T, typename U>

inline bool
operator >= (const T& t, const U& u)
{
return !(t < u);
}

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

STL Utility Operators (cont’d)

• Question: why require that parameterized types support operator ==

as well as operator <?
– Operators > & >= & <= are implemented only in terms of
operator < on u & t (and ! on boolean results)
– Could implement operator == as
!(t < u) && !(u < t)
so classes T & U only had to provide operator < & did not have to
provide operator ==
• Answer: efficiency (two operator < calls are needed to implement
operator == implicitly)
• Answer: allows equivalence classes of ordered types

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

STL Example: Course Schedule

• Goals:
– Read in a list of course names, along with the corresponding
day(s) of the week & time(s) each course meets
∗ Days of the week are read in as characters M,T,W,R,F,S,U
∗ Times are read as unsigned decimal integers in 24 hour HHMM
format, with no leading zeroes (e.g., 11:59pm should be read in
as 2359, & midnight should be read in as 0)
– Sort the list according to day of the week & then time of day
– Detect any times of overlap between courses & print them out
– Print out an ordered schedule for the week
• STL provides most of the code for the above

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

STL Example: Course Schedule (cont’d)

% cat infile % cat infile | xargs main
CS101 W 1730 2030
CS242 T 1000 1130 CONFLICT:
CS242 T 1230 1430 CS242 T 1230 1430
CS242 R 1000 1130 CS281 T 1300 1430
CS281 T 1300 1430
CS281 R 1300 1430 CS282 M 1300 1430
CS282 M 1300 1430 CS242 T 1000 1130
CS282 W 1300 1430 CS242 T 1230 1430
CS201 T 1600 1730 CS281 T 1300 1430
CS201 R 1600 1730 CS201 T 1600 1730
CS282 W 1300 1430
CS101 W 1730 2030
CS242 R 1000 1130
CS281 R 1300 1430
CS201 R 1600 1730

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

STL Example: Course Schedule (cont’d)

struct Meeting { std::string title_;
enum Day_Of_Week // Title of the meeting
{MO, TU, WE, TH, FR, SA, SU};
static Day_Of_Week Day_Of_Week day_;
day_of_week (char c); // Week day of meeting

Meeting (const std::string &title, size_t start_time_;

Day_Of_Week day, // Meeting start time in HHMM format
size_t start_time,
size_t finish_time); size_t finish_time_;
Meeting (const Meeting & m); // Meeting finish time in HHMM format
Meeting (char **argv); };

Meeting &operator = // Helper operator for output

(const Meeting &m); std::ostream &
bool operator < operator << (std::ostream &os,
(const Meeting &m) const; const Meeting & m);
bool operator ==
(const Meeting &m) const;

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

STL Example: Course Schedule (cont’d)

Meeting::Day_Of_Week Meeting::Meeting
Meeting::day_of_week (char c) (const std::string &title,
{ Day_Of_Week day,
switch (c) { size_t start, size_t finish)
case ’M’: return Meeting::MO; : title_ (title), day_ (day),
case ’T’: return Meeting::TU; start_time_ (start),
case ’W’: return Meeting::WE; finish_time_ (finish) {}
case ’R’: return Meeting::TH;
case ’F’: return Meeting::FR; Meeting::Meeting (const Meeting &m)
case ’S’: return Meeting::SA; : title_ (m.title_), day_ (m.day_),
case ’U’: return Meeting::SU; start_time_ (m.start_time_),
default: finish_time_ (m.finish_time_) {}
assert (!"not a week day");
return Meeting::MO; Meeting::Meeting (char **argv)
} : title_ (argv[0]),
} day_ (Meeting::day_of_week (*argv[1])),
start_time_ (atoi (argv[2])),
finish_time_ (atoi (argv[3])) {}

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

STL Example: Course Schedule (cont’d)

Meeting &Meeting::operator = bool Meeting::operator <
(const Meeting &m) { (const Meeting &m) const
title_ = m.title_; {
day_ = m.day_; return
start_time_ = m.start_time_; day_ < m.day_
finish_time_ = m.finish_time_; ||
return *this; (day_ == m.day_
} &&
bool Meeting::operator == start_time_ < m.start_time_)
(const Meeting &m) const { ||
return (day_ == m.day_
(day_ == m.day_ && &&
((start_time_ <= m.start_time_ && start_time_ == m.start_time_
m.start_time_ <= finish_time_) || &&
(m.start_time_ <= start_time_ && finish_time_ < m.finish_time_)
start_time_ <= m.finish_time_))) ? true : false;
? true : false; }
}

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

STL Example: Course Schedule (cont’d)

std::ostream &operator << struct print_conflicts {
(std::ostream &os, print_conflicts (std::ostream &os)
const Meeting &m) { : os_ (os) {}
const char *d = " ";
switch (m.day_) { Meeting operator () (const Meeting &lhs,
case Meeting::MO: d="M "; break; const Meeting &rhs) {
case Meeting::TU: d="T "; break; if (lhs == rhs)
case Meeting::WE: d="W "; break; os_ << "CONFLICT:" << std::endl
case Meeting::TH: d="R "; break; << " " << lhs << std::endl
case Meeting::FR: d="F "; break; << " " << rhs << std::endl
case Meeting::SA: d="S "; break; << std::endl;
case Meeting::SU: d="U "; break; return lhs;
} }
return std::ostream &os_;
os << m.title_ << " " << d };
<< m.start_time_ << " "
<< m.finish_time_;
}

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

STL Example: Course Schedule (cont’d)

template <typename T>
class argv_iterator : public std::iterator <std::forward_iterator_tag, T> {
public:
argv_iterator (void) {}
argv_iterator (int argc, char **argv, int increment)
: argc_ (argc), argv_ (argv), base_argv_ (argv), increment_ (increment) {}

argv_iterator begin () { return *this; }

argv_iterator end () { return *this; }

bool operator != (const argv_iterator &) { return argv_ != (base_argv_ + argc_); }

T operator *() { return T (argv_); }

void operator++ () { argv_ += increment_; }

private:
int argc_;
char **argv_, **base_argv_;
int increment_;
};

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

STL Example: Course Schedule (cont’d)

int main (int argc, char *argv[]) {
std::vector<Meeting> schedule;

std::copy (argv_iterator<Meeting> (argc - 1, argv + 1, 4),

argv_iterator<Meeting> (),
std::back_inserter (schedule));

std::sort (schedule.begin (), schedule.end (), std::less<Meeting> ());

// Find & print out any conflicts.

std::transform (sched.begin (), sched.end () - 1,
sched.begin () + 1,
sched.begin (),
print_conflicts (std::cout));

// Print out schedule, using STL output stream iterator adapter.

std::copy (sched.begin (), sched.end (),
std::ostream_iterator<Meeting> (os, "\n"));
return 0;
}

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

Summary of the Class Scheduling Example

• STL promotes software reuse: writing less, doing more
– Effort focused on the Meeting class
– STL provided algorithms (e.g., sorting & copying), containers,
iterators, & functors
• STL is flexible, according to open/closed principle
– std::copy() algorithm with output iterator prints schedule
– Sort in ascending (default std::less) or descending (via
std::greater) order
• STL is efficient
– STL inlines methods, uses templates extensively
– Optimized both for performance & for programming model
complexity (e.g., requiring < & == & no others)

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

References: For More Information on STL

• David Musser’s STL page
– http://www.cs.rpi.edu/ musser/stl.html
• Stepanov & Lee, “The Standard Template Library”
– http://www.cs.rpi.edu/ musser/doc.ps
• SGI STL Programmer’s Guide
– http://www.sgi.com/Technology/STL/
• Musser & Saini, “STL Tutorial & Reference Guide”
– ISBN 0-201-63398-1
• Austern, “Generic Programming & the STL”
– ISBN 0-201-30956-4

Vanderbilt University 79