Re: Iterate intrusive list without container?

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2021-10-24 20:32:35

On 21/10/2021 20:08, John W via Boost-users wrote:
> With a traditional "hand-rolled" doubly-linked list, if you have a
> reference to a Node, you can traverse from that node to the end of the
> list easily. Just check for "pNext == NULL" to know when you're at the
> end. You don't need any reference to the owning "list container"
> object.
> 
> However, I can't seem to accomplish the same with  boost::intrusive::list.
> 
> Traversal with an intrusive::list's iterator is done STL-style, and
> for that you need to compare to the container's ".end()" value.
> 
> I am aware of the "s_iterator_to" function[1], which can statically
> get an iterator from a node, but there doesn't seem to be any way to
> statically get a usable ".end()" value to compare to. There is also
> "container_from_end_iterator"[2], which gives the container if you
> have "end()" available already — not quite what I want, but I guess
> shows that end() is intimately tied to the container.
> 
> I also notice that if I have an iterator to the last element in a
> list, and I increment it (++iterator), no error is given. But if I try
> to dereference it, I get garbage data.
> 
> Peeking into the implementation, from what I can tell,
> boost::intrusive::list is actually a circular list, with a special
> "root node" that the container owns, and which represents the "end".
> So, iterating beyond the end gives you that root node.
> 
> I guess my questions are:
> 
> (1) Is my analysis above correct? I feel I might have missed something
> wading through all the templates, and the docs I've found don't
> discuss these implementation details.

Yes

> (2) Is there any way to accomplish what I want? That is: iterating
> from an arbitrary node to the end of the list, *without* a reference
> to the owning container?

No, it's not possible.

> (3) [aside] If the answer to the above is "no", does anyone know what
> the rationale is for this design choice? It seems odd that such a
> basic feature of a traditional hand-made intrusive list would be
> dropped if there were no benefit.

Because Boost.Intrusive is designed around the idea of a "container". A 
circular linked list allows constant-time insertion in the back 
(push_back implementation) without continuously tracking which is the 
last node (which complicates code). std::list containers are also 
implemented using doubly linked circular lists.

Best,

Ion