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