Implementation of Erase Remove Idiom

The following example demonstrates how to use Erase Remove Idiom for removing odd numbers from a vector container.

C++

// C Program to remove the odd numbers in vector using erase 
// remove idiom 
#include <algorithm> 
#include <iostream> 
#include <vector> 
  
// utility function to print vector 
void printV(std::vector<int>& v) 
{ 
    for (auto i : v) { 
        std::cout << i << " "; 
    } 
  
    std::cout << std::endl; 
} 
  
// driver code 
int main() 
{ 
    // declaring and defining a vector 
    std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
  
    // printing original vector 
    std::cout << "Original Vector\t\t\t: "; 
    printV(v); 
  
    // using remove_if method to move all the odd elements 
    // to the end and get the new logical end 
    auto new_logical_end = std::remove_if( 
        v.begin(), v.end(), [](int a) { return a % 2; }); 
  
    // printing vector after using remove_if() 
    std::cout << "After using remove_if()\t: "; 
    printV(v); 
  
    // erasing the elements from new logical end 
    v.erase(new_logical_end, v.end()); 
    std::cout << "After using erase()\t\t: "; 
    printV(v); 
}

Output

Original Vector            : 1 2 3 4 5 6 7 8 9 
After using remove_if()    : 2 4 6 8 5 6 7 8 9 
After using erase()        : 2 4 6 8

Erase-Remove Idiom in C++

Erase-Remove-Idiom is a C++ STL (Standard Template Library) technique to remove elements from a container. It is used to remove all the elements satisfying certain conditions from the container.

The erase-remove idiom is especially useful in array-based containers like vectors, where each elimination requires all the remaining elements to adjust. In the worst case, this may lead to O ( n²) time complexity. This technique avoids this by providing the elimination of the elements in a single parse. That is why, the erase-remove idiom provides O( n ) time complexity.

In this technique, we use the combination of two member functions of the container to remove the elements efficiently.

std::erase
std::remove or std::remove_if

It is due to the use of this function that this technique is called the erase-remove idiom.

Implementation of Erase Remove Idiom

C++

Erase-Remove Idiom in C++

Similar Reads