Стирание объектов из списка STL

Списки 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;
    }
}

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

Решение 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 итератор указывает на это положение, когда алгоритм заканчивается, в то время как во втором решении это - итератор, возвращенный [1 112], который указывает на это положение. Я мог возвратить пару итераторов, но ради создания вещей, простых, я просто возвращаю один из итераторов.

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

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

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

Указание, которое раздел () дает Вам достаточно для различения соответствующих объектов от не соответствия. (список:: соединение встык () является дешевым однако)

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

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

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