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
        }
    }
};

Breeze

The question is not 100% clear - you want to sort a (conceptual) sequence of unsorted_sets? – Gilmer

I have a list of items that I need to sort based on their member variables. One of the member variables to be compared in this sorting is an unordered_set. I just wanted to make it clear that I own the item's comparison operator, so I can make changes to how the operator compares unordered_sets. – Breeze

So apparently you know enough to implement an ordering predicate (like operator <) on the items. I am still unclear what the question is - do you have a "less than" criterion for the unorderd_sets which you have trouble expressin in code (if so, please add it to the question), or is it something else? – Gilmer

So I've added a minimal explanation class of the code I'm trying to work with. The "less_than criterion" is what I was hoping to get help with, cause I do not have one. – Breeze

So, basically your ordering on the two sets is defined as lexicographical_compare(sort(uo1), sort(uo2))? Also, if you are re-creating and destroying items very often you really want to make sure to reuse the memory of the sets. So instead of destroying them, assign to them. – Zelaya

Yeah pretty much, as I stated in the question, I've currently switched these into being sets so I can just use an operator< to compare. But I'm taking a performance hit on insertion. Is there some magic that I can do to sort unordered_sets? – Breeze

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

Latini

Can you help me understand what the Hash command in your lambda is doing, I don't understand how that would help us maintain a strict weak ordering (or even what that's doing in general.) – Breeze

@JonathanMee In general, elements in an unordered_set don't have an operator< defined (your int has, but that's an exception). The only assumption you can make is that they can be hashed to an integral number. So you can define an ordering based on that. The Hash()(kL) command creates a function object of type Hash and calls it with argument kL. – Latini