#include <algorithm>
#include <chrono>
#include <random>
#include <list>
#include <iostream>
#include <vector>

template <typename T> void orderedInsert(T &List, int Elem) {
  auto Iter = std::lower_bound(List.begin(), List.end(), Elem);
  List.insert(Iter, Elem);
}

template <typename T> void orderedDelete(T &List, int Elem) {
  // Finds the first thing greater than or equal to Elem.
  auto Iter = std::lower_bound(List.begin(), List.end(), Elem);
  if (Iter != List.end() && *Iter == Elem)
    List.erase(Iter);
}

// Ensure that inling doesn't play with things...
template <typename T> __attribute__((noinline)) void touchElems(T &List) {
  volatile int *Ptr;
  for (int &I : List) {
    Ptr = &I;
    // Compilers can't kill volatile ops ;)
    *Ptr;
  }
}

// Ensure that inling doesn't play with things...
template <typename T>
__attribute__((noinline)) void runTest(T &__restrict__ List,
                                       const std::vector<int> &ToInsert) {
  for (int I : ToInsert)
    orderedInsert(List, I);

  for (int I : ToInsert)
    orderedDelete(List, I);
}

using BenchDuration = std::chrono::duration<double, std::ratio<1, 1000>>;
template <typename T> BenchDuration timeIt(const T &Fn) {
  using Clock = std::chrono::high_resolution_clock;
  auto Start = Clock::now();
  Fn();
  return Clock::now() - Start;
}

template <typename Iter> void printRange(Iter Start, Iter End) {
  std::cout << '[';
  bool First = true;
  for (auto I = Start; I != End; ++I) {
    if (!First)
      std::cout << ", ";
    else
      First = false;
    std::cout << I->count() << "ms";
  }
  std::cout << ']';
}

int main() {
  constexpr int NumElems = 5000;
  constexpr int NumOps = 5000;
  constexpr int NumRuns = 5;
  std::vector<int> Numbers(NumElems);
  std::list<int> NumbersList;

  for (unsigned I = 0, E = NumElems; I != E; ++I) {
    Numbers[I] = I * 2;
    NumbersList.push_back(I * 2);
  }

  std::vector<int> Ops(NumOps);
  std::mt19937 RNG;
  int UpperBound = Numbers.back();
  for (int &I : Ops)
    I = RNG() % UpperBound;

  std::vector<BenchDuration> VecTimes(NumRuns);
  for (auto &Time : VecTimes) {
    touchElems(Numbers);
    touchElems(Ops);
    Time = timeIt([&] { runTest(Numbers, Ops); });
  }

  std::vector<BenchDuration> ListTimes(NumRuns);
  for (auto &Time : ListTimes) {
    touchElems(NumbersList);
    touchElems(Ops);
    Time = timeIt([&] { runTest(NumbersList, Ops); });
  }

  std::cout << "Vec times: ";
  printRange(VecTimes.begin(), VecTimes.end());
  std::cout << '\n';

  std::cout << "List times: ";
  printRange(ListTimes.begin(), ListTimes.end());
  std::cout << '\n';
}