Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?

Subject: Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2015-03-19 04:29:06

El 18/03/2015 a las 22:37, Mathias Gaunard escribió:

>
> How is that any different from the following?
>
> flat_set S;
> flat_set b;
> b.insert(xxx);
> b.insert(yyy);
> S.insert_sorted(b.begin(), b.end());

Currently you can do this:

S.insert(ordered_unique_range, b.begin(), b.end());

It's more efficient that a loop inserting one by one, but it still can 
be improved. If:

- distance(b.begin(), b.end()) == M and
- S.size() == N

currently (Boost 1.58) it does MlogN comparisons and at most N + M 
moves/copies for Bidirectional Iterators. It allocates extra memory for 
that (memory for insertion positions/indexes that allow linear 
move/copies when inserting M objects in those positions.

Currently I'm working on vector::merge/merge_unique functions that need 
N + M comparisons and moves, while trying to minimize extra memory (if 
vector memory needs to be reallocated because S.capacity() < N + M, it 
uses a std::merge variant to achieve O(N). I plan this improvement for 
Boost 1.59. If there is enough room in current vector memory for to 
store N elements plus indexes, it achieves also O(N) without allocating 
a new buffer. An optional refinement would be to fallback to MlogN 
(using binary search) instead of N+M comparisons when N >> M.

I have plans to improve non-ordered range insertion to achieve optimal 
complexity but that requires storing and sorting (stable sorting for 
non-unique containers) the range [b.begin(), b.end()) in auxiliary 
memory, and then merging the newly ordered M elements with already 
stored N elements. Using std::stable_sort/sort + 
std::merge/inplace_merge is not optimal as they require additional data 
movements and memory allocations (e.g. memory from 
get_temporary_storage() is not reused). Since this optimal solution 
requires reimplementing stable_sort/sort/inplace_merge adding support 
for external temporary storage and Boost.Move I don't think it's 
feasible in the short term.

Best,

Ion