Одновременно повторяя и изменяя неупорядоченный_set?

Рассмотрим следующий код:

unordered_set<T> S = ...;

for (const auto& x : S)
   if (...)
       S.insert(...);

Это неверно? Если мы вставляем что-то в S, итераторы могут быть недействительными (из-за переименования), что приведет к поломке диапазона, потому что под капотом используется S.begin... S.end.

Есть ли какой-нибудь шаблон, чтобы справиться с этим?

Один из способов:

unordered_set<T> S = ...;

vector<T> S2;

for (const auto& x : S)
   if (...)
       S2.emplace_back(...);

for (auto& x : S2)
    S.insert(move(x));

Это кажется неуклюжим. Есть ли лучший способ, которым я не хватает?

(В частности, если я использовал ручную таблицу хэша, и я мог бы заблокировать ее от повторного воспроизведения до конца цикла, было бы безопасно использовать первую версию.)

Update:

Из http://en.cppreference.com/w/cpp/container/unordered_map/insert

Если повторная запись происходит из-за вставки, все итераторы становятся недействительными. В противном случае итераторы не будут затронуты. Ссылки не являются недействительными. Повторное воспроизведение происходит только в том случае, если новое число элементов больше, чем max_load_factor() * bucket_count().

Не могли бы вы каким-то образом возиться с max_load_factor, чтобы не перефразировать?

Ответы

Ответ 1

Не могли бы вы каким-то образом испортить max_load_factor, чтобы предотвратить повторное использование?

Да, вы можете установить max_load_factor() на бесконечность, чтобы не было никакой перезагрузки:

#include <iostream>
#include <limits>
#include <unordered_set>

int main()
{
    // initialize
    std::unordered_set<int> S;

    for (int i = 0; i < 8; ++i)
        S.insert(i);

    std::cout << "buckets: " << S.bucket_count() << std::endl;

    // infinite max load factor => never need to rehash
    const auto oldLoadFactor = S.max_load_factor();
    S.max_load_factor(std::numeric_limits<float>::infinity());

    for (const auto& x : S)
    {
        if (x > 2)
            S.insert(x * 2);
    }

    // restore load factor, verify same bucket count
    S.max_load_factor(oldLoadFactor);
    std::cout << "buckets: " << S.bucket_count() << std::endl;

    // now force rehash
    S.rehash(0);
    std::cout << "buckets: " << S.bucket_count() << std::endl;
}

Обратите внимание, что просто установка нового коэффициента загрузки не требует повторной перемотки, поэтому это дешевые операции.

Бит rehash(0) работает, потому что это запрос: 1) я получаю по крайней мере n ведер, а 2) у меня достаточно ведра, чтобы удовлетворить мой max_load_factor(). Мы просто используем ноль, чтобы указать, что мы не заботимся о минимальной сумме, мы просто хотим перефразировать, чтобы удовлетворить наш "новый" фактор, как если бы он никогда не менялся до бесконечности.

Конечно, это не исключение; если что-то между звонками на max_load_factor(), наш старый фактор потерян навсегда. Легко фиксируется с помощью вашей любимой утилиты для защиты области видимости или класса утилиты.

Обратите внимание, что вы не получаете никаких гарантий, если вы будете перебирать новые элементы. Вы будете перебирать существующие элементы, но можете или не будете перебирать новые элементы. Если это нормально (что в нашем чате должно быть), тогда это будет работать.

Например, рассмотрим, как вы перебираете неупорядоченный набор целых чисел и для каждого четного целого x, вставьте x * 2. Если они всегда вставлены сразу после вашей текущей позиции (случайно из-за детализации реализации и состояния контейнера), вы никогда не прекратите цикл, за исключением исключений.

Если вам понадобятся некоторые гарантии, вам необходимо использовать альтернативное решение для хранения.

Ответ 2

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

Даже если бы это работало, между прочим, была двусмысленность: должны ли повторные и вновь вставленные члены повторяться или нет? Можно ли включать их в эту итерацию только иногда (т.е. Только если они заканчиваются после текущего итератора)?

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

Ответ 3

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

std::vector<T> tmp;
std::copy_if(S.begin(), S.end(), std::back_inserter(tmp),
             [](T const& value) { return ...; });
S.insert(std::make_move_iterator(tmp.begin()),
         std::make_move_iterator(tmp.end()));