Remove all Occurences of an Element from vector in O(n) Complexity

Vectors are similar to dynamic arrays in that they can resize themselves when an element is added or removed, and the container takes care of their storage. Iterators can access and traverse vector elements since they’re stored in contiguous storage. Data is inserted at the top of vectors. Inserting at the end takes longer since the array may need to be extended at times. There is no resizing, and removing the final variable still takes the same amount of time. Inserting and erasing at the start or within the middle is linear in terms of your time .

Given a vector, the task is to remove all occurrences of an element from vector in an efficient way.

Examples:

Input:

vector = {1,3,2,4,5,3,7,3,9,8,7} element=3

Output:

1 2 4 5 7 9 8 7

Efficient way to delete all occurrences of an element from vector

1)Brute force method(non efficient way)

• Iterate through the vector’s elements, checking each one to see if it matches the required number.
• If it matches, remove that element and continue.

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
int main()
{
// taking a array
int array[11] = { 1, 3, 2, 4, 5, 3, 7, 3, 9, 8, 7 };
// converting array to vector
vector<int> vect(array, array + 11);
// given element
int element = 3;
// initializing iterator to beginning of the vector
vector<int>::iterator itr = vect.begin();
// removing the given element from vector using loop
while (itr != vect.end()) {
if (*itr == element) {
itr = vect.erase(itr);
}
else
itr++;
}
itr = vect.begin();
// printing the vector
while (itr != vect.end())
cout << (*itr++) << " ";
cout << endl;
}

Output:

1 2 4 5 7 9 8 7

2)Efficient method using erase() and remove() methods

std::remove moves all elements that compare not equal to the given element to the beginning of the container from the given set. So don’t get rid of the elements that are paired.
It simply moves the non-moatched to the beginning and assigns an iterator to the new valid end.
Only O(n) complexity is needed.

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
int main()
{
// taking a array
int array[11] = { 1, 3, 2, 4, 5, 3, 7, 3, 9, 8, 7 };
// converting array to vector
vector<int> vect(array, array + 11);
// given element
int element = 3;
// initializing iterator to beginning of the vector
vector<int>::iterator itr = vect.begin();
// removing the given element from vector using loop
vect.erase(remove(vect.begin(), vect.end(), element),
vect.end());
itr = vect.begin();
// printing the vector
while (itr != vect.end())
cout << (*itr++) << " ";
cout << endl;
}

Output:

1 2 4 5 7 9 8 7

Related Programs: