Теперь удалить элементы, которые соответствуют предикату?

Question

У меня есть исходный контейнер строк. Я хочу удалить из исходного контейнера все строки, которые соответствуют предикату, и добавить их в целевой контейнер.

remove_copy_if и другие алгоритмы могут только переупорядочивать элементы в контейнере, и поэтому должны сопровождаться функцией-членом erase. Моя книга (Josuttis) говорит, что remove_copy_if возвращает итератор после последней позиции в контейнере назначения. Поэтому, если у меня есть только итератор в контейнере назначения, как я могу вызвать erase для исходного контейнера? Я попытался использовать размер места назначения, чтобы определить, как далеко от конца исходного контейнера удалить, но безуспешно. Я только придумал следующий код, но он делает два вызова (remove_if и remove_copy_if).

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

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

using namespace std;  

class CPred : public unary_function<string, bool>
{
public:
        CPred(const string& arString)
                :mString(arString)
        {
        }

        bool operator()(const string& arString) const
        {
                return (arString.find(mString) == std::string::npos);
        }
private:
        string mString;
};

int main()
{
        vector<string> Strings;
        vector<string> Container;

        Strings.push_back("123");
        Strings.push_back("145");
        Strings.push_back("ABC");
        Strings.push_back("167");
        Strings.push_back("DEF");

        cout << "Original list" << endl;
        copy(Strings.begin(), Strings.end(),ostream_iterator<string>(cout,"\n"));

        CPred Pred("1");

        remove_copy_if(Strings.begin(), Strings.end(),
                       back_inserter(Container),
                       Pred);

        Strings.erase(remove_if(Strings.begin(), Strings.end(),
                      not1(Pred)), Strings.end());

        cout << "Elements beginning with 1 removed" << endl;
        copy(Strings.begin(), Strings.end(),ostream_iterator<string>(cout,"\n"));

        cout << "Elements beginning with 1" << endl;
        copy(Container.begin(), Container.end(),ostream_iterator<string>(cout,"\n"));

        return 0;
}

Answer 1

При всем уважении к тяжелой работе Фреда позвольте мне добавить следующее: move_if ничем не отличается от remove_copy_if на абстрактном уровне. Единственное изменение уровня реализации - итератор end(). Вы все еще не получаете erase(). Принятый ответ не erase() соответствующих элементов - часть постановки задачи ОП.

Что касается вопроса ОП: то, что вы хотите - это соединение на месте. Это возможно для списков. Однако с vectors это не будет работать. Читайте о том, когда и как и почему итераторы признаны недействительными. Вам нужно будет использовать алгоритм двух проходов.

remove_copy_if и другие алгоритмы могут только переупорядочивать элементы в контейнере,

Из документации SGI по remove_copy_if:

Эта операция стабильна, это означает, что относительный порядок копируемых элементов такой же, как в диапазоне [first, last).

Так что никакого относительного переупорядочения не происходит. Более того, это копия, которая означает, что элементы из Source vector в вашем случае копируются в Container vector.

как я могу вызвать стирание в исходном контейнере?

Вам нужно использовать другой алгоритм, который называется remove_if:

remove_if удаляет из диапазона [first, last) каждый элемент x, так что pred(x) имеет значение true. То есть remove_if возвращает итератор new_last, так что диапазон [first, new_last) не содержит элементов, для которых pred имеет значение true. Все итераторы в диапазоне [new_last, last) все еще разыменовываются, но элементы, на которые они указывают, не определены. Remove_if стабильно, это означает, что относительный порядок элементов, которые не удалены, не изменяется.

Итак, просто измените этот remove_copy_if вызов на:

vector<string>::iterator new_last = remove_if(Strings.begin(), 
                                              Strings.end(), 
                                              Pred);

и все готово. Просто имейте в виду, ваш диапазон Strings vector больше не определяется итераторами [first(), end()), а [first(), new_last).

Вы можете, если хотите, удалить оставшиеся [new_last, end()) следующим образом:

Strings.erase(new_last, Strings.end());

Теперь ваши vector сокращены, а end() и new_last одинаковы (один за последним элементом), поэтому вы можете использовать как всегда:

copy(Strings.begin(), Strings.end(), ostream_iterator(cout, "\"));

чтобы получить распечатку строк на вашей консоли (stdout).

Answer 2

Я понимаю, что вы хотели бы избежать двух проходов над вашим исходным контейнером. К сожалению, я не верю, что есть стандартный алгоритм, который сделает это. Можно было бы создать свой собственный алгоритм, который бы копировал элементы в новый контейнер и удалял из исходного контейнера (в том же смысле, что и remove_if; после этого вам нужно было бы удалить) за один проход. Требования к размеру контейнера и производительности будут определять, будет ли лучше создание такого алгоритма, чем два прохода.

Редактировать: я придумал быструю реализацию:

template<typename F_ITER, typename O_ITER, typename FTOR>
F_ITER move_if(F_ITER begin, F_ITER end, O_ITER dest, FTOR match)
{
  F_ITER result = begin;
  for(; begin != end; ++begin)
  {
    if (match(*begin))
    {
      *dest++ = *begin;
    }
    else
    {
      *result++ = *begin;
    }
  }

  return result;
}

Edit: Может быть, есть путаница в том, что подразумевается под «пасс». В решении OP есть вызов remove_copy_if () и вызов remove_if (). Каждый из них будет проходить через весь оригинальный контейнер. Тогда есть вызов, чтобы стереть (). Это будет проходить через все элементы, которые были удалены из исходного контейнера.

Если мой алгоритм используется для копирования удаленных элементов в новый контейнер (с использованием begin () оригинальный контейнер для выходного итератора не будет работать, как это было продемонстрировано), он выполнит один проход, скопировав удаленные элементы в новый контейнер с помощью back_inserter или некоторого такого механизма. Стирание все равно потребуется, как и в случае с remove_if (). Один проход по оригинальному контейнеру исключен, что, как я полагаю, и было после ОП.

Answer 3

Там будут copy_if и remove_if.

copy_if( Strings.begin(), Strings.end(), 
         back_inserter(Container), not1(Pred) );
Strings.erase( remove_if( Strings.begin(), Strings.end(), not1(Pred) ), 
               Strings.end() );

Лучше понять код, в котором класс Predicate отвечает "true", если что-то присутствует. В этом случае вам не понадобится not1 два раза.

Поскольку std :: find ищет подстроку не обязательно с самого начала, вам нужно изменить «начиная с 1» на «с 1», чтобы избежать недопонимания вашего кода в будущем.

Answer 4

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

#include "stdafx.h"

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

using namespace std;

class CPred : public unary_function<string, bool>
{
public:
        CPred(const string& arString)
                :mString(arString)
        {
        }

        bool operator()(const string& arString) const
        {
                return (arString.find(mString) == std::string::npos);
        }
private:
        string mString;
};

int main()
{
        vector<string> Strings;

        Strings.push_back("213");
        Strings.push_back("145");
        Strings.push_back("ABC");
        Strings.push_back("167");
        Strings.push_back("DEF");

        cout << "Original list" << endl;
        copy(Strings.begin(), Strings.end(),ostream_iterator<string>(cout,"\n"));

        CPred Pred("1");

        vector<string>::iterator end1 = 
        partition(Strings.begin(), Strings.end(), Pred);

        cout << "Elements matching with 1" << endl;
        copy(end1, Strings.end(), ostream_iterator<string>(cout,"\n"));

        cout << "Elements not matching with 1" << endl;
        copy(Strings.begin(), end1, ostream_iterator<string>(cout,"\n"));

        return 0;
}

Answer 5

1. Вся причина, по которой алгоритмы remove_ * не стирают элементы, состоит в том, что невозможно "удалить" элемент одним итератором. Вы не можете получить контейнер итератором Этот момент более подробно объясняется в книге «Эффективный STL»

2. Используйте «copy_if», затем «remove_if». remove_copy_if не изменяет источник.

3. В списках вы можете сделать лучше - переупорядочение с последующим соединением.

Answer 6

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

source.erase(source.remove(source.begin(), source.end(), element), source.end());

remove_if () делает то же самое, но с предикатом.

source.erase(source.remove_if(source.begin(), source.end(), predicate), source.end());

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

// target must be of a size ready to accomodate the copy
target.erase(source.remove_copy_if(source.begin(), source.end(), target.begin(), predicate), target.end());