fork download 
  1. #include <list>
  2. #include <vector>
  3. #include <array>
  4.  
  5. template<typename K, typename V, typename H = std::hash<K>, typename P = std::equal_to<K>, typename A = std::allocator<std::pair<const K, V>>> class hash_map {
  6.     struct item {
  7.         std::pair<const K, V> data;
  8.         std::size_t cached_hash;
  9.     };
  10.     std::list<item, A> data;
  11.     H hash;
  12.     P predicate;
  13.     static const auto items_per_bucket = 5; // Arbitrary- determine by profile if performance undesirable
  14. public:
  15.  
  16.     struct iterator {
  17.         iterator(typename std::list<item, A>::iterator arg)
  18.             : it(arg) {}
  19.  
  20.         typename std::list<item, A>::iterator it;
  21.  
  22.         std::pair<const K, V>& operator*() { return it->data; }
  23.         std::pair<const K, V>* operator->() { return &it->data; }
  24.  
  25.         bool operator==(iterator other) {
  26.             return it == other.it;
  27.         }
  28.  
  29.         iterator operator++(int) {
  30.             auto ret(*this);
  31.             ++it;
  32.             return ret;
  33.         }
  34.         iterator& operator++() {
  35.             ++it;
  36.             return *this;
  37.         }
  38.         iterator operator--(int) {
  39.             auto ret(*this);
  40.             --it;
  41.             return ret;
  42.         }
  43.         iterator& operator--() {
  44.             --it;
  45.             return *this;
  46.         }
  47.  
  48.     };
  49.  
  50.     iterator begin() { return iterator(data.begin()); }
  51.     iterator end() { return iterator(data.end()); }
  52.     std::size_t size() const { return data.size(); }
  53.     void clear() { data.clear(); buckets.clear(); }
  54.  
  55. private:
  56.     std::vector<std::vector<iterator>> buckets;
  57.  
  58.     void insert_into_buckets(iterator it) {
  59.         if (buckets.size() == 0)
  60.             rehash(10); // Arbitrary- determine by profile if performance undesirable
  61.         auto&& bucket = buckets[it->cached_hash % buckets.size()];
  62.         if (bucket.size() >= items_per_bucket)
  63.             rehash(buckets.size() * 2);
  64.         buckets[it->cached_hash % buckets.size()].push_back(it);
  65.     }
  66. public:
  67.     void rehash(std::size_t size) {
  68.         auto oldbuckets = std::move(buckets);
  69.         buckets.resize(size);
  70.         for(auto&& iterators : oldbuckets) {
  71.             for(auto&& i : iterators) {
  72.                 insert_into_buckets(i);
  73.             }
  74.         }
  75.     }
  76.  
  77.     std::pair<iterator, bool> insert(K k, V v) {
  78.         auto it = find(k);
  79.         if (it == end()) {
  80.             std::size_t val = hash(k);
  81.             data.push_back(item { { std::move(k), std::move(v) }, val });
  82.             try {
  83.                 insert_into_buckets(--data.end());
  84.             } catch(...) {
  85.                 data.pop_back();
  86.                 throw;
  87.             }
  88.             return { --data.end(), true };
  89.         }
  90.         return { it, false };
  91.     }
  92.  
  93.     template<typename AK> iterator find(AK&& k) {
  94.         return find(std::forward<AK>(k), hash, predicate);
  95.     }
  96.     template<typename AK, typename AH> iterator find(AK&& k, AH&& h) {
  97.         return find(std::forward<AK>(k), std::forward<AH>(h), predicate);
  98.     }
  99.     template<typename AK, typename AH, typename AP> iterator find(AK&& k, AH&& h, AP&& p) {
  100.         auto&& bucket = buckets[h(k) % buckets.size()];
  101.         for(auto it : bucket) {
  102.             if (p(k, it->data.first))
  103.                 return it;
  104.         }
  105.         return end();
  106.     }
  107.  
  108.     template<typename AK> iterator erase(AK&& k) {
  109.         return erase(find(std::forward<AK>(k), hash, predicate));
  110.     }
  111.     template<typename AK, typename AH> iterator erase(AK&& k, AH&& h) {
  112.         return erase(find(std::forward<AK>(k), std::forward<AH>(h), predicate));
  113.     }
  114.     template<typename AK, typename AH, typename AP> iterator erase(AK&& k, AH&& h, AP&& p) {
  115.         return erase(find(std::forward<AK>(k), std::forward<AH>(h), std:forward<AP>(p)));
  116.     }
  117.  
  118.     iterator erase(iterator it) {
  119.         auto&& bucket = buckets[it.it->cached_hash % buckets.size()];
  120.         for(int i = 0; i < bucket.size(); i++) {
  121.             if (bucket[i] == it) {
  122.                 bucket.erase(bucket.begin() + i);
  123.                 return data.erase(it.it);
  124.             }
  125.         }
  126.         return end();
  127.     }
  128.  
  129.     template<typename AK> V& operator[](AK&& ak) {
  130.         auto it = find(std::forward<AK>(ak));
  131.         if (it == end())
  132.             return insert(ak, V()).first->data.second;
  133.         return it->data.second;
  134.     }
  135. };
  136. int main() {
  137.     hash_map<int, int> x;
  138.     auto y = x.begin();
  139.     auto z = x.end();
  140.     x.erase(y);
  141. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In member function 'void hash_map<K, V, H, P, A>::rehash(size_t)':
prog.cpp:70:30: error: expected initializer before ':' token
prog.cpp:75:5: error: expected primary-expression at end of input
prog.cpp:75:5: error: expected ';' at end of input
prog.cpp:75:5: error: expected primary-expression at end of input
prog.cpp:75:5: error: expected ')' at end of input
prog.cpp:75:5: error: expected statement at end of input
prog.cpp:75:5: error: expected '}' at end of input
prog.cpp: In member function 'hash_map<K, V, H, P, A>::iterator hash_map<K, V, H, P, A>::find(AK&&, AH&&, AP&&)':
prog.cpp:101:21: error: expected initializer before ':' token
prog.cpp:105:9: error: expected primary-expression before 'return'
prog.cpp:105:9: error: expected ';' before 'return'
prog.cpp:105:9: error: expected primary-expression before 'return'
prog.cpp:105:9: error: expected ')' before 'return'
prog.cpp: In member function 'hash_map<K, V, H, P, A>::iterator hash_map<K, V, H, P, A>::erase(AK&&, AH&&, AP&&)':
prog.cpp:115:72: error: expected primary-expression before ':' token
stdout 
Standard output is empty
https://ideone.com/Lck5O8
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!