Suppose we have a vector of integers and we want to delete all occurences of a number from it i.e.

Let’s say vector contain following numbers 1,2,5,4,5,1,5,7,8,9.
Now we want to delete all the occurences of 5 from it, so that vector contents should become – 1 2 4 1 7 8 9 .
Also the order of elements should be mentained.

There are two ways to do this,

First Method: A Non efficient way

1.) Iterate through all elements in vector and check for each elements if it matches with required number.
2.) If it matches then erase that element and go forward.

ALthough it seems to be quite efficient but its not. Because erase function deletes the elements and shifts all the elements in right by 1.
So, it complexity will be O(n^2).

Let’s do it in a more efficient way,

Second Method : An Efficient Way

Use Erase-Remove idiom.

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 dont remove the matched elements.
It just shifted the non moatched to starting and gives an iterator to new valid end.
It just requires O(n) complexity.

Output of remove algo will be,

1 2 4 1 7 8 9 ? ? ?

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

Hence this new algo does the job in O(n) complexity.

Checkout the complete code,


Python Recommendations:

C++ & C++11 Recommendations:

If you didn't find what you were looking, then do suggest us in the comments below. We will be more than happy to add that.

Subscribe with us to join 1500+ Python & C++ developers, to get more Tips &  Tutorials like this.