Сортировка по unordered_sets

Question

У меня есть список элементов, которые создаются каждый кадр и должны быть отсортированы. Первая переменная-член каждого элемента для сортировки является unordered_set,

Я переместил это в упорядоченный набор везде в системе, чтобы я мог отсортировать его в списке элементов. Но я страдаю от снижения производительности в другом коде для этого.

Принимая во внимание, что каждый элемент будет уничтожен и воссоздан для каждого кадра, могу ли я что-то сделать для unordered_setи сортировать их?

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

Дано std::unordered_set<Key, Hash> для произвольного хеширования KeyВы могли бы определить

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

который будет использовать порядок по хеш-индексам Key, Затем вы можете определить порядок на item

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

а также std::tie сделаю std::tuple из ссылок на членов вашего item так что вы можете использовать operator< от std::tuple,

ПРИМЕЧАНИЕ: вы можете легко доказать, что приведенное выше сравнение является StrictWeakOrder (требование для std::sort) поскольку оба std::tuple сравнение и lexicographical_compare иметь это свойство.

Тем не менее, порядок unordered_set очень необычен в других отношениях.

• индекс хешированного ключа не соответствует порядку, в котором вы перебираете элементы (есть некоторая операция по модулю, которая отображает хешированные ключи на индексы в контейнере)
• добавление элементов в unordered_set может привести к перефразированию и аннулированию предыдущего заказа