Boost logo

Boost :

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:
> "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

> 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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at