fork download 
  1. #pragma once
  2.  
  3. #include <list>
  4. #include <vector>
  5.  
  6. namespace Wide {
  7.     namespace Utility {
  8.         template<typename T, typename H = std::hash<T>, typename P = std::equal_to<T>, typename A = std::allocator<T>> class hash_set {
  9.             struct item {
  10.                 T data;
  11.                 std::size_t cached_hash;
  12.                 item(T t, std::size_t hash)
  13.                     : data(std::move(t)), cached_hash(hash) {}
  14.             };
  15.             std::list<item, A> data;
  16.             H hash;
  17.             P predicate;
  18.             static const auto items_per_bucket = 5; // Arbitrary- determine by profile if performance undesirable
  19.         public:    
  20.             struct iterator {
  21.                 iterator(typename std::list<item, A>::iterator arg)
  22.                     : it(arg) {}
  23.  
  24.                 typename std::list<item, A>::iterator it;
  25.  
  26.                 T& operator*() { return it->data; }
  27.                 T* operator->() { return &it->data; }
  28.  
  29.                 bool operator==(iterator other) {
  30.                     return it == other.it;
  31.                 }
  32.                 bool operator!=(iterator other) {
  33.                     return it != other.it;
  34.                 }
  35.  
  36.                 iterator operator++(int) {
  37.                     auto ret(*this);
  38.                     ++it;
  39.                     return ret;
  40.                 }
  41.                 iterator& operator++() {
  42.                     ++it;
  43.                     return *this;
  44.                 }
  45.                 iterator operator--(int) {
  46.                     auto ret(*this);
  47.                     --it;
  48.                     return ret;
  49.                 }
  50.                 iterator& operator--() {
  51.                     --it;
  52.                     return *this;
  53.                 }
  54.  
  55.             };
  56.  
  57.             iterator begin() { return iterator(data.begin()); }
  58.             iterator end() { return iterator(data.end()); }
  59.             std::size_t size() const { return data.size(); }
  60.             void clear() { data.clear(); buckets.clear(); }
  61.  
  62.         private:
  63.             std::vector<std::vector<iterator>> buckets;    
  64.             void insert_into_buckets(iterator it) {
  65.                 if (buckets.size() == 0)
  66.                     rehash(10); // Arbitrary- determine by profile if performance undesirable
  67.                 if (load_factor() > 0.75) {
  68.                     rehash(buckets.size() * 2);
  69.                     return insert_into_buckets(it);
  70.                 }
  71.                 if (buckets[it.it->cached_hash % buckets.size()].size() >= items_per_bucket) {
  72.                     rehash(buckets.size() * 2);
  73.                     return insert_into_buckets(it);
  74.                 }
  75.                 buckets[it.it->cached_hash % buckets.size()].push_back(it);
  76.             }
  77.         public:
  78.             float load_factor() {
  79.                 return (float)size() / (float)buckets.size();
  80.             }
  81.             float max_load_factor() {
  82.                 return items_per_bucket;
  83.             }
  84.  
  85.             void rehash(std::size_t size) {
  86.                 auto oldbuckets = std::move(buckets);
  87.                 buckets.resize(size);
  88.                 for(auto&& iterators : oldbuckets) {
  89.                     for(auto&& i : iterators) {
  90.                         insert_into_buckets(i);
  91.                     }
  92.                 }
  93.             }
  94.  
  95.             bool empty() { return data.size() == 0; }
  96.  
  97.             std::pair<iterator, bool> insert(T t) {
  98.                 auto it = find(t);
  99.                 if (it == end()) {
  100.                     std::size_t val = hash(t);
  101.                     data.push_back(item( std::move(t), val));
  102.                     try {
  103.                         insert_into_buckets(--data.end());
  104.                     } catch(...) {
  105.                         data.pop_back();
  106.                         throw;
  107.                     }
  108.                     return std::make_pair(--data.end(), true);
  109.                 }
  110.                 return std::make_pair(it, false);
  111.             }
  112.  
  113.             template<typename AK> iterator find(AK&& k) {
  114.                 return find(std::forward<AK>(k), hash, predicate);
  115.             }
  116.             template<typename AK, typename AH> iterator find(AK&& k, AH&& h) {
  117.                 return find(std::forward<AK>(k), std::forward<AH>(h), predicate);
  118.             }
  119.             template<typename AK, typename AH, typename AP> iterator find(AK&& k, AH&& h, AP&& p) {
  120.                 if (empty()) return end();
  121.                 auto&& bucket = buckets[h(k) % buckets.size()];
  122.                 for(auto it : bucket) {
  123.                     if (p(k, it.it->data))
  124.                         return it;
  125.                 }
  126.                 return end();
  127.             }
  128.  
  129.             template<typename AK> iterator erase(AK&& k) {
  130.                 return erase(find(std::forward<AK>(k), hash, predicate));
  131.             }
  132.             template<typename AK, typename AH> iterator erase(AK&& k, AH&& h) {
  133.                 return erase(find(std::forward<AK>(k), std::forward<AH>(h), predicate));
  134.             }
  135.             template<typename AK, typename AH, typename AP> iterator erase(AK&& k, AH&& h, AP&& p) {
  136.                 return erase(find(std::forward<AK>(k), std::forward<AH>(h), std:forward<AP>(p)));
  137.             }
  138.  
  139.             iterator erase(iterator it) {
  140.                 if (empty()) return end();
  141.                 auto&& bucket = buckets[it.it->cached_hash % buckets.size()];
  142.                 for(int i = 0; i < bucket.size(); i++) {
  143.                     if (bucket[i] == it) {
  144.                         bucket.erase(bucket.begin() + i);
  145.                         return data.erase(it.it);
  146.                     }
  147.                 }
  148.                 return end();
  149.             }
  150.  
  151.             void swap(hash_set& other) {
  152.                 std::swap(data, other.data);
  153.                 std::swap(buckets, other.buckets);
  154.                 std::swap(hash, other.hash);
  155.                 std::swap(predicate, other.predicate);
  156.             }
  157.  
  158.             hash_set& operator=(hash_set h) {
  159.                 swap(h);
  160.                 return *this;
  161.             }
  162.             hash_set(hash_set&& other)
  163.                 : data(std::move(other.data))
  164.                 , buckets(std::move(other.buckets))
  165.             {}
  166.             hash_set(const hash_set& other)
  167.                 : data(other.data) 
  168.             {
  169.                 buckets.resize(other.buckets.size());
  170.                 for(auto it = data.begin(); it != data.end(); ++it)
  171.                     insert_into_buckets(it);
  172.             }
  173.             hash_set() {}
  174.         };
  175.     }
  176. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:1:9: warning: #pragma once in main file [enabled by default]
prog.cpp:8:43: error: expected type-specifier
prog.cpp:8:43: error: expected ‘>’
prog.cpp:8:135: error: expected unqualified-id before ‘{’ token
stdout 
Standard output is empty
https://ideone.com/Xa2Bkw
language:
C++ (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!