Iterate intrusive list without container?
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/f44b0102b4ee9acf7b0304b3f5b27dde0... [2] https://github.com/boostorg/intrusive/blob/f44b0102b4ee9acf7b0304b3f5b27dde0...
Сус амогус On Thu, 21 Oct 2021 at 11:09, John W via Boost-users<boost-users@lists.boost.org> 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/f44b0102b4ee9acf7b0304b3f5b27dde0... [2] https://github.com/boostorg/intrusive/blob/f44b0102b4ee9acf7b0304b3f5b27dde0... _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
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
participants (1)
-
bobby gurnham -
Ion Gaztañaga -
John W