[boost] Re: Intrusive containers: second iteration

From: Olaf Krzikalla (krzikalla_at_[hidden])
Date: 2005-04-29 16:27:56

Hi,

frank_at_[hidden] wrote:
> As far as I understood the stored elements are not owned by the 
> containers itself, but allocated by some other object. 
Right. Actually the term 'store' is little bit misleading. But even in 
our native language german I didn't found a better term.

> But why not
> using a reference type and storing this in the usual non-instrusive
> containers?
Performance reasons. Look at Overview, section 'Properties of intrusive 
containers' and then go to Usage, section 'When to use?'. It not only 
mentions your idea, but should answers your question too. In fact, the 
development of these containers was the result of falling in a deep 
performance hole while developing some mathematical algorithms (e.g. a 
fast triangulation algorithm, which needs 3 sequences over the 
vertices). Another example is the open source polygon clipping algorithm 
GPC. A C++ version of GPC could draw huge advantages from Boost.Intrusive.

> My second question goes into data integrity.
> I feel really bad, when I see the example.cpp where the
> test class is inherited from imultiset_node_d. 
> So the value of a object of type test is defined by x
> and is accessibly from the user's side? I mean changing that
> value from outside the underlying RB-tree implementation
> would easily break it.
Hmm, big point. I have to change this. Indeed the public interface of 
imultiset_node_d should consist only of the members mentioned in the 
docs (same for the other nodes).

> So it's all about being more efficient and being compatible
> with existing algorithms that work on STL containers?
Right again.

Best regards,
Olaf Krzikalla