Difference between erase and remove

I am bit confused about the difference between the usage of std::remove algorithm. Specifically I am not able to understand what is being removed when I use this algorithm. I wrote a small test code like this:

std::vector<int> a;
a.push_back(1);
a.push_back(2);

std::remove(a.begin(), a.end(), 1);


int s = a.size();

std::vector<int>::iterator iter = a.begin();
std::vector<int>::iterator endIter = a.end();

std::cout<<"Using iter...\n";
for(; iter != endIter; ++iter)
{
    std::cout<<*iter<<"\n";
}

std::cout<<"Using size...\n";
for(int i = 0; i < a.size(); ++i)
{
    std::cout<<a[i]<<"\n";
}

The output was 2,2 in both the cases.

However, if I use erase with the remove something like this:

a.erase(std::remove(a.begin(), a.end(), 1), a.end());

I get the output as 2.

So my questions are:

(1). Is there any use of std::remove other than using it with erase function.

(2). Even after doing std::remove, why a.size() returns 2 and not 1?

I read the item in Scott Meyer's Effective STL book about the erase-remove idiom. But am still having this confusion.

Solution 1:

remove() doesn't actually delete elements from the container -- it only shunts non-deleted elements forwards on top of deleted elements. The key is to realise that remove() is designed to work on not just a container but on any arbitrary forward iterator pair: that means it can't actually delete the elements, because an arbitrary iterator pair doesn't necessarily have the ability to delete elements.

For example, pointers to the beginning and end of a regular C array are forward iterators and as such can be used with remove():

int foo[100];

...

remove(foo, foo + 100, 42);    // Remove all elements equal to 42

Here it's obvious that remove() cannot resize the array!

Solution 2:

What does std::remove do?

Here's pseudo code of std::remove. Take few seconds to see what it's doing and then read the explanation.

Iter remove(Iter start, Iter end, T val) {
    Iter destination = start;

    //loop through entire list
    while(start != end) { 
        //skip element(s) to be removed
        if (*start == val) { 
            start++; 
         }
         else //retain rest of the elements
             *destination++ = *start++;
     }

     //return the new end of the list
     return destination;
}

Notice that remove simply moved up the elements in the sequence, overwriting the values that you wanted to remove. So the values you wanted to remove are indeed gone, but then what's the problem? Let say you had vector with values {1, 2, 3, 4, 5}. After you call remove for val = 3, the vector now has {1, 2, 4, 5, 5}. That is, 4 and 5 got moved up so that 3 is gone from the vector but the size of vector hasn't changed. Also, the end of the vector now contains additional left over copy of 5.

What does vector::erase do?

std::erase takes start and end of the range you want to get rid off. It does not take the value you want to remove, only start and end of the range. Here's pseudo code for how it works:

erase(Iter first, Iter last)
{
    //copy remaining elements from last
    while (last != end())
        *first++ = *last++;

   //truncate vector
   resize(first - begin());
}

So the erase operation actually changes the size of container and frees up the memory.

The remove-erase idiom

The combination of std::remove and std::erase allows you to remove matching elements from the container so that container would actually get truncated if elements were removed. Here's how to do it:

//first do the remove
auto removed = std::remove(vec.begin(), vec.end(), val);

//now truncate the vector
vec.erase(removed, vec.end());

This is known as the remove-erase idiom. Why is it designed like this? The insight is that the operation of finding elements is more generic and independent of underlying container (only dependent on iterators). However operation of erase depends on how container is storing memory (for example, you might have linked list instead of dynamic array). So STL expects containers to do its own erase while providing generic "remove" operation so all containers don't have to implement that code. In my view, the name is very misleading and std::remove should have been called std::find_move.

Note: Above code is strictly pseudocode. The actual STL implementation is more smarter, for example, using std::move instead of copy.

Solution 3:

std::remove does not remove the actual objects, rather, pushes them to the end of the container. Actual deletion and deallocation of memory is done via erase. So:

(1). Is there any use of std::remove other than using it with erase function.

Yes, it helps to get a pair of iterators to a new sequence without having worry about proper de-allocation etc.

(2). Even after doing std::remove, why a.size() returns 2 and not 1?

The container still holds to those objects, you only have a new set of iterators to work with. Hence the size is still what it used to be.

Solution 4:

i faced the same issue, trying to understand the difference. the explanations that have been give so far are right on the money, but i only understood them after seeing an example;

#include <algorithm>
#include <string>
#include <iostream>
#include <cctype>

int main()
{
    std::string str1 = "Text with some   spaces";
    std::string::iterator it = remove(str1.begin(), str1.end(), 't');
    std::cout << str1 << std::endl;// prints "Tex wih some   spaceses"
    for (str1.begin();it != str1.end(); ++it) 
    {
         std::cout << *it; //prints "es"
    }

}

as you can see, the remove, only moves the lower case 't' to the end of the string, while returning a new iterator to the end of the new string (new string is the old string up to where the removed element are inserted) this is why when you print the iterator that you got from "remove"

   "Text with some   spaces"
       ^   ^removes both 't', then shift all elements forward -1 //what we want to remove
   "Text with some   spaces"
                          ^ end of string                    -2 //original state of string
   "Tex with some   spacess"
                          ^end of string                     -3 //first 't' removed
   "Tex wih some   spaceses"
                          ^end of string                     -4 //second 't' removed
   "Tex wih some   spaceses"
                        ^new iterator that remove() returned -5 // the state of string after "remove" and without "erase"

if you pass the iterator you obtained from step 5 to "erase()" it will know to erase from there to the end of string re-sizing the string in process

Difference between erase and remove

Solution 1:

Solution 2:

Solution 3:

Solution 4:

Related

Recent Posts