Как отсортировать элементы в корзине std::unordered_set?

Question

После заполнения STL unordered_set я пытаюсь отсортировать элементы в каждом сегменте в соответствии с определенным порядком (несмотря на противоречивое имя контейнера). Это известный факт, что нельзя вносить изменения в элементы в контейнере, и, насколько я понимаю, это мешает стандартному std::sort работать. Например, следующий код не скомпилируется:

#include <unordered_set>
int main()
{
    std::unordered_set<int> set_;

    set_.max_load_factor(100);

    set_.insert(6);
    set_.insert(3);
    set_.insert(8);
    set_.insert(17);
    set_.insert(1);
    set_.insert(2);
    set_.insert(9);

    for (int i = 0; i < set_.bucket_count(); ++i)
    {
        std::sort(set_.begin(i), set_.end(i));
    }
}

Итак, есть ли способ обойти это препятствие? Можно ли получить временный отсортированный список, а затем назначить его начальному сегменту?

Answer 1

"в моем реальном коде... пользовательская хеш-функция... размещает элементы так, как мне нужно" - вы в этом уверены? - Ваша пользовательская хеш-функция напрямую не выбирает сегмент - unordered_set использует его в качестве входных данных для выбора сегмента, часто делая что-то вроде % bucket_count()или возможно & (bucket_count() - 1) в качестве оптимизации, если bucket_count() всегда сила двух. И вы не можете обязательно контролировать количество сегментов - вызов reserve(n) может округлять n например, до ближайшего (не обязательно следующего) простого числа или, возможно, степени двойки. Вся реализация определена. Тем не менее, вы могли бы использовать bucket_count() в вашей хэш-функции, чтобы по-настоящему контролировать, как ваши ключи сгруппированы в сегменты, или только производить значения хеша меньше n вы поставили reserve(), но к тому времени, когда вы делаете это, вы с таким же успехом можете управлять индексами в std::vector ключей. В любом случае, этого достаточно - давайте просто поверить, что вы действительно управляете хэшированием и ведением так, как вы намерены: если вы хотите отсортированный список элементов из корзины, вы можете просто использовать:

std::unordered_map<KeyOnly, AnotherContainer<KeyAndValue>> x;

куда AnotherContainer любой контейнер, который по своей природе отсортирован (например, std::set) или могут быть явно отсортированы в вашем коде так, как вы пытаетесь ответить на вопрос (например, std::list, std::vector).

Answer 2

Нет API для того, чтобы делать то, что вы делаете, потому что это нарушение принципа проектирования STL, согласно которому контейнеры предоставляют интерфейс, а не реализацию. Нет никакой гарантии, что "сортировка каждого сегмента" имеет какой-либо смысл (даже если это возможно в вашей конкретной реализации).

Если вы уверены, что вам нужно "отсортировать каждую корзину" в хеш-таблице, вам нужно будет реализовать собственную хеш-таблицу. Учитывая множество реализаций с открытым исходным кодом, это не составит труда. Там, где сегмент часто реализуется с использованием связанного списка, вы можете использовать сбалансированное двоичное дерево.