Почему я не могу удалить строку из std :: set с помощью std :: remove_if?

Возможный дубликат:
remove_if для std :: map

У меня есть набор строк:

set <wstring> strings;
// ...

Я хочу удалить строки в соответствии с предикатом, например:

std::remove_if ( strings.begin(), strings.end(), []( const wstring &s ) -> bool { return s == L"matching"; });

Когда я пытаюсь это сделать, я получаю следующую ошибку компилятора:

c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(1840): error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>'

Похоже, что ошибка указывает на то, что std::string не имеет конструктора копирования по-значению (что было бы незаконным). Как-то плохо использовать std::remove_if с std::set? Должен ли я делать что-то другое, например, несколько итераций set::find() за которыми следует set::erase()?

Ответ 1

std::remove_if (или std::erase) работает переназначение значения членов ряда. Он не понимает, как std::set организует данные или как удалить узел из своей внутренней структуры данных дерева. В самом деле, это невозможно сделать, используя только ссылки на узлы, не имея самого set объекта.

Стандартные алгоритмы предназначены для обеспечения прозрачных (или, по крайней мере, последовательно запоминаемых) вычислительных сложностей. Функция выборочного удаления элементов из set будет O (N log N) из-за необходимости перебалансировать дерево, которое не лучше, чем цикл, вызывающий my_set.remove(). Таким образом, стандарт не предоставляет этого, и это то, что вам нужно написать.

С другой стороны, наивно ручной код для удаления элементов из vector один за другим будет O (N ^ 2), тогда как std::remove_if - O (N). Таким образом, библиотека действительно дает ощутимую выгоду в этом случае.

Типичный цикл (стиль С++ 03):

for ( set_t::iterator i = my_set.begin(); i != my_set.end(); ) {
    if ( condition ) {
        my_set.erase( i ++ ); // strict C++03
        // i = my_set.erase( i ); // more modern, typically accepted as C++03
    } else {
        ++ i; // do not include ++ i inside for ( )
    }
}

Редактировать (4 года спустя!): i ++ выглядит подозрительно. Что, если erase аннулирует i до того, как оператор post-increment сможет его обновить? Это прекрасно, хотя, потому что это перегруженный operator++ а не встроенный оператор. Функция безопасно обновляет i на месте, а затем возвращает копию исходного значения.

Ответ 2

В сообщении об ошибке

оператор не найден, который принимает левый операнд типа ' const std :: basic_string <_Elem, _Traits, _Ax>'

Обратите внимание на константу. Компилятор прав, что std::wstring не имеет operator= который можно вызвать в const-объекте.

Почему строка const? Ответ заключается в том, что значения в std::set неизменяемы, потому что значения в наборе упорядочены, а изменение значения может изменить его упорядочение в наборе, аннулируя набор.

Почему компилятор пытается скопировать значение набора?

std::remove_if (и std::remove) на самом деле ничего не стереть (и не могут, потому что у них нет контейнера, только итераторы). То, что они делают, это скопировать все значения в диапазоне, которые не соответствуют критерию в начале диапазона, и вернуть итератор в следующий элемент после соответствующих элементов. Затем вы должны вручную удалить из возвращенного итератора в конец диапазона. Поскольку набор сохраняет свои элементы в порядке, было бы неправильно перемещать любые элементы вокруг, поэтому remove_if нельзя использовать в наборе (или в любом другом ассоциативном контейнере).

Короче говоря, вам нужно использовать цикл std::find_if и set::erase std::find_if, например:

template<class V, class P>
void erase_if(std::set<V>& s, P p)
{
  std::set<V>::iterator e = s.begin();
  for (;;)
  {
    e = std::find_if(e, s.end(), p);
    if (e == s.end())
      break;
    e = s.erase(e);
  }
}