Chapter 16. The STL

Once C++ had a good template mechanism, people started implementing data structures using these templates. The most widespread collection of templates came from SGI and HP and was called the STL.

Standard Template Library (STL)

A set of data structures and algorithms using templates. Now part of the C++ standard.

For a complete reference to the STL:


A Container is an object that stores other objects (its elements), and that has methods for accessing its elements.

All Containers provide methods to create iterators (see iterators below).

All containers provide the following methods:

unsigned int size()

returns the current size of the container

bool empty()

returns true if the container is empty


In most containers that we have seen so far, the order of elements is important. The STL provides several sequence containers.

Most of these containers support the same operations. Then why bother having two implementations for it? Because every container performs differently on different operations!


We'll talk about the two template types "vector" and "list" (in the <vector> and <list> includes)

A vector is based on an array.

  • Getting the nth element of an array is fast -> getting the nth element of a vector is fast

  • Adding an element to the end of the list is fast

  • Adding an element in the middle requires moving all elements past this one back -> slow

  • Adding an element to the beginning requires moving all elements back -> very slow

list is based on a liked list

  • Getting the nth element of a linked list requires traversing all elements to that point -> slow

  • Adding an element anywhere in the list does not require any movement -> fast (once the element is found)

You will learn more about the implementation issues in the data structures class.

Both vector and list support:

push_back(T x)

add an element to the end of the list


removes the last element

T back()

returns the last element

T front()

returns the first element

Only list supports:

push_front(T x)

add an element to the beginning of the list


removes the first element

Only vector supports:

[] or at()

access element at the given index.

Here are some examples:

#include <iostream>
#include <list>   // For list
#include <vector> // For vector

using namespace std; // All STL containers are 
                     // in the std namespace.

int main()
  vector<int> a;  // Declare a vector that takes int
  a.push_back(3); // add to end of vector
  // as long as we still have elements
  while (!a.empty()) { 
    // print the last element
    cout << a.back() << " ";
    // and remove it!
  cout << endl;
  // this (above) printed 42 24 3
  list<int> b; // declares a linked list that takes int
  // adds some elements to the end
  // as long as there are elements left
  while (!b.empty()) {
    // print the last element
    cout << b.back() << " ";
    // and remove it
  cout << endl;
  // this (above) printed 42 24 3
  list<int> c; // declares a linked list that takes int
  // adds some elements to the end
  // as long as there are elements left
  while (!c.empty()) {
    // print the first element
    cout << c.front() << " ";
    // and remove it
  cout << endl;
  // this (above) printed 3 24 42
  return 0;

So now that we see the use of different containers, lets see what we have available:


A deque (double-ended queue) is a sequence container that supports fast insertions and deletions at the beginning and end of the container. Inserting or deleting at any other position is slow, but indexing to any item is fast. The header is <deque>. Pg 470

deque supports: [], at(), front(), back(), push_front(), push_back(), pop_front(), pop_back(), empty(), size(), ...


A list is a seuqence container that supports rapid insertion or deletion at any position, but does not support random access. The header is <list>. Pg 559


A vector is a sequence container that is like an arrays, except that it can grow in size as needed. Items can be rapidly added or removed only at the end. At other positions, inserting and deleting items is slower. The header is <vector>. Pg 722

Practice: Implement a short program (the whole program) that

  • declares a deque of type float

  • add the elements 1.234, 12.34, and 123.4

  • prints the first element

  • removes the first element

  • prints how many elements are in the deque

#include <iostream>
#include <deque>
using namespace std;
int main()
  deque<float> f;
  cout << f.front() << " ";
  cout << << " ";
  cout << f[0] << endl;
  cout << "There are " << f.size() << " elements left!";
  cout << endl;
  return 0;


Since all the containers have a different implementation, we need a standard way of going through all the items.

These things are called "iterators".

We are already used to iterators, we just didn't know it: For vector and arrays we used integers. We ran theses from 0 to size()-1. Therefore this "int" was an iterator.

Iterators use a lot of operator overloading to behave similar to pointers.

Declaring: To declare an iterator use the subclass "iterator" for your specific data type. Example:

vector<int> a; // Your vector a
// ... a lot of a.push_back()

// The actual declaration:
vector<int>::iterator it;

There are two standard functions for iterators:


returns an iterator pointing to the first element


returns an iterator pointing after the last element

Iterators can be advanced with the ++ operator (some can go backwards with --) and compared with the == or != operator. To run over all element, you can therefore use:

it = a.begin();
while (it!=a.end()) {
  // ...

Or quicker:

for (it = a.begin();it!=a.end();it++) { ... }

To get the element an iterator points to, you act as if iterator would be a pointer and use the dereference operator *. Example:

cout << *it;


Assume you have given the following declaration:

list<char> l;

Write a for loop that uses an iterator to iterate over l and print all the contents of the list.

list<char>::iterator li;
for (li=l.begin();li!=l.end();li++) 
  cout << *li;

Print just the second element (emulate at(1) )

list<char>::iterator li;
li = l.begin();
li++;  // can not use li = li+1 in this case
cout << *li;

All of these containers support insert() and erase(), but we had to introduce iterators first.

iterator erase(iterator p)

erases the item that p points to. erase returns an iterator that points to the item that comes immediately after the deleted item or end().

iterator insert(iterator p, T x)

inserts x immediately before p and returns an iterator that points to the newly inserted element x.

Warning: Iterators may become "invalid" after an insert or a delete operation! You should therefore use the return value if possible!


vector<int> v;
// ...
// same as p.pop_front(), would it exist.

A more complex example: Delete all occurences of "42" in a list:

list<int> l;
// ...
list<int>::iterator i = l.begin();
while (i!=l.end()) {
  if ((*i) == 42) 
    i = l.erase(i);

Another example:

list<int>::iterator i = l.begin();
// insert the number 0 at the beginning
i = l.insert(i,0);
// make sure i points after the first element


Assume this given deque:

deque<int> d;
// d gets filles with some values

Write a loop that inserts a 42 before every occurence of 0 in d. Two hints:

  • iterators to a deque become invalid after insertion. Make sure you use the return value!

  • don't write an infinite loop!

deque<int>::iterator i = d.begin();
while (i!=d.end()) {
  if (*i == 0) {
     i = d.insert(i,42);

Possible test question:

For a server application you need to write a FIFO (first in, first out) queue, so that all incoming jobs are processed in the order they arrive. Which STL container would you use for such a queue and why (1-2 sentences)?

Associative Containers

An associative container contains keys that can be quickly associated with values. There is:


Stores a pair of keys and associated values. The keys determine the order of the elements in the map. map requires unique keys. Header: <map>. Pg 202


same as map, but allows duplicate keys. Header: <map>. Pg 608


Stores just keys in ascending order. Set requires unique keys. Header: <set>


same as set, but allows duplicate keys. Header: <set>

To declare a map we need two datatypes, the key and the value datatype:

map<string,int> m;

We can then use keys of the given type as index to store and retrieve contents:

m["Jan"] = 1;
m["Feb"] = 2;
cout << m["Jan"] << endl;

Most operations on map can take a key as parameter where we usually have to use iterators, e.g. erase:


Trying to use an element that was not set works fine. If the valuetype is a class, then it will even create a new object for you (calls the default constructor).

cout << m["Mar"] << endl;


To map from student id's to name it is usually wise to use a map, since we do not want to create an array with 10000000000 elments.

  • Define a variable of a map type with "long" as keytype and "string" as valuetype

  • Fill in two random students of your discretion (do NOT use your real SSN!!!)

map<long,string> students;
students[123456789] = "Some";
students[987654321] = "One";
students[987654321] = "Else";

An iterator over a map<K,V> will give you a pair<K,V> for every element you access (this is the real pair which is differnt from the one we used in lab).

You can access the key in the member variable first, and the value in the member variable second. Thanks to operator overloading you may either use the dereference (*) or the dereference and access member (->) operator (or both, as you wish). Example:

for (map<string,int>::iterator i=m.begin();i!=m.end();i++) {
  cout << (*i).first << " " << i->second;


Using an iterator, iterate over your students map defined earlier. For every student print something like this on the screen (remember: first is the key, second is the value):

Student: Max Berger
Student ID: 123456789
map<long,string>::iterator si;
for (si=students.begin();si!=students.end();si++) {
  cout << "Student: " << si->second << endl;
  cout << "ID: " << si->first << endl;

Iterator categories

There are five categories of iterators:


Permits you to read a sequence in one pass. The increment operator (++) advances to the next element, but there is no decrement operator. The dereference operator returns an rvalue, not an lvalue, so you can read elements but not modify them.


Permits you to write a sequence in one pass. The increment operator (++) advances to the next element, but there is no decrement operator. You can dereference an element only to assign a value to it. You cannot compare output iterators.


Permits unidirectional access to a sequence. You can refer to and assign to an item as many times as you want. You can use a forward iterator whenever an input or an output iterator is required.


Similar to a forward iterator but also supports the decrement (--) operator to move the iterator back one position. Example: list<>::iterator.

Random access

Similar to bidirectional iterator but also supports the subscript [] operator to access any index in the sequence. Also, you can add or subtract an integer to move a random access iterator by more than one position at a time. Subtracting two random access iterators yields the distance between them. You can compare two random iterators with < or >.Thus, a random access iterator is most like a conventional pointer, and a pointer can be used as a random access iterator. Examples: deque<>::iterator, vector<>::iterator.

We will hardly every see anything but bidirectional and random access iterators. But it is important to know the other types exist.

With the exception of output each of these iterators includes all of the above. (a bidi is also forward and input, etc.).

In this example we use the fact that we can do math with iterators to find the index of elements that match a certain value.

vector<int> v;

for (vector<int>::iterator i=v.begin();i!=v.end();i++) {
  if ((*i) == 2) {
    cout << "I found the number 2 at index " << i - v.begin() << endl;


Assume the vector definition from above. Write a for loop that uses an iterator to output every other element. Actually advance the iterator by 2. Here you'll have to use the < operator instead of !=.

for (vector<int>::iterator i=v.begin();i<v.end();i+=2) {
  cout << *i << endl;