CODEWITHSUNDEEP
c++algorithm
thinkdeep
thinkdeep

Reputation: 1033

Algorithm for removing elements

I understand there is erase-remove idiom for c++. And the remove method under <algorithm> will move target elements to the back of the range.

However, the output below is confusing to me. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {10, 20, 30, 20, 30, 20, 10, 10, 20};

    auto pend = remove(vec.begin(), vec.end(), 20);
    cout << "After removing 20: " << endl;
    for (const auto& x : vec) {
        cout << x << " ";
    }
    cout << endl;

    cout << "use pend: " << endl;
    for (auto p = vec.begin(); p != pend; p++) {
        cout << " " << *p;
    }

    cout << endl;
    return 0;
}

The output is:

After removing 20:
10 30 30 10 10 20 10 10 20
use pend:
10 30 30 10 10

There are two questions here:

  1. For "After removing 20", why are there 10 mixed with 20 at the back? 10 30 30 10 10 20 10 10 20

  2. For "use pend:", why does it fail to print the last two more 10's? There are five 10's in the original vector, and 10's are not supposed to be removed?

From the library, remove() method returns the iterator pend

template ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val); An iterator to the element that follows the last element not removed. The range between first and this iterator includes all the elements in the sequence that do not compare equal to val.

Upvotes: 4

Views: 855

Answers (2)

Paul Floyd
Paul Floyd

Reputation: 6906

In C++ this is called the erase-remove idiom. From the Wikipedia page:

The erase–remove idiom is a common C++ technique to eliminate elements that fulfill a certain criterion from a C++ Standard Library container.

See also Scott Meyers Effective C++ books.

Upvotes: 2

rom1v
rom1v

Reputation: 2969

From the array:

10 20 30 20 30 20 10 10 20

When you remove all 20, you expect to get:

10 30 30 10 10

But std::remove just shifts the items, it lets the remaining values unspecified:

Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values

So you get:

10 30 30 10 10 xx xx xx xx
               ^
               pend

Which explains your results.

If you need to erase the items, call vec.erase(pend, vec.end()):

A call to remove is typically followed by a call to a container's erase method, which erases the unspecified values and reduces the physical size of the container to match its new logical size.

Upvotes: 14

Related Questions