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

Olaf Krzikalla skrev:

Hi,

Thorsten Ottosen wrote:

...

...

...

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) ? Hmm, from a quick glance I can definitely say it raises from O(m*n) to at least O(m*n*lg(n)), maybe even worse (m being the number of all veritces in a polygon, n being the number of concave vertices in it).

Ok. And what are typical values of m and n? -Thorsten