El 13/03/2015 a las 16:04, Peter Dimov escribió:
It doesn't have to have an interface, at least in principle. flat_map can just append the new elements to the end, keeping them sorted, until it hits a threshold, then merge. Lookups will first look at the new element range (because those are likely to be in cache), if not found, at the old element range.
That would complicate the container, and break some invariants, like "equal_range". flat_map is designed to cover an scenario for more searches than insertions, maybe another container could be designed for a different scenario.
Actually, the new element range doesn't even need to be kept sorted, if the merge threshold is low, although on the other hand this runs into op< vs op== issues, so maybe not.
You've touched an interesting point. Sort+Merging could improve flat_map performance in some other scenarios. The option to do a merge can be added to a range insertion, current implementation has not very good performance due to excessive data movement. In this scenario we could back-insert, sort and merge. The problem is: -> It requires additional memory (stable_sort is needed for flat_multimap) to achieve O(N·log(N)). inplace_merge requires additional memory to obtain O(N). A user might not want to pay for this (you might need 2x temporary memory). One option is to use the remaining capacity as additional memory by default and optionally add an insertion option that allocates temporary storage to achieve maximum performance. -> we need to reimplement std::sort/std::stable_sort/std::inplace_merge in a Boost.Move-compatible way (using boost::adl_move_swap). It should allow customizing the temporary storage source. Maybe sorting experts would like to implement it in Boost.Move.
Of course, when the underlying vector runs out of capacity, a non-inplace merge will be performed after reallocation.
Upon closer look on the subject line, did I just reinvent a wheel? :-)
Maybe, but everyone should reinvent the wheel at least once in life. It's an great pleasure! Best, Ion