peltorator

!hash-set (slow, stupid)

Apr 12th, 2019
157
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. typedef unsigned long long integer;
  2.  
  3. struct my_hash_map
  4. {
  5.     vector<integer> q;
  6.     vector<char> used;
  7.     int cnt;
  8.  
  9.     my_hash_map(int sz = 1)
  10.     {
  11.         q.assign(sz, 0);
  12.         used.assign(sz, 0);
  13.         cnt = 0;
  14.     }
  15.  
  16.     void rehash(int sz)
  17.     {
  18.         if (sz <= sz(q))
  19.             return;
  20.         vector<integer> q_(sz, 0);
  21.         vector<char> used_(sz, 0);
  22.         for (int i = 0; i < sz(q); i++)
  23.             if (used[i])
  24.             {
  25.                 int pos = q[i] % (integer)sz;
  26.                 while (used_[pos])
  27.                     pos = (pos + 1 == sz ? 0 : pos + 1);
  28.                 used_[pos] = 1;
  29.                 q_[pos] = q[i];
  30.             }
  31.         swap(q, q_);
  32.         swap(used, used_);
  33.     }
  34.  
  35.     void insert(integer val)
  36.     {
  37.         int pos = val % (integer)sz(q);
  38.         while (used[pos])
  39.         {
  40.             if (q[pos] == val)
  41.                 return;
  42.             pos = (pos + 1 == sz(q) ? 0 : pos + 1);
  43.         }
  44.         used[pos] = 1;
  45.         q[pos] = val;
  46.         cnt++;
  47.         if (cnt * 2 > sz(q))
  48.             rehash(2 * sz(q) + 3); // random (lol)
  49.     }
  50.  
  51.     void erase(integer val)
  52.     {
  53.         int pos = val % (integer)sz(q);
  54.         while (used[pos])
  55.         {
  56.             if (q[pos] == val)
  57.             {
  58.                 cnt--;
  59.                 used[pos] = 0;
  60.                 return;
  61.             }
  62.             pos = (pos + 1 == sz(q) ? 0 : pos + 1);
  63.         }
  64.         return;
  65.     }
  66.  
  67.     int count(integer val)
  68.     {
  69.         int pos = val % (integer)sz(q);
  70.         while (used[pos])
  71.         {
  72.             if (q[pos] == val)
  73.                 return 1;
  74.             pos = (pos + 1 == sz(q) ? 0 : pos + 1);
  75.         }
  76.         return 0;
  77.     }
  78. };
RAW Paste Data