Recipe7.2.Removing Objects from a Container

Recipe 7.2. Removing Objects from a Container

Problem

You want to remove objects from a container.

Solution

Use the container's erase member function to erase a single element or a range of elements, and possibly use one of the standard algorithms to make the job easier. Example 7-2 shows a couple of different ways to remove elements from a sequence.

Example 7-2. Removing elements from a container

#include <iostream>
#include <string>
#include <list>
#include <algorithm>
#include <functional>
#include "utils.h" // For printContainer( ): see 7.10

using namespace std;

int main( ) {

   list<string> lstStr;

   lstStr.push_back("On");
   lstStr.push_back("a");
   lstStr.push_back("cloudy");
   lstStr.push_back("cloudy");
   lstStr.push_back("day");

   list<string>::iterator p;

   // Find what you want with find
   p = find(lstStr.begin( ), lstStr.end( ), "day");

   p = lstStr.erase(p); // Now p points to the last element

   // Or, to erase all occurrences of something, use remove
   lstStr.erase(remove(lstStr.begin( ), lstStr.end( ), "cloudy"),
                lstStr.end( ));
   printContainer(lstStr); // See 7.10
}

Discussion

Use a container's erase member function to remove one or more elements from it. All containers have two overloads of erase : one that takes a single iterator argument that points to the element you want to delete, and another that takes two iterator s that represent a range of elements you want deleted. To erase a single element, obtain an iterator referring to that element and pass the iterator to erase , as in Example 7-2:

p = find(lstStr.begin( ), lstStr.end( ), "day");
p = lstStr.erase(p);

This will delete the object that p refers to by calling its destructor, and then do any necessary reorganization of the remaining elements in the range. The reorganization that happens depends on the type of container, and therefore the complexity of the operation will vary from one kind of container to another. The signature and behavior also differs slightly when you are using a sequence container versus an associative container.

In sequences, erase returns an iterator that refers to the first element immediately following the last element that was deleted, which may be end if the last element in the sequence was the last one deleted. The complexity of the operation is different for each container because sequences are implemented in different ways. For example, since all elements in a vector are stored in a contiguous chunk of memory, removing an element from anywhere except the end requires shifting all the elements following it toward the beginning to fill the gap. This is a hefty performance penalty (linear), which is why you shouldn't use a vector if you have to delete (or insert, for that matter) elements anywhere except at the end. I discuss this very matter in more detail in Recipe 6.2.

In associative containers, erase returns void . The complexity is amortized constant if you are deleting a single element, and logarithmic plus the number of elements deleted if you are deleting a range of elements. This is because associative containers are often implemented as balanced trees (e.g., red-black tree).

erase is handy, but not very interesting. If you want more flexibility in how you express what should be deleted, you will have to turn to the standard algorithms (in <algorithm> ). Consider this line from Example 7-2:

lstStr.erase(std::remove(lstStr.begin( ), lstStr.end( ), "cloudy"),
             lstStr.end( ));

Notice that I am still using erase , but this time, for my own reasons, I want to delete all occurrences of the word "cloudy" from my list<string> . remove returns an iterator , which I pass to erase as the beginning of the doomed range, and I pass end to erase as the end point for the range. This deletes each object obj (by calling its delete method) in the range for which obj == " cloudy " is true. But it may not behave exactly as you expect. Here is where I need to clarify some terminology.

remove doesn't actually remove anything. It moves everything that isn't equal to the value you specify to the beginning of the sequence, and returns an iterator that refers to the first element following them. Then, it is up to you to actually call erase on the container to delete the objects between [p, end) , where p is the iterator returned by remove .

remove has some variants, too. What if you want to remove elements that satisfy some predicate, and not simply those equal to some value? Use remove_if . For example, imagine you have a class named Conn that represents some sort of connection. If the connection has an idle time greater than some value, you want to remove it. First, create a functor as follows :

struct IdleConnFn :
   public std::unary_function<const Conn, bool> {  // Include this line
   bool operator( ) (const Conn& c) const {         // so it works with
      if (c.getIdleTime( ) > TIMEOUT) {             // other stuff in
         return(true);                             // <functional>
      }
      else
         return(false);
   }
} idle;

Then you can call remove_if with erase and pass in your functor, like this:

vec.erase(std::remove_if(vec.begin( ), vec.end( ), idle), vec.end( ));

You want to derive such functors from unary_function for a good reason. unary_function defines some typedef s that are used by other functors in <functional> , and if they aren't there, the other functors won't compile. For example, if you are particularly malicious, and you want to remove connections that aren't idle, you can employ the not1 functor with your idle-checking functor:

vec.erase(std::remove_if(vec.begin( ), vec.end( ),

std::not1

(idle)),
          vec.end( ));

Finally, you may want to leave the original sequence alone (maybe it's const ) and copy the results minus some elements into a new sequence. You can do that with remove_copy and remove_copy_if , which work the same way as remove and remove_if , except that there is also an output iterator you pass in where the resulting data is supposed to go. For example, to copy strings from one list to another, do this:

std::remove_copy(lstStr.begin( ), lstStr.end( ),

lstStr2

, "cloudy");

The thing you have to remember when using remove_copy , or any standard algorithm that writes to an output range, is that the output range must already be large enough to accommodate the elements that are about to be written to it.

erase and remove (and its family of related algorithms) offer a convenient way to erase certain elements from a sequence. They provide a clean, ready-made alternative to looping yourself to find all the elements you want, then erasing them one by one.

See Also

Recipe 6.2 and Recipe 7.1