1

In the Boost.Intrusive docs in the chapter "When to use?" https://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/usage_when.html, it is stated that you can use intrusive containers containing objects of different or unknown size. 

#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
{  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;
}

My problem is that I don't understand when someone would need that (example of usage?). And I dont understand which part in the given example shows this behaviour and why you cannot do this with standard containers.

Caleth
  • 52,200
  • 2
  • 44
  • 75
Zweistein
  • 293
  • 1
  • 4
  • 11

1 Answers1

2

My problem is that I don't understand when someone would need that

They have measured the performance of their program, and found that the slowdown of using std::vector<Window *> over this is unacceptable. The given example shows a "how to", it isn't an example of the "when to".

And I dont understand which part in the given example shows this behaviour and why you cannot do this with standard containers.

You can't have a std::vector<Window> (nor std::list<Window> etc), because Window is an abstract type. The std:: containers own the Window objects they contain, having allocated space for them.

The intrusive list works because the boost::intrusive::list_base_hook base contains the prev / next pointers, and the objects contain the hook. That means the Window objects can live anywhere, e.g. in main as the example with MainWindow window and it's member Windows.

Caleth
  • 52,200
  • 2
  • 44
  • 75
  • Ok thanks, I think I got a better understanding of that comment now. Why is it possible to do so for Boost.Intrusive Containers? Is It because the node is embedded in the Class itself? I tried to implement the example using std containers and the Error is quite long. It seems to me that the problem is the use of an allocator. So does this work for Boost.Intruse because there is no memory allocation? – Zweistein Jan 22 '20 at 18:17
  • For the second use-case a [ptr_vector, ptr_list or similar](https://www.boost.org/doc/libs/1_72_0/libs/ptr_container/doc/ptr_sequence_adapter.html) would be enough. For the classical case where operating on (e.g. enumerating) polymorphic containers would be too costly there's the awesome [Boost PolyCollection](https://www.boost.org/doc/libs/develop/doc/html/poly_collection/an_efficient_polymorphic_data_st.html) – sehe Jan 23 '20 at 10:30
  • @Caleth "...and the objects themselves live somewhere else." This is not quite true. The object itself is the node, and it contains the hook used by the container. The intrusive list works because it doesn't care about the final dynamic type of the node, all it needs to function is the hook. – Andrey Semashev Jan 23 '20 at 14:55
  • @sehe I don't doubt that there are more specialised containers for the niches that intrusive used to occupy. `std::vector` and `std::vector>` are still the go-to for observing and owning polymorphic containers – Caleth Jan 23 '20 at 15:09