Вопрос по algorithm, remove-if, c++, set – Почему я не могу удалить строку из std :: set с помощью std :: remove_if? [Дубликат]

10

Possible Duplicate:
remove_if equivalent for 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() ?

Ваш простой образец может быть замененstrings.erase(L"matching");, Предполагается, что вашactual предикат не является тривиальным. Robᵩ
@ Rob & # x1D69; Да, это был только пример, мне нужен объект функции. Benj

Ваш Ответ

2   ответа
20

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). Таким образом, библиотека обеспечивает ощутимую выгоду в этом случае.

Типичный цикл (стиль C ++ 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 прежде чем оператор постинкрементного может его обновить? Это хорошо, хотя, потому что это перегруженоoperator++ а не встроенный оператор. Функция безопасно обновляетi на месте иthen возвращает копию своего первоначального значения.

remove_if должен быть названshuffle_to_the_front_unlessтогда было бы легко увидеть, что он, возможно, не может использоваться в наборе, и что он не вносит структурные изменения в любой контейнер, над которым он был использован. Что, как вы говорите, итераторы никогда не делают.
@ Rook Существует такое понятие, но оно не является исправлением. Проблема в том, чтоstd::remove_if определяется как O (N), и реализация, которая не является O (N), не может быть вызванаstd::remove_if по букве закона. Вы можете предоставить свою собственную реализацию в собственном пространстве имен. Перегрузка будет конфликтовать сstd, хоть. Вам лучше просто написать цикл.
@Rook: в этом случае проблема не в итераторе, а вvalue_type контейнера.std::remove_if modifies значения через разыменование итератора, ноvalue_type вstd::set постоянный объект
Ах, я небрежно предположил, что итератор возвращает постоянную ссылку. Наличие типа значения, являющегося постоянным, довольно очевидно в ретроспективе.
Интересно, почему они не обобщают понятие «назначаемого итератора»? (из-за отсутствия лучшего термина), учитывая, что есть несколько контейнеров, которые демонстрируют это поведение.
9

Сообщение об ошибке говорит

no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>'

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

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

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

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

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

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);
  }
}
@ Бенджамин Линдли Хорошо, изменился.
Упсend() узел, а не корень, но вы поняли.
На самом деле библиотека могла бы предоставитьstd::remove_if совместим сstd::set, используя специальные знания о том, что корневой узел действительно живет внутри объекта контейнера. Тем не менее, он не будет соответствовать требованию времени выполнения O (N).
+1, вы очень хорошо изложили аргументацию и предоставили хорошую альтернативу, но я бы назвал эту функциюerase_if.
@Potatoswatter Это также будет противоречивым - его поведение будет очень отличаться отremove_if на других контейнерах.

Похожие вопросы