📅 2015-Oct-30 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ bucket, cpp, hash table, unordered_set ⬩ 📚 Archive
The unordered containers in C++ are implemented as hash tables with separate chaining. The standard does not specify this implementation explicitly. But, by examining the requirements of the container, this is and will be the implementation in any C++ standard library.
Given this implementation, it would be an instructive exercise to be able to print out the actual structure of the hash table, with its buckets and linked list of keys. Thankfully, this is possible since the standard provides a bucket_count
method and a begin
method that takes a bucket index as input.
Here is simple code that prints buckets of unordered_set
and its output on my computer:
#include <unordered_set>
#include <iostream>
using IntHashTable = std::unordered_set<int>;
void PrintBuckets(const IntHashTable& htab)
{for (auto bi = 0; bi < htab.bucket_count(); ++bi)
{std::cout << "B[" << bi << "]:";
for (auto it = htab.begin(bi); it != htab.end(bi); ++it)
std::cout << " -> " << *it;
std::cout << "\n";
}
}
int main()
{3, 6, -2, 9, 199, 42};
IntHashTable htab = {
PrintBuckets(htab);
return 0;
}
// Output on my computer:
//
// $ ./a.out
// B[0]: -> 42 -> -2
// B[1]:
// B[2]: -> 9
// B[3]: -> 199 -> 3
// B[4]:
// B[5]:
// B[6]: -> 6
Tried with: GCC 5.1 and Ubuntu 14.04