Benchmarks for insertion of random values into C++ containers maintaining order

random_insertion_containers.cc

#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <list>
#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;


void insert_vector_ordered(int n) {
  vector<int> v;
  for (int i = 0; i < n; i++) {
    int w = rand();
    auto it = lower_bound(v.begin(), v.end(), w);
    v.insert(it, w);
  }
}

void insert_vector_then_sort(int n) {
  vector<int> v;
  for (int i = 0; i < n; i++) {
    int w = rand();
    v.push_back(w);
  }
  sort(v.begin(), v.end());
}

void insert_list_ordered(int n) {
  list<int> v;
  for (int i = 0; i < n; i++) {
    int w = rand();
    auto it = lower_bound(v.begin(), v.end(), w);
    v.insert(it, w);
  }
}

void insert_list_then_sort(int n) {
  list<int> v;
  for (int i = 0; i < n; i++) {
    int w = rand();
    v.push_back(w);
  }
  v.sort();
}

void insert_set(int n) {
  set<int> s;
  for (int i = 0; i < n; i++) {
    int w = rand();
    s.insert(w);
  }
}

void timeit(int n, void (*test)(int)) {
  high_resolution_clock::time_point start = high_resolution_clock::now();
  test(n);
  high_resolution_clock::time_point end =  high_resolution_clock::now();

  milliseconds ms = duration_cast<milliseconds>(end - start);
  cout << n << " random values inserted in " << ms.count() << "ms" << endl;
}

int main() {
  cout << "insert_vector_ordered" << endl;
  timeit(100, insert_vector_ordered);
  timeit(1000, insert_vector_ordered);
  timeit(10000, insert_vector_ordered);
  timeit(100000, insert_vector_ordered);
  // timeit(1000000, insert_vector_ordered);

  cout << "insert_vector_then_sort" << endl;
  timeit(100, insert_vector_then_sort);
  timeit(1000, insert_vector_then_sort);
  timeit(10000, insert_vector_then_sort);
  timeit(100000, insert_vector_then_sort);
  timeit(1000000, insert_vector_then_sort);

  cout << "insert_list_ordered" << endl;
  timeit(100, insert_list_ordered);
  timeit(1000, insert_list_ordered);
  timeit(10000, insert_list_ordered);
  timeit(100000, insert_list_ordered);
  // timeit(1000000, insert_list_ordered);

  cout << "insert_list_then_sort" << endl;
  timeit(100, insert_list_then_sort);
  timeit(1000, insert_list_then_sort);
  timeit(10000, insert_list_then_sort);
  timeit(100000, insert_list_then_sort);
  timeit(1000000, insert_list_then_sort);

  cout << "insert_set" << endl;
  timeit(100, insert_set);
  timeit(1000, insert_set);
  timeit(10000, insert_set);
  timeit(100000, insert_set);
  timeit(1000000, insert_set);
  return 0;
}