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