fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <unordered_set>
  4. #include <functional>
  5. #include <chrono>
  6. #include <cmath>
  7. #include <random>
  8. #include <ctime>
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. using namespace __gnu_pbds;
  11. using namespace std;
  12. int getTicks()
  13. {
  14.     static auto startTime = std::chrono::high_resolution_clock::now();
  15.     auto t = std::chrono::high_resolution_clock::now();
  16.     return std::chrono::duration_cast<std::chrono::milliseconds>(t - startTime).count();
  17. }
  18. template<class T> struct hset
  19. {
  20.     size_t sz, (*hfunc)(T);
  21.     static constexpr uint8_t dead = 0, filled = 1, empty = 2;
  22.     uint8_t *state;
  23.     T *x;
  24.     int buffer;
  25.     hset(int s,
  26.          size_t (*hf)(T) = [](T val)->size_t{hash<T> hfunc; return hfunc(val);})
  27.     {
  28.         hfunc = hf;
  29.         sz = s;
  30.         buffer = 2*log2(sz) + 5; //a buffer lets us work faster because we don't have to check that pos<sz at the cost of a minimal chance of runtime error + a little memory
  31.         state = new uint8_t[sz+buffer];
  32.         x = new T[sz+buffer];
  33.         fill(state, state+sz+buffer, empty);
  34.     }
  35.     ~hset()
  36.     {
  37.         delete state;
  38.         delete x;
  39.     }
  40.     void clear()
  41.     {
  42.         fill(state, state+sz+buffer, empty);
  43.     }
  44.     bool erase(const T &v)
  45.     {
  46.         int pos = hfunc(v) % sz;
  47.         while(true)
  48.         {
  49.             if(state[pos] == empty)
  50.                 return false;
  51.             if(state[pos]==filled && x[pos]==v)
  52.             {
  53.                 state[pos] = dead;
  54.                 return true;
  55.             }
  56.             pos++;
  57.         }
  58.     }
  59.     void erase_x(const T &v) //UNSAFE! crashes if element is not found
  60.     {
  61.         int pos = hfunc(v) % sz;
  62.         while(true)
  63.         {
  64.             if(state[pos]==filled && x[pos]==v)
  65.             {
  66.                 state[pos] = dead;
  67.                 return;
  68.             }
  69.             pos++;
  70.         }
  71.     }
  72.     bool insert(const T &v)
  73.     {
  74.         int pos = hfunc(v) % sz;
  75.         int first = -1;
  76.         while(true)
  77.         {
  78.             if(state[pos] != filled)
  79.             {
  80.                 if(state[pos] == empty)
  81.                 {
  82.                     if(first == -1)
  83.                         first = pos;
  84.                     state[first] = filled;
  85.                     x[first] = v;
  86.                     return true;
  87.                 }
  88.                 else if(first == -1)
  89.                     first = pos;
  90.             }
  91.             else if(x[pos] == v)
  92.                 return false;
  93.             pos++;
  94.         }
  95.     }
  96.     int count(const T &v) const
  97.     {
  98.         int pos = hfunc(v) % sz;
  99.         while(true)
  100.         {
  101.             if(state[pos] == empty)
  102.                 return 0;
  103.             if(state[pos]==filled && x[pos]==v)
  104.                 return 1;
  105.             pos++;
  106.         }
  107.     }
  108.     T *find(const T &v) const
  109.     {
  110.         int pos = hfunc(v) % sz;
  111.         while(true)
  112.         {
  113.             if(state[pos] == empty)
  114.                 return NULL;
  115.             else if(state[pos]==filled && x[pos]==v)
  116.                 return &x[pos];
  117.             pos++;
  118.         }
  119.     }
  120.     size_t size()
  121.     {
  122.         return sz;
  123.     }
  124. };
  125. const int n = 3e6;
  126. int a[n], b[n];
  127. void testHSET()
  128. {
  129.     hset<int> v(4*n);
  130.     for(int i=0; i<n; i++)
  131.         v.insert(a[i]);
  132.     for(int i=0; i<n; i++)
  133.         v.erase(b[i]);
  134. }
  135. void testPBuset()
  136. {
  137.     gp_hash_table<int, null_type> v;
  138.     for(int i=0; i<n; i++)
  139.         v.insert(a[i]);
  140.     for(int i=0; i<n; i++)
  141.         v.erase(b[i]);
  142. }
  143. void testPBuset2()
  144. {
  145.     cc_hash_table<int, null_type> v;
  146.     for(int i=0; i<n; i++)
  147.         v.insert(a[i]);
  148.     for(int i=0; i<n; i++)
  149.         v.erase(b[i]);
  150. }
  151. void teststluset()
  152. {
  153.     unordered_set<int> v;
  154.     v.max_load_factor(0.5);
  155.     v.reserve(n);
  156.     for(int i=0; i<n; i++)
  157.         v.insert(a[i]);
  158.     for(int i=0; i<n; i++)
  159.         v.erase(b[i]);
  160. }
  161. #define RANDUZ_MAX 0x0fffffff
  162. int randuz()
  163. {
  164.     static std::mt19937 gen(time(NULL));
  165.     static std::uniform_int_distribution<int> d(0, RANDUZ_MAX);
  166.     return d(gen);
  167. }
  168. void testgood()
  169. {
  170.     unordered_set<int> s1;
  171.     hset<int> s2(10000, [](int x)->size_t{return x*x;});
  172.     for(int i=0; i<0xfff; i++)
  173.     {
  174.         s1.insert(i);
  175.         s2.insert(i);
  176.     }
  177.     for(int i=0; i<20000; i++)
  178.     {
  179.         int x = randuz() & 0xfff;
  180.         switch(randuz() % 3)
  181.         {
  182.         case 0:
  183.             s1.erase(x);
  184.             s2.erase(x);
  185.             break;
  186.         case 1:
  187.             s1.insert(x);
  188.             s2.insert(x);
  189.             break;
  190.         case 2:
  191.             if(s1.count(x) != s2.count(x))
  192.                 cout << "BAD\n";
  193.             break;
  194.         }
  195.     }
  196. }
  197. int main()
  198. {
  199.     testgood(); //test to make sure our hash set actually works
  200.     for(int i=0; i<n; i++)
  201.         a[i] = randuz(), b[i] = randuz();;
  202.     int s = getTicks();
  203.     testHSET();
  204.     int t = getTicks();
  205.     cout << "Custom hash set: " << t-s << "ms\n";
  206.     for(int i=0; i<n; i++)
  207.         a[i] = randuz(), b[i] = randuz();
  208.     s = getTicks();
  209.     testPBuset();
  210.     t = getTicks();
  211.     cout << "gp_hash_table: " << t-s << "ms\n";
  212.     for(int i=0; i<n; i++)
  213.         a[i] = randuz(), b[i] = randuz();
  214.     s = getTicks();
  215.     testPBuset2();
  216.     t = getTicks();
  217.     cout << "cc_hash_table: " << t-s << "ms\n";
  218.     for(int i=0; i<n; i++)
  219.         a[i] = randuz(), b[i] = randuz();;
  220.     s = getTicks();
  221.     teststluset();
  222.     t = getTicks();
  223.     cout << "unordered_set: " << t-s << "ms\n";
  224.     return 0;
  225. }
  226.  
Success #stdin #stdout 3.59s 190008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Custom hash set: 234ms
gp_hash_table: 247ms
cc_hash_table: 1713ms
unordered_set: 858ms
https://ideone.com/JqOprC
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!