Introduction to STL (standard template library) in C++

October 2016


One of the difficulties of C is to implement easy to use and effective, generic containers (vectors, linked lists, ordered sets). Generic containers require the use of use generic pointers (void *) and Cast operators. Moreover, when these containers are nested within each other (e.g a set of vectors) and the code quickly becomes complex to use.
  • To meet this end, the STL (standard template library) implements a large number of class template which describes generic containers for C ++. The STL also provides the algorithms which can easily handle these containers (to initialize them, search values, ...).
  • The concepts developed in the STL are now extended by the boost library which allows the manipulation of generic graph structures.
  • The aim of this introduction is not to make an exhaustive inventory of the possibilities offered by the STL, but to give common examples of use. You can find a very detailed overview of the STL classes here: Subsequently, we shall present the STL classes with templates (simple parameters).

The Main STL classes

It is particularly important to choose a class provided by the STL, which is consistent to your needs. Some structures are actually more or less efficient to access memory or in term of memory re-allocation. The aim of this section is to present the advantages and disadvantages of each class.

It is first necessary to have some notions of complexity. Let n be the size of a container. An algorithm is called linear (O(n)), if the computation time is proportional to n. Similarly, an algorithm is said to be instantaneous (O(1)), logarithmic O(log(n)), polynomial O(n^k), exponential O(e(n)), etc ...

To summarize, here is the list of complexities in order of increasing proportions of computation time:
  • O(1)
  • O(log(n))
  • O(n)
  • O(n^k)
  • O(e(n))

Here we will mainly focus on the complexity of access (search) to the data stored in a container and complexity to insert data.


A pair is a structure containing two elements, which may be of different types. Some algorithms of the STL (e.g find) return pairs (position of the found element and a boolean indicating if the latter has been located).

Complexity: insertion et acces in O(1)
#include <pair>
#include <iostream>
#include <string>

int main() { 
  std::pair<int,std::string> p = std::make_pair(5, "pouet"); 
  std::cout << p.first << ' ' << p.second << std::endl; 
  return 0; 


The class provides a generic list of linked lists which may optionally contain duplicates.

  • Insertion (at the beginning or end of the list): O(1)
  • Search: O(n) and O(1) for first and last link.


This example shows how to insert the values ??4, 5, 4, 1 in a list, and view its contents:

#include <list> 
#include <iostream> 

int main() { 
  std::list<int> ma_liste; 
    lit (ma_liste.begin()), 
  for(;lit!=lend;++lit) std::cout << *lit << ' '; 
  std::cout << std::endl;  
  return 0; 


The vector class is close to the table in C. All elements of the vector are adjacent in memory, allowing immediate access to any element. The advantage of the vector compared to the table is its ability to reallocate elements automatically when needed during a push_back or resize example.

  • Access O(1)
  • Insert: O(n) at the beginning of vector (pop_back), O(1) at the end of vector (push_back). In both cases, reallocations may occur.

We must not lose sight of that memory reallocation is costly in terms of performance.


#include <vector> 
#include <iostream> 

int main() { 
  std::vector<int> mon_vecteur; 

  // Pour parcourir un vector (même const) on peut utiliser les iterators ou les index 
  for(std::size_t i=0;i<mon_vecteur.size();++i) {
    std::cout << mon_vecteur[i] << ' ';
  std::cout << std::endl; 

  std::vector<int> mon_vecteur(5,69); // crée le vecteur 69,69,69,69,69 
  v[0] = 5; 
  v[1] = 3; 
  v[2] = 7; 
  v[3] = 4; 
  v[4] = 8; 
  return 0; 


This class allows you to describe an ordered set of elements without duplicates.:: less functor <T> (based on the <operator) is used, which is to have a set of elements ordered from smallest to largest.
Complexity: O(log(n)) for search and insertion.

# Include <set>
# Include <iostream>

int main () {
  std :: set <int> s / / equivalent to std :: set <int, std :: less <int>>
  s.insert (2) / / s contains two
  s.insert (5) / / s contains 2 May
  s.insert (2) / / the duplicate is not inserted
  s.insert (1) / / 1 2 5 s contains
  std :: set :: const_iterator <int>
    sit (s.begin ()),
    send (s.end ());
  for (; sit! = send, sit + +) std :: cout << * sit << '';
  std :: cout << std :: endl;
  return 0;


Deleting or adding an element in a std::set will make the iterators invalid.


A map to associate a key (identifier) ??to data (associative table).
The map takes at least two parameters templates:
  • the type of the key K
  • the type of the data T

O(log(n)) for search and insertion.

Deleting or adding an element in a std::map gives invalidates its iterators.


#include <map> 
#include <string> 
#include <iostream> 

int main() { 
  std::map<std::string,unsigned> map_mois_idx; 
  map_mois_idx["janvier"] = 1; 
  map_mois_idx["février"] = 2; 
    mit (map_mois_idx.begin()), 
  for(;mit!=mend;++mit) {
    std::cout << mit->first << '\t' << mit->second << std::endl; 
  return 0; 

The iterators

Iterators allows you to view the structure the STL from one end to the other. An iterator is somewhat reminiscent of the notion of pointer, but it is not an address.
We will now see four classic STL iterators.

They are defined for all STL classes mentioned above except for std::pair.

iterator and const_iterator

An iterator (and const_iterator) allows you to browse a container from the beginning to the end.
  • A const_iterator, unlike an iterator gives only read access to the pointed element.
  • An iterator provide both read and write access to an element (You can therefore modify the contents of the container).

This is why a "const" container can be viewed by const_iterators but not by iterators. Generally, when provided with a choice between iterators or const_iterator, you

should always favor the use of const_iterator, because they make the code section to which they belong more generic.
  • begin(): returns an iterator pointing to the first element.
  • end(): returns an iterator that points just "after" the last element
  • ++: Increments the iterator by passing it to the next item.


#include <list> 
#include <iostream> 

const std::list<int> creer_liste() { 
  std::list<int> l; 
  return l; 

int main() { 
  const std::list<int> ma_liste(creer_liste()); 

  // ne compile pas car l est const 
    lit1 (l.begin()), 
  for(;lit1!=lend1;++lit1) std::cout << *lit1 << ' '; 
  std::cout << std::endl;  */

    lit2 (l.begin()), 
  for(;lit2!=lend2;++lit2) std::cout << *lit2 << ' '; 
  std::cout << std::endl;  

  return 0; 

reverse_iterator and const_reverse_iterator

The principle of reverse_iterators and const_reverse_iterator is similar to iterators and const_iterator except that the path is in the opposite direction.

When used:
  • rbegin(): returns an iterator pointing to the last element
  • rend(): returns an iterator that points just "before" the first element
  • ++: Can increment the reverse_iterator by passing it to the previous item.


#include <set> 
#include <iostream> 

int main(){ 
  std::set<unsigned> s; 
  s.insert(1); // s = {1} 
  s.insert(4); // s = {1, 4} 
  s.insert(3); // s = {1, 3, 4} 
    sit (s.rbegin()), 
  for(;sit!=send;++sit) std::cout << *sit << std::endl; 
  return 0; 

... displays :


If the concept of iterator is mastered,you can refer to this page:

Related :

This document entitled « Introduction to STL (standard template library) in C++ » from CCM ( is made available under the Creative Commons license. You can copy, modify copies of this page, under the conditions stipulated by the license, as this note appears clearly.