Re: Proposal: intrusive containers
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
Jaap Suter wrote:
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.
I'm not sure about this, most of the difficulty is involved in manipulating the links - iterator adaptor or facade can be used to easily create iterators for types with their own next and prev pointers.
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.
If there was a check that a node wasn't in a container on insertion wouldn't these problems disappear? Daniel
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. Interestingly enough, the motivation for the intrusive containers came from legacy stuff. And in an initial approach I tried to use legacy prev and next, but failed. But today I tried it again and it was quite easy. Some things just need time. You can now download a new version, there is a new legacy accessor. As I've also stated on the page, I think, that
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. Checking for correctness will be always a crucial thing in C++, because
Hi, thank you and the others for the positive feedback. Jaap Suter wrote: this legacy accessor will actually fits most of the needs (btw, it seems to be the fastest accessor, too [not measured yet]) and hence will be renamed shortly. the speed caveat is often an issue. And intrusive containers are no exceptions. So I still hesitate to add checks. But policy-based checks are a possibility.
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. Interesting ideas. An islist is of course a natural extension, since intrusive containers will be used in environments with spare ressources.
All in all, I still have to collect ideas. It seems, that in the end there will be some full-fledged policy-based intrusive containers. Best regards Olaf Krzikalla
participants (3)
-
Daniel James -
Jaap Suter -
Olaf Krzikalla