hash_set

std/hash_set.h

• Member Types
• Member Variables
• Member Functions
  • Constructor
  • Utility
  • Iterators
  • Accessors
  • Modifiers

---

template <class key_type, uint32_t (*hash_func)(const char *,int,uint32_t)>
struct hash_set : list<pair<int, key_type> >

This structure implements hash set. It uses a linked list of keys bucketed using a dynamic array of list iterators.

Member Types

• typedef list<pair<int, key_type> > super allows generic wrappers to access this container's inherited class type.
• typedef key_type type allows generic wrappers to access this container's key_type
• hash_set::iterator allows you to step through the elements in this set in hash value order.
• hash_set::const_iterator allows you to step through the elements in this set in hash value order.

Member Variables

• array<super::iterator> buckets keeps track of the locations of each bucket in the list.
• uint32_t salt is a random value added onto each hash to increase hashing security for sensitive applications.
• int shift represents the number of bits to shift the hash value down to get a bucket index.
• int count keeps track of the number of elements in this set.

Member Functions

Constructor

hash_set()

The default constructor, initializes buckets to a size of 16 elements pointing to begin(), producing a shift of 28 bits. count is initialized to 0 and salt is given a random value using rand().

Utility

int size() Returns count.

Iterators

iterator begin()
const_iterator begin() const

Returns an iterator to the first element.

iterator end()
const_iterator end() const

returns an iterator to one after the last element.

iterator rbegin()
const_iterator rbegin() const

returns an iterator to the last element.

iterator rend()
const_iterator rend() const

returns an iterator to one before the first element.

iterator at(int i)
const_iterator at(int i) const

returns an iterator to the ith element.

Accessors

value_type &front() Returns the value of the first element.

value_type &back() Returns the value of the last element.

value_type &get(int i) Returns the value of the ith element.

value_type *ptr(int i) Returns a pointer to the ith element.

value_type &operator[](int i) Returns the value of the ith element.

Modifiers

iterator insert(const key_type &key)

This places the given key into the hash set. It calculates the hash using hash_func, then uses the hash to look up the associated bucket. It then places the key into the list within the bucket range in sorted order with respect to the hash. This also increases the number of buckets if necessary, re-bucketing the keys.

iterator find(const key_type &key)
const_iterator find(const key_type &key)

This looks for a particular key in the set using a hash computed using hash_func.

int count_all(const key_type &key)

Computes the number of elements in this set equal to key.

bool contains(const key_type &key)

Checks to see if an element of key can be found in this set.