Ted Gould wrote:
I don't see any specific issue with Boost.Intrusive, but I'm curious if GLib's lists can do all of that as GLib is already a dep.
After this suggestion I tried it, and it also works, but there are rough edges. Here are the problems: 1. GLists do not store a pointer to the last node, so I have to resort to awful hacks or accept having to walk the entire list just to find the last node. This is a big problem as the most common operations like appending or finding the node adjacent to the first node of a closed path require this. 2. In general, representing lists as a pointer to first node has many shortcomings. Boost.Intrusive, as well as most std::list implementations, use a cyclic list with an empty first node (without any associated value) as a header. This makes it trivially easy to implement iterators, in particular the end iterator, and both begin() and end() are constant time as expected from a doubly-linked list. With GList I have to special case the end iterator. With Boost.Intrusive I don't even have to implement iterators, only the cyclic adjacency operation (next/prev), which is trivial: void next_node(iterator i) { ++i; if (i.pointed_node()->is_header && i.pointed_node()->closed) ++i;) } 3. GLists do not support slicing, only concatenation. I will need slicing or at least splitting into multiple lists to implement break and delete segment.
Regards, Krzysztof Kosiński