|
| | HashTable () |
| | Constructs an empty hash table.
|
| |
| template<typename InputIt > |
| | HashTable (InputIt first, InputIt last) |
| | Constructs a hash table containing elements from a pair of iterators.
|
| |
|
size_type | size () const |
| | Returns the number of elements in the hash table.
|
| |
|
bool | empty () const |
| | Returns whether the hash table contains no element.
|
| |
| size_type | capacity () const |
| | Returns the size of the underlying array of cells.
|
| |
|
cell_iterator | cell_begin () |
| | Returns pointer to the beginning of the cell array.
|
| |
| cell_iterator | cell_end () |
| | Returns pointer to the end of the cell array.
|
| |
| template<bool Revive = false> |
| cell_iterator | find_cell (const T &x) |
| | Find an element that compares equal to the given value, or an empty cell if not found.
|
| |
|
bool | contains (const T &x) const |
| | Returns whether an element that compares equal to the given value is found in the hash table.
|
| |
| template<bool Replace = false> |
| bool | insert (const T &x) |
| | Insert an element if there is no element already present that compares equal to it.
|
| |
| template<bool Replace = false> |
| bool | insert (T &&x) |
| | Insert an element if there is no element already present that compares equal to it.
|
| |
|
bool | erase (const T &x) |
| | Remove the element that compares equal to the given value if it is present.
|
| |
| void | rehash (size_type new_cap) |
| | Allocate the given capacity, and rehash all elements.
|
| |
| void | reserve (size_type new_size) |
| | Reserve capacity and temporary disable shrinking.
|
| |
template<typename T, typename Hash = WyHash<T>, typename Eq = std::equal_to<T>>
class cplib::HashTable< T, Hash, Eq >
Linear probing hash table with std non-compliant interface.
This hash table aims to be fast for typical competitive programming use cases. Insertion, lookup and deletion takes expected \(O(1)\) time.
Only the lower bits of the hash value are used, so the hash function must be reasonably chaotic, and for integer types std::hash is not acceptable. By default it uses WyHash.
Due to lazy deletion, there are two load factors, the larger "non-empty" load factor which counts cells marked for deletion, and the smaller "occupied" load factor which doesn't. The rehashing policy is that both load factors are always within \([\frac{1}{8},\frac{1}{2}]\), unless the capacity is manually set (see HashTable::reserve). The lower bound is required for \(O(N)\) traversal. In addition, the capacity is always a power of two, and is at least 4.
- Template Parameters
-
| T | Type of elements. |
| Hash | Hash function object. |
| Eq | Equality comparison function object. |
template<typename T , typename Hash = WyHash<T>, typename Eq = std::equal_to<T>>
template<typename InputIt >
Constructs a hash table containing elements from a pair of iterators.
If the iterators are random access iterators, the number of elements is known, so sufficient space will be allocated in advance, so that no rehashing happens during construction.
template<typename T , typename Hash = WyHash<T>, typename Eq = std::equal_to<T>>
Reserve capacity and temporary disable shrinking.
If current capacity can hold at least new_size non-empty cells, does nothing. Note that if there are already some deleted cells, which are also considered non-empty, the hash table may not be able to hold new_size elements without rehashing.
Otherwise, rehashes and allocates enough capacity for holding at least new_size non-empty cells, After this, the capacity will never "naturally" shrink (due to low load factor), unless it has "naturally" grown (due to high load factor) at least once.
Note that the cost of traversing the hash table is proportional to its capacity, not its size. Thus traversal should be avoided after calling this function until all desired elements are inserted.
1.9.6