#include <iostream>
#include <chrono>
#include <random>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <set>

const int Size = 10000;

int rnd(int max) { static auto engine = std::default_random_engine(); return engine() % max; }

// really simple RAII timer utility
struct timer
{
   typedef std::chrono::high_resolution_clock clock;
   clock::time_point start_;

   timer() : start_(clock::now()) {}
   ~timer()
   {
      std::cout 
         << ((double)std::chrono::duration_cast<std::chrono::microseconds>(clock::now() - start_).count() / 1000.)
         << "ms" << std::endl;
   }
};

//
// std::vector<> specialisations
//

// insert into a sorted vector<>
void insert(std::vector<int> & c, int val)
{
   // first find the insertion point (naiively)
   auto it = c.begin(); 
   while (it != c.end() && *it <= val) ++it;

   c.insert(it, val);
}

// remove from a sorted vector<>
bool remove(std::vector<int> & c, int val)
{
   // first find the insertion point (naiively)
   auto it = c.begin(); 
   while (it != c.end() && *it < val) ++it;

   if (it == c.end() || *it != val) return false;
   c.erase(it);
   return true;
}

bool isSorted(std::vector<int> & c)
{
   int prev = -1;
   for (auto v : c)
   {
      if (v < prev) return false;
      prev = v;
   }
   return true;
}

//
// std::deque<> specialisations
//

// insert into a sorted deque<>
void insert(std::deque<int> & c, int val)
{
   // first find the insertion point (naiively)
   auto it = c.begin(); 
   while (it != c.end() && *it <= val) ++it;

   c.insert(it, val);
}

// remove from a sorted deque<>
bool remove(std::deque<int> & c, int val)
{
   // first find the insertion point (naiively)
   auto it = c.begin(); 
   while (it != c.end() && *it < val) ++it;

   if (it == c.end() || *it != val) return false;
   c.erase(it);
   return true;
}

bool isSorted(std::deque<int> & c)
{
   int prev = -1;
   for (auto v : c)
   {
      if (v < prev) return false;
      prev = v;
   }
   return true;
}

//
// std::set<> specialisations
//

void insert(std::set<int> & c, int val)
{
   c.insert(val);
}

bool remove(std::set<int> & c, int val)
{
   return 1 == c.erase(val);
}

bool isSorted(std::set<int> &)
{
	// set is always sorted
   return true;
}

//
// test drivers
//

template <typename C>
void test(std::string name, std::vector<int> v, C & c)
{
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : v) insert(c, val);
      
#if false
	  std::cerr << "WARNING: this line should not be printed in the actual test" << std::endl;
	  // verify that inserts all worked - dont do this in the actual test though!
	  if (c.size() != Size) std::cerr << "ERROR: output is not big enough!" << std::endl;
	  if (!isSorted(c)) std::cout << "ERROR: output is not sorted!" << std::endl;
#endif

      for (auto val : v)
      {
      	auto removed = remove(c, val);
      	if (!removed) std::cerr << "not removed!" << std::endl;
      }
   }
   if (0 != c.size()) std::cerr << "ERROR: elements not removed!" << std::endl;
}

int main()
{
   // assume we are always inserting unique numbers
   // (this should bias towards std::vector because it will ensure the
   // std::set is as large as possible)
   std::cout << "shuffling numbers..." << std::endl;
   std::vector<int> v;
   for (auto i = 0; i < Size; i++) v.push_back(i);
   std::random_shuffle(v.begin(), v.end());
   
   std::cout << "numbers shuffled. first few numbers:";
   for (auto i = 0; i < 10; i++) std::cout << " " << v[i];
   std::cout << std::endl;

   // vector<> test
   {
      std::vector<int> sorted;
      sorted.reserve(Size); // ensure we arent reallocating unnecessarily

      test("vector", v, sorted);
   }

   // deque<> test
   {
      std::deque<int> sorted;
      test("deque", v, sorted);
   }
   
   // set<> test
   {
      std::set<int> sorted;

      test("set", v, sorted);
   }
}