Re: [Boost-users] [multi-index] Complex searches, multiple predicates, foreign keys

Subject: Re: [Boost-users] [multi-index] Complex searches, multiple predicates, foreign keys
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2011-06-07 15:52:42

dv <dv <at> pseudoterminal.org> writes:

> 
> Hi,
> 
> I stumbled upon this multi-index example: 
> http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/examples.html#example6
> and I do not understand the gains in the second step.
> 
> [...]
> 
> It is this copying and creating of the 2nd container that bugs me. Isn't 
> this unnecessary? It implies O(n) steps to insert the search results, n 
> being the number of results from the 1st search. Then, why use a second 
> multi-index container? Why shouldn't I just use remove_copy_if() 
> instead? it would make sense if copying the subset into a new 
> multi-index container were faster than O(n), but I doubt that. What do 
> you think?

Copying the subset into the the view is actually slower than
O(n) --it is O(n log n). The example aims to show how to take
advantage of some advanced functionalities of the key extractors
provided by the library:

 
http://boost.org/libs/multi_index/doc/tutorial/key_extraction.html#advanced_key_extractors

and it's certainly not optimal in terms of efficiency. Using
remove_copy_if or something similar as you suggest is faster
(with the only difference that results won't be sorted).

Thanks for pointing this out --an example is, well, an example,
not a production program, and example 6 is in this sense
admittedly somewhat clumsy.

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