In C++ programming paradigm, we extensively use the collection frameworks like STL, Its very common practice to remove element(s) from collection(s) like vector. The common practice is just iterate through the container to remove the desired element. But STL has builtin feature specifically to avoid this situation. Erase-Remove idiom comes in our rescue. Erase-Remove is an efficient way to permanently remove element(s) from an STL container.
Let’s see couple of methods to understand it further – erase() and remove() (and remove_if()).
- erase: – STL containers provide erase method to remove an element or a range of elements from the container. erase method reduces the size of the container.
- remove: – remove and remove_if methods are also a part of STL algorithm.
- These methods pushes the element(s), which matches the ‘remove’ criteria, to end of the container.
- remove method returns an iterator pointing to the first removed element.
- The removed element is still part of the container but it is pushed to the end of container.
Program: Example to illustrate erase-remove idiom.
We will demonstrate the above discussed methods with the help of methods remove_example(), erase_remove_example() and erase_remove_if_example() as follows:
#include <algorithm> // remove
#include <vector> // vector
#include <iostream> // cout
/////////////////////////////////////////////////////////////////////////////////////////
void print_vec(const std::vector<int>& vec)
{
for (std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl
<< "Vector Size :" << vec.size() << std::endl;
return;
}
bool greater_than_five(int i)
{
return (i > 5);
}
/////////////////////////////////////////////////////////////////////////////////////////
void remove_example(void)
{
std::vector<int> my_vec;
for (int i = 0; i < 10; i++) {
my_vec.push_back(i % 2);
}
std::cout << "Printing input vector contents for remove example" << std::endl;
print_vec(my_vec);
std::vector<int>::iterator new_end = std::remove(my_vec.begin(), my_vec.end(), 0);
std::cout << "Printing vector contents after remove operation " << std::endl;
for (std::vector<int>::const_iterator it = my_vec.begin(); it != new_end; it++) {
std::cout << *it << " ";
}
std::cout << std::endl
<< "Vector New Size :" << my_vec.size() << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
void erase_remove_example(void)
{
std::vector<int> my_vec;
for (int i = 0; i < 10; i++) {
my_vec.push_back(i % 2);
}
std::cout << "Printing input vector contents for erase_remove example" << std::endl;
print_vec(my_vec);
my_vec.erase(std::remove(my_vec.begin(), my_vec.end(), 0), my_vec.end());
std::cout << "Printing vector contents after erase remove operation " << std::endl;
print_vec(my_vec);
}
/////////////////////////////////////////////////////////////////////////////////////////
void erase_remove_if_example(void)
{
std::vector my_vec;
for (int i = 0; i < 10; i++) {
my_vec.push_back(i);
}
std::cout << "Printing input vector contents for erase_remove_if example" << std::endl;
print_vec(my_vec);
my_vec.erase(std::remove_if(my_vec.begin(), my_vec.end(), greater_than_five), my_vec.end());
std::cout << "Printing vector contents after erase_remove_if operation " << std::endl;
print_vec(my_vec);
}
/////////////////////////////////////////////////////////////////////////////////////////
int main(int argc, char** argv)
{
std::cout << "================================================================" << std::endl;
remove_example();
std::cout << "================================================================" << std::endl;
erase_remove_example();
std::cout << "================================================================" << std::endl;
erase_remove_if_example();
return 0;
}
- remove_example method:
This method uses the std::remove() to remove the 0’s from the vector, which contains alternate 0’s and 1s.
Output of remove_example method is as follows:
============================================================= Printing input vector contents for remove example 0 1 0 1 0 1 0 1 0 1 Vector Size :10 Printing vector contents after remove operation 1 1 1 1 1 Vector New Size :10 =============================================================
After the remove() call, when we print the vector contents with the newly returned iterator, we got only 1’s in the vector. The point to notice here is that the size of the vector is still 10, which signify that the remove() method actually doesn’t remove the elements from the vector.
erase_remove_example method:
- erase_remove_example method uses erase and remove feature together, to remove the 0’s from the vector.
- erase() method’s first argument is the return value of remove function (refer above code std::remove(my_vec.begin(), my_vec.end(), 0).
- remove() function returns an iterator (which follows the last element, which is not removed).
The erase functions will remove all the 0’s, which were pushed to the end.
============================================================= Printing input vector contents for erase_remove example 0 1 0 1 0 1 0 1 0 1 Vector Size :10 Printing vector contents after erase remove operation 1 1 1 1 1 Vector Size :5 =============================================================
erase_remove_if_example method:
erase_remove_if_example method is quite similar to the erase_remove_example but it uses remove_if method instead of remove method. erase_remove_if_example method removes all the elements from the vector, which are greater than 5.
============================================================= Printing input vector contents for erase_remove_if example 0 1 2 3 4 5 6 7 8 9 Vector Size :10 Printing vector contents after erase_remove_if operation 0 1 2 3 4 5 Vector Size :6 =============================================================