Re: [boost] [MultiIndex] Recursive data structure with MultiIndex

Subject: Re: [boost] [MultiIndex] Recursive data structure with MultiIndex
From: joaquin_at_[hidden]
Date: 2009-05-28 05:22:29

Sebastian Redl escribió:
> Hi,
>
> I'm trying to implement property_tree in terms of multi_index, but have
> run into a problem.
>
> The old implementation boiled down to this (using no templates for clarity):
>
> class ptree
> {
>   typedef std::pair<std::string, ptree> value_type;
>   typedef std::list<value_type> list_type;
>   list_type m_children;
> };
>
> This is undefined behavior, because at the point where the list is
> instantiated, ptree is incomplete, so the pair cannot be fully
> instantiated. However, apparently it worked on enough compilers.
>
> Now I want to use MultiIndex instead, so that I can have both the order
> of children preserved and offer O(log(N)) lookup of children. (The old
> code was O(N), but claimed to be O(log(N)).) But MultiIndex actually
> fails to instantiate with the incomplete type.

Please disregard the previous mail, I answered too quickly and wrongly.
multi_index_container *can't* be instantiated with an incomplete type,
regardless of the kind of key extractors you're using; as things stands now,
instantiating a multi_index_container<T,...> implies the instantiation 
of its internal
node type, which needs to know sizeof(T).

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo