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

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-03-22 11:17:52

Olaf Krzikalla skrev:
> 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.

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

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

-Thorsten