fork download 
  1. #ifndef LITB_HASHTABLE_H
  2. #define LITB_HASHTABLE_H
  3.  
  4. #include "vector.hpp"
  5. #include "utils.hpp"
  6. #include <utility>
  7. #include <cstdint>
  8.  
  9. namespace litb {
  10. namespace detail {
  11.    uint32_t hash() = delete;
  12. }
  13.  
  14. // A hash table mapping "Key" to "Value". 
  15. // "Key" must provide a "hash" function that is
  16. // found by argument-dependent-lookup.
  17. template<typename Key, typename Value>
  18. class HashTable {
  19.    struct Bucket;
  20.  
  21.    template<typename BucketType>
  22.    struct Iterator;
  23.  
  24.    typedef Iterator<Bucket> iterator;
  25.    typedef Iterator<const Bucket> const_iterator;
  26.    typedef Pair<const Key, Value> value_type;
  27.    typedef Key key_type;
  28.    typedef Value mapped_type;
  29.  
  30. public:
  31.    HashTable():_size() {}
  32.    ~Hash() {
  33.       clear();
  34.    }
  35.  
  36.    // returns the size (number of keys) of this table
  37.    int size() const {
  38.       return _size;
  39.    }
  40.  
  41.    // inserts the given mapping, returning false if the key was already mapped. in that case,
  42.    // the value will not be updated.
  43.    bool insert(const Pair<Key, Value>& mapping) {
  44.       struct C { 
  45.          const Value &operator()() const { 
  46.             return value;
  47.          }
  48.          const Value& value;
  49.       } creator = { mapping.second };
  50.       return internalInsert(key, creator);
  51.    }
  52.  
  53.    // inserts a mapping of key to value.
  54.    // returns true if the mapping was inserted, and false if the key was already
  55.    // mapped. In that case, the value will not be updated.
  56.    bool insert(const Key& key, const Value& value) {
  57.       struct C { 
  58.          const Value &operator()() const { 
  59.             return value;
  60.          }
  61.          const Value& value;
  62.       } creator = { value };
  63.       return internalInsert(key, creator);
  64.    }
  65.  
  66.    // returns true if the table contains a mapping from key to a value
  67.    bool contains(const Key& key) const {
  68.       return getBucket(key) != nullptr;
  69.    }
  70.  
  71.    // returns a reference to the value mapped by the given key. If the element
  72.    // does not exist yet, it is value-initialized and copied to the map.
  73.    Value &at(const Key& key) {
  74.       struct C { 
  75.          Value operator()() const {
  76.             return Value();
  77.          }
  78.       } creator;
  79.       return getOrCreateBucket(key, c)->_value;
  80.    }
  81.  
  82.    Value &operator[](const Key& key) {
  83.       return at(key);
  84.    }
  85.  
  86.    // if for this overload the element does not exist, behavior is undefined
  87.    const Value& at(const Key& key) const {
  88.       return getBucket(key)->_value;
  89.    }
  90.  
  91.    const Value& operator[](const Key& key) const {
  92.       return at(key);
  93.    }
  94.  
  95.    // after calling this the map contains no elements anymore
  96.    void clear() {
  97.       erase(begin(), end());
  98.    }
  99.  
  100. private:
  101.    // one bucket in the buckets array
  102.    struct Bucket {
  103.       Bucket(const Key& key, const Value& value, Bucket *next)
  104.          :_data(key, value), _next(next)
  105.       { }
  106.  
  107.       value_type _data;
  108.       Bucket *_next;
  109.    };
  110.  
  111.    template<typename BucketType>
  112.    struct Iterator {
  113.       typedef HashTable::value_type value_type;
  114.       typedef typename TransferCv<value_type, BucketType>::type &reference_type;
  115.       typedef typename TransferCv<value_type, BucketType>::type *pointer;
  116.       typedef int difference_type;
  117.       typedef std::forward_iterator_tag iterator_category;
  118.  
  119.       IteratorBase(BucketType *const *bucketHead)
  120.          :_bucketHead(bucketHead), _bucket(bucketHead) 
  121.       { }
  122.  
  123.    public:
  124.       reference_type operator*() const {
  125.          return _bucket->_data;
  126.       }
  127.  
  128.       pointer operator->() const {
  129.          return &_bucket->_data;
  130.       }
  131.  
  132.       // convenience wrappers key() and value() return the key and the mapped data 
  133.       // respectively
  134.       const key_type& key() const {
  135.          return (*this)->first;
  136.       }
  137.  
  138.       typedef typename TransferCv<mapped_type, BucketType>::type &value() const {
  139.          return (*this)->second;
  140.       }
  141.  
  142.    public:
  143.       Iterator operator++(int) {
  144.          Iterator it(*this);
  145.          ++it;
  146.          return it;
  147.       }
  148.  
  149.       Iterator &operator++() {
  150.          if(!_bucket->_next) {
  151.             _bucketHead++;
  152.             _bucket = _bucketHead;
  153.          }
  154.          return *this;
  155.       }
  156.  
  157.       BucketType *const *_bucketHead;
  158.       BucketType *_bucket;
  159.    };
  160.  
  161. private:
  162.    static uint32_t hash(const Key& key) const {
  163.       using detail::hash;
  164.       return hash(key);
  165.    }
  166.  
  167.    template<typename Creator>
  168.    bool internalInsert(const Key& key, const Creator& c) {
  169.       int oldSize = size();
  170.       Bucket *bucket = getOrCreateBucket(key, c);
  171.       return size() != oldSize;
  172.    }
  173.  
  174.    // returns a bucket for the given key and value.
  175.    // if not yet existing, call "creator()" to create and return a new
  176.    // instance of the value.
  177.    template<typename Creator>
  178.    Bucket *getOrCreateBucket(const Key& key, const Creator& c) {
  179.       if(_buckets.empty()) {
  180.          _buckets.resize(128);
  181.       } else {
  182.          const float loadFactor = size() / (float)_buckets.size();
  183.          if(loadFactor > 0.75) {
  184.             rehash();
  185.          }
  186.       }
  187.  
  188.       int bucketIndex = hash(key) % _buckets.size();
  189.       Bucket *bucket = _buckets[bucketIndex];
  190.       for(Bucket *bucket1 = bucket; bucket1; bucket1 = bucket1->_next) {
  191.          if(bucket1->_data.first == key) {
  192.             return bucket1;
  193.          }
  194.       }
  195.       bucket = new Bucket(key, c(), bucket);
  196.       _buckets[bucketIndex] = bucket;
  197.       _size++;
  198.       return bucket;
  199.    }
  200.  
  201.    // returns the bucket for the given key and nullptr if it is not found
  202.    const Bucket *getBucket(const Key& key) const {
  203.       int bucketIndex = hash(key) % _buckets.size();
  204.       const Bucket *bucket = _buckets[bucketIndex];
  205.       for(const Bucket *bucket1 = bucket; bucket1; bucket1 = bucket1->_next) {
  206.          if(bucket1->_data.first == key) {
  207.             return bucket1;
  208.          }
  209.       }
  210.       return nullptr;
  211.    }
  212.  
  213.    // this will reallocate the bucket array and rehash everything
  214.    void rehash() {
  215.       int newSize = _buckets.size() * 2;
  216.       VectorBase<Bucket*> newBuckets;
  217.       newBuckets.resize(newSize);
  218.       for(Bucket *bucket : _buckets) {
  219.          while(bucket) {
  220.             int bucketIndex = hash(bucket->_data.first) % newBuckets.size();
  221.  
  222.             Bucket *bucket1 = bucket;
  223.             bucket = bucket->next;
  224.             bucket1->next = newBuckets[bucketIndex];
  225.             newBuckets[bucketIndex] = bucket1;
  226.          }
  227.       }
  228.       _buckets = std::move(newBuckets);
  229.    }
  230.  
  231. private:
  232.    VectorBase<Bucket*> _buckets;
  233.    int _size;
  234. };
  235. }
  236.  
  237. #endif
  238.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/m6qisL
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!