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

Subject: Re: [boost] [flat_set] When to sort?
From: Oswin Krause (Oswin.Krause_at_[hidden])
Date: 2017-03-26 19:03:30

Hi,

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

This would have consequences both in asymptotic run time (lookups are 
O(log(N)+K) where K is the maximum allowed size of the unsorted region) 
as well as constants (more complex code, more ifs etc). If K is 
independent of N, we would still have overall quadratic time of 
inserting a lot of elements using insert(single_element). So this does 
not help.

What I meant with my previous comment: it is probably the easiest way 
just to buffer all elements to be inserted in an intermediate storage 
area and then insert them at once. Of course we might not want to use 
the current insert for this as this would require storing all new 
elements. Here is my approach to this:

flat_set maintains an array and three iterators(set_begin, set_end and 
vector_end). the range [set_begin,set_end) contains all inserted 
elements and size() begin(), end() will only return this range. the 
range [set_end, vector_end) contains all newly inserted elements, 
however they´are still "staging" and will not show up unless the 
flat_set is told to.

so we would add two new methods

staging_insert(single_element)//pushes element to the back of the 
staging area
sort_staging()//calls sort() on the old range. afterwards 
set_end=staging_end.