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 03:41:17

Hi Sebastian,

Sebastian Redl escribió:
> Hi,
>
> I'm trying to implement property_tree in terms of multi_index, but have
> run into a problem.
>
> [...]
>
> 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. More concretely, what
> fails to instantiate is the key retriever, a member<value_type,
> std::string, &value_type::first>. This is because the member access into
> the pair requires pair to be fully instantiated, and the instantiation
> fails as the ptree is incomplete.

Well, currently multi_index_containers are not guaranteed to be instantiable
with incomplete types (analogously to stdlib containers: the std 
explicitly bans
this possibility), so the following is basically undocumented behavior: 
try using
a custom key extractor, just like shown in the following example:

  struct value_type;

  struct key_extractor;

  using namespace boost::multi_index;

  typedef multi_index_container<
   value_type,
   indexed_by<
     ordered_unique<key_extractor>
   >
  > container;

  struct value_type
  {
    value_type(int x):x(x){}
    int x;
  };

  struct key_extractor:member<value_type,int,&value_type::x>{};

Hope this helps. Thanks for using Boost.MultiIndex.

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