________________________________________ 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