Re: [Boost-users] [Multi-index] Sorted range selection

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2005-12-29 11:01:48

Hello Tamas,

----- Mensaje original -----
De: Tamas Szepes <tamas.szepes_at_[hidden]>
Fecha: Miércoles, Diciembre 28, 2005 9:11 pm
Asunto: [Boost-users] [Multi-index] Sorted range selection

> Hi All,
> 
> I'm learning to use the multi-index library by rewriting an 
> existing STL 
> based code.
> I'm storing rectangles (X, Y, Width, Height, ...) in a set ordered 
> by a
> composite key on X, Y.
> 
> What is the best way to select rectangles where X has a certain 
> value and
> sort the result by Width? Can I use a sorted indice on Width, or I 
> must sort
> the range? I also thought to create a composite key on X and 
> Width, but
> sorting order is run time determined and I have a dosen other 
> properties.

Your analysis is correct. I'm afraid you have to externally sort
the interval returned by range(), pseudocode follows:

std::vector<boost::reference_wrapper<const Rectangle> > rng;
std::pair<
  YourCompositeKeyIndex::iterator,
  YourCompositeKeyIndex::iterator> p=
  yourcompositekeyindex.range(...);
while(p.first!=p.second)rng.push_back(boost::cref(*p.first++));
std::sort(rng.begin(),rng.end(),WidthCompare());

Having a composite key on (X,Width) is also an option,
but as you say the number of combinations might be too large,
and manipulating those indices with run-time decisions is
not trivial. So, my suggestion is to follow the scheme
proposed on the pseudocode above.

> I'm realy looking for the possibility to mimic SQL's ORDER BY clause.

Well, Boost.MultiIndex does not aim to provide complete
functionality for relational stuff, as stated explicitly in
the rationale at http://boost.org/libs/multi_index/doc/tutorial.html.
The idea is to keep Boost.MultiIndex application-agnostic and
more focused on the STL conceptual framework.
As I see it, this kind of funcionality could be better served
by a relational-specific lib built on top of Boost.MultiIndex.
There are currently two libs approaching this goal,
Arkadiy Vertleyb's RTL and Calum Grant's RML (look for those
on recent discussions on the Boost list.) Unfortunately,
neither of these libs actually uses internally Boost.MultiIndex,
but this is another story :)

> 
> Thanks for any help in advance,

I'm sorry I can't be more helpful. Thanks for using
Boost.MultiIndex and please come back if you have further
problems or want to comment on proposals for enhancements of
the library.

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