Code Yarns ‍👨‍💻
Tech BlogPersonal Blog

How to print structure of C++ unordered container

📅 2015-Oct-30 ⬩ ✍️ Ashwin Nanjappa ⬩ 📚 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()
{
    IntHashTable htab = {3, 6, -2, 9, 199, 42};

    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