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

From: Olaf Krzikalla (krzikalla_at_[hidden])
Date: 2007-03-22 07:15:41

Hi,

Thorsten Ottosen wrote:
> 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 
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.

> 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<Vertex*> 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.

Best regards
Olaf Krzikalla