The C++ Standard Template Library1

The C++ Standard Template Library (STL) is a collection of templates for several containers (vector, pair, stack, queue, set, etc) that there is no need to re-implement. In this page we will give a short description of some of the templates and methods. For more information see cppreference.com.

To use the STL containers and methods when compiling with `g++ it is necessary to use the flag -std=c++11.

The rationale behind the STL is to have an interface as uniform as possible. For instance, it is possible to give initialization lists to STL containers.

Example 
  vector<int>   v = {0, 1, 2};
  pair<double,char> p = {2.5, 'a'};
  set<set<int>> s = { {2,3}, {5,1,5}, {}, {3} };

In the same spirit of uniformity, there are several common methods. For instance the followings.

Some common methods
Method Cost
bool empty() const says whether the container is empty \Theta(1)
unsigned int size() const returns the size of the container \Theta(1)

Costs are always intended to be worst case (unless stated otherwise).

Moreover, since the C++11 standard, if the compiler can infer the type of a variable, instead of writing explicitly its type, it is possible to use auto.

Example of usage of auto 
  map<string, int> m;
  auto it = m.find("hello");

Also for loops got an alternative (less error prone) syntax when used in collections such as set<T>.

Example of for loop over a set<T>

The following code outputs the elements of the set s one by one (in the order they are stored in s).

  set<int> s;
  for(int x : s) cout << x << endl;

pair<T1,T2>

pair<T1,T2> is equivalent to

struct pair {
  T1 first;
  T2 second;
};

A pair allows to form a pair with the first value of type T1 and the second value of type T2. It is possible to access the values with first and second.

The pairs are useful since some functions of the STL need to return 2 values. Moreover they have automatically defined some operators, for instance:

  • equality == (component-wise)
  • comparison < (lexicographically)2
Example of usage 
#include<iostream>

using namespace std;

int main(){
  pair<double, char> a(2.5, 'A');
  pair<double, char> b;
  b.first = 3.5;
  b.second = 'B';
  cout << (a == make_pair(2.5, 'A')) << endl;  // --> 1
  cout << (a < b) << endl;                     // --> 1
}

priority_queue<T>

A priority_queue<T> is a priority queue of elements of T. By default, the largest element is the one on top, i.e. the first to come out.

Some methods for priority_queue<T>. For the full list see cppreference.com.
Method Cost
void push(const T& x) adds x to the queue \Theta(\log n)
void pop() removes the largest element \Theta(\log n)
const T& top() const returns the top of the queue \Theta(1)

To use priority_queue<T> it is necessary #include <queue>.

Example (Heapsort)

Read a sequence of integers and write it in decreasing order.

#include <queue>
#include<iostream>

using namespace std;

int main() {
  priority_queue<int> pq;
  int x;
  while (cin >> x) pq.push(x);
  while (not pq.empty()) {
    cout << pq.top() << endl;
    pq.pop();
  }
}

set<T>

A set<T> is a ordered set of elements of type T. By default, the elements are ordered increasingly.3

To use set<T> it is necessary #include <set>.

An interator set<T>::iterator it is moved forward with ++it and backward --it. To access the element pointed by an iterator it we use *it.

Some methods for set<T>. For the full list see cppreference.com.
Method Cost
pair<set<T>::iterator,bool> insert (const T& x); adds x to the set.
If x was not in the set it returns an iterator to the place of x and true. Otherwise, an iterator to x in the set and false		 \Theta(\log n)
set<T>::iterator begin() returns an iterator to the first element of the set \Theta(1)
set<T>::iterator end() returns an iterator after the last element of the set \Theta(1)
set<T>::iterator find(const T& x) const looks for x in the set.
If x was in the set it returns an iterator pointing to it. Otherwise it returns end()		 \Theta(\log n)
void erase(iterator it) deletes the element pointed by it \Theta(1) (amortized)
int erase(const T& x) if x is in the set, deletes it and returns 1. Otherwise, returns 0 \Theta(\log n)
Example

Read two sequences of integers (ending wth 0) and write their intersection.

#include <set>

int main() {
  set<int> s1, s2;
  int x;
  while (cin >> x and x != 0) s1.insert(x);
  while (cin >> x and x != 0) s2.insert(x);

  for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it)
    if (s2.find(*it) != s2.end())
      cout << *it << endl;
}

map<K,V>

A map<K,V> is a dictionary with keys K and values V. It behaves similarly yo a set of pairs (key,value), that is keys are never repeated. By default, the keys are ordered increasingly.4

To use map<K,V> it is necessary #include <map>.

An iterator map<K,V>::iterator it is moved forward using ++it and backward --it. To access the pair pointed by it we use *it. To access the key pointed by it we can use (*it).first or it->first. To access the value pointd by it we can use (*it).second or it->second.

Some methods for map<K,V>. For the full list see cppreference.com.
Method Cost
pair<map<K,V>::iterator,bool> insert (const pair<K,V>& p) add the pair p. If there was a pair with that key, it returns an iterator to the exsiting pair and false. Otherwise, adds the pair p to the map and returns an iterator to it and true \Theta(\log n)
map<K,V>::iterator begin() returns an iterator to the pair with the first key in the ordering (by default the smallest key) \Theta(1)
map<K,V>::iterator end() returns an interator after the pair with the last key in the ordering (by default the largest key) \Theta(1)
map<K,V>::iterator find(const K& k) const looks for the pair with key k in the map. If it finds it, returns an iterator pointing to it. Otherwise returns end() \Theta(\log n)
void erase(map<K,V>::iterator it) deletes the pair pointed by it \Theta(1) (amortized)
int erase (const K& k) if there is an element with key k, deletes it and returns 1. Otherwise, returns 0 \Theta(\log n)
Example

The following code

#include <map>

using namespace std;

using P = pair<char,int>;
using M = map<char,int>;

int main(){

  M m;

  m.insert( P('a', 10) );
  m.insert( make_pair('c', 30) );
  m['d'] = 40;
  /* 
  The operator [] admits a key k as an argument.
  If there is a pair with the key k, it returns a reference to the value of the pair (k,value) in the map.
  Otherwise, it inserts a pair (k,value) and uses the constructor by default of the associated type (e.g. for the type int assigns 0). Then, it returns a reference to the second element of the pair (the value).
  */

  m.erase('c');

  for (M::iterator it = m.begin(); it != m.end(); ++it) 
    cout << it->first << " " << it->second << endl;
}

has output

a 10
d 40

unordered_set<T>

An unordered_set<T> is like a set but it does not guarantees an order on the elements.

insert, find, erase work in time \Theta(n) (worst case), but in time \Theta(1) on average.5

Example 
#include <iostream>
#include <unordered_set>

using namespace std;

int main() {

  unordered_set<int> s1, s2;
  int x;

  while (cin >> x and x != 0)
    s1.insert(x);
  
  while (cin >> x and x != 0)
    s2.insert(x);

  for (auto y : s1) 
    if (s2.find(y) != s2.end()) 
      cout << y << endl;
}

unordered_map<K,V>

An unordered_map<K,V> is like a map but it does not guarantee an order on the pairs.

insert, find, erase work in time \Theta(n) (worst case), but in time \Theta(1) on average.6

Example 
#include <unordered_map>
#include <iostream>

using namespace std;

int main() {
  unordered_map<string, int> m;
  string x;
  while (cin >> x) ++m[x];
  for(auto p : m)
    cout << p.first << " " << p.second << endl;
}

Footnotes

  1. The content of this page is mostly based on STL and Algorithms in C++.↩︎

  2. That is a<b is true when either a.first < b.first or when a.first == b.first and a.second < b.second.↩︎

  3. Internally, set<T> is implemented with a balanced binary search tree.↩︎

  4. Internally, map<K,V> is implemented with balanced binary search trees.↩︎

  5. Internally, unordered_set<T> is implemented with a Hash table.↩︎

  6. Internally, unordered_map<K,V> is implemented with a Hash table.↩︎