fork download 
  1. template<typename K, typename V, typename H = std::hash<K>, typename P = std::equal_to<K>> class hash_set {
  2.     struct item {
  3.         std::pair<const K, V> data;
  4.         std::size_t cached_hash;
  5.     };
  6.     std::list<item> data;
  7.     H hash;
  8.     P predicate;
  9.     static const auto items_per_bucket = 5; // Arbitrary- determine by profile if performance undesirable
  10. public:
  11.  
  12.     struct iterator {
  13.         typename std::list<item>::iterator it;
  14.         std::pair<const K, V>& operator*() { return it->data; }
  15.         std::pair<const K, V>* operator->() { return &it->data; }
  16.  
  17.         iterator operator++(int) {
  18.             auto ret(*this);
  19.             ++it;
  20.             return ret;
  21.         }
  22.         iterator& operator++() {
  23.             ++it;
  24.             return *this;
  25.         }
  26.         iterator operator--(int) {
  27.             auto ret(*this);
  28.             --it;
  29.             return ret;
  30.         }
  31.         iterator& operator--() {
  32.             --it;
  33.             return *this;
  34.         }
  35.  
  36.     };
  37.  
  38.     iterator begin() { return iterator { data.begin() }; }
  39.     iterator end() { return iterator { data.end() }; }
  40.     std::size_t size() const { return data.size(); }
  41.     void clear() { data.clear(); buckets.clear(); }
  42.  
  43. private:
  44.     std::vector<std::vector<iterator>> buckets;
  45.  
  46.     void insert_into_buckets(iterator it) {
  47.         if (buckets.size() == 0)
  48.             rehash(10); // Arbitrary- determine by profile if performance undesirable
  49.         auto&& bucket = buckets[it->cached_hash % buckets.size()];
  50.         if (bucket.size() >= items_per_bucket)
  51.             rehash(buckets.size() * 2);
  52.         buckets[it->cached_hash % buckets.size()].push_back(it);
  53.     }
  54. public:
  55.     void rehash(std::size_t size) {
  56.         auto oldbuckets = std::move(buckets);
  57.         buckets.resize(size);
  58.         for(auto&& iterators : oldbuckets) {
  59.             for(auto&& i : iterators) {
  60.                 insert_into_buckets(i);
  61.             }
  62.         }
  63.     }
  64.  
  65.     std::pair<iterator, bool> insert(K k, V v) {
  66.         auto it = find(k);
  67.         if (it == end()) {
  68.             std::size_t val = hash(k);
  69.             data.push_back(item { { std::move(k), std::move(v) }, val });
  70.             try {
  71.                 insert_into_buckets(--data.end());
  72.             } catch(...) {
  73.                 data.pop_back();
  74.                 throw;
  75.             }
  76.             return { --data.end(), true };
  77.         }
  78.         return { it, false };
  79.     }
  80.  
  81.     template<typename AK> iterator find(AK&& k, H h = H(), P p = P()) {
  82.         return find(std::forward<AK>(k), h, p);
  83.     }
  84.     template<typename AK, typename AH> iterator find(AK&& k, AH&& h = AH(), P p = P()) {
  85.         return find(std::forward<AK>(k), std::forward<AH>(h), p);
  86.     }
  87.     template<typename AK, typename AH, typename AP> iterator find(AK&& k, AH&& h = AH(), AP&& p = AP()) {
  88.         auto&& bucket = buckets[h(k) % buckets.size()];
  89.         for(auto it : bucket) {
  90.             if (p(k, it->data.first))
  91.                 return it;
  92.         }
  93.         return end();
  94.     }
  95.     template<typename AK> iterator erase(AK&& k, H h = H(), P p = P()) {
  96.         return erase(find(std::forward<AK>(k), h, p));
  97.     }
  98.     template<typename AK, typename AH> iterator erase(AK&& k, AH&& h = AH(), P p = P()) {
  99.         return erase(find(std::forward<AK>(k), std::forward<AH>(h), p));
  100.     }
  101.     template<typename AK, typename AH, typename AP> iterator erase(AK&& k, AH&& h = AH(), AP&& p = AP()) {
  102.         return erase(find(std::forward<AK>(k), std::forward<AH>(h), std:forward<AP>(p)));
  103.     }
  104.     iterator erase(iterator it) {
  105.         auto&& bucket = buckets[it->cached_hash % buckets.size()];
  106.         for(int i = 0; i < bucket.size(); i++) {
  107.             if (bucket[i] == it) {
  108.                 bucket.erase(bucket.begin() + i);
  109.                 return data.erase(it.it);
  110.             }
  111.         }
  112.         return end();
  113.     }
  114.     template<typename AK> V& operator[](AK&& ak) {
  115.         auto it = find(std::forward<AK>(ak));
  116.         if (it == end())
  117.             return insert(ak, V()).first->data.second;
  118.         return it->data.second;
  119.     }
  120. };
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/eHOi4y
language:
C++14 (gcc 8.3)
created:
11 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!