C++: Using unordered_set

📅 2012-Jun-26 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ cpp, unordered_set ⬩ 📚 Archive

There are many additions to STL in C++11, one of which is unordered_set. This is just a long and complicated name for a hash table to store keys. (To store key-value pairs, use unordered_map).

To compile and function correctly, unordered_set needs two functions: 1. An equality comparison function for the key type. 2. A hash function to generate a hash value for any key.

For in-built types, like int, both of these functions are already implemented, so creating and using an unordered_set of int is very easy:

#include <iostream>
#include <unordered_set>

typedef std::unordered_set< int > IntUSet;

int main()
{
    IntUSet iset;

    // Insert
    iset.insert( 10 );
    iset.insert( 99 );
    iset.insert( 1000 );

    // Find
    if ( iset.end() == iset.find( 99 ) )
        std::cout << "Not found\n";
    else
        std::cout << "Found\n";

    // Remove
    iset.erase( 10 );

    return 0;
}

If you need an unordered_set of your custom struct or class, you will need to provide these two functions. The usage is a bit different:

#include <iostream>
#include <unordered_set>

struct Point
{
    int x, y;

    bool operator == ( const Point& p ) const
    {
        return ( ( x == p.x ) && ( y == p.y ) );
    }
};

struct PointHash
{
    std::size_t operator () ( const Point& p ) const
    {
        // Modified Bernstein hash
        // http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

        return ( 33 * p.x ) ^ p.y;
    }
};

typedef std::unordered_set< Point, PointHash > PointUSet;

int main()
{
    PointUSet pset;

    // Insert
    Point parr[3] = {
        { 0, 0 },
        { 10, -20 },
        { 99, 1000 }
    };

    pset.insert( parr[0] );
    pset.insert( parr[1] );
    pset.insert( parr[2] );

    // Find
    if ( pset.end() == pset.find( parr[1] ) )
        std::cout << "Not found\n";
    else
        std::cout << "Found\n";

    // Remove
    pset.erase( parr[2] );

    return 0;
}

Tried with: Visual C++ 2010