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