Re: [boost] [Boost][GSOC] proposal for Trie

2013/4/23 Michael Marcin :

On 4/22/13 11:08 AM, Antony Polukhin wrote:

...

2013/4/22 Michael Marcin : <...>

...

You can take a non-intrusive container and make it intrusive?

Black magic?

And how are you going to make intrusive container manage memory and objects lifetime?

Stefan Strasser said it well not long ago, I'll just quote him.

On 4/6/13 10:08 AM, Stefan Strasser wrote:

...

Zitat von Vadim Stadnik :

...

If Boost.Intrusive containers (and containers based on Boost.Intrusive containers) outperform all other containers, they are the best possible choice. They are winners by both of these important parameters. Otherwise their advantage is not so obvious.

a non-intrusive container that is implemented in terms of an intrusive container is as efficient as any other non-intrusive container. it is a little more work to implement, to provide the Intrusive public interface. However, you can not implement an Intrusive container in terms of a non-intrusive container but have to reimplement the entire data structure. That's why Boost.Intrusive is not based on namespace std containers but are a reimplementation of the algorithms.

The implementation of a non-intrusive container in terms of an intrusive one is as simple as:

struct value_holder : intrusive::hook{ T value; };

and forwarding all calls of the STL container interface.

May be I'm missing something, but Stefan Strasser was talking about STL and Boosts intrusive containers, and his words shall be interpreted in context that we have no access to internals of STL. But when we have access to internals it is a totally different situation: * If we develop a non-intrusive container, we are free to split its implementation to resource management and intrusive logic. * If we develop an intrusive container - we need to add resource management to make a non-intrusive container. In both situations we achieve same results - we have intrusive and non-intrusive containers. So it works both ways *when we have access to internals* . -- Best regards, Antony Polukhin