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.