Pointer to objects in Boost.MultiIndex
Consider the following code snippet: #include <iostream> #include <boost/multi_index_container.hpp> #include <boost/multi_index/ordered_index.hpp> #include <boost/multi_index/member.hpp> using namespace std; using namespace boost::multi_index; struct LinkList; struct LinkList { size_t index; LinkList* parent; LinkList(size_t index, LinkList* parent) : index(index), parent(parent) {} }; struct llindex {}; typedef ordered_unique<tag<llindex>, member<LinkList, size_t, &LinkList::index> > LinkListIndex; typedef boost::multi_index_container<LinkList, indexed_by<LinkListIndex> > IndexedLinkList; template <typename T> void show(T& iterable) { for(auto const& element: iterable) { if(element.parent != nullptr) { std::cout << "Index<" << element.index << ">: " << element.parent->index << std::endl; } else { std::cout << "Index<" << element.index << ">: " << "NULL" << std::endl; } } } int main() { IndexedLinkList ill; auto &index_ll = ill.get<0>(); ill.insert(LinkList{0, nullptr}); ill.insert(LinkList{1, (LinkList*)(&(*index_ll.find(0)))}); ill.insert(LinkList{2, (LinkList*)(&(*index_ll.find(0)))}); ill.insert(LinkList{3, (LinkList*)(&(*index_ll.find(2)))}); show(ill); return 0; } Would (LinkList*)(&(*index__ll.find(value))) be the recommended way to fetch the pointer to parent?
Amit Prakash Ambasta <amit.prakash.ambasta <at> gmail.com> writes:
Consider the following code snippet:
[...]
struct LinkList;
struct LinkList { size_t index; LinkList* parent; LinkList(size_t index, LinkList* parent) : index(index), parent(parent) {} };
struct llindex {};
typedef ordered_unique< tag<llindex>, member<LinkList, size_t, &LinkList::index>
LinkListIndex; typedef boost::multi_index_container< LinkList, indexed_by<LinkListIndex> IndexedLinkList;
[...]
int main() { IndexedLinkList ill; auto &index_ll = ill.get<0>();
ill.insert(LinkList{0, nullptr}); ill.insert(LinkList{1, (LinkList*)(&(*index_ll.find(0)))}); ill.insert(LinkList{2, (LinkList*)(&(*index_ll.find(0)))}); ill.insert(LinkList{3, (LinkList*)(&(*index_ll.find(2)))});
show(ill); return 0; }
Would (LinkList*)(&(*index__ll.find(value))) be the recommended way to fetch the pointer to parent?
Depends on the context. If you're inserting the elements in sequential ordering (i.e. the newly inserted element is linked to the last one), then this is faster as you don't do any lookup: auto it=ill.insert(LinkList{0, nullptr}).first; it=ill.insert(LinkList{1, (LinkList*)(&*it)}).first; it=ill.insert(LinkList{2, (LinkList*)(&*it)}).first; it=ill.insert(LinkList{3, (LinkList*)(&*it)}).first; Maybe you can provide some more info on the purpose of the structure you're buliding here? Boost.MultiIndex might help further. For instance, this is a list-like structure quicky searchable by index: typedef boost::multi_index_container< node, indexed_by< sequenced<>, ordered_unique<member<node,int,&node::index>> > > IndexedLinkList; void show(const IndexedLinkList& ill) { for(auto begin=ill.begin(),first=begin,last=ill.end(); first!=last;++first){ if(first!=begin){ auto prior=first;--prior; std::cout<<"Index<"<<first->index<<">: " <<prior->index<<std::endl; } else{ std::cout<<"Index<"<<first->index<< ">: " <<"NULL"<<std::endl; } } } int main() { IndexedLinkList ill={{0},{1},{2},{3}}; show(ill); return 0; } Also, a simple random_access index might be sufficient if you only want to know the position of the element and access by position in constant time. Joaquín M López Muñoz Telefónica
Hi, The structure I'm building is to hold a graph. However, since I need to only perform lookups on the nodes via multiple indices, I'm using a struct with a pointer to parent as a member and Boost.MultiIndex to instances. Elements are not necessarily inserted in sequential order. However, there is some strict ordering in insertion (child elements can not be inserted before parent elements) The expression ill.insert(LinkList{1, (LinkList*)(&(*index_ll.find(0)))}); here inserts a new node with index in the graph with a parent whose index is 0. Hence I am trying to convert the iterator to container of LinkList via index_ll.find(0) to a pointer to LinkList instance.. i.e. LinkList const& parent = *index_ll.find(0); ill.insert(LinkList{1, (LinkList*)(&(*parent))}) On Wed, Dec 30, 2015 at 4:21 PM Joaquin M Lopez Munoz <joaquin@tid.es> wrote:
Amit Prakash Ambasta <amit.prakash.ambasta <at> gmail.com> writes:
Consider the following code snippet:
[...]
struct LinkList;
struct LinkList { size_t index; LinkList* parent; LinkList(size_t index, LinkList* parent) : index(index), parent(parent) {} };
struct llindex {};
typedef ordered_unique< tag<llindex>, member<LinkList, size_t, &LinkList::index>
LinkListIndex; typedef boost::multi_index_container< LinkList, indexed_by<LinkListIndex> IndexedLinkList;
[...]
int main() { IndexedLinkList ill; auto &index_ll = ill.get<0>();
ill.insert(LinkList{0, nullptr}); ill.insert(LinkList{1, (LinkList*)(&(*index_ll.find(0)))}); ill.insert(LinkList{2, (LinkList*)(&(*index_ll.find(0)))}); ill.insert(LinkList{3, (LinkList*)(&(*index_ll.find(2)))});
show(ill); return 0; }
Would (LinkList*)(&(*index__ll.find(value))) be the recommended way to fetch the pointer to parent?
Depends on the context. If you're inserting the elements in sequential ordering (i.e. the newly inserted element is linked to the last one), then this is faster as you don't do any lookup:
auto it=ill.insert(LinkList{0, nullptr}).first; it=ill.insert(LinkList{1, (LinkList*)(&*it)}).first; it=ill.insert(LinkList{2, (LinkList*)(&*it)}).first; it=ill.insert(LinkList{3, (LinkList*)(&*it)}).first;
Maybe you can provide some more info on the purpose of the structure you're buliding here? Boost.MultiIndex might help further. For instance, this is a list-like structure quicky searchable by index:
typedef boost::multi_index_container< node, indexed_by< sequenced<>, ordered_unique<member<node,int,&node::index>> > > IndexedLinkList;
void show(const IndexedLinkList& ill) { for(auto begin=ill.begin(),first=begin,last=ill.end(); first!=last;++first){ if(first!=begin){ auto prior=first;--prior; std::cout<<"Index<"<<first->index<<">: " <<prior->index<<std::endl; } else{ std::cout<<"Index<"<<first->index<< ">: " <<"NULL"<<std::endl; } } }
int main() { IndexedLinkList ill={{0},{1},{2},{3}}; show(ill); return 0; }
Also, a simple random_access index might be sufficient if you only want to know the position of the element and access by position in constant time.
Joaquín M López Muñoz Telefónica _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Amit Prakash Ambasta <amit.prakash.ambasta <at> gmail.com> writes:
Hi, The structure I'm building is to hold a graph. However, since I need to only perform lookups on the nodes via multiple indices, I'm using a struct with a pointer to parent as a member and Boost.MultiIndex to instances.
Elements are not necessarily inserted in sequential order. However, there is some strict ordering in insertion (child elements can not be inserted before parent elements)
I think I understand. If there can be more than one children to the same parent (i.e. if parent->child arrows don't form a linear sequence) then no index can substitute for the kind of design you have.
[...] Hence I am trying to convert the iterator to container of LinkList via index_ll.find(0) to a pointer to LinkList instance..
i.e. LinkList const& parent = *index_ll.find(0); ill.insert(LinkList{1, (LinkList*)(&(*parent))})
The cast is ugly an potentially dangerous, as you can modify a key of an element via a non-const LinkList*, thus breaking the container invariants (this is why Boost.MultiIndex iterators are constant). If your design can handle const pointers to parent: struct LinkList { size_t index; const LinkList* parent; //... }; then no cast is needed. Other than this, your technique works as long as you play nicely with keys. Joaquín M López Muñoz Telefónica
participants (2)
-
Amit Prakash Ambasta
-
Joaquin M Lopez Munoz