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.