Erasing items from an STL list

Question

I want to make a function which moves items from one STL list to another if they match a certain condition.

This code is not the way to do it. The iterator will most likely be invalidated by the erase() function and cause a problem:

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

So can anyone suggest a better way to do this ?

Answer 1

Another attempt:

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

Answer 2

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 3

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

The idea is simple. What you want to do is remove elements from one container and place them in another if a predicate is true. So take the code of the std::remove() algorithm, which already does the remove part, and adapt it to your extra needs. In the code above I added the else line to copy the element when the predicate is true.

Notice that because we use the std::remove() code, the algorithm doesn't actually shrink the input container. It does return the updated end iterator of the input container though, so you can just use that and disregard the extra elements. Use the erase-remove idiom if you really want to shrink the input container.

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

The second approach uses the STL to implement the algorithm. I personally find it more readable than the first solution, but it has two drawbacks: First, it requires the more-powerful bidirectional iterators for the input container, rather than the forward iterators we used in the first solution. Second, and this is may or may not be an issue for you, the containers are not guaranteed to have the same ordering as before the call to std::partition(). If you wish to maintain the ordering, replace that call with a call to std::stable_partition(). std::stable_partition() might be slightly slower, but it has the same runtime complexity as std::partition().

Either Way: Calling the Function

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

Final Remarks

While writing the code I encountered a dilemma: what should the move_if() algorithm return? On the one hand the algorithm should return an iterator pointing to the new end position of the input container, so the caller can use the erase-remove idiom to shrink the container. But on the other hand the algorithm should return the position of the end of the result container, because otherwise it could be expensive for the caller to find it. In the first solution the result iterator points to this position when the algorithm ends, while in the second solution it is the iterator returned by std::copy() that points to this position. I could return a pair of iterators, but for the sake of making things simple I just return one of the iterators.

Answer 4

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

Note that partition() gives you enough to discriminate matching objects from non matching ones. (list::splice() is cheap however)

See the following code on a concrete case inspired from Now to remove elements that match a predicate?

#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

Erase returns an iterator pointing to the element after the erased one:

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 6

STL lists have an interesting feature: the splice() method lets you destructively move elements from one list to another.

splice() operates in constant time, and doesn't copy the elements or perform any free store allocations/deallocations. Note that both lists must be of the same type, and they must be separate list instances (not two references to the same list).

Here's an example of how you could use 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;
    }
}