Re: [boost] [Intrusive]

Subject: Re: [boost] [Intrusive]
From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2017-08-23 09:03:28

On 08/23/17 10:18, degski via Boost wrote:
> I having trouble understanding the documentation of Boost.Intrusive. I'm
> referring to this section in particular:
> http://www.boost.org/doc/libs/1_65_0/doc/html/intrusive/intrusive_vs_nontrusive.html#intrusive.intrusive_vs_nontrusive.differences_intrusive_vs_nontrusive
> 
> "The main difference between intrusive containers and non-intrusive
> containers is that in C++ non-intrusive containers store *copies* of values
> passed by the user."
> 
> This is confusing, as that might not be true in case of C++11 and up.
> 
> "On the other hand, an intrusive container does not store copies of passed
> objects, but it stores the objects themselves. The additional data needed
> to insert the object in the container must be provided by the object
> itself."

I think the important point here is that the conventional containers 
wrap user's objects in the auxiliary structures and therefore store a 
*different* object than the one passed by the user. In C++03 this is 
achieved by copying the object, in C++11 and later this can also be done 
by moving (ignoring emplacement as in this case the object doesn't exist 
until it is created by the container). Boost.Intrusive, on the other 
hand, links the exact same object that you passed into the container 
without copying and moving.

 > Does
 > (or rather, can) move-construction invalidate the use case for
 > Intrusive containers?

I guess, if your object's move is cheap and copy is expensive, and you 
were considering Boost.Intrusive as a way to avoid copying the object 
then you could use a conventional container with move-construction 
instead. But I wouldn't consider this a main use case of Boost.Intrusive.

For me, there are two main use cases for Boost.Intrusive. First is when 
your object is not copyable or movable, which is often the case when the 
object is referenced by another API. The only alternative to 
Boost.Intrusive is keeping a pointer to the object in a separate 
container, which is way too cumbersome. Second is when you want your 
object to be a member of multiple containers and you don't want or 
cannot copy it. In a way, this is similar to Boost.MultiIndex, but you 
are not constrained to have the object present either in all indexes or 
none.

> But then in the example for slist, it seems from the example code that (a)
> pointer(s) to the original object are stored (and makes it look like the
> object), but that's not what I read from the quoted text.
> 
> class MyClass{
>     MyClass *next;
>     MyClass *previous;
>     //Other members...};
> int main(){
>     acme_intrusive_list<MyClass> list;
> 
>     MyClass myclass;
>     list.push_back(myclass);
> 
>     //"myclass" object is stored in the list
>     assert(&myclass == &list.front());
>     return 0;}

Yes, the assert is correct.

> I would like to ask for somebody to confirm I'm right, or explain to me in
> language (palatable to a thick user) what is actually stored (in terms of
> implementation).

Internally, Boost.Intrusive containers mostly deal with linking. All the 
necessary data needed for container is stored in the hook that has to be 
injected somehow into the object. They do not allocate or free memory, 
they do not copy, move or construct user's objects. They can be *asked* 
to destroy the user's object upon removing it from the container but by 
default do not do that either. This makes the containers completely 
agnostic to the storage they operate on. In the hindsight, they are data 
structures with no cruft.