Subject: Re: [boost] [flat_set] When to sort?
From: Peter Dimov (lists_at_[hidden])
Date: 2017-03-26 14:32:27
Oswin Krause wrote:
> I think the issue is that you use the wrong insert method. a single insert
> is O(N)...
> flat_set has range-insert:
> inserting a range of size K in a flat_set of size N should have complexity
> O(K log(K) + K+N) in the first case (implementable as: copy all new
> elements to the end, sort the new elements and perform an inplace-merge).
In the use case the elements may come one by one. To use range insert,
you'll have to buffer them until lookup is needed, then insert them at once.
This is exactly what Vladimir has been suggesting that flat_set ought to do
itself. Insert elements at the end, when lookup is needed, merge them into
There is another variation of this approach, one I'm sure we've discussed
before: the flat_set keeps the unsorted range at the end and on lookup tries
both, first the unsorted part, then the sorted one. The unsorted part is
merged into place when it exceeds some size. This doesn't do non-const
operations on logically const lookups, but iteration becomes problematic if
iterators have to give you a sorted view. (Although you could keep the
suffix part sorted as well and merge on demand in iter::op++ if so
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk