Oswin Krause wrote: ...
I think the issue is that you use the wrong insert method. a single insert is O(N)...
flat_set has range-insert: ... inserting a range of size K in a flat_set of size N should have complexity O(K log(K) + K+N) in the first case (implementable as: copy all new elements to the end, sort the new elements and perform an inplace-merge).
In the use case the elements may come one by one. To use range insert, you'll have to buffer them until lookup is needed, then insert them at once. This is exactly what Vladimir has been suggesting that flat_set ought to do itself. Insert elements at the end, when lookup is needed, merge them into place. 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.)