#include <vector>
#include <random>
#include <algorithm>

#include <boost/container/vector.hpp>
#include <boost/double_ended/devector.hpp>

#include <boost/range/counting_range.hpp>

#include <benchmark/benchmark.h>

namespace {

void devector_insert(benchmark::State& state)
{
  boost::double_ended::devector<std::size_t> c(state.range(0), 123lu);
  c.reserve_front(c.size() + 10);
  c.reserve_back(c.size() + 10);

  while (state.KeepRunning())
  {
    for (std::size_t p = 0; p < c.size(); ++p)
    {
      c.insert(c.begin() + p, p);
      state.PauseTiming();
      c.erase(c.begin() + p);
      state.ResumeTiming();
    }
  }
}

BENCHMARK(devector_insert)->Range(8, 8<<13);

void cvector_insert(benchmark::State& state)
{
  boost::container::vector<std::size_t> c(state.range(0), 123);
  c.reserve(c.size() + 20);

  while (state.KeepRunning())
  {
    for (std::size_t p = 0; p < c.size(); ++p)
    {
      c.insert(c.begin() + p, p);
      state.PauseTiming();
      c.erase(c.begin() + p);
      state.ResumeTiming();
    }
  }
}

BENCHMARK(cvector_insert)->Range(8, 8<<13);

}

BENCHMARK_MAIN();