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

$ 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