Удаление элементов из списка STL

Ответ 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;
  }
}

Ответ 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;
    }
}

Ответ 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, чтобы скопировать элемент, когда предикат является истинным.

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

Решение 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(), который указывает на эту позицию. Я мог бы вернуть пару итераторов, но для упрощения дела я просто возвращаю один из итераторов.

Ответ 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;
}

Ответ 5

Другая попытка:

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);
    }
}

Ответ 6

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()
)