STL Guide - A Tutorial and Reference

Introduction
This section will provide basic coverage of the STL and discuss some of the most common usage and functions found in your typical production C++ source code. STL is a collection of containers (data structures) and algorithms that can be applied to the containers or contained objects. If you've studied computer science then you will be familiar with (some) of the common data structures and algorithms that STL provides.

Containers are structures that are used to hold other objects which may also be other containers. The types of containers provided by STL are listed in the containers section. Containers come in two forms:

C++ usually defines the default ctor and dtor, and default copy ctor; in order to make your objects storable in a STL container, you have to make sure they are declared in the public scope. If you don't, your code will not compile.

When STL stores an object into a container, it makes a copy of the object and stores the copied object. Sometimes you don't want this (a copy) to occur, specially for complex objects that would require a deep copy ctor to be implemented or resource allocations to take place. Most developers get around the need to declare the default ctor and copy ctor by creating an object on the heap and storing a pointer to the object in the container. It's still the developer's responsibility to free these objects not the containers.

class Person
{
   int m_age;
   Person() {
   }

public:
   Person( int age ) : m_age(age) {
   }
};

int _tmain(int argc, _TCHAR* argv[])
{
   std::vector<Person> pList;
   Person a(12);
   pList.push_back( a ); // save copy of object a!!!
   return 0;
}

There are times when we create objects that we don't want to be able to make copies. If we change the definition of class Person to prevent copying, our STL code will no longer compile.

// will cause a compile error with the STL container
class Person
{
   int m_age;
   Person()
   }

   // private copy ctor
   Person( Person& obj ) {
   }
public:
   Person( int age ) : m_age(age) {
   }
};

Namespace
The STL library is contained in the C++ standard namespace called "std". You can either use the "using" directive or the "std::" scope operator to access STL members.

Iterators
In order to be able to access objects inside the containers, you will need to learn how to use iterators. Iterators work like pointers in C/C++, they can be incremented, decremented and dereferenced. There are 5 types of iterators:

Note: STL has reverse bidirectional iterators that move in the opposite direction of the normal iterator.

You should not hold or store iterators and be very careful when passing iterators around. Should an element be added or removed from the container, all iterators to that container should be considered invalid.

STL End Node
In a container the last node end( ) is the node following the last valid object, and it designates when to stop iterating in the sequence. You must be aware not to dereference the end( ) container node. Following is a diagram of a STL list containing 4 objects, also note how begin( ) always points to the first node.

Understanding Container Size and Capacity
A container size is alway the count of the number of elements it hold. The capacity of a container is the maximum allocated space it has before the container is required to allocate more space. The size of a container is always equal to or less than it's capacity. When a container is declared, the initial capacity can be defined to save time when a container needs to be expanded once the the capacity limit is exceeded. The following code sample show the difference.

#include <vector>
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
   std::vector<int> v1;
   std::vector<int> v2;

   v2.reserve(50); // set initial capacity of vector

   cout << "Before Insert" << endl;
   cout << "-------------" << endl;
   cout << "capacity of v1 " << v1.capacity() << endl;
   cout << "capacity of v2 " << v2.capacity() << endl << endl;

   cout << "size of v1 " << v1.size() << endl;
   cout << "size of v2 " << v2.size() << endl << endl;

   for( int i=0; i<10; ++i ) { // insert 10 integers into vector v1
      v1.push_back( i );
   }

   for( int i=0; i<500; ++i ) { // insert 500 integers into vector v1
      v2.push_back( i );
   }

   cout << "After Insert" << endl;
   cout << "------------" << endl;
   cout << "capacity of v1 " << v1.capacity() << endl;
   cout << "capacity of v2 " << v2.capacity() << endl << endl;

   cout << "size of v1 " << v1.size() << endl;
   cout << "size of v2 " << v2.size() << endl;

    return 0;
}

OUTPUT
Before Insert
-------------
capacity of v1 0
capacity of v2 0

size of v1 0
size of v2 0

Before Insert
-------------
capacity of v1 13
capacity of v2 567

size of v1 10
size of v2 500

Notice capacity of vector v1 has increased to 13 after inserting 10 integers, while v2 has is capacity increased to 567 after 500 integers have been inserted.

Performance
The three main types of performance cost associated with container access and algorithms is measured as: constant, linear and logarithmic time.

Note: In the matrix provided, insert and remove shown in bold are operations performed with the iterator. For the vector, there is a push_back( ) operation but no push_front( ), that is why "Insert Tail" shows O(1) while "Insert Head" shows "n/a". Mind you insert can be done at the front with the use of an iterator, but to keep the table "method specific" the information is presented this way. For the stack container, "Head" should be taken to mean top.

(*) Index referencing for map, multimap, set, multiset are done with the key value. For multimap and multiset indexed referencing takes place in amortized constant time.

Adaptors
The container adaptor alters how the underlying container behaves. The stack is a container adaptor, by default it uses the list container to provide the functionality. One thing to note about container adaptors is that they do not support iterators, therefore they cannot be used with STL algorithms.

Algorithms
Algorithms work on containers, they provide ways to manipulate the content such as sorting, or applying transformation operation such as performing some operation on a range of elements. Algorithm classes are designed to be generic because they need to be able to work on various containers as well as data structures and arrays that satisfy the requirements of a given algorithm. Algorithms can maintain their generality because they operate on a container using iterators that allow them to work on a range of elements.

Functors
There are many function objects that provide operator functionality. Functor can be unary such as negate( ), or binary comparison operators such as less( ), or binary arithmetic operators such as minus( ). Unary functors take one argument and binary functors take two arguments.

Functors are used with algorithms and passed as predicates, they can also be passed to some containers to specify how elements are ordered. The set is one such container that has a default unary predicate of less( ). The C++ standard requires that functors object classes inherit from the unary_function and binary_function base classes.

vector
Elements are arranged in a linear structure much like an array and thus allows fast random(indexed) access to the elements. Random access happens in constant time, Big-O(1), and linear time Big-O(n) using an iterator. Elements are inserted at the tail of the vector and take place in Big-O(1).

list
Elements are arranged in a linear structure much like a linked-list with bidirectional navigation. It allows element to be inserted/removed at any location in constant time Big-O(1). Lists can also be split or merged in constant time Big-O(1), and one would choose a list when these type or operations are required. Lookup takes linear time, Big-O(n) because each element needs to be iterated over.

deque
Elements can be added and removed from the head and tail of the queue in constant time Big-O(1). Like vectors, queues also allow efficient random (indexed) access to stored elements.

map
Elements are stored as (key,value) pairs in the container, insert/remove operations take logarithmic time Big-O(log n), lookup take constant time Big-O(1). Each element is accessed using a unique key value, associated values on the other hand do not need to be unique. The map orders the elements by their keys using a stored function key_compare, which simply does a less-than comparison.

set
Elements contained in a set must be unique, insert/remove operations take logarithmic time Big-O(log n), lookup take constant time Big-O(1). A values in a set cannot be modified, it must be removed and a new value needs to be inserted. The set orders the elements by their keys using a stored function key_compare, which simply does a less-than comparison.

multimap
Elements are stored as (key,value) pairs in the container, insert/remove operations take logarithmic time Big-O(log n), lookup take constant time Big-O(1). Each element is accessed using a key value, unlike the map, a multimap key value needs not be unique, associated values do not need to be unique. The map orders the elements by their keys using a stored function key_compare, which simply does a less-than comparison.

multiset
Elements contained in a multiset no not need to be unique as in the set container. Insert/remove operations take logarithmic time Big-O(log n), lookup take constant time Big-O(1). A values in a multiset cannot be modified, it must be removed and a new value needs to be inserted. The multiset orders the elements by their keys using a stored function key_compare, which simply does a less-than comparison.

queue
Elements can only be pushed at the tail and popped from the head, operation take place in const time Big-O(1). the queue is ideal for accessing elements in a first in first out order. The queue is an adaptor container and uses the deque as the base container.

stack
Elements are pushed and popped from the top(head) of the container in constant time Big-O(1). The stack is an adaptor container that uses the queue as the based container. The stack is ideal for accessing elements in a first in last out order.

STL - Standard Template Library