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". I'm currently using a MultiIndex that orders the individuals by Individual::I, and therefore gives me fast lookups on the I field. I had thought about creating a composite key on both I and N, and then using the range() method to return iterators to the required individuals. However, I can't seem to find the correct syntax for a predicate for the composite key. Can anyone help me out? Is there a better way to achieve what I need? Thanks, Chris -- Dr Chris Jewell Department of Statistics University of Warwick Coventry CV4 7AL UK Tel: +44 (0)24 7615 0778
________________________________________ De: boost-users-bounces@lists.boost.org [boost-users-bounces@lists.boost.org] En nombre de Chris Jewell [chris.jewell@warwick.ac.uk] Enviado el: viernes, 03 de diciembre de 2010 14:00 Para: boost-users@lists.boost.org 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
On 3 Dec 2010, at 18:44, JOAQUIN M. LOPEZ MUÑOZ wrote:
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).
Hi, Thanks Joaquin, that's very useful to know! Chris -- Dr Chris Jewell Department of Statistics University of Warwick Coventry CV4 7AL UK Tel: +44 (0)24 7615 0778
participants (2)
-
Chris Jewell -
JOAQUIN M. LOPEZ MUÑOZ