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-27 15:36:48

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

I think the solution is much less complex than a solution that requires 
locks and atomics. It looks more complex from the outside though, I 
agree.
Moreover, we do not come in the situation that we have a change of the 
data structure in a const-environment.