Здравствуйте, T4r4sB, Вы писали:
N>>Стандартизация того, что корзины 1) есть, 2) их только один набор — очень жёстко зажимает реализацию до closed addressing hash map с рывочной пересборкой. По эффективности получается амортизированное O(1), но не стабильное O(1), как было раньше в Dinkumware и вслед Microsoft STL. А это значит, что критичные к постоянству времени приложения не могут его использовать.
TB>А как в хеш-мапе может быть стабильное O(1)? Вот не повезло и хеши совпали — и что?
Разумеется, всё работает в предположении, что на один хэш приходится не более K элементов, где K — константа, ограниченная задачей. Иначе хэш-мапа вообще не может быть полезной, и надо переходить к чему-то другому — например, мапе на дереве (собственно std::map в C++). Извините, абсолютных чудес не бывает. (Кстати, в Java начиная с 8-й защита против таких перекосов: если у корзины более 8 элементов, она преобразуется в маленький самопальный TreeMap. Вместо O(N) худшего случая получаем в результате O(log N).)
Я же говорил о другом. Если в процессе операции, которая имеет право делать создание новых корзин и перераспределение по ним (для unordered_map это позволено для insert с родственными, но не для erase), движок подсчитает, что надо перераспределить по другому составу корзин, это и есть O(N) для данной операции, а если нет, O(1). То есть время одного insert (emplace, etc.) может оказаться непредсказуемо высоким. Как говорил герой фильма, "стабильности нет". Сейчас в библиотеках для GCC и Clang именно так, они грубым рывком пересчитывают и перемещают всех.
А вот названные старые реализации позволяли иметь одновременно два набора корзин. Например, идёт активное заполнение, первый на 1024 корзин, второй на 2048. Каждый insert вставляет новый элемент (ключ+значение) в новый набор (который на 2048) и заодно перемещает два элемента из старого в новый. Действие по перегруппировке между корзинами, таким образом, аккуратно размазывается на разные операции. Или при удалении элементов, наоборот, новый набор тоньше, действие по сути то же самое.
В принципе, можно подобное накостылять (именно что накостылять) и в рамках требований C++11. Возвращал bucket_count() число 1024. Решили создать новый набор, оп — уже 3072, старый плюс новый. Закончился перенос из старого — старый удалили — 2048. Только сжатие назад неудобно. На erase() оно запрещено. Значит, если после всех erase() будет один insert(), на него надо навесить дополнительно сколько-то перемещений (минимум 2, лучше 3) из опустыненного широкого набора в новый узкий. Вроде я никаких подводных камней не заметил, но кто знает.
TB>А STLьную мапу ограничивает в первую очередь требование стабильности указателей на элементы — всё, dense_map пролетает, примет аллокация на каждый элемент
Ну если в большинстве корзин 0 или 1 элемент (GCC поддерживает по умолчанию load factor, равный 1) — это совмещено с самими корзинами. Можно оставлять место и на ещё один, больше — вряд ли, надо рисовать списки (или деревья, как выше).
