Re: [Boost-users] [review] intrusive container comments

Olaf Krzikalla skrev:

Hi,

...

I have zero experience with the normal use cases for intrusive containers. FWIW very typical use cases are algorithms which need to compute the iterator to an element from the element itself. Whenever I've used intrusive containers so far, I used them because of their ability to do

Thorsten Ottosen wrote: that computation in constant time and to detect if they are in a particular container respectively. I think, that constant-time detection, whether a given element is in a container and constant-time computation of an iterator are outstanding abilites of intrusive containers.

Ok, that seems hard to do with the extrusive approach; unless the the actual algorithm can be made to work on list::node instead of the original container.

...

What I would like to know is if typically all objects is inside intrusive containers; also for the use of 2,3, or 4 simultaneous containers. I wouldn't say so. In fact, at least one triangulation algorithm needs to maintain and iterate over a list of all concave vertices of a polygon again and again (the list becomes smaller during the triangulation process). But usually in a typical polygon there are much more convex vertices. Thus just marking the vertices with a flag was no option, because you'd have to iterate over the whole set of vertices just to (re)find the concave ones. A "std::list concaves;" could help and in usual cases generate less memory overhead than the intrusive approach. However, the triangulation algorithm also needs to detect, whether a given vertex was concave. By using the linked() property of the intrusive node used by the "concave ilist" it was possible to have a very fast test for that. IMHO a typical example of the classic space vs. time tradeoff.

Ok. How badly would the algorithm perform if these two types of test where only O(lg N) ? -Thorsten