Re: [Boost-users] walk thru multi_index

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2006-02-02 04:29:18

Hello Dmitriy,

Dmitriy Bure ha escrito:

> Hello,
> I'm very interested to use multi_index container in my work. But
> didn't found much documentation and\or examples. Maybe anyone could
> suggest a place to find it?

I assume you already have visited the official documentation page at

http://boost.org/libs/multi_index/

Other than this, I don't think you will find more info on
Boost.MultiIndex on the net.
Do you find the aforementioned docs insufficient? I'm open to
suggestions for
improvement.

>
> Basically now I'm trying to implement probably very simple thing.
> There is basic structure:
>
> struct AvNode
> {
>   CNode* var;
>   int context;
>   MemoryPlace location;
>   ...
> };
>
> And I'd like to have multi_index container with such nodes (all fields
> are non-equal). Something like this:
>
> typedef multi_index_container<
>   AvNode,
>   indexed_by<
>     ordered_non_unique<
>       tag<varNcontextIndex>,
>       composite_key<
>         AvNode,
>         BOOST_MULTI_INDEX_MEMBER(AvNode,CNode*,var),
>         BOOST_MULTI_INDEX_MEMBER(AvNode,int,context)
>       >
>     >
>   >
> > AvNodeSet;
>
> And then I need to iterate on this container. Better to say that I'd
> like to group elements in container by first two fields. Could you
> help me in this problem? In fact I have one solution but it's too
> large and non-fine:
>

[...]

The loop you propose can be drastically simplified as follows:

for(
  AvNodesSet2VarNcontext::iterator it = avNodes2VarNcontext.begin();
  it != avNodes2VarNcontext.end();
  it =
avNodes2VarNcontext.upper_bound(avNodes2VarNcontext.key_extractor()(*it)))

{
    FOO(make_pair(it->var, it->context));
}

The point here is how using upper_bound() let you jump to the next
different value. Please notice the use of key_extractor(), since in
Boost.MultiIndex
upper_bound() and similar lookup functions do not accept whole elements
(AvNode's in this case) but rather the keys on which the index works on:
so,
"avNodes2VarNcontext.upper_bound(*it)" wouldn't compile. The following
variation is probably simplier to understand, though it incurs some
temporary
object constructions:

for(
  AvNodesSet2VarNcontext::iterator it = avNodes2VarNcontext.begin();
  it != avNodes2VarNcontext.end();
  it =
avNodes2VarNcontext.upper_bound(boost::make_tuple(it->var,it->context)))

{
    FOO(make_pair(it->var, it->context));
}

When invoking upper_bound(), we construct a tuple containing the current

values for the composite key. This latter variation lends itself to easy

modification, for instance the following groups elements only by
the first value of the composite_key (that is, AvNode::var):

for(
  AvNodesSet2VarNcontext::iterator it = avNodes2VarNcontext.begin();
  it != avNodes2VarNcontext.end();
  it = avNodes2VarNcontext.upper_bound(boost::make_tuple(it->var)))
{
    FOO(make_pair(it->var, it->context));
}

Hope this helps. Don't hesitate to come back if you need further help,
and thanks for using Boost.MultiIndex.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo