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

Advertisements

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;
}

 

Do you want to Learn Modern C++ from best?

We have curated a list of Best C++ Courses, that will teach you the cutting edge Modern C++ from the absolute beginning to advanced level. It will also introduce to you the word of Smart Pointers, Move semantics, Rvalue, Lambda function, auto, Variadic template, range based for loops, Multi-threading and many other latest features of C++ i.e. from C++11 to C++20.

Check Detailed Reviews of Best Modern C++ Courses

Remember, C++ requires a lot of patience, persistence, and practice. So, start learning today.

Leave a Comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top