[MultiIndex] Recursive data structure with MultiIndex
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
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
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
joaquin@tid.es wrote:
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). OK, good to know.
Does multi_index support any move_ptr emulation we have in boost? (Do we have any move_ptr emulation in boost?) I can live with making the element a pointer, but I'd much rather it not be a raw pointer, and I have no use for reference counting overhead either. Sebastian
Sebastian Redl escribió:
joaquin@tid.es wrote:
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).
OK, good to know.
Does multi_index support any move_ptr emulation we have in boost? (Do we have any move_ptr emulation in boost?) I can live with making the element a pointer, but I'd much rather it not be a raw pointer, and I have no use for reference counting overhead either.
I think there's no official move pointer in Boost. I don't see any reason, however, why a using a move pointer with B.MI shouldn't work. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (2)
-
joaquin＠tid.es -
Sebastian Redl