Re: [Boost-users] Lookup on composite key in MultiIndex

Subject: Re: [Boost-users] Lookup on composite key in MultiIndex
From: JOAQUIN M. LOPEZ MUÑOZ (joaquin_at_[hidden])
Date: 2010-12-03 13:44:27

________________________________________
De: boost-users-bounces_at_[hidden] [boost-users-bounces_at_[hidden]] En nombre de Chris Jewell [chris.jewell_at_[hidden]]
Enviado el: viernes, 03 de diciembre de 2010 14:00
Para: boost-users_at_[hidden]
Asunto: [Boost-users] Lookup on composite key in MultiIndex
> 
> Hi All,
> 
> A question about fast lookup on ordered indices, if I may.  I have a data structure:
> 
> struct Individual
> {
>         double I;
>         double N;
>         ...
> }
> 
> I need some way of indexing Individuals such that I can perform queries such as
> "Return the set of Individuals such that Individual::I < T and Individual::N > N". 
> [...]

Hi Chris,

I'm afraid to say that there is no way you can do that with
Boost.MultiIndex: Any lookup operation with Boost.MultiIndex
returns a *contiguous* range of elements, and it is mathematically
impossible to order an arbitrary set of Individual's in a way that
all the sets of the form

  Individual::I < T and Individual::N > N

are contiguous according to the order. These type of bi-dimensional
lookups require (if you want to make them efficiently) some
sort of special data structure such as kd-trees. Otherwise the best
you can do is

  lookup for Individual::I < T
  traverse the returned range and filter elements with Individual::N > N

which is linear in time complexity (but maybe acceptable for your
needs).

HTH,

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