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

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8dW5vcmRlcmVkX3NldD4KI2luY2x1ZGUgPHN5cy90aW1lLmg+CiNpbmNsdWRlIDxyYW5kb20+CiNpbmNsdWRlIDxhbGdvcml0aG0+CgpuYW1lc3BhY2UgYmV0dGVyIHsKICB0ZW1wbGF0ZSA8dHlwZW5hbWUgVD5zdHJ1Y3QgaGFzaDsKICB0ZW1wbGF0ZTw+IHN0cnVjdCBoYXNoPHVuc2lnbmVkPiB7CiAgICBzdGQ6OnNpemVfdCB0YWJsZXNbMjU2XVs4XTsKCiAgICB0ZW1wbGF0ZSA8dHlwZW5hbWUgU3NlcT4KICAgIGhhc2goU3NlcSYmIHEpCiAgICB7CiAgICAgIHN0ZDo6bXQxOTkzNyBnZW4ocSk7CiAgICAgIHN0ZDo6Z2VuZXJhdGUoJnRhYmxlc1swXVswXSwKICAgICAgICAgICAgJnRhYmxlc1swXVswXSArIHNpemVvZih0YWJsZXMpL3NpemVvZigqKnRhYmxlcyksCgkJICAgIGdlbik7CiAgICB9CiAgCiAgICBzdGQ6OnNpemVfdCBvcGVyYXRvcigpICh1bnNpZ25lZCB4KSBjb25zdAogICAgewogICAgICByZXR1cm4gdGFibGVzWyh4Pj4gMCkmMHhmZl1bMF1eCiAgICAgICAgICAgICB0YWJsZXNbKHg+PiA4KSYweGZmXVsxXV4KICAgICAgICAgICAgIHRhYmxlc1soeD4+MTYpJjB4ZmZdWzJdXgogICAgICAgICAgICAgdGFibGVzWyh4Pj4yNCkmMHhmZl1bM107CiAgICB9CiAgfTsKfQoKc3RydWN0IHN0b3B3YXRjaCB7CiAgdGltZXZhbCB0MTsKICBjb25zdCBjaGFyICpzOwogIHN0b3B3YXRjaChjb25zdCBjaGFyKiBzKSA6IHMocykgeyBnZXR0aW1lb2ZkYXkoJnQxLCBOVUxMKTsgfQogIH5zdG9wd2F0Y2goKSB7CiAgICB0aW1ldmFsIHQyOyBnZXR0aW1lb2ZkYXkoJnQyLCBOVUxMKTsKICAgIHRpbWV2YWwgZDsgdGltZXJzdWIoJnQyLCAmdDEsICZkKTsKICAgIHN0ZDo6Y291dCA8PCBkLnR2X3NlYyA8PCAicyAiPDwgZC50dl91c2VjIDw8ICJuczogIiA8PCBzIDw8c3RkOjplbmRsOwogIH0KfTsKCnRlbXBsYXRlIDxjbGFzcyBTPgp2b2lkIHRlc3QoY29uc3QgY2hhciAqd2F0LCBTJiYgc2V0KQp7CiAgY29uc3QgaW50IHRlc3RzID0gNTA7CiAgY29uc3QgaW50IGluc2VydCA9IDUwMDsgLy8gZsO8ciBpZGVvbmUgZXR3YXMga2xlbmVyCiAgY29uc3QgaW50IGxvb2t1cCA9IDUwMDsgLy8gZGFzIGF1Y2gKCiAgc3RvcHdhdGNoIHMod2F0KTsKCiAgc3RkOjptdDE5OTM3IGdlbigxKTsKCiAgZm9yIChpbnQgaT0wOyBpPHRlc3RzOyArK2kpIHsKICAgIGZvciAoaW50IGk9MDsgaTxpbnNlcnQ7ICsraSkKICAgICAgc2V0Lmluc2VydChnZW4oKSk7CiAgICBmb3IgKGludCBpPTA7IGk8bG9va3VwOyArK2kpCiAgICAgIHNldC5maW5kKGdlbigpKTsKICB9Cn0KCmludCBtYWluKCkKewogIGZvciAoaW50IGk9MDsgaTw1OyArK2kpIHsKICAgIHRlc3QoInN0ZDo6c2V0Iiwgc3RkOjpzZXQ8dW5zaWduZWQ+KCkpOwogICAgdGVzdCgic3RkOjp1bm9yZGVyZWRfc2V0Iiwgc3RkOjp1bm9yZGVyZWRfc2V0PHVuc2lnbmVkPigpKTsKICAgIHRlc3QoInN0ZDo6dW5vcmRlcmVkX3NldCArIGJldHRlcjpoYXNoIiwKICAgICBzdGQ6OnVub3JkZXJlZF9zZXQ8dW5zaWduZWQsYmV0dGVyOjpoYXNoPHVuc2lnbmVkPj4oMCxiZXR0ZXI6Omhhc2g8dW5zaWduZWQ+KDU0ODl1KSkpOwogIH0KfQo=