1. Homepage of Dr. Zoltán Porkoláb
    1. Home
    2. Archive
  2. Teaching
    1. Timetable
    2. Bolyai College
    3. C++ (for mathematicians)
    4. Imperative programming (BSc)
    5. Multiparadigm programming (MSc)
    6. Programming (C in English)
    7. Programming languages (PhD)
    8. Software technology lab
    9. Theses proposals (BSc and MSc)
  3. Research
    1. CodeChecker
    2. CodeCompass
    3. Templight
    4. Projects
    5. Publications
    6. PhD students
  4. Affiliations
    1. Dept. of Programming Languages and Compilers
    2. Ericsson Hungary Ltd

Practice 17.

The containers of the STL

Video: cpp-mat-gyak17-stl.mkv

In this example we compare different STL containers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <chrono>
#include <algorithm>

const int nelems = 10000000;   // # elements to insert

template <typename Container>  // generic version to add
void add( Container &c, typename Container::value_type v)
{
  c.push_back(v);
}
template <typename T> 
void add( std::set<T> &c, // specialization for set
          typename std::set<T>::value_type v)
{
  c.insert(v);	
}
template <typename T>  // sepcialization for unordered_set
void add( std::unordered_set<T> &c, 
          typename std::unordered_set<T>::value_type v)
{
  c.insert(v);	
}
template <typename Container>
void test( Container &c)
{
  // start timer
  auto tp1 = std::chrono::system_clock::now();

  for ( int i = 0; i < nelems; ++i)
  {
    add( c, rand() ); // fill the container
  }
  auto comp = *c.begin();   // the first element to compare
  int cnt = std::count_if( c.begin(), c.end(),
                        [comp](int x) { return x < comp; });

  // stop timer
  auto tp2 = std::chrono::system_clock::now();

  std::cout << "size = " << c.size();
  std::cout << ", # smaller " << comp << " " << cnt << "\n";  
  std::cout << "time = " << std::chrono::duration_cast<
               std::chrono::milliseconds>(tp2-tp1).count()
	    << "ms\n";
}
int main()
{
  std::vector<int>     vec1;
  std::vector<int>     vec2;  vec2.reserve(nelems);
  std::list<int>       lst1;
  std::deque<int>      deq1;
  std::set<int>        set1;
  std::unordered_set<int> uos1;
  std::unordered_set<int> uos2; uos2.rehash(nelems);

  test( vec1);
  test( vec2);
  test( lst1);
  test( deq1);
  test( set1);
  test( uos1);
  test( uos2);

  return 0;
}

Running the pogram we can recognize, that teh set and unordered_set structures have less size that nelems. The reason is that they cannot store multiple values with the same key. Use the multiset and unordered_multiset to store key duplicates (homework).

$ g++ -Wall -Wextra cont.cpp
$ ./a.out
size = 10000000, # smaller 1804289383 8401922
time = 276ms 
size = 10000000, # smaller 241090179 1121513
time = 253ms
size = 10000000, # smaller 456457288 2126289
time = 845ms
size = 10000000, # smaller 520980426 2422857
time = 272ms
size = 9976628, # smaller 456 0
time = 13940ms
size = 9976916, # smaller 310716277 1441706
time = 7451ms
size = 9976482, # smaller 1528376374 7099003
time = 3768ms

Financed from the financial support ELTE won from the Higher Education Restructuring Fund of the Hungarian Government.