Remove all occurences of an element from vector in O(n) complexity

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

Algo:
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.

	std::vector<int>::iterator it = vec.begin();
	while(it != vec.end())
	{
		if(*it == elem)
		{
			it = vec.erase(it);
		}
		else
			it++;
	}

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.

[showads ad=inside_post]

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.

	vec.erase(std::remove(vec.begin(), vec.end(), elem), vec.end());

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

Checkout the complete code,

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

void removeAllMatchingElements_nonEfficient(std::vector<int> & vec, int elem)
{
   std::vector<int>::iterator it = vec.begin();
   while(it != vec.end())
   {
     if(*it == elem)
     {
        it = vec.erase(it);
     }
     else
        it++;
  }
}

void removeAllMatchingElements_Efficient(std::vector<int> & vec, int elem)
{
    vec.erase(std::remove(vec.begin(), vec.end(), elem), vec.end());
}

void displayVector(std::vector<int> & vec)
{
   std::vector<int>::iterator it = vec.begin();
   while(it != vec.end())
       std::cout<<(*it++)<<" ";
   std::cout<<std::endl;
}
int main()
{
   int arr[10] = {1,2,5,4,5,1,5,7,8,9};

   std::vector<int> vec(arr , arr + 10);
   removeAllMatchingElements_nonEfficient(vec, 5);
   displayVector(vec);

   std::vector<int> vec2(arr , arr + 10);
   removeAllMatchingElements_Efficient(vec2, 5);
   displayVector(vec2);

   return 0;
}