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,


Click Here to Subscribe for more Articles / Tutorials like this.