Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards


Erasing and disposing values from Boost.Intrusive containers

One of the most tedious tasks when using intrusive containers is the management of the erased elements. When using STL containers, the container itself unlinks and destroys the contained elements, but with intrusive containers, the user must explicitly destroy the object after erasing an element from the container. This makes STL-like functions erasing multiple objects unhelpful: the user can't destroy every erased element. For example, let's take the function remove_if from list:

template<class Pred>
void remove_if(Pred pred);

How can the user destroy the elements (say, using operator delete) that will be erased according to the predicate? Boost.Intrusive containers offer additional functions that take a function object that will be called after the element has been erased from the container. For example, list offers:

template<class Pred, class Disposer>
void remove_and_dispose_if(Pred pred, Disposer disposer)

With this function the user can efficiently remove and destroy elements if the disposer function destroys an object: remove_and_dispose_if will call the "disposer" function object for every removed element. list offers more functions taking a disposer function object as argument, like erase_and_dispose, clear_and_dispose, remove_and_dispose, etc.

Note that the disposing function does not need to just destroy the object. It can implement any other operation like inserting the remove object in another container. Let's see a small example:

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

//A class that can be inserted in an intrusive list
class my_class : public list_base_hook<>
   my_class(int i)
      :  int_(i)

   int int_;

//Definition of the intrusive list
typedef list<my_class> my_class_list;

//The predicate function
struct is_even
   bool operator()(const my_class &c) const
   {  return 0 == (c.int_ % 2);  }

//The disposer object function
struct delete_disposer
   void operator()(my_class *delete_this)
   {  delete delete_this;  }

int main()
   const int MaxElem = 100;

   //Fill all the nodes and insert them in the list
   my_class_list list;

      //Insert new objects in the container
      for(int i = 0; i < MaxElem; ++i) list.push_back(*new my_class(i));

      //Now use remove_and_dispose_if to erase and delete the objects
      list.remove_and_dispose_if(is_even(), delete_disposer());
      //If something throws, make sure that all the memory is freed

   //Dispose remaining elements
   list.erase_and_dispose(list.begin(), list.end(), delete_disposer());
   return 0;

All Boost.Intrusive containers offer these "erase + dispose" additional members for all functions that erase an element from the container.