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