|
| | HashTable () |
| | Construct an empty hash table with normal default value.
|
| |
| | HashTable (const mapped_type &d) |
| | Construct an empty hash table with default value d.
|
| |
| | HashTable (const mapped_type &d, bucket_count_type n) |
| | Construct an empty hash table with at least n buckets.
|
| |
| | HashTable (const HashTable< K, V > &x) |
| | Construct a hash table as a copy of x.
|
| |
| | ~HashTable () |
| | Destroy this hash table, freeing its memory.
|
| |
| size_type | size () const |
| | Return the number of elements in the hash table.
|
| |
| bool | empty () const |
| | Return true iff size() == 0.
|
| |
| bucket_count_type | bucket_count () const |
| | Return the number of buckets in the hash table.
|
| |
| size_type | bucket_size (bucket_count_type n) const |
| | Return the number of elements in bucket n.
|
| |
| const mapped_type & | default_value () const |
| | Return the hash table's default value.
|
| |
| iterator | begin () |
| | Return an iterator for the first element in the table.
|
| |
| const_iterator | begin () const |
| |
| iterator | end () |
| | Return an iterator for the end of the table.
|
| |
| const_iterator | end () const |
| |
| size_type | count (key_const_reference key) const |
| | Return 1 if an element with key key exists, 0 otherwise.
|
| |
| const_iterator | find (key_const_reference key) const |
| | Return an iterator for the element with key key, if any.
|
| |
| iterator | find (key_const_reference key) |
| |
| iterator | find_prefer (key_const_reference key) |
| | Return an iterator for the element with key key, if any.
|
| |
| const mapped_type & | get (key_const_reference key) const |
| | Return the value for key.
|
| |
| mapped_type * | get_pointer (key_const_reference key) |
| | Return a pointer to the value for key.
|
| |
| const mapped_type * | get_pointer (key_const_reference key) const |
| |
| const mapped_type & | operator[] (key_const_reference key) const |
| | Return the value for key.
|
| |
| mapped_type & | operator[] (key_const_reference key) |
| | Return a reference to the value for key.
|
| |
| iterator | find_insert (key_const_reference key) |
| | Ensure an element with key key and return its iterator.
|
| |
| iterator | find_insert (key_const_reference key, const mapped_type &value) |
| | Ensure an element for key key and return its iterator.
|
| |
| bool | set (key_const_reference key, const mapped_type &value) |
| | Set the mapping for key to value.
|
| |
| bool | replace (key_const_reference key, const mapped_type &value) |
| | Set the mapping for key to value.
|
| |
| iterator | erase (const iterator &it) |
| | Remove the element indicated by it.
|
| |
| size_type | erase (key_const_reference key) |
| | Remove any element with key.
|
| |
| void | clear () |
| | Remove all elements.
|
| |
| void | swap (HashTable< K, V > &x) |
| | Swap the contents of this hash table and x.
|
| |
| void | rehash (bucket_count_type nb) |
| | Rehash the table, ensuring it contains at least n buckets.
|
| |
| HashTable< K, V > & | operator= (const HashTable< K, V > &x) |
| | Assign this hash table's contents to a copy of x.
|
| |
template<typename K, typename V>
class HashTable< K, V >
Hash table template.
The HashTable template implements a hash table or associative array suitable for use in the kernel or at user level. Its interface is similar to C++'s std::map and std::unordered_map, although those types have more methods.
Used with two template parameters, as HashTable<K, V>, the table maps keys K to values V. Used with one template parameter, as HashTable<T>, HashTable is a hash set. The type T must declare types named key_type and key_const_reference. It also must declare a hashkey() member function returning type key_const_reference. An object's hashkey() defines its key.
HashTable is a chained hash table. (Open coding is not appropriate in the kernel, where large contiguous memory allocations are essentially impossible.) When run through Google's sparse_hash_table tests (April 2008, sparsehash-1.1), HashTable appears to perform slightly better than g++'s hash_map, better than sparse_hash_map, and worse than dense_hash_map; it takes less memory than hash_map and dense_hash_map.
HashTable is faster than Click's prior HashMap class and has fewer potential race conditions in multithreaded use. HashMap remains for backward compatibility but should not be used in new code.
- Warning
- HashMap users should beware of HashTable's operator[]. HashMap's operator[] returned a non-assignable const reference; it would never add an element to the hash table. In contrast, the HashTable operator[] may add an element to the table. (If added, the element will initially have the table's default value.) For instance, consider:
HashMap<String, int> h(0);
h.insert("A", 1);
if (!h["B"])
printf("B wasn't in table, and still isn't\n");
for (HashMap<String, int>::iterator it = h.begin(); it; ++it)
printf("%s -> %d\n", it.key().c_str(), it.value());
-
Here the h["B"] reference does not add an element to the hash table, as you can see from the iteration. Similar HashTable code has a different result:
h["A"] = 1;
if (!h["B"])
printf("B wasn't in table, but it is now\n");
for (HashMap<String, int>::iterator it = h.begin(); it; ++it)
printf("%s -> %d\n", it.key().c_str(), it.value());
Hash table template.
Definition hashtable.hh:570
-
If you don't want operator[] to add an element, either access operator[] through a const hash table, or use get():
if (!h.get("B"))
printf("B wasn't in table, and still isn't\n");
if (!const_h["B"])
printf("B wasn't in table, and still isn't\n");
template<typename K , typename V >
Set the mapping for key to value.
If an element for key already exists in the table, then its value is assigned to value and the function returns false. Otherwise, a new element mapping key to value is added and the function returns true.
The behavior is basically the same as "(*this)[@a key] = @a value". (The difference is that if (*this)[key] is not already in the hash table, the new value is constructed rather than assigned.)
- Note
- Inserting an element into a HashTable invalidates all existing iterators.
