I have finished the first version of my STL-like intrusive containers More information on: http://people.freenet.de/turtle++/intrusive.html
Hi Olaf, I am using intrusive lists a lot in my work, and I would love to see high-quality Boost versions. I have not looked at your code, but I'm impressed with your write-up, and it already addresses many issues. Here are my initial comments and thoughts: 1. Instead of providing the two options of deriving and embedding, let the user provide ADL-style 'next' and 'prev' lookup functions that for a given type provide hooks to the intrusive containers. Look at the boost::intrusive_ptr documentation for more information on this style. You can still provide the existing two methods as possible ways of providing these hooks, but if my legacy code (or for some other reason) has types with their own next and prev pointers, I still want to be able to use your code. 2. As you mention, inserting an object twice leads to problems. In general, intrusive lists need to be handled with more care. I would like to see a diagnostics mode that checks invariants and preconditions. Things to check for would be checking if an instance doesn't already exist on inserts, and checking whether there are no loops in a list. Because this will make list-manipulation really slow, I'd like to be able to enable this on a per-instance basis, probably through boolean-ish or policy-based template parameters. 3. I would love to see a single-linked intrusive container that only supports forward iteration, as well as a list decorator that turns an exiting single or doubly linked list into a ring. Thanks for the work, it looks very promising! Regards, Jaap Suter