Boost logo

Boost Users :

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>> writes:

> Hi,
> I stumbled upon this multi-index example:
> 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:

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at