165

I was looking at the API documentation for stl vector, and noticed there was no method on the vector class that allowed the removal of an element with a certain value. This seems like a common operation, and it seems odd that there's no built in way to do this.

3

12 Answers 12

191

std::remove does not actually erase elements from the container: it overwrites the elements that should not be removed at the beginning of the container, and returns the iterator pointing to the next element after them. This iterator can be passed to container_type::erase to do the actual removal of the extra elements that are now at the end of the container:

std::vector<int> vec;
// .. put in some values ..
int int_to_remove = n;
vec.erase(std::remove(vec.begin(), vec.end(), int_to_remove), vec.end());
15
  • 3
    Does this all-in-one-statement form depend on the order in which the compiler evaluates the arguments, or is vec.end() guaranteed to be the same on either side of the call to std::remove? It looks to me in reading other parts of the web like this is safe, but it should be stated clearly. Nov 5, 2011 at 21:28
  • 1
    It's fine. The result of vec.end() doesn't need to be the same; it just needs to be correct (which it is).
    – Jim Buck
    Nov 6, 2011 at 1:50
  • 8
    vec.end() does need to be the same, but that's OK because std::remove doesn't change it. If it did change it (and invalidate the old value) then there would be a problem: order of evaluation of parameters is unspecified and therefore you wouldn't know whether the second vec.end() is still valid by the time it's used. The reason it's the same is simple, std::remove doesn't change the size of the container, it just moves the contents around. Jan 16, 2013 at 21:00
  • 4
    I've found this question important, since I have the same problem. But, my visual studio takes std::remove with only one argument; that is const char *_Filename. What method do I need to call?
    – Victor
    Aug 24, 2013 at 12:28
  • 16
    That is the version of remove that deletes a file. You need to include <algorithm> in order to access the version of remove that deals with containers.
    – Jim Buck
    Aug 24, 2013 at 17:00
81

If you want to remove an item, the following will be a bit more efficient.

std::vector<int> v;


auto it = std::find(v.begin(), v.end(), 5);
if(it != v.end())
    v.erase(it);

or you may avoid overhead of moving the items if the order does not matter to you:

std::vector<int> v;

auto it = std::find(v.begin(), v.end(), 5);

if (it != v.end()) {
  using std::swap;

  // swap the one to be removed with the last element
  // and remove the item at the end of the container
  // to prevent moving all items after '5' by one
  swap(*it, v.back());
  v.pop_back();
}

Which is what Jim's method of std::vector::erase + std::remove does under the hood.

1
  • 4
    Note this will not remove duplicates of the item if they exist, whereas the std::remove_if approach does.
    – Den-Jason
    Apr 12, 2018 at 11:35
16

Use the global method std::remove with the begin and end iterator, and then use std::vector.erase to actually remove the elements.

Documentation links
std::remove http://www.cppreference.com/cppalgorithm/remove.html
std::vector.erase http://www.cppreference.com/cppvector/erase.html

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

//Vector should contain the elements 1, 2

//Find new end iterator
std::vector<int>::iterator newEnd = std::remove(v.begin(), v.end(), 1);

//Erase the "removed" elements.
v.erase(newEnd, v.end());

//Vector should now only contain 2

Thanks to Jim Buck for pointing out my error.

1
  • This has the ability to prevent movement of other elements on erasure of an element in the middle of the vector therefore this is faster. It moves them to the end of the vector first then you can just discard from the end of the vector. Mar 4, 2015 at 11:46
15

From c++20:

A non-member function introduced std::erase, which takes the vector and value to be removed as inputs.

ex:

std::vector<int> v = {90,80,70,60,50};
std::erase(v,50);
2
  • 2
    Not only that, it's overloaded for each specific container! May 15, 2019 at 20:37
  • 1
    ... and takes advantage of container-specific properties, like map::erase!
    – L. F.
    Apr 19, 2020 at 6:21
5

The other answers cover how to do this well, but I thought I'd also point out that it's not really odd that this isn't in the vector API: it's inefficient, linear search through the vector for the value, followed by a bunch of copying to remove it.

If you're doing this operation intensively, it can be worth considering std::set instead for this reason.

5

If you have an unsorted vector, then you can simply swap with the last vector element then resize().

With an ordered container, you'll be best off with ‍std::vector::erase(). Note that there is a std::remove() defined in <algorithm>, but that doesn't actually do the erasing. (Read the documentation carefully).

5

See also std::remove_if to be able to use a predicate...

Here's the example from the link above:

vector<int> V;
V.push_back(1);
V.push_back(4);
V.push_back(2);
V.push_back(8);
V.push_back(5);
V.push_back(7);

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    // The output is "1 4 2 8 5 7"

vector<int>::iterator new_end = 
    remove_if(V.begin(), V.end(), 
              compose1(bind2nd(equal_to<int>(), 0),
                       bind2nd(modulus<int>(), 2)));
V.erase(new_end, V.end()); [1]

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    // The output is "1 5 7".
2
  • 2
    Please add more detail to this post. As it stands, a majority of its content comes from a link, and would be lost if the link ever breaks. Feb 26, 2014 at 17:44
  • what about the fact bind2nd is -(deprecated in C++11) (removed in C++17) Dec 20, 2018 at 14:35
4

*

C++ community has heard your request :)

*

C++ 20 provides an easy way of doing it now. It gets as simple as :

#include <vector>
...
vector<int> cnt{5, 0, 2, 8, 0, 7};
std::erase(cnt, 0);

You should check out std::erase and std::erase_if.

Not only will it remove all elements of the value (here '0'), it will do it in O(n) time complexity. Which is the very best you can get.

If your compiler does not support C++ 20, you should use erase-remove idiom:

#include <algorithm>
...
vec.erase(std::remove(vec.begin(), vec.end(), 0), vec.end());
3

A shorter solution (which doesn't force you to repeat the vector name 4 times) would be to use Boost:

#include <boost/range/algorithm_ext/erase.hpp>

// ...

boost::remove_erase(vec, int_to_remove);

See http://www.boost.org/doc/libs/1_64_0/libs/range/doc/html/range/reference/algorithms/new/remove_erase.html

0

Two ways are there by which you can use to erase an item particularly. lets take a vector

std :: vector < int > v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(40);
v.push_back(50);

1) Non efficient way : Although it seems to be quite efficient but it's not because erase function delets the elements and shifts all the elements towards left by 1. so its complexity will be O(n^2)

std :: vector < int > :: iterator itr = v.begin();
int value = 40;
while ( itr != v.end() )
{
   if(*itr == value)
   { 
      v.erase(itr);
   }
   else
       ++itr;
}

2) Efficient way ( RECOMMENDED ) : It is also known as ERASE - REMOVE idioms .

  • std::remove transforms the given range into a range with all the elements that compare not equal to given element shifted to the start of the container.
  • So, actually don't remove the matched elements. It just shifted the non matched to starting and gives an iterator to new valid end. It just requires O(n) complexity.

output of the remove algorithm is :

10 20 30 50 40 50 

as return type of remove is iterator to the new end of that range.

template <class ForwardIterator, class T>
  ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

Now use vector’s erase function to delete elements from the new end to old end of the vector. It requires O(1) time.

v.erase ( std :: remove (v.begin() , v.end() , element ) , v.end () );

so this method work in O(n)

0

Similar to the erase remove idiom, for vector one could use resize and remove and use iterator distance computation:

std::vector<int> vec;
// .. put in some values ..
int int_to_remove = n;
vec.resize(std::remove(vec.begin(), vec.end(), int_to_remove) - vec.begin());

Tested here.

-1

If you want to do it without any extra includes:

vector<IComponent*> myComponents; //assume it has items in it already.
void RemoveComponent(IComponent* componentToRemove)
{
    IComponent* juggler;

    if (componentToRemove != NULL)
    {
        for (int currComponentIndex = 0; currComponentIndex < myComponents.size(); currComponentIndex++)
        {
            if (componentToRemove == myComponents[currComponentIndex])
            {
                //Since we don't care about order, swap with the last element, then delete it.
                juggler = myComponents[currComponentIndex];
                myComponents[currComponentIndex] = myComponents[myComponents.size() - 1];
                myComponents[myComponents.size() - 1] = juggler;

                //Remove it from memory and let the vector know too.
                myComponents.pop_back();
                delete juggler;
            }
        }
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.