bslstl_hashtableiterator

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Iterating a Hash Table Using HashTableIterator

Purpose

Provide an STL compliant iterator for hash tables.

Classes

• bslstl::HashTableIterator: an STL compliant forward iterator

Canonical header: bsl_unordered_map.h, bsl_unordered_set.h

See also

bslalg_bidirectionallink, bslstl_unorderedmap, 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:

typedef bslalg::BidirectionalNode<int> Node;

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:

bslalg::HashTableBucket buckets[NUM_BUCKETS];
for (int i = 0; i < NUM_BUCKETS; ++i) {
    buckets[i].reset();
}
bslalg::HashTableAnchor hashTable(buckets, NUM_BUCKETS, 0);

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:

for (int i = 0; i < NUM_NODES; ++i) {
    bslalg::HashTableImpUtil::insertAtFrontOfBucket(&hashTable,
                                                    nodes[i],
                                                    nodes[i]->value());
}

Next, we define a typedef that is an alias an instance of HashTableIterator that can traverse hash tables holding integer values.

typedef bslstl::HashTableIterator<int, ptrdiff_t> Iter;

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:

2
4
1
3
0

Finally, we deallocate the memory used by the hash table:

for (int i = 0; i < NUM_NODES; ++i) {
    scratch.deallocate(nodes[i]);
}