Re: Iterate intrusive list without container?

From: bobby gurnham (bobbygurnham7_at_[hidden])
Date: 2021-10-21 18:17:26

Сус амогус
 
 
  On Thu, 21 Oct 2021 at 11:09, John W via Boost-users<boost-users_at_[hidden]> 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.

(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?

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

Thanks
-John

[1] https://github.com/boostorg/intrusive/blob/f44b0102b4ee9acf7b0304b3f5b27dde02297202/include/boost/intrusive/list.hpp#L1272
[2] https://github.com/boostorg/intrusive/blob/f44b0102b4ee9acf7b0304b3f5b27dde02297202/include/boost/intrusive/list.hpp#L1394
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
https://lists.boost.org/mailman/listinfo.cgi/boost-users