[multi-index] Complex searches, multiple predicates, foreign keys
Hi, I stumbled upon this multi-index example: http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/examples.html#exam... and I do not understand the gains in the second step. To sum up, the example wants to apply two predicates to the search - select elements with the given manufacturer, and select elements that fall in a certain price range. It does so by using one predicate in a first search (for example, finding all elements with the given manufacturer), then taking the range of search results, and copy it to another multi-index container (using pointers to avoid unnecessary deep copying of the elements). Then it performs a second search using the other predicate (in this example, the price range) to further narrow down the range of results. 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? regards
dv
Hi,
I stumbled upon this multi-index example: http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/examples.html#exam... 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_... 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
participants (2)
-
dv -
Joaquin M Lopez Munoz