When to use?

| Home | Libraries | People | FAQ | More

## When to use?

Intrusive containers can be used for highly optimized algorithms, where speed is a crucial issue and...

- additional memory management should be avoided.
- the programmer needs to efficiently track the construction and destruction of objects.
- exception safety, especially the no-throw guarantee, is needed.
- the computation of an iterator to an element from a pointer or reference to that element should be a constant time operation.
- it's important to achieve a well-known worst-time system response.
- localization of data (e.g. for cache hit optimization) leads to measureable effects.

The last point is important if you have a lot of containers over a set of elements. E.g. if you have a vector of objects (say, `std::vector<Object>`) and you also have a list storing a subset of those objects (`std::list<Object*>`), then operating on an Object from the list iterator (`std::list<Object*>::iterator`) needs two steps:

- Access from the iterator (usually on the stack) to the list node storing a pointer to `Object`.
- Access from the pointer to `Object` to the Object stored in the vector.

While the objects themselves are tightly packed in the memory of the vector (vector's memory is guaranteed to be contiguous), and form something like a data block, list nodes can stay dispersed in the heap memory. Hence depending on your system you can get a lot of cache misses. The same doesn't hold for an intrusive list. Indeed, dereferencing an an iterator from an intrusive list is performed in the same two steps as described above. But the list node is already embedded in the Object, so the memory is directly tracked from the iterator to the Object.

It's also possible to use intrusive containers when the objects to be stored can have different or unknown size. This allows storing base and derived objects in the same container as shown in the following example:

    #include <boost/intrusive/list.hpp>

    using namespace boost::intrusive;

    //An abstract class that can be inserted in an intrusive list
    class Window : public list_base_hook<>
    {
       public:
       //This is a container those value is an abstract class: you can't do this with std::list.
       typedef list<Window> win_list;

       //An static intrusive list declaration
       static win_list all_windows;

       //Constructor. Includes this window in the list
       Window()             {  all_windows.push_back(*this);  }
       //Destructor. Removes this node from the list
       virtual ~Window()    {  all_windows.erase(win_list::s_iterator_to(*this));  }
       //Pure virtual function to be implemented by derived classes
       virtual void Paint() = 0;
    };

    //The static intrusive list declaration
    Window::win_list Window::all_windows;

    //Some Window derived classes
    class FrameWindow :  public Window
    {  void Paint(){/**/} };

    class EditWindow :  public Window
    {  void Paint(){/**/} };

    class CanvasWindow :  public Window
    {  void Paint(){/**/} };

    //A function that prints all windows stored in the intrusive list
    void paint_all_windows()
    {
       for(Window::win_list::iterator i(Window::all_windows.begin())
                                    , e(Window::all_windows.end())
          ; i != e; ++i)
          i->Paint();
    }

    //...

    //A class derived from Window
    class MainWindow  :  public Window
    {
       FrameWindow   frame_;  //these are derived from Window too
       EditWindow    edit_;
       CanvasWindow  canvas_;

       public:
       void Paint(){/**/}
       //...
    };

    //Main function
    int main()
    {
       //When a Window class is created, is automatically registered in the global list
       MainWindow window;

       //Paint all the windows, sub-windows and so on
       paint_all_windows();

       //All the windows are automatically unregistered in their destructors.
       return 0;
    }

Due to certain properties of intrusive containers they are often more difficult to use than their STL-counterparts. That's why you should avoid them in public interfaces of libraries. Classes to be stored in intrusive containers must change their implementation to store the hook and this is not always posible or desirable.