Provide an STL compliant iterator for hash tables.
More...
Detailed Description
- Outline
-
-
- Purpose:
- Provide an STL compliant iterator for hash tables.
-
- Classes:
-
- See also:
- Component bslalg_bidirectionallink, Component bslstl_unorderedmap, Component bslstl_unorderedset
-
- Description:
- This component provides a standard-conforming forward iterator,
bslstl::HashTableIterator
, over a list of elements (of type bslalg::BidirectionalLink
) in a hashtable. The requirements of a forward iterator are outlined in the C++11 standard in section [24.2.5] under the tag [forward.iterators]. The bslstl::HashTableIterator
class template has two template parameters: VALUE_TYPE
, and DIFFERENCE_TYPE
. VALUE_TYPE
indicates the type of the value to which this iterator provides references, and may be const-qualified for constant iterators. DIFFERENCE_TYPE
determines the (standard mandated) difference_type
for the iterator, and will typically be supplied by the allocator used by the hash-table being iterated over.
-
- Usage:
- This section illustrates intended use of this component.
-
- Example 1: Iterating a Hash Table Using HashTableIterator:
- In the following example we create a simple hashtable and then use a
HashTableIterator
to iterate through its elements.
- First, we define a typedef,
Node
, prepresenting a bidirectional node holding an integer value: Then, we construct a test allocator, and we use it to allocate an array of Node
objects, each holding a unique integer value: bslma::TestAllocator scratch;
const int NUM_NODES = 5;
const int NUM_BUCKETS = 3;
Node *nodes[NUM_NODES];
for (int i = 0; i < NUM_NODES; ++i) {
nodes[i] = static_cast<Node *>(scratch.allocate(sizeof(Node)));
nodes[i]->value() = i;
}
Next, we create an array of HashTableBuckets
objects, and we use the array to construct an empty hash table characterized by a HashTableAnchor
object: Then, we insert each node in the array of nodes into the hash table using bslalg::HashTableImpUtil
, supplying the integer value held by each node as its hash value: Next, we define a typedef
that is an alias an instance of HashTableIterator
that can traverse hash tables holding integer values. Now, we create two iterators: one pointing to the start of the bidirectional linked list held by the hash table, and the other representing the end sentinel. We use them to navigate and print the elements of the hash table: Iter iter(hashTable.listRootAddress());
Iter end;
for (;iter != end; ++iter) {
printf("%d\n", *iter);
}
Then, we observe the following output: Finally, we deallocate the memory used by the hash table: for (int i = 0; i < NUM_NODES; ++i) {
scratch.deallocate(nodes[i]);
}