Re: [Boost-users] Pointer to objects in Boost.MultiIndex

Subject: Re: [Boost-users] Pointer to objects in Boost.MultiIndex
From: Amit Prakash Ambasta (amit.prakash.ambasta_at_[hidden])
Date: 2015-12-31 16:08:05

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_at_[hidden]>
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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users