How to Permanently Remove Items in STL Containers

remove – What is does and does not do

Like all STL algorithms, remove receives a pair of iterators to identify the range of container elements over which it needs to operate, as shown in its declaration:

template< class ForwardIterator, class T >
ForwardIterator remove( ForwardIterator first,
                        ForwardIterator last,
                        const T& value );

remove does not know about the container that holds the iterator elements it is looking at, only the iterators. remove is not able to go from the iterator to the container holding that iterator, and as consequence is not physically able to remove elements from that container.

That remove does not actually remove in the literal sense is a source of confusion for many! Try it and see how removeing elements from a container does not actually change the total number of elements in that container:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	// Set up some numbers
	std::vector< int > v;
	v.reserve( 10 );
	for ( int i = 0; i < 10; i++ ) v.push_back( i );

	// Set the first half all equal to zero
	v[ 1 ] = v[ 2 ] = v[ 3 ] = v[ 4 ] = 0;
	cout << "Size = " << v.size() << endl;

	// Remove all elements equal to zero
	remove( v.begin(), v.end(), 0 );

	// Display size once again - no change!
	cout << "Size = " << v.size() << endl;

	return 0;
}

So if remove does not actually remove anything, what does it do?

This is what the vector v looks like prior to applying remove:

After applying remove to get rid of all numbers equal to zero and storing the iterator returned by remove , the vector looks like this:

The ‘?’ characters represent numbers that have been conceptually removed from the vector, but still exist. The removed numbers may still continue to exist in that range, but this is not guaranteed. remove does not put the removed values in any special place. The remove operator arranges for all the “unremoved” numbers to be shifted to the beginning (the order of the elements remaining unchanged) and returns the iterator pointing to the end of the range.

So how do I physically remove the elements as well?

To get rid of the numbers themselves, you need to call the vector’s erase operator in conjunction with remove:

v.erase( remove( v.begin(), v.end(), 0 ),
         v.end() );

This requires that you pass it the iterators to identify the range of elements you wish to delete. Given that remove gives you the iterator pointing to the logical end of the “unremoved” range, it is simple to apply:

int main()
{
	// Set up some numbers
	std::vector< int > v;
	v.reserve( 10 );
	for ( int i = 0; i < 10; i++ ) v.push_back( i );

	// Set the first half all equal to zero
	v[ 1 ] = v[ 2 ] = v[ 3 ] = v[ 4 ] = 0;
	cout << "Size = " << v.size() << endl;

	// Physically remove all elements equal to zero
	v.erase( remove( v.begin(), v.end(), 0 ),
             v.end() );

	// Display size once again - minus removed elements
	cout << "Size = " << v.size() << endl;

	return 0;
}

Another example: combine remove_if with function object (functor)

We might wish to apply different or more complicated criteria for deletion of vector elements instead of checking for zero. For this purpose I would recommend using a function object (functor). A functor is simply a class that contains an overloaded function call operator, operator(). In this example, the functor is used as a means of stripping out all even numbers from the vector set, though feel free to make up ones that suit your own purpose.

This example also uses code from a previous posting to generically print the STL container contents.

#include <iostream>
#include <algorithm>
#include <iterator> 
#include <vector>

using namespace std;

typedef std::vector<int>::iterator iter_s;  

template<typename T, typename InputIterator>  
void Print(std::ostream& ostr,   
            InputIterator itbegin,   
            InputIterator itend,   
            const std::string& delimiter)  
{  
    std::copy(itbegin,   
                itend,   
                std::ostream_iterator<T>(ostr, delimiter.c_str()));  
}  

// Is even functor
class IsEven
{
public:
	bool operator() ( int i )
	{ return i % 2 == 0; }
};

int main()
{
	int vals[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	std::vector<int> v( vals, vals + sizeof( vals ) / sizeof( vals[ 0 ] ) );

	v.erase( remove_if( v.begin(), v.end(), IsEven() ), v.end() );

	Print<int, iter_s>( std::cout, v.begin(), v.end(), " " );  

	return 0;
}

Giving the printed result:

1 3 5 7 9