[boost] [MultiIndex] Recursive data structure with MultiIndex

Subject: [boost] [MultiIndex] Recursive data structure with MultiIndex
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2009-05-27 12:57:37

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. 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.

I'm not very fond of the idea of storing pointers, especially as there
is no ptr_multi_index_container. But is there any other way, really?

Sebastian