C++ STL "Association Set/Map"

Question

I'm looking for the name of a particular kind of set/map, for which there is hopefully some existing code, such as the C++ STL.

Call the set A.

I would like to run the following commands:

A.associate(3,5)
A.associate(3,6)
A.associate(6,8)
A.associate(8,10)
A.associate(4,9)

And then be able to ask the following questions, receiving the answers indicated:

A.is_associated(3,5)  -> True
A.is_associated(5,10) -> True
A.is_associated(10,3) -> True
A.is_associated(4,10) -> False

Do you know the name of this kind of construct/set?

Do you know if there is an existing C/C++ implementation?

Answer 1

In general I think this data structure is a graph: that is, a set of nodes which are in your case identified using integer, and a set of edges which are possibly directed pairs of nodes. There are many ways to represent and graphs depending on your specific needs. Boost has a number of typical graph data structure plus a collection of algorithms operating on them.

Based on some the clarifications in the comments: the is_associated() operation is a path search in an undirected graph. Depending on the graph's need, adding edge can be made to represent the data structure such that is_associated() is constant time at the cost of insertion costing linear time.

Answer 2

Edit: if you want to go the extra step, you should think about an efficient implementation of Disjoint-set Union-Find.

Unfortunately the only sane way I see is making a std::map over std::sets -- you need to check each time at insert, whether the two elements are in different subsets -- if so, you merge them.

So the outer set stores all elements and points them to the sets they belong to.

Now if you add a new association:

1. check to which sets do A and B belong to
2. if neither belongs to any set, create a new set and map both values to that set (end)
3. if one belongs to a set and the other doesn't, put the other into the first ones set and map it there (end)
4. if both belong to different sets, merge the sets and update the elements mappings accordingly.

Now the is_associated function is really fast -- just check if the two elements belong to the same set.

In english:

typedef std::map< int, std::set< int >& > assoc_set; // note that you need to 
                 // store the sets somewhere else, maybe in another set

Something maybe like this:

class assoc_set
{
    typedef std::set< int > int_set;
    typedef std::set< int_set > int_set_set;
    typedef std::map< int, int_set_set::iterator > set_map;
public:
    void associate( int a, int b )
    {
        set_set_map::iterator ia = iss.find( a );
        set_set_map::iterator ib = iss.find( b );
        if ( ia == set_set_map::end() )
        {
            if ( ib == set_set_map::end() )
            {
                // create new
                int_set ab;
                ab.insert(a);
                ab.insert(b);
                int_set_set::iterator r = iss.insert( ab ).second;
                smap[a] = r;
                smap[b] = r;
            }
            else
            {
                // add to a
                smap[a] = ib;
                ib->insert( a );
            }
        }
        else
        {
            if ( ib == set_set_map::end() )
            {
                // add to b
                smap[b] = ia;
                ia->insert( b );
            }
            else
            {
                // merge
                ia->insert( ib->begin(), ib->end() );
                // this could be done better
                for ( int_set::iterator i = it->begin(); i != it->end(); ++i )
                {
                    smap[*i] = ia;
                }

            }

        }


    }

    bool is_associated( int a, int b )
    {
        set_set_map::iterator ia = iss.find( a );
        set_set_map::iterator ib = iss.find( b );

        return ia != set_set_map::end() && ia = ib;
    }

private:
    int_set_set iss;
    set_map smap;
}

There will be errors and bugs, I have just notepad available (and spent too much time on this anyway).

Adding is O(n) (but might be reduced to O(log(n)) by using an additional layer of indirection (and getting rid of the stupid map loop). Query is O(log(n)).

Using unordered_set/unordered_map you might reduce both to O(1) amortized.