...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Intrusive containers can be used for highly optimized algorithms, where speed is a crucial issue and:
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
) requires two steps:
Object
.
Object
to the Object stored in the vector.
While the objects themselves are tightly packed in the memory of the vector (a vector's memory is guaranteed to be contiguous), and form something like a data block, list nodes may be dispersed in the heap memory. Hence depending on your system you might get a lot of cache misses. The same doesn't hold for an intrusive list. Indeed, dereferencing 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; //A 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 { virtual void Paint() BOOST_OVERRIDE {/**/} }; class EditWindow : public Window { virtual void Paint() BOOST_OVERRIDE {/**/} }; class CanvasWindow : public Window { virtual void Paint() BOOST_OVERRIDE {/**/} }; //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() BOOST_OVERRIDE {/**/} //... }; //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 possible or desirable.