Boost logo

Boost :

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.



Boost list run by bdawes at, gregod at, cpdaniel at, john at