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

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);
}

// find in a sorted vector<>
bool find(std::vector<int> & c, int val)
{
   return c.end() != std::find(c.begin(), c.end(), val);
}

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);
}

// find in a sorted deque<>
bool find(std::deque<int> & c, int val)
{
   return c.end() != std::find(c.begin(), c.end(), val);
}

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 find(std::set<int> & c, int val)
{
   return c.end() != c.find(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;
   
   for (auto val : v) insert(c, val);
   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;
   
   {
      timer t;

      for (auto val : v)
      {
      	auto found = find(c, val);
      	if (!found) std::cerr << "not found!" << 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);
   }
}