#include <iostream>
#include <set>
#include <unordered_set>
#include <sys/time.h>
#include <random>
#include <algorithm>

namespace better {
  template <typename T>struct hash;
  template<> struct hash<unsigned> {
    std::size_t tables[256][8];

    template <typename Sseq>
    hash(Sseq&& q)
    {
      std::mt19937 gen(q);
      std::generate(&tables[0][0],
            &tables[0][0] + sizeof(tables)/sizeof(**tables),
		    gen);
    }
  
    std::size_t operator() (unsigned x) const
    {
      return tables[(x>> 0)&0xff][0]^
             tables[(x>> 8)&0xff][1]^
             tables[(x>>16)&0xff][2]^
             tables[(x>>24)&0xff][3];
    }
  };
}

struct stopwatch {
  timeval t1;
  const char *s;
  stopwatch(const char* s) : s(s) { gettimeofday(&t1, NULL); }
  ~stopwatch() {
    timeval t2; gettimeofday(&t2, NULL);
    timeval d; timersub(&t2, &t1, &d);
    std::cout << d.tv_sec << "s "<< d.tv_usec << "ns: " << s <<std::endl;
  }
};

template <class S>
void test(const char *wat, S&& set)
{
  const int tests = 50;
  const int insert = 500; // für ideone etwas klener
  const int lookup = 500; // das auch

  stopwatch s(wat);

  std::mt19937 gen(1);

  for (int i=0; i<tests; ++i) {
    for (int i=0; i<insert; ++i)
      set.insert(gen());
    for (int i=0; i<lookup; ++i)
      set.find(gen());
  }
}

int main()
{
  for (int i=0; i<5; ++i) {
    test("std::set", std::set<unsigned>());
    test("std::unordered_set", std::unordered_set<unsigned>());
    test("std::unordered_set + better:hash",
     std::unordered_set<unsigned,better::hash<unsigned>>(0,better::hash<unsigned>(5489u)));
  }
}