Sorting on unordered_sets

Question

I have a list of items that are created each frame and need to be sorted. Each Item's first member variable to sort by is an unordered_set.

I've moved this to an ordered set everywhere in the system so I can sort it in the list of items. But I'm suffering a performance hit in another are of the code foe this.

Bearing in mind that each item will be destroyed and be recreated on a per-frame basis, is there anything I can do to hold these in unordered_sets and sort them?

class item
{
    public:
    unordered_set< int > _sortUS;
    int _sortI;
    //Other members to sort
    bool operator<( const item& that ) const
    {
        if( _sortI != that._sortI )
        {
            return _sortI < that._sortI;
        }
        else if( _sortUS != that._sortUS )
        {
            return ??? // this is what I need. I don't know how to compare these without converting them to sets
        }
    }
};

Answer 1

Given std::unordered_set<Key, Hash> for arbitrary hashable Key, you could define

template<class Key, class Hash = std::hash<Key>>
bool operator< (std::unordered_set<Key, Hash> const& L, std::unordered_set<Key, Hash> const& R)
{
    return std::lexicographical_compare(
        begin(L), end(L), begin(R), end(R), 
        [](Key const& kL, Key const& kR) {
        return Hash()(kL) < Hash()(kR);     
    });
}

which will use the ordering on hash indices of Key. You can then define an ordering on item

bool operator< (item const& L, item const& R)
{
     return std::tie(L.sortI, L.sortUS) < std::tie(R.sortI, R.sortUS);
}

and std::tie will make a std::tuple out of references to the members of your item so that you can use the operator< from std::tuple.

NOTE: you can easily prove that the above comparison is a StrictWeakOrder (a requirement for std::sort) since both the std::tuple comparison and the lexicographical_compare have this property.

However, the ordering of unordered_set is very unusual in other respects.

• the hashed key index doesn't correspond to the order in which you iterate over elements (there is some modulo operation that maps hashed keys to indices in the container)
• adding elements to an unordered_set can result in rehashing and invalidation of previous orderering