0
Thanks

A few words of thanks would be greatly appreciated.

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

Introduction

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.

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.

std::pair<T1,T2>

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; 
} 

std::list<T,...>

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

Complexity:

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

Example:

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; 
  ma_liste.push_back(4); 
  ma_liste.push_back(5); 
  ma_liste.push_back(4); 
  ma_liste.push_back(1); 
  std::list<int>::const_iterator 
    lit (ma_liste.begin()), 
    lend(ma_liste.end()); 
  for(;lit!=lend;++lit) std::cout << *lit << ' '; 
  std::cout << std::endl;  
  return 0; 
} 

std::vector<T,...>

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.

Complexity:

  • 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.

Example:

#include <vector> 
#include <iostream> 

int main() { 
  std::vector<int> mon_vecteur; 
  mon_vecteur.push_back(4); 
  mon_vecteur.push_back(2); 
  mon_vecteur.push_back(5); 

  // 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; 
} 

std::set<T,...>

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;
}

Warning:

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

std::map<K,T,...>

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

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

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

Example:

#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; 
  //... 
  std::map<std::string,unsigned>::const_iterator 
    mit (map_mois_idx.begin()), 
    mend(map_mois_idx.end()); 
  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.

Example:

#include <list> 
#include <iostream> 

const std::list<int> creer_liste() { 
  std::list<int> l; 
  l.push_back(3); 
  l.push_back(4); 
  return l; 
} 

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

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

  std::list<int>::const_iterator 
    lit2 (l.begin()), 
    lend2(l.end()); 
  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.

Example:

#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} 
  std::set<unsigned>::const_reverse_iterator 
    sit (s.rbegin()), 
    send(s.rend()); 
  for(;sit!=send;++sit) std::cout << *sit << std::endl; 
  return 0; 
}

... displays :

4 
3 
1

Algorithms

If the concept of iterator is mastered,you can refer to this page: https://community.hpe.com/t5/custom/page/page-id/HPPSocialUserSignonPage?redirectreason=permissiondenied&referer=https%3A%2F%2Fcommunity.hpe.com%2Ft5%2Fservers-systems-the-right%2Fsgi-com-tech-archive-resources-now-retired%2Fba-p%2F6992583.

0
Thanks

A few words of thanks would be greatly appreciated.

Ask a question
CCM is a leading international tech website. Our content is written in collaboration with IT experts, under the direction of Jean-François Pillou, founder of CCM.net. CCM reaches more than 50 million unique visitors per month and is available in 11 languages.
Related
This document, titled « Introduction to STL (standard template library) in C++ », is available under the Creative Commons license. Any copy, reuse, or modification of the content should be sufficiently credited to CCM (ccm.net).