STL Containers

Container basics

An STL container is a collection of objects of the same type (the elements).

Two basic types of containers:

Container concepts

There are three main container concepts:

container_concepts.png

Container concepts are not as important for generic programming as iterator concepts.

However, container concepts standardize basic features.

The Container concept

Properties shared by all STL containers.

In addition, a reversible container has the properties:

Sequences

Common properties of all sequence containers:

vector

vector should be used by default as the (sequence) container:

Properties of vector in addition to sequences:

Memory management

  • The elements are stored into a contiguous memory area on the heap.

    • capacity() is the number of elements that fit into the area.
    • size() is the actual number of elements. The remainder of the area is unused (raw memory).
    • reserve(n) increases the capacity to n without changing the size.
    • The capacity is increased automatically if needed due to insertions.

  • Capacity increase may cause copying of all elements.

    • A larger memory area is obtained and elements are copied there.
    • Capacity increase by an insertion doubles the capacity to achieve amortized constant time.

  • Capacity never decreases.

    • Memory is not released.
    • But the following gets rid of all extra capacity/memory:
    vector<int> v;
...
vector<int>(v).swap(v);  // copy and swap

  • Use &v[0] to obtain a pointer to the memory area.

    • May be needed as an argument to non-STL functions.
    vector<char> v(12);
strcpy(&v[0], "hello world");

Limitations of vector

  • Insertions and deletions in the beginning or in the middle are slow.

    • Requires moving other elements.
    • Prefer push_back() and pop_back().
    • Insert or erase many elements at a time by using the range forms of insert and erase.

  • Insertions and deletions invalidate all iterators, and pointers and references to the elements.

    vector<int> v;
...
vector<int> b = v.begin();
v. push_back(x);
find(b, v.end());  // error: b is invalid

deque

deque stands for double-ended queue. It is much like vector.

Memory management

deque stores the elements something like this:

deque.png
  • Element access and iterators are more complicated.
  • Fast insertions and deletions to the beginning.
  • Handles size changes gracefully: - Capacity increases or decreases one block at a time.
  • Memory area is not contiguous.

list

The third standard sequence container is list. The underlying data structure is a doubly-linked list:

Member functions in addition to sequence:

list<int> c;
c.push_back(10);
c.push_back(20);
c.push_back(30);
list<int>::iterator i = c.begin();
assert(*i==10); // i points to the first element: 10
c.reverse();
assert(*i==10); // i continues to point to 10
                // which is now to the last element
reverse(c.begin(), c.end());
assert(*i==30); // i still points to the last element
                // which now contains 30

string

string class was designed before STL, but STL container properties were added to it later. It is similar to vectors; the differences include:

vector<bool>

vector<bool> has some special properties.

Associative containers

The STL standard associative containers (set, multiset, map, multimap) allow access to elements using a key:

The underlying data structure is a balanced search tree:

The order comparison

  • operator< by default but can be changed
struct my_less {
  bool operator() (int a, int b) { return a < b; }
}

// all three sets have the same ordering:
set<int> s1;  // default: operator< as key order
set<int, std::less<int> > s2;
set<int, my_less> s3;

  • Two keys are equivalent if neither is smaller than the other.

    • operator== is not used for comparing keys.
    • Ensures consistency of order and equivalence.

  • must be strict weak ordering:

    1. irreflexivity: x<x is always false.

    2. transitivity: (x<y) && (y<z) implies x<z.

    3. transitivity of equivalence: if x equals y and y equals z, then x equals z.

      // NOT strict weak ordering:
// 1 equals 2 and 2 equals 3 but 1 does not equal 3
struct clearly_less {
  bool operator() (int a, int b) { return a < b-1; }
}
    • asymmetry: x<y implies !(y<x).
      • Often mentioned as a requirement, but it is implied by 1. and 2.
      • Often called antisymmetry in STL literature, but asymmetry is the correct mathematical term.

Common properties

In addition to properties of the Container concept, all associative containers have:

  • member types
    • key_type
    • key_compare
  • comparison operators
    • key_comp() returns the key comparison operator
    • value_comp() returns a comparison operator comparing elements not keys.
  • constructors
    • Range constructor Container(i,j) fills container with the contents of the range [i,j).
    • (All constructors accept a comparison object as an extra optional argument.)
  • insert
    • insert(x)
    • insert(i, x). Iterator i is a hint pointing to where the search for insertion position should start.
      • Allows insert_iterator to operate on associative containers.
    • range insert insert(i, j)
    • For set and map insertions are not done if the key is already there.
  • erase
    • erase(k) erases all elements with key k
    • erase(i) erase element pointed to by i
    • range erase erase(i,j)
  • searching
    • find(k) returns iterator to the element with key k or end() if no such element
    • count(k)
    • lower_bound(k) find first element with key not less than k
    • upper_bound(k) find first element with key greater than k
    • equal_range(k) returns pair<iterator,iterator> representing the range of element with key k

set and multiset

// count distinct words
set<string> words;
string s;
while (cin >> s) words.insert(s);
cout << words.size() << " distinct words\n";

There are no member operations for set intersection, union, etc. However, the following generic algorithms work on any sorted range, including [s.begin(),s.end()) for a set or multiset s:

string str1("abcabcbac");
string str2("abcdabcd");

multiset<char> mset1(str1.begin(), str1.end());
multiset<char> mset2(str2.begin(), str2.end());

multiset<char> result;
set_intersection (mset1.begin(), mset1.end(),
                  mset2.begin(), mset2.end(),
                  inserter(result, result.begin()) );

copy(result.begin(), result.end(), ostream_iterator<char>(cout));
// outputs: "aabbcc"

map and multimap

Container adaptors

The container adaptors stack, queue, priority_queue are containers implemented on top of another container.

They provide a limited set of container operations:

Stack

stack can be implemented on top of vector, deque or list.

  • The default is deque.
// these are equivalent
stack<int> st1;
stack<int, deque<int> > st2;

Additional operations:

  • constructor stack(const container&)
  • push(val)
  • top()
  • pop()

Queue

queue can be implemented on top of deque or list.

  • The default is deque.

Additional operations:

  • front()
  • back()
  • push(val)
  • pop()

Priority queue

priority_queue can be implemented on top of deque or vector.

  • The default is vector.

Uses order comparison operators of elements similar to the associative containers.

// these are equivalent
priority_queue<int> pq1;
priority_queue<int, vector<int> > pq2;
priority_queue<int, vector<int>, less<int> > pq3;

Additional operations:

  • range constructor
  • comparison object as an extra optional argument of constructors
  • push(val)
  • top() returns the largest element
  • pop() removes the largest element

There is no method for changing the priority of an element or removing an element that is not the largest.

  • Sufficient for some applications like event simulation.
  • Not sufficient for others like Dijkstra's algorithm.

Hash tables

The standard has no containers using hashing, but they are a common extension. They are also included in the Technical Report on C++ Standard Library Extensions, commonly known as TR1, an extension of the standard library likely to be included in the next C++ standard:

More details can be found in the proposal.

Container elements

The type of container elements should always be a model of the Assignable concept:

Some member functions have additional requirements:

Pointers in containers

Pointers as container elements require special care. There two kinds of pointers:

  • Pointers that do not own the object they point to.

    • Example: the same element in multiple containers.
      • for example, different iteration orders
      • One container stores the elements, others store pointers to the elements.
    • Prefer iterators to pointers.
      • They enable container manipulation.
    • Be careful about validity
      • With deque use pointers instead of iterators if there are insertions or deletions at the beginning or the end.
      • With vector use index if there are insertions or deletions at the end.

  • Pointers that own the element they point to.

    • Example: polymorphic container:
    struct animal {
  virtual ~animal() {};
  virtual void eat() =0;
  // ...
}

struct baboon : animal {
  // ...
}

struct lion : animal {
  // ...
}

// ...

vector<animal*> zoo;
zoo.push_back(new baboon);
zoo.push_back(new lion);
zoo[1]->eat();

    • Such pointers are problematic elements.

      • Containers take care that the destructor of an element is called, when the element is erased (or the container is destroyed).
      • But an owning pointer's destructor does not do what it should: destroy the pointed to object and release the memory.
      • The user of the container must ensure that the pointed to objects are properly destroyed and freed. This is inconvenient and error-prone.
      • Achieving exception safety is difficult.

    • Better to use a smart pointer, whose destructor does the right thing.

      • auto_ptr has the right kind of destructor, but unfortunately the wrong kind of copy constructor and assignment.
      • Use boost::shared_ptr if possible.
      typedef boost::shared_ptr<animal> animal_ptr;
vector<animal_ptr> zoo;

animal_ptr p(new baboon);
zoo.push_back(p);
p.reset(new lion);
zoo.push_back(p);
zoo[1]->eat();

Exception safety

Exceptions are a common error reporting mechanism in C++. The elements of STL containers are allowed to throw exceptions (except in destructors). In particular, if a copy of an element fails and throws an exception during a container operation, one of the following guarantees are provided:

  • Strong guarantee: The container operation is cancelled, and the container's state is as if the operation was never called.
    • Most list operations.
    • All single element operations on lists and associative containers.
    • push and pop operations on vector and deque.
  • Basic guarantee: There are no memory leaks, and the container is in a consistent state. In particular, the container can be destroyed safely.

These guarantees make it possible to recover from an exception without memory leaks.