Какая политика хранения используется в сегменте boost :: intrusive :: unordered_set?
Я понимаю, что внутреннее повышение реализовано как любимые списки, верно? По крайней мере, в соответствии с http://www.boost.org/doc/libs/1_50_0/doc/html/unordered/buckets.html похоже на это.
У меня вопрос, каков порядок элементов в этих ведрах? Если они неупорядочены, есть ли способ применить MRU (последний использовавшийся) или какую-либо другую эвристику перемещения к фронту для порядка элементов в этих корзинах?
Изменить: я понимаю аргументы против применения MRU внутри ведра. Но в моем конкретном случае я знаю, что применение MRU [или даже «последний в первом обслуженном») превзошло бы меньший коэффициент загрузки. Вопрос в том, каков порядок? Есть ли простой способ обеспечить, по крайней мере, последний вставленный первым вышел&служил.
Решение
Ведра не отсортированы. Существуют веские причины, по которым ведра не сортируются. Хотя я уверен, что вы знаете об этом, я перечислю пару, чтобы помочь будущим посетителям сайта.
- Структура данных типа карты хеша не должна делать недействительными итераторы, если только вставка не приводит к перефразировке
- Чтобы сохранить быстрый поиск, ведра должны быть небольшими; в идеале каждое ведро должно содержать только один элемент.
На мой взгляд, принудительное упорядочение блоков MRU противоречит самой идее структуры типа хэш-карты. Идея состоит в том, чтобы контейнеры были небольшими, чтобы в среднем первым был тот элемент, который вам нужен.
Из-за этого, я сомневаюсь, что есть какой-либо встроенный способ обеспечить порядок MRU в контейнерах. Я бы порекомендовал вместо этого настроить алгоритм хэширования, возможно, уменьшив максимальный коэффициент загрузки.
Другие решения
После некоторого взлома, отвечая на мой собственный вопрос.
Реализация Boost Buckets находится в: http://www.boost.org/doc/libs/1_51_0/boost/unordered/detail/buckets.hpp.
Хотя это зависит от реализации и может измениться в любое время, в настоящее время, для навязчивого unordered_set, обход корзины [in .find ()] начинается с элементов, вставленных последними.
Например, если вы объявите unordered_set с 1000 сегментами:
class A : public unordered_set_base_hook<> { ... }
unordered_set<A>::bucket_type buckets[1000];
unordered_set<A> a(unordered_set<A>::bucket_traits(buckets, 1000));
и вставьте 10000 случайно выбранных элементов [смехотворно высокий коэффициент загрузки 10], элементы, вставленные в конец, будут иметь более быстрое [на порядок] время доступа [найти].