c++ - Check for end-of-list in boost::intrusive::list without container?

Question

I'm getting started with Boost.Intrusive, specifically interested in the doubly-linked list (boost::intrusive::list).

This would be trivial to do in a "hand-rolled" linked list, but so far I can't find a Boost equivalent:

Given a node that belongs to a list, how do I check to see if it represents the end of the list, without needing the owning container.

In a hand-made list, this would be as simple as checking if the "next" pointer is NULL.

With boost::intrusive::list, there is the s_iterator_to function, which converts a plain node to an iterator. And you can check that against mylist.end(), which gives the desired result, but it requires a reference to the list container itself.

I also note that using operator++ on such an iterator simply produces a garbage value once it is moved past the end — no error or assert from Boost.

Answer 1

After some more research and thought, it seems that there is no way to do what I want with the standard boost::intrusive::list functionality.

The list provided is, in fact, a circular linked list, not a linear one. So, there is no "null pointer" at the end.

The implementation seems to follow a similar design to the Linux kernel's list.h. You always need a reference to the container object because that contains the "head" of the circular list, which is a special node containing no user data. This is also the node that represents end() during traversal.

As to why this design is chosen, I haven't found any hard evidence. Seemingly, the circular list design allows a simpler implementation, with fewer branches. See, for example, this old article, which says "The circular nature of the list makes inserting and removing nodes simple and branch free."

I am not fully convinced by that, since I think using "pointer-to-pointer" style handling can avoid the branches, too. But that's how it's done in boost::intrusive::list, regardless.