This article is based on all the version of C++. However, programs are written in C++11.
Question: Remove odd numbers from an interger vector?
Input:
vector<int> v = {11, 22, 33, 44, 55, 66, 77, 88, 99}
Output:
vector<int> v = {22, 44, 66, 88}
This is one of the common requirement nowadays, and only a few people know the effective way to achieve it.
Approach - 1: (Lengthy approach, Not recommended)
Complexity: O(N^2)
Traverse over the vector. Compare each element and remove it.
This approach is not recommended. Vector is a sequential container. All of the elements of the vector are sequentially placed. So, when you delete one element from the vector, then rest of the element of the vector will shift and this is quite costly operation. Hence, for every deletion of the vector element, vector will be reallocated.
auto it = v.begin();
while(it != v.end()) {
if (*it % 2 == 1) {
// Vector element is odd. Remove it.
// DO NOT INCREMENT THE ITERATOR IN THIS CASE
// OHERWISE, PROGRAM WILL CRASH, BECAUSE YOUR
// ITERATOR WILL BE INVALIDATED
v.erase(it);
} else {
++it;
}
}
Approach - 2 : (Optimized approach, Recommended)
Complexity: O(N)
Use erase-remove idiom. In this approach, no need to delete element one by one, copy of the un-favorable element to the end of the vector by using std::remove() algorithm and then pass the iterator to erase function of the vector.
Using functor with this approach.
bool isOdd(int& i) {
return (i%2 == 1);
}
v.erase(remove_if(v.begin(), v.end(), isOdd), v.end());
Approach - 3 : (Optimized approach, Highly Recommended)
This is same as the approach-2. The only difference is, we are using lambda function in this approach instaed of functor.
v.erase(remove_if(v.begin(), v.end(), [](int& i){ return (i%2 == 1); }), v.end());
Program:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printVector(vector<int>& v) {
for(auto elem : v)
cout << elem << " ";
cout << endl;
}
void initializeVector(vector<int>& v) {
v = {11, 22, 33, 44, 55, 66, 77, 88, 99};
}
bool isOdd(int& i) {
return (i%2 == 1);
}
int main() {
vector<int> v;
// Approach - 1
// Traverse over vector
// Check all the elements
// Remove the element if it is odd
cout << endl << endl << "Executing Step-1" << endl << endl;
initializeVector(v);
printVector(v);
auto it = v.begin();
while(it != v.end()) {
if (*it % 2 == 1) {
// Vector element is odd. Remove it.
// DO NOT INCREMENT THE ITERATOR IN THIS CASE
// OHERWISE, PROGRAM WILL CRASH, BECAUSE YOUR
// ITERATOR WILL BE INVALIDATED
v.erase(it);
} else {
++it;
}
}
printVector(v);
// Approach - 2
// Use erase-remove idioms with functor
cout << endl << endl << "Executing Step-2" << endl << endl;
initializeVector(v);
printVector(v);
v.erase(remove_if(v.begin(), v.end(), isOdd), v.end());
printVector(v);
// Approach - 3
// Use erase-remove idioms with lambda function
cout << endl << endl << "Executing Step-3" << endl << endl;
initializeVector(v);
printVector(v);
v.erase(remove_if(v.begin(), v.end(), [](int& i){ return (i%2 == 1); }), v.end());
printVector(v);
return 0;
}
Output:
Executing Step-1
11 22 33 44 55 66 77 88 99
22 44 66 88
Executing Step-2
11 22 33 44 55 66 77 88 99
22 44 66 88
Executing Step-3
11 22 33 44 55 66 77 88 99
22 44 66 88
Like and share the article. Happy coding. You can write your comment in the comment section.
Comments