Ordered insertion into a vector: using learn search vs. binary search

gistfile1.cpp

// Victor Guerra <[email protected]>
// 2014-09-26

#include <cstdlib>
#include <cassert>

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

#include <chrono>

class timer {
  public:

  void start() { start_time = std::chrono::system_clock::now(); }
  std::chrono::microseconds microseconds() const {
    return std::chrono::microseconds(std::chrono::system_clock::now() -
                                     start_time);
  }

  private:
  using timer_t = std::chrono::system_clock::time_point;
  timer_t start_time;
};

// ordered_insert using linear search 
template <typename T>
typename std::vector<T>::iterator ordered_insert(
    std::vector<T>& container, typename std::vector<T>::value_type v) {
  typename std::vector<T>::iterator i(container.begin());
  while (i != container.end() && !(v < *i)) ++i;
  return container.insert(i, v);
}

// ordered_insert using binary search
template <typename T>
typename std::vector<T>::iterator ordered_insert_new(
    std::vector<T>& container, typename std::vector<T>::value_type v) {
  return container.insert(
      std::lower_bound(std::begin(container), std::end(container), v), v);
}

using namespace std;
using vInt = vector<uint64_t>;

static const size_t elements = 10000;

int main() {
  vInt vec(elements);
  iota(begin(vec), end(vec), 1);

  vec.erase(begin(vec) + elements / 2);
  assert(vec.size() == elements - 1);

  timer t1;

  t1.start();
  ordered_insert(vec, (elements / 2) + 1);
  cout << "O(n) insertion : " << t1.microseconds().count() << " us" << endl;

  vec.erase(begin(vec) + elements / 2);
  t1.start();
  ordered_insert_new(vec, (elements / 2) + 1);
  cout << "O(log(n)) insertion : " << t1.microseconds().count() << " us"<< endl;

  return EXIT_SUCCESS;
}