Стирание предметов из списка STL

Question

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

Этот код не подходит для этого. Скорее всего, итератор будет признан недействительным функцией erase () и вызовет проблему:

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end(); it++)
{
  if(myCondition(*it))
  {
    myOtherList.push_back(*it);
    myList.erase(it);
  }
}

Так кто-нибудь может предложить лучший способ сделать это?

Answer 1

Erase возвращает итератор , указывающий на элемент после стертого:

std::list<MyClass>::iterator it = myList.begin();
while (it != myList.end())
{
  if(myCondition(*it))
  {
    myOtherList.push_back(*it);
    it = myList.erase(it);
  }
  else
  {
    ++it;
  }
}

Answer 2

STL-списки имеют интересную особенность: метод splice() позволяет вам разрушительным образом перемещать элементы из одного списка в другой.

splice() работает в постоянном времени и не копирует элементы и не выполняет каких-либо бесплатных распределений / освобождений магазина. Обратите внимание, что оба списка должны быть одного типа, и они должны быть отдельными экземплярами списка (а не двумя ссылками на один и тот же список).

Вот пример того, как вы можете использовать splice():

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end(); ) {
    if(myCondition(*it)) {
        std::list<MyClass>::iterator oldIt = it++;
        myOtherList.splice(myOtherList.end(), myList, oldIt);
    } else {
        ++it;
    }
}

Answer 3

Раствор 1

template<typename Fwd, typename Out, typename Operation>
Fwd move_if(Fwd first, Fwd last, Out result, Operation op)
{
    Fwd swap_pos = first;
    for( ; first != last; ++first ) {
        if( !op(*first) ) *swap_pos++ = *first;
        else *result++ = *first;
    }
    return swap_pos;
}

Идея проста. Что вы хотите сделать, это удалить элементы из одного контейнера и поместить их в другой, если предикат верен. Итак, возьмите код алгоритма std::remove(), который уже выполняет удаление, и адаптируйте его к вашим дополнительным потребностям. В приведенном выше коде я добавил строку else для копирования элемента, когда предикат имеет значение true.

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

Решение 2

template<typename Bidi, typename Out, typename Operation>
Bidi move_if(Bidi first, Bidi last, Out result, Operation op)
{
    Bidi new_end = partition(first, last, not1(op));
    copy(new_end, last, result);
    return new_end;
}

Второй подход использует STL для реализации алгоритма. Лично я нахожу его более читабельным, чем первое решение, но у него есть два недостатка: во-первых, он требует более мощных двунаправленных итераторов для контейнера ввода, а не прямых итераторов, которые мы использовали в первом решении. Во-вторых, и это может или не может быть проблемой для вас, контейнеры не гарантированно имеют тот же порядок, что и до вызова std::partition(). Если вы хотите сохранить порядок, замените этот вызов на std::stable_partition(). std::stable_partition() может быть немного медленнее, но имеет ту же сложность во время выполнения, что и std::partition().

Любой путь: вызов функции

list<int>::iterator p = move_if(l1.begin(), l1.end(),
                                back_inserter(l2),
                                bind2nd(less<int>(), 3));

Заключительные замечания

При написании кода я столкнулся с дилеммой: что должен возвращать алгоритм move_if()? С одной стороны, алгоритм должен возвращать итератор, указывающий на новую конечную позицию входного контейнера, чтобы вызывающий мог использовать идиому удаления-удаления, чтобы уменьшить контейнер. Но с другой стороны, алгоритм должен возвращать позицию конца контейнера результата, потому что в противном случае вызывающий может найти его дорого. В первом решении итератор result указывает на эту позицию, когда алгоритм заканчивается, тогда как во втором решении именно итератор, возвращаемый std::copy(), указывает на эту позицию. Я мог бы вернуть пару итераторов, но для простоты я просто вернул один из итераторов.

Answer 4

std::list<MyClass>::iterator endMatching =
    partition(myList.begin(), myList.end(), myCondition);
myOtherList.splice(myOtherList.begin(), myList, endMatching, myList.end());

Обратите внимание, что partition () дает вам достаточно, чтобы отличить совпадающие объекты от несоответствующих. (list :: splice (), однако, дешев)

См. Следующий код на конкретный случай, вдохновленный Теперь, чтобы удалить элементы, которые соответствуют предикату?

#include <iostream>
#include <iterator>
#include <list>
#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()
{
        list<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");

        // Linear. Exactly last - first applications of pred, and at most (last - first)/2 swaps. 
        list<string>::iterator end1 =
        partition(Strings.begin(), Strings.end(), Pred);

        list<string> NotMatching;

        // This function is constant time. 
        NotMatching.splice(NotMatching.begin(),Strings, Strings.begin(), end1); 

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

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

        return 0;
}

Answer 5

template <typename ForwardIterator, typename OutputIterator, typename Predicate>
void splice_if(ForwardIterator begin, ForwardIterator end, OutputIterator out, Predicate pred)
{
    ForwardIterator it = begin;
    while( it != end )
    {
        if( pred(*it) )
        {
            *begin++ = *out++ = *it;
        }
        ++it;
    }
    return begin;
}

myList.erase( 
    splice_if( myList.begin(), myList.end(), back_inserter(myOutputList),
        myCondition
    ),
    myList.end()
)

Answer 6

Еще одна попытка:

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end; ) {
    std::list<MyClass>::iterator eraseiter = it;
    ++it;
    if(myCondition(*eraseiter)) {
        myOtherList.push_back(*eraseiter);
        myList.erase(eraseiter);
    }
}