Почему не удаляет std:: remove_copy_if()?

Может ли это быть наихудшей названной функцией в STL? (риторический вопрос)

std:: remove_copy_if() фактически не выполняет никакого удаления. Насколько я могу судить, он больше похож на copy_if_not.

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

Если нет, существует ли алгоритм STL для условного удаления (перемещения?) элементов из контейнера и помещения их в другой контейнер?

Редактирование, чтобы добавить пример, чтобы читатели были менее запутаны.

Появится следующая программа, оставляющая входной диапазон (V1) нетронутой:

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

using std::cout;
using std::endl;

int main (void)
{
    std::vector<int> V1, V2;
    V1.push_back(-2);
    V1.push_back(0);
    V1.push_back(-1);
    V1.push_back(0);
    V1.push_back(1);
    V1.push_back(2);

    std::copy(V1.begin(), V1.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;

    std::remove_copy_if(
        V1.begin(),
        V1.end(),
        std::back_inserter(V2),
        std::bind2nd(std::less<int>(), 0));

    std::copy(V2.begin(), V2.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
    std::copy(V1.begin(), V1.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
}

Он выводит:

-2 0 -1 0 1 2 
0 0 1 2 
-2 0 -1 0 1 2

Я ожидал увидеть что-то вроде:

-2 0 -1 0 1 2 
0 0 1 2 
0 0 1 2 ? ? ?

Где? может быть любой ценностью. Но я был удивлен, увидев, что диапазон ввода не затронут, и что возвращаемое значение не может использоваться (в данном случае) std::vector:: erase(). (Возвращаемое значение является выходным итератором.)

Ответы

Ответ 1

Может ли это быть наихудшей названной функцией в STL?

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

Это разделение имеет приятную особенность, что вы можете применять алгоритмы к диапазонам элементов, которые не принадлежат контейнеру (рассмотрите адаптеры итератора, такие как std::istream_iterator или std::ostream_iterator), или что, принадлежащие контейнеру, не учитывают все элементы (std::sort( v.begin(), v.begin()+v.size()/2 ), чтобы сократить первую половину контейнера).

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

v.erase( std::remove_if( v.begin(), v.end(), pred ),
         v.end() );

Кроме того, для мутирующих алгоритмов (тех, которые выполняют изменения), например, std::remove, существует не мутирующая версия с именем, добавив copy к имени: std::remove_copy_if. Считается, что ни один из алгоритмов XXXcopyYYY не изменяет входную последовательность (хотя они могут, если вы используете итераторы сглаживания).

В то время как это действительно не является оправданием для именования std::remove_copy_if, я надеюсь, что это поможет понять, что алгоритм дал свое имя: remove_if изменит содержимое диапазона и даст диапазон, для которого все элементы, которые соответствуют предикат был удален (возвращаемый диапазон - это тот, который формируется первым аргументом алгоритма возвращенному итератору). std::remove_copy_if делает то же самое, но вместо того, чтобы модифицировать базовую последовательность, он создает копию последовательности, в которой те элементы, которые соответствуют предикату, были удалены. То есть все алгоритмы * copy * эквивалентны копированию, а затем применяются исходный алгоритм (обратите внимание, что эквивалентность логична, std::remove_copy_if требует только OutputIterator, что означает, что он не может копировать, а затем пройти скопированный диапазон, применяя std::remove_if.

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

Если нет, существует ли алгоритм STL для условного удаления (перемещения?) элементов из контейнера и помещения их в другой контейнер?

В STL нет такого алгоритма, но его можно легко реализовать:

template <typename FIterator, typename OIterator, typename Pred>
FIterator splice_if( FIterator first, FIterator last, OIterator out, Pred p )
{
   FIterator result = first;
   for ( ; first != last; ++first ) {
      if ( p( *first ) ) {
         *result++ = *first;
      } else {
         *out++ = *first;
      }
   }
   return result;
}

Ответ 2

существует ли алгоритм STL для условного удаления (перемещения?) элементов из контейнера и помещения их в другой контейнер?

Ближайшая вещь, о которой я могу думать, - std::stable_partition:

std::vector<int> v;
// ...
auto it = std::stable_partition(v.begin(), v.end(), pick_the_good_elements);
std::vector<int> w(std::make_move_iter(it), std::make_move_iter(v.end()));
v.erase(it, v.end());

Теперь v будет содержать "хорошие" элементы, а w будет содержать "плохие" элементы.

Ответ 3

Если нет, существует ли алгоритм STL для условного удаления (перемещения?) элементов из контейнера и помещения их в другой контейнер?

Не совсем. Идея состоит в том, что модифицирующим алгоритмам разрешено "перемещать" (не в смысле С++ смысл слова) элементы в контейнере, но не могут изменить длину контейнера. Таким образом, алгоритмы remove можно было бы назвать prepare_for_removal.

Кстати, С++ 11 обеспечивает std:: copy_if, что позволяет копировать выбранные элементы из одного контейнера в другой без воспроизведения смешные логические игры с remove_copy_if.

Ответ 4

Вы правы, это то, что он делает... std:: remove_copy_if копирует вектор, удаляя все, что соответствует pred.

std:: remove_if... удаляет условие (или, скорее, перемещает вещи вокруг).

Ответ 5

Я согласен, что remove не лучшее имя для этого семейства функций.

Но поскольку Люк сказал, есть причина, по которой он работает так, как это делает, и элемент GoTW, который он упоминает, объясняет, как он работает. remove_if работает точно так же, как и удаление - что и следовало ожидать.

Вы также можете прочитать эту статью статью Wikibooks.