Re: [boost] [flat_set] When to sort?

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 
place.

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 
inclined.)