Как эффективно перебирать std::(unordered)set при удалении из него элементов?

Вы хотите перебирать контейнер по кругу, пока не выполните полный проход, в котором вы ничего не удаляете.

template<class C, class F>
void multi_pass_erase( C& c, F&& f )
{
  auto stop_at = c.end();
  auto it = current;
  while (true)
  {
    if (c.empty())
      return;
    if (f(*it))
    {
      it = c.erase(it);
      if (it == c.begin())
        stop_at = c.end();
      else
        stop_at = it;
    }
    else
    {
      ++it;
      if (it == stop_at)
        return;
    }
    if (it == c.end())
      it = c.begin();
  }
}

В начале цикла он ссылается на следующий элемент для проверки и ссылается на конец только в том случае, если контейнер пуст.

Итак, если контейнер пуст, вернитесь.

stop_at отслеживает элемент, который, если мы до него дошли, то мы перебрали весь контейнер и не нашли что фильтровать.

Если мы что-то удаляем, мы замечаем, что нужно остановиться после стираемого элемента.

Если мы что-то не удаляем, мы продвигаем итератор и проверяем, стоит ли останавливаться.

Затем, если мы достигли конца контейнера, мы возвращаемся к началу.

Есть немного тщательной работы, когда мы проверяем «стоп», прежде чем перемещать его из конца назад в начало, поэтому мы никогда не должны хранить stop_at как ссылку на begin().

Теперь давайте сравним его с

while (true) {
  if (!std::erase_if ( set, test ))
    break;
}

Представьте, если каждый цикл удаляет один элемент. Это может потребовать O(n^2) времени.

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

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

Дополнительная сложность, вероятно, того не стоит.

Но можем ли мы написать что-то более сложное и эффективное?

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

Рассмотрите возможность отслеживания этой информации и просмотра только этих элементов, а не всего списка.

template<class C, class Test, class Dependencies>
void dependent_erase( C& c, Test&& t, Dependencies&& d ) {
  auto it = c.begin();
  using key_type = typename C::key_type;
  std::vector<key_type> todo_list;
  while (it != c.end())
  {
    if (t(*it)) {
      d( *it, &todo_list );
      it = c.erase(it);
    } else {
      ++it;
    }
  }
  // remove duplicates:
  std::vector<key_type> next_todo_list;
  while (!todo_list.empty()) {
    // better to shrink the list and ask f(x) less often
    std::sort(todo_list.begin(), todo_list.end());
    todo_list.erase( std::unique(todo_list.begin(), todo_list.end()), todo_list.end() );
    for (auto&& todo : todo_list) {
      auto it = c.find( todo );
      if (f(*it))
      {
        d( *it, &next_todo_list );
        c.erase(it);
      }
    }
    todo_list = std::move( next_todo_list );
    next_todo_list.clear();
  }
}

здесь у нас есть наш Test t (хотим ли мы удалить этот элемент?). Если мы это делаем, мы вызываем d( item, vector* ) и сохраняем все прямые зависимости, которые мы хотели бы повторно протестировать.

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

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

...

Код не тестировался и даже не компилировался. Но я делал это раньше, так что это может сработать. По крайней мере, это должно работать как псевдокод.

Если вы ожидаете МНОГО зависимостей для каждого удаленного узла и много совпадений, список задач на основе наборов может быть лучше, чем векторный. То есть, если у вас удалено N элементов, каждый из которых имеет M зависимостей, этот вектор вырастет до размера NM. Но если M имеет тенденцию быть небольшим и не сильно перекрываться другими элементами, тогда вектор будет намного быстрее, чем набор на основе узлов.

Используйте std::erase_if () в цикле:

while (std::erase_if (your_set, your_predcate))
    /**/;

Если у вас нет C++20, не отчаивайтесь. Cppreference.com также дает пример реализации.

Если это окажется узким местом, может быть полезно создать собственный all_erase_if () со специализацией для контейнеров на основе узлов:

template <class T>
constexpr bool has_node_type = requires { typename T::node_type; };
template <class T>
constexpr bool is_node_based = has_node_type<T>;

template <class C, class P>
auto all_erase_if (C& c, F f) requires is_node_based<C> {
    const auto old_size = std::size(c);
    if (!old_size)
        return old_size;
    auto it = std::begin(c), stop = std::begin(c);
    do {
        while (f(*it)) {
            it = stop = c.erase(it);
            if (it != std::end(c))
                /**/;
            else if (std::empty(c))
                return old_size;
            else
                it = stop = std::begin(c);
        }
        if (++it == std::end(c))
            it = std::begin(c);
    } while (it != stop);
    return old_size - std::size(c);
}

template <class C, class P>
auto all_erase_if (C& c, F f) requires !is_node_based<C> {
    const auto old_size = std::size(c);
    while (std::erase_if (c, std::ref(f)))
        /**/;
    return old_size - std::size(c);
}