C++ Standard Template Library (STL)

Published by Gabriela Rata on October 14, 2011

The C++ Standard Template Library provides a set of common classes and interfaces that greatly extend the core C++ language. It provides a set of classes such as containers, associative arrays, iterators, functions objects, and strings. It also provides algorithms for counting, sorting,  finding, coping, and replacing elements in a container.

STL is almost entirely written in the form of C++ template classes that provide common programming data structures and functions. These template classes are all members of the std namespace.

 

STL code examples

We provide detailed code examples in the use of STL with MoSync, HelloSTL , that you can download from our GitHub repository. It provides many examples of how to use the containers, algorithms, strings, functors, auto_ptr and other components of STL. 

Iterators

An iterator is an object that can iterate through a range, pointing to the elements in the range. All iterators in STL provide at least the operator++, to iterate forward in the range, and the derreference operator(*), which provides the way to access the object to which the iterator points.

All containers define their own iterators, which have different abilities. There are five types of iterator in STL:

Input iterators

  • Allow only reading elements from a sequence and moving forward, one step, using operator++. The elements are read with operator*. Input iterators also provide operator== and operator!=.

Output iterators

  • Allow only writing elements from a sequence and only moving forward, one step, using operator++.
  • The elements are written with operator*.
  • These iterators also provide operator== and operator!=.

Forward iterators

  • Allow reading and writing elements from a sequence.
  • Only moving forward, one step, using the operator++ is possible.
  • The elements are read and written with operator*.
  • These iterators also provide operator== and operator!=.

Bidirectional iterators

  • Allow reading and writing elements from a sequence.
  • Allow moving forward and backward, one step, using operator++ and operator--.
  • Elements are read and written with operator*.
  • Bidirectional iterators also provide operator== and operator!=.
  • Examples of bidirectional iterator implemented in STL are the ones provided by the containers list, multiset, map, and multimap.

Random access iterators

  • Allow all operations a normal pointer does: add and subtract integral values, move forward and backward, one or more steps, use the operator[ ], subtraction of one iterator from another, and so on.
  • Such iterators overload operator<, operator>, operator==, operator!=.
  • Examples of random access iterators implemented in STL are the ones provided by the containers vector, deque, and for string.

Containers

STL provides sequence and associative containers. For an associative container, the index does not have to be an integer; it can be any type.

bitset

A special container class that is designed to store bits. It is optimized for space allocation: each element occupies only one bit.

Bitset is defined in the <bitset> header.

deque

A container that holds it's elements in multiple blocks of memory and keeps track of them, making it fast on insertions at the end and also at the beginning. It doesn't need to copy and destroy objects when it needs to allocate more memory. Deques invalidate iterators, pointers, and references when the size is changed.

Deques are the right choice:

  • for random access to elements
  • for iterating through it (from beginning to end or backwards)
  • for add or remove an element from the beginning and end
  • if it is important that the amount of memory used decreases as elements are removed from the deque.

Deque is defined in the <deque> header.

list

List is implemented as a doubly linked list of elements. std::list doesn't have random access, it provides only bidirectional iterators. For accessing an element you have to iterate through list, until you reach the element. Compared with vector or deque, list is not efficient for  random access.

List is the right choice for:

  • inserting and removing of elements anywhere in the container
  • moving elements (or block of elements) within the container (or between different containers)
  • iterating through it (backwards or forward).

List doesn’t invalidate an iterator that refers to an element as long as the element is not erased from the container.

map

The map container is an associative container. An entry in the map is a combination of key - value (std::pair). The key is used to identify an element in the map (the index).

  • the key/value pair must be assignable and copyable (the operator= and == must be defined for std::pair<key, value>).
  • the key must be comparable with the sorting criterion (the operator== must be defined for the pair<key, value>).

Map sorts its elements automatically by key ( from lower to higher ). The default comparison criterion is std::less, and it's provided as a default template parameter. Another ordering criterion, can be provided as the third template parameter. It has  to be a class that defines an operator() taking two arguments of the key type and returns a bool. It can be also just a function (with the same prototype as operator()).

std::map allows only unique entries. That means that you can't have in a map two entries with the same key. If you try to insert in map a entry with a certain key, and inside the map exits already an element with that key, the element will be overridden.

Map is the right choice:

  • if we need unique key values
  • element are pairs of key-value.
  • elements are sorted at all times.

Map provides bidirectional iterators.

Map is defined in the <map> header.

multiset

std::multiset sorts automatically it's elements from lower to higher and accepts multiple copies of an object.

Multiset sorts automatically it's elements from lower to higher and it is implemented usually as a binary search tree. The ordering criterion is, by default, std:less. Another one can supplied as the second template parameter. It can be a function, taking two arguments, of the key type and returning a bool or a class defining operator()  with the same prototype.

Multiset is the right choice:

  • if we need multiple elements with equal key.
  • if we need the elements are sorted at all times.
  • if we need to search for elements according to a certain criterion.       

Multiset is defined in the <set> header.

priority_queue

Priority_queue is implemented as a container adaptor. Containers adapters are classes that use an encapsulated container and provide a restricted interface to that container. The underlying container can be a STL container or some other  container type and it has to provide the  following public member functions: back(), push_back(), pop_back().

Priority_queue  is defined so that the first element is always the one with the highest value.

The default comparison criterion used is std::less. We can provide another comparison class, a functor, with it's operator() taking two  arguments, of the same type as the container elements, and returning a bool.

priority_queue is defined in the <queue> header.

queue

queue is implemented as a container adaptor. Containers adapters are classes that use an encapsulated container and provide a restricted interface to that container. The underlying container can be a STL container or some other  container type and it has to provide the  following public member functions:  front(), back(), push_back(), pop_front().

Queue is designed to operate in a FIFO mode (first-in first-out).

Queue is defined in the <queue> header.

set

std::set is an associative container, that stores unique elements. If you try to insert an object that is equivalent to one that is already in the set, the set won't make the insertion.
 
Set sorts automatically it's elements from lower to higher and it is implemented usually as a binary search tree. The ordering criterion can be supplied as the second template parameter and  is by default std::less.
 
The ordering criterion can be a function taking two arguments of the key type and returning a bool. A class defining operator() with the same parameters and returning value as the function can be also used as an ordering criterion.
 
Set is the right choice:

  • if we need unique elements
  • if we need the elements are sorted at all times.
  • if we need to search for elements according to a certain criterion. 

Set is defined in the <set> header.

stack

std::stack is implemented as a container adaptor. Containers adapters are classes that use an encapsulated container and provide a restricted interface to that container.
 
The underlying container can be a STL container or some other  container type and it has to provide the  following public member functions: back(), push_back(), pop_back().
 
Stack is a container that operates as in a LIFO (last in first out) mode.
 
The elements are inserted and extracted only from the end of the container.
 
std::stack is defined in the <stack> header.

vector

Vector keeps its elements in a dynamic array and maintains its storage as a single contiguous array of objects (in order to have efficient indexing and iteration).  That means that we can have random access to its elements, not only though iterators but also with pointers to elements, just like with regular arrays.
 
Accessing the elements of a vector provides almost the same performance as the regular arrays do. Compared with the other STL containers, vector has the fastest random access to its elements.
 
A dynamic array is allocated first time the vector is constructed. When vector needs a bigger array, to hold its elements, it will allocate a new, bigger, chunk of memory and will copy all the elements to this new chunk, deleting the old chunk and destroying the objects contained in it.
 
Vectors invalidate their iterators on insertions and deletions. Also when the capacity is exceeded, and new memory has to be allocated.
 
Vectors are the right choice for:

  • random access to its elements
  • iterating through it (from beginning to end or backwards)
  • add or remove an element from the end 

Vector is defined in the <vector> header.

Strings

String is a template class designed to manipulate sequences of characters. It is a special type of container holding characters. The string class is defined in the <string> header.

Functors 

A functor is a class that can act like a function. It has the advantage that, unlike functions, it can store data.
 
A functor is a class/struct that overloads the function call operator so that an instance of that class acts just like a function ( and can be supplied were a function is expected ).
 
For example:

class MyFunctor
{
         public:
         int operator()()
         {
               //some implementation
               //returns an integer value
         }
         private:
              //some data
 };

MyFunctor getNumber;
int someNumber = getNumber();        // MyFunctor::operator()() is called

The function call operator can be defined to take any number of parameters, or no parameters at all.

Algorithms

STL algorithms are function templates,implementing algorithms for sorting, filling, searching containers,comparing ranges, copying ranges, etc.

They can be used with any type of container (STL container or not) that provides the proper iterator and holds elements of types that overload the operators required by the algorithm.
For example the std::count algorithm, compares every element in a container with a value we provide. For comparison it uses operator==, so we have to have inside the container a type that has an operator== defined.

STL algorithms are defined in the <algorithm> header.

Utilities

auto_ptr

A smart pointer that takes ownership of the pointer it stores. When the auto_ptr object is destroyed, the pointer will be deleted.

auto_ptr is defined in the <memory> header.

pair

The pair structure is provided to treat two values as a single unit. It is defined in <utility> header.

min, max template functions

If both values are equal, usually the first element is returned. Both functions are provided with an additional argument, that is the comparison criterion.

The default comparison criterion is operator<.

These functions are defined in the <algorithm> header.

swap

This function is provided to swap the values of two objects. The swap is possible only if the copy constructor and the assignment operators are defined.

The function is defined in the <algorithm> header.

Missing STL headers

Due to platform limitiations some of the STL headers is not included in this package. They will be added later.

  • fstream
  • iomanip
  • ios
  • iostream
  • sstream
  • queue