Standard Template Library (STL)

a compile-time error. In C99, <stdint.h> may define the types intptr_h and
uintptr_h.
Conventions for "Structured" TMP
14

5.2 Standard Template Library (STL)

The Standard Template Library (STL), part of the C++ S TANDARD L I BRARY 15 , offers collections of algorithms, containers, iterators, and other fundamental components, implemented as templates, classes, and functions essential to
extend functionality and standardization to C++. STL main focus is to provide
improvements implementation standardization with emphasis in performance and
correctness.
Instead of wondering if your array would ever need to hold 257 records or having
nightmares of string buffer overflows, you can enjoy vector and string that automatically extend to contain more records or characters. For example, vector is
just like an array, except that vectors size can expand to hold more cells or shrink
when fewer will suffice. One must keep in mind that the STL does not conflict with
OOP but in itself is not object oriented; In particular it makes no use of runtime
polymorphism (i.e., has no virtual functions).
The true power of the STL lies not in its CONTAINER16 classes, but in the fact
that it is a framework, combining algorithms with data structures using indirection
through iterators to allow generic implementations of higher order algorithms to
work efficiently on varied forms of data. To give a simple example, the same
std::copy function can be used to copy elements from one array to another, or to
copy the bytes of a file, or to copy the whitespace-separated words in "text like
this" into a container such as std::vector<std::string>.
// std::copy from array a to array b
int a[10] = { 3,1,4,1,5,9,2,6,5,4 };
int b[10];
std::copy(&a[0], &a[10], b);

14
15
16

H T T P :// E N . W I K I B O O K S . O R G / W I K I /C A T E G O R Y %3AC%2B%2B%20P R O G R A M M I N G
Chapter 3.1.2 on page 45
H T T P :// E N . W I K I B O O K S . O R G / W I K I /%23C O N T A I N E R S

499

Advanced Features

// std::copy from input stream a to an arbitrary OutputIterator

template <typename OutputIterator>
void f(std::istream &a, OutputIterator destination) {
std::copy(std::istreambuf_iterator<char>(a),
std::istreambuf_iterator<char>(),
destination);
}
// std::copy from a buffer containing text, inserting items in
// order at the back of the container called words.
std::istringstream buffer("text like this");
std::vector<std::string> words;
std::copy(std::istream_iterator<std::string>(buffer),
std::istream_iterator<std::string>(),
std::back_inserter(words));
assert(words[0] == "text");
assert(words[1] == "like");
assert(words[2] == "this");

5.2.1 History

Figure 25: Alexander

Stepanov

The C++ Standard Library incorporated part of the STL (published as a software
library by SGI17 /Hewlett-Packard Company). The primary implementer of the
C++ Standard Template Library was A LEXANDER S TEPANOV18 .
Today we call STL to what was adopted into the C++ Standard. The ISO C++
does not specify header content, and allows implementation of the STL either in
the headers, or in a true library.
17
18

500

H T T P :// E N . W I K I P E D I A . O R G / W I K I /S I L I C O N %20G R A P H I C S
H T T P :// E N . W I K I P E D I A . O R G / W I K I /A L E X A N D E R %20S T E P A N O V

Standard Template Library (STL)

Note:
In an interview Alexander Stepanov, stated that he originally, wanted all auxiliary functions in STL to be visible but it was not politically possible, especially
the heap functions. That Bjarne did reduce the number of components in STL
by a factor of two as to permit the adoption into the standard.
Compilers will already have one implementation included as part of the C++ Standard (i.e., MS Visual Studio uses the Dinkum STL). All implementations will have
to comply to the standards requirements regarding functionality and behavior, but
consistency of programs across all major hardware implementations, operating
systems, and compilers will also depends on the portability of the STL implementation. They may also offer extended features or be optimized to distinct setups.
List of STL implementations.

libstdc++ from gnu (was part of libg++)

SGI STL library (HTTP :// WWW. SGI . COM / TECH / STL /)19 free STL implementation.
Rogue Wave standard library (HP, SGI, SunSoft, Siemens-Nixdorf) / A PACHE
C++ S TANDARD L IBRARY (STDCXX)20
Dinkum STL library by P.J. Plauger (HTTP :// WWW. DINKUMWARE . COM /)21
commercial STL implementation widely used, since it was licensed in is comaintained by Microsoft and it is the STL implementation that ships with Visual
Studio.
There are many different implementations of the STL, all based on the language
standard but nevertheless differing from each other, making it transparent for the
programmer, enabling specialization and rapid evolution of the code base.
Open Source versions of the STL are available (can be useful to consult)

Apache C++ Standard Library (STDCXX) ( HTTP :// STDCXX . APACHE . ORG /22
).

19
20
21
22

H T T P :// W W W . S G I . C O M / T E C H / S T L /)
H T T P :// E N . W I K I P E D I A . O R G / W I K I /A P A C H E %20C%2B%2B%20S T A N D A R D %
20L I B R A R Y
H T T P :// W W W . D I N K U M W A R E . C O M /)
H T T P :// S T D C X X . A P A C H E . O R G /

501

Advanced Features
STLport STL library (HTTP :// WWW. STLPORT. COM /)23 free and highly crossplatform implementation based on the SGI implementation.
Note:
There are advantages on having compartmentalized functionalities, some developers actively avoid using some of the language features, for a multitude of
reasons. C++ permits the programmer to chose how to express himself, have
control over the development paradigms and not be constricted by an higher
level of abstraction.

5.2.2 Containers
The containers we will discuss in this section of the book are part of the standard
namespace (std::). They all originated in the original SGI implementation of the
STL.
Note:
When choosing a container, you should have in mind what makes them different, this will help you produce more efficient code. See also the O PTIMIZA TION S ECTION a of the book, about USING THE RIGHT DATA IN THE RIGHT
CONTAINER b .
a
b

Chapter 6.7.2 on page 628

Chapter 6.8.1 on page 630

Sequence Containers
Sequences - easier than arrays

Sequences are similar to C arrays, but they are easier to use. Vector is usually
the first sequence to be learned. Other sequences, list and double-ended queues,
are similar to vector but more efficient in some special cases. (Their behavior is
also different in important ways concerning validity of iterators when the container
is changed; iterator validity is an important, though somewhat advanced, concept
when using containers in C++.)

23

502

H T T P :// W W W . S T L P O R T . C O M /)

Standard Template Library (STL)

vector - "an easy-to-use array"
list - in effect, a doubly-linked list
deque - double-ended queue (properly pronounced "deck", often mispronounced
as "dee-queue")
vector
The vector is a template class in itself, it is a Sequence Container and allows you
to easily create a DYNAMIC ARRAY24 of elements (one type per instance) of almost
any data-type or object within a programs when using it. The vector class handles
most of the memory management for you.
Since a vector contain contiguous elements it is an ideal choice to replace the old
C style array, in a situation where you need to store data, and ideal in a situation
where you need to store dynamic data as an array that changes in size during the
programs execution (old C style arrays cant do it). However, vectors do incur a
very small overhead compared to static arrays (depending on the quality of your
compiler), and cannot be initialized through an initialization list.
Note:
Vector is known to be slow when using the MSVC compiler due to the
SECURE_SCL flag, that, by default, forces bounds checking even in optimized
builds.
Accessing members of a vector or appending elements takes a fixed amount of
time, no matter how large the vector is, whereas locating a specific value in a vector element or inserting elements into the vector takes an amount of time directly
proportional to its location in it (size dependent).

24

H T T P :// E N . W I K I P E D I A . O R G / W I K I / D Y N A M I C %20 A R R A Y

503

Advanced Features

Note:
If you create a vector you can access its data using consecutive pointers:
std::vector<type> myvector(8); type * ptr = myvector[0]; ptr[0],
ptr[7]; // access the first and last objects in myvector

this information is present in INCITS/ISO/IEC 14882-2003 but was not

properly documented in the 1998 version of the C++ standard.
Be aware that ptr[i] is faster than myvector.at(i) because no error checking is
performed. Watch out for how long that pointer is valid. The contiguous nature
of vectors is most often important when interfacing to C code.
You should also keep in mind that std::vector<T>::iterator may not be a pointer;
using an iterator is the safest mode to access a container but safety has always
a cost in performance.
Example

/*
David Cary 2009-03-04
quick demo for wikibooks
*/
#include <iostream>
#include <vector>
using namespace std;
vector<int> pick_vector_with_biggest_fifth_element(vector<int> left,vector<int>
right)
{
if(left[5] < right[5])
{
return( right );
}
// else
return left ;
}
int* pick_array_with_biggest_fifth_element(int * left,int * right)
{
if(left[5] < right[5])
{
return( right );
}
// else
return left ;
}

504

Standard Template Library (STL)

int vector_demo(void)
{
cout << "vector demo" << endl;
vector<int> left(7);
vector<int> right(7);
left[5] = 7;
right[5] = 8;
cout << left[5] << endl;
cout << right[5] << endl;
vector<int> biggest(pick_vector_with_biggest_fifth_element( left, right ) );
cout << biggest[5] << endl;
return 0;
}
int array_demo(void)
{
cout << "array demo" << endl;
int left[7];
int right[7];
left[5] = 7;
right[5] = 8;
cout << left[5] << endl;
cout << right[5] << endl;
int * biggest =
pick_array_with_biggest_fifth_element( left, right );
cout << biggest[5] << endl;
return 0;
}
int main(void)
{
vector_demo();
array_demo();
}

Member Functions

The vector class models the C ONTAINER25 CONCEPT26 , which means it has
begin(), end(), size(), max_size(), empty(), and swap() methods.

25
26

H T T P :// W W W . S G I . C O M / T E C H / S T L /C O N T A I N E R . H T M L
H T T P :// E N . W I K I P E D I A . O R G / W I K I / C O N C E P T %20%28 G E N E R I C %
20 P R O G R A M M I N G %29

505

Advanced Features

Note:
Since most vector (or deque) implementations typically reserves some extra
internal storage for future growth. Prefer the swap() method when altering
a standard vector size (or freeing the memory used) when memory resources
becomes a factor.
informative
vector::front - Returns reference to first element of vector.
vector::back - Returns reference to last element of vector.
vector::size - Returns number of elements in the vector.
vector::empty - Returns true if vector has no elements.
standard operations
vector::insert - Inserts elements into a vector (single & range), shifts later
elements up. Inefficient.
vector::push_back - Appends (inserts) an element to the end of a vector,
allocating memory for it if necessary. A MORTIZED27 O(1) time.
vector::erase - Deletes elements from a vector (single & range), shifts later
elements down. Inefficient.
vector::pop_back - Erases the last element of the vector, (possibly reducing
capacity - usually it isnt reduced, but this depends on particular STL implementation). A MORTIZED28 O(1) time.
vector::clear - Erases all of the elements. Note however that if the data
elements are pointers to memory that was created dynamically (e.g., the new
operator was used), the memory will not be freed.
allocation/size modification
vector::assign - Used to delete a origin vector and copies the specified
elements to an empty target vector.
vector::reserve - Changes capacity (allocates more memory) of vector, if
needed. In many STL implementations capacity can only grow, and is never
reduced.
vector::capacity - Returns current capacity (allocated memory) of vector.
vector::resize - Changes the vector size.
iteration
vector::begin - Returns an iterator to start traversal of the vector.
vector::end - Returns an iterator that points just beyond the end of the vector.
vector::at - Returns a reference to the data element at the specified location
in the vector, with bounds checking.
27
28

506

H T T P :// E N . W I K I P E D I A . O R G / W I K I /A M O R T I Z E D %20 A N A L Y S I S
H T T P :// E N . W I K I P E D I A . O R G / W I K I /A M O R T I Z E D %20 A N A L Y S I S

Standard Template Library (STL)

Note:
It is important to remember the distinctions of capacity(), size() and empty()
when dealing with containers.

vector<int> v;
for (vector<int>::iterator it = v.begin(); it!=v.end(); ++it/* increment operand
is used to move to next element*/) {
cout << *it << endl;
}

vector::Iterators
std::vector<T> provides Random Access Iterators; as with all containers, the
primary access to iterators is via begin() and end() member functions. These
are overloaded for const- and non-const containers, returning iterators of types
std::vector<T>::const_iterator and std::vector<T>::iterator respectively.
vector examples

/* Vector sort example */

#include <iostream>
#include <vector>
int main()
{
using namespace std;
cout << "Sorting STL vector, \"the easier array\"... " << endl;
cout << "Enter numbers, one per line. Press ctrl-D to quit." << endl;
vector<int> vec;
int tmp;
while (cin>>tmp) {
vec.push_back(tmp);
}
cout << "Sorted: " << endl;
sort(vec.begin(), vec.end());
int i = 0;
for (i=0; i<vec.size(); i++) {
cout << vec[i] << endl;;
}
return 0;
}

507

Advanced Features
The call to sort above actually calls an instantiation of the function template
std::sort, which will work on any half-open range specified by two random
access iterators.
If you like to make the code above more "STLish" you can write this program in
the following way:
#include
#include
#include
#include

<iostream>
<vector>
<algorithm>
<iterator>

int main()
{
using namespace std;
cout << "Sorting STL vector, \"the easier array\"... " << endl;
cout << "Enter numbers, one per line. Press ctrl-D to quit." << endl;
vector<int> vec(istream_iterator<int>(cin), istream_iterator<int>());
sort(vec.begin(), vec.end());
cout << "Sorted: " << endl;
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "\n"));
return 0;
}

Linked lists
The STL provides a class template called list (part of the standard namespace
(std::)) which implements a non-intrusive doubly-LINKED LIST29 . Linked lists can
insert or remove elements in the middle in constant time, but do not have random
access. One useful feature of std::list is that references, pointers and iterators to
items inserted into a list remain valid so long as that item remains in the list.
Note:
Consider using vector instead of list for better cache coherency and avoid
"death by swapping", see the O PTIMIZATION S ECTIONa , about using the
RIGHT DATA IN THE RIGHT CONTAINER b .
a
b

Chapter 6.7.2 on page 628

Chapter 6.8.1 on page 630

29

H T T P :// E N . W I K I P E D I A . O R G / W I K I / L I N K E D %20 L I S T

508

Standard Template Library (STL)

list examples

Associative Containers (key and value)

This type of container point to each element in the container with a key value, thus
simplifying searching containers for the programmer. Instead of iterating through
an array or vector element by element to find a specific one, you can simply ask
for people["tero"]. Just like vectors and other containers, associative containers
can expand to hold any number of elements.
Maps and Multimaps
map and multimap are associative containers that manage key/value pairs as elements as seen above. The elements of each container will sort automatically using
the actual key for sorting criterion. The difference between the two is that maps do
not allow duplicates, whereas, multimaps does.

map - unique keys

multimap - same key can be used many times
set - unique key is the value
multiset - key is the value, same key can be used many times
/* Map example - character distribution
#include <iostream>
#include <map>
#include <string>
#include <cctype>

*/

using namespace std;

int main()
{
/* Character counts are stored in a map, so that
* character is the key.
* Count of char a is chars[a]. */
map<char, long> chars;
cout << "chardist - Count character distributions" << endl;
cout << "Type some text. Press ctrl-D to quit." << endl;
char c;
while (cin.get(c)) {
// Upper A and lower a are considered the same
c=tolower(static_cast<unsigned char>(c));
chars[c]=chars[c]+1; // Could be written as ++chars[c];
}
cout << "Character distribution: " << endl;

509

Advanced Features

string alphabet("abcdefghijklmnopqrstuvwxyz");
for (string::iterator letter_index=alphabet.begin(); letter_index !=
alphabet.end(); letter_index++) {
if (chars[*letter_index] != 0) {
cout << char(toupper(*letter_index))
<< ":" << chars[*letter_index]
<< "\t" << endl;
}
}
return 0;
}

Container Adapters
stack - last in, first out (LIFO)
queue - first in, first out (FIFO)
priority queue

5.2.3 Iterators
C++s iterators are one of the foundation of the STL. Iterators exist in languages
other than C++, but C++ uses an unusual form of iterators, with pros and cons.
In C++, an iterator is a concept rather than a specific type, they are a generalization
of the pointers as an abstraction for the use of containers. Iterators are further
divided based on properties such as traversal properties.
The basic idea of an iterator is to provide a way to navigate over some collection
of objects concept.
Some (overlapping) categories of iterators are:

Singular iterators
Invalid iterators
Random access iterators
Bidirectional iterators
Forward iterators
Input iterators
Output iterators
Mutable iterators

510

Standard Template Library (STL)

A pair of iterators [begin, end) is used to define a HALF OPEN RANGE30 , which
includes the element identified from begin to end, except for the element identified
by end. As a special case, the half open range [x, x) is empty, for any valid iterator
x.
Note:
The range notation may vary, the meaning is to express the inclusion or exclusion of the range limits. An also common notation is [begin, end[ (meaning
begin is part of the range and end is not).
The most primitive examples of iterators in C++ (and likely the inspiration for their
syntax) are the built-in pointers, which are commonly used to iterate over elements
within arrays.
Iteration over a Container
Accessing (but not modifying) each element of a container group of type C<T>
using an iterator.
for (
typename C<T>::const_iterator iter = group.begin();
iter != group.end();
++iter
)
{
T const &element = *iter;
// access element here
}

Note the usage of typename. It informs the compiler that const_iterator is a type
as opposed to a static member variable. (It is only necessary inside templated code,
and indeed in C++98 is invalid in regular, non-template, code. This may change
in the next revision of the C++ standard so that the typename above is always
permitted.)
Modifying each element of a container group of type C<T> using an iterator.
for (
typename C<T>::iterator iter = group.begin();
iter != group.end();
++iter
)

30

H T T P :// E N . W I K I B O O K S . O R G / W I K I /A L G E B R A %2FI N T E R V A L %20N O T A T I O N

511

Advanced Features

{
T &element = *iter;
// modify element here
}

When modifying the container itself while iterating over it, some containers (such
as vector) require care that the iterator doesnt become invalidated, and end up
pointing to an invalid element. For example, instead of:
for (i = v.begin(); i != v.end(); ++i) {
...
if (erase_required) {
v.erase(i);
}
}

Do:
for (i = v.begin(); i != v.end(); ) {
...
if (erase_required) {
i = v.erase(i);
} else {
++i;
}
}

The erase() member function returns the next valid iterator, or end(), thus ending the loop. Note that ++i is not executed when erase() has been called on an
element.

5.2.4 Functors
A functor or function object, is an object that has an operator (). The importance of functors is that they can be used in many contexts in which C++ functions
can be used, whilst also having the ability to maintain state information. Next to
iterators, functors are one of the most fundamental ideas exploited by the STL.
The STL provides a number of pre-built functor classes; std::less, for example,
is often used to specify a default comparison function for algorithms that need to
determine which of two objects comes "before" the other.

#include <vector>
#include <algorithm>
#include <iostream>

512

Standard Template Library (STL)

// Define the Functor for AccumulateSquareValues

template<typename T>
struct AccumulateSquareValues
{
AccumulateSquareValues() : sumOfSquares()
{
}
void operator()(const T& value)
{
sumOfSquares += value*value;
}
T Result() const
{
return sumOfSquares;
}
T sumOfSquares;
};
std::vector<int> intVec;
intVec.reserve(10);
for( int idx = 0; idx < 10; ++idx )
{
intVec.push_back(idx);
}
AccumulateSquareValues<int> sumOfSquare = std::for_each(intVec.begin(),
intVec.end(),
AccumulateSquareValues<int>() );
std::cout << "The sum of squares for 1-10 is " << sumOfSquare.Result() <<
std::endl;
// note: this problem can be solved in another, more clear way:
// int sum_of_squares = std::inner_product(intVec.begin(), intVec.end(),
intVec.begin(), 0);

5.2.5 Algorithms
The STL also provides several useful algorithms, in the form of template functions,
that are provided to, with the help of the iterator concept, manipulate the STL
containers (or derivations).
The STL algorithms arent restricted to STL containers, for instance:
#include <algorithm>
int array[10] = { 2,3,4,5,6,7,1,9,8,0 }
int* begin = &array[0];
int* end = &array[0] + 10;
std::sort( begin, end);// the sort algorithm will work on a C style array

The _if suffix

513

Advanced Features

The _copy suffix

Non-modifying algorithms
Modifying algorithms
Removing algorithms
Mutating algorithms
Sorting algorithms
Sorted range algorithms
Numeric algorithms

Permutations
Sorting and related operations
sort

stable_sort

partial_sort

Minimum and maximum

The standard library provides function templates min and max, which return the
minimum and maximum of their two arguments respectively. Each has an overload
available that allows you to customize the way the values are compared.
template<class T>
const T& min(const T& a, const T& b);
template<class T, class Compare>
const T& min(const T& a, const T& b, Compare c);
template<class T>
const T& max(const T& a, const T& b);
template<class T, class Compare>
const T& max(const T& a, const T& b, Compare c);

514

Smart Pointers

5.2.6 Allocators
Allocators are used by the Standard C++ Library (and particularly by the STL) to
allow parameterization of memory allocation strategies.
The subject of allocators is somewhat obscure, and can safely be ignored by most
application software developers. All standard library constructs that allow for specification of an allocator have a default allocator which is used if none is given by
the user.
Custom allocators can be useful if the memory use of a piece of code is unusual in
a way that leads to performance problems if used with the general-purpose default
allocator. There are also other cases in which the default allocator is inappropriate,
such as when using standard containers within an implementation of replacements
for global operators new and delete.
31

5.3 Smart Pointers

Using raw pointers to store allocated data and then cleaning them up in the destructor can generally be considered a very bad idea since it is error-prone. Even
temporarily storing allocated data in a raw pointer and then deleting it when done
with it should be avoided for this reason. For example, if your code throws an
exception, it can be cumbersome to properly catch the exception and delete all
allocated objects.
Smart pointers can alleviate this headache by using the compiler and language
semantics to ensure the pointer content is automatically released when the pointer
itself goes out of scope.
#include <memory>
class A
{
public:
virtual ~A() {}
virtual char val() = 0;
};
class B : public A
{
public:

31

H T T P :// E N . W I K I B O O K S . O R G / W I K I /C A T E G O R Y %3AC%2B%2B%20P R O G R A M M I N G

515