Как эффективно удалить ключ из std :: unordered_set, если ключ отсутствует в std :: map?

Question

У меня есть std::map и std::unordered_set с одним и тем же ключом.

Я хочу удалить все ключи из набора, которых нет на карте.

Моя идеядолжен был сделать что-то вроде следующего:

#include <map>
#include <unordered_set>

int main()
{
    std::map<uint64_t, std::string> myMap = { 
                                                {1, "foo"},
                                                {2, "bar"},
                                                {3, "morefoo"},
                                                {4, "morebar"} 
                                            };

    std::unordered_set<uint64_t> mySet = { 1, 2, 3, 4, 123 };

    for (const auto key : mySet)
    {
        const auto mapIterator = myMap.find(key);

        if (myMap.end() == mapIterator)
            mySet.erase(key);
    }

    return 0;
}

и затем вызывать его при обратном вызове таймера каждые несколько секунд, однако приведенный выше фрагмент кода выдает утверждение при попытке удалить ключ 123 из mySet, заявив:

Итератор списка не может быть увеличен.

Дело в том, что даже если это не исключение, я чувствую, что эта идея далека от элегантной / оптимальной.Мне интересно, есть ли лучший способ решить эту проблему?

Спасибо.

Answer 1

Как указано в ответах на этот вопрос Как удалить из карты при ее повторении? вы не можете стирать элементы в контейнере, когда перебираете его в цикле for, поэтому ваш код должен использовать итератор.Так как такой ответ уже предоставлен, я бы не стал его дублировать.

Для эффективности у вас совершенно неправильный подход - вы выполняете поиск в std::map, повторяя итерацию std::unordered_set, которая должна быть противоположной, поскольку std::unorederd_set обеспечивает быстреевремя поиска (иначе нет смысла использовать его вместо std::set).Одним из возможных подходов является создание копии:

auto copySet = mySet;
for( const auto &p : myMap )
    copySet.erase( p.first );
for( const auto v : copySet )
    mySet.erase( v );

, которая может быть более эффективной, но это зависит от ваших данных.Лучший подход к выбору правильных типов данных для ваших контейнеров.

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

Answer 2

Как указано в комментариях

for (const auto key : mySet)
{
    const auto mapIterator = myMap.find(key);

    if (myMap.end() == mapIterator)
        mySet.erase(key);
}

будет иметь неопределенное поведение.Когда вы удаляете элемент 123 из mySet, вы лишаете законной силы итератор, который использует диапазон, основанный на цикле.увеличение этого итератора после этого не допускается.Что вы можете сделать, так это переключиться на обычный цикл for, чтобы вы могли контролировать, когда увеличивается итератор, например

for (auto it = mySet.begin(); it != mySet.end();)
{
    if (myMap.find(*it) == myMap.end())
        it = mySet.erase(it);
    else
        ++it;
}

, и теперь у вас всегда есть действительный итератор, так как erase вернет следующий действительный итератор.