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

Subject: Re: [boost] [flat_set] When to sort?
From: Vladimir Batov (Vladimir.Batov_at_[hidden])
Date: 2017-03-26 21:49:41

On 03/27/2017 06:03 AM, Oswin Krause via Boost wrote:
>
>> 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. 

I am sorry but I have to disagree on this one. I can't possibly see it 
as the "easiest way". My use-case (which I do not believe is exotic by 
any stretch of imagination) goes around and cherry-picks the elements 
essentially one-by-one. So, having another container to populate feels 
like a huge hassle. I thought the whole idea of flat_set was to get the 
benefits without the hard work. :-) If I have to have such a container 
to begin with, I might not need flat_set at all as I'd be then 
transferring straight into std::vector, right?

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

That feels quite complex... what is wrong with my (seemingly) simple 
suggestion of sorting on when-needed basis?