Какое использование локального итератора для неупорядоченных контейнеров STL?

Question

В §23.2.7 неупорядоченные ассоциативные контейнеры [unord.req] стандартной таблицы C++ 91 описывают дополнительные требования, которым должен соответствовать неупорядоченный ассоциативный контейнер STL. В этой таблице стандарт диктует, что STL неупорядоченные контейнеры (т.е. unordered_set, unordered_map, unordered_multiset а также unordered_multimap) должны предоставить в качестве типов членов local_iterator а также const_local_iterator,

• local_iterator является типом итератора, у которого типы категорий, значений, разностей, указателей и ссылок совпадают с типами неупорядоченного контейнера iterator, Этот итератор может использоваться для перебора одного сегмента, но не между сегментами.
• const_local_iterator является типом итератора, у которого типы категорий, значений, разностей, указателей и ссылок совпадают с типами неупорядоченного контейнера const_iterator, Этот итератор может использоваться для перебора одного сегмента, но не между сегментами.

Q

Каковы некоторые применения этих итераторов?

Answer 1

Главное, для чего я вижу, это проверить, сколько у вас коллизий. С помощью bucket Вы можете получить, в каком контейнере хранится ключ. Затем вы можете передать это значение в begin который вернет local_iterator к предметам в этом ведре. Теперь вы можете выполнить итерацию этого сегмента и посмотреть, сталкиваетесь ли вы с какими-либо другими элементами, и если вы, то каковы эти элементы. Это, в свою очередь, позволяет настроить функцию хеширования.

Answer 2

Эта функция очень полезна, когда вы хотите эффективно получить случайный элемент из файла .

Сvector, мы можем сгенерировать случайный индекс и получить случайные элементы с этим индексом за O (1). Однако это работает сunordered_map.

Вместо этого мы можем сгенерировать случайный индекс корзины и вызватьunordered_map::begin(index)чтобы получить случайное ведро за O(1). Затем мы можем сгенерировать случайный локальный индекс, т. е. индекс элементов в корзине, и перебрать элементы сlocal_iteratorчтобы получить случайный элемент (этот шаг НЕ O(1), однако обычно количество элементов в корзине невелико).

      unordered_map<int, int>::const_local_iterator random_element(const unordered_map<int, int> &m) {
    if (m.bucket_count() == 0)
        throw runtime_error("empty map");
    while (true) {
        auto bucket_index = gen_random_num() % m.bucket_count();
        auto bucket_size = m.bucket_size(bucket_index);
        if (bucket_size == 0)
            continue;
        auto element_index = gen_random_num() % bucket_size;
        return std::next(m.cbegin(bucket_index), element_index);
    }
}