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

Subject: Re: [boost] [flat_set] When to sort?
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-03-28 19:51:43

El 26/03/2017 a las 5:02, Vladimir Batov via Boost escribió:
> I've been using boost::container::flat_set with quite a success until 
> recently when I profiled my app to see that 30-50% of the run-time was 
> spent in insert() for a container of around 50,000 in size. [...]

For what it's worth, I wrote something about this very problem at

https://bannalia.blogspot.com/2015/06/design-patterns-for-invariant-suspension.html

The solution I like the most is the one dubbed "external invariant 
suspension". The idea is that the
container (flat_set in this case) transfer its underlying buffer out for 
fast insertion and
sorts it once when this is moved in back:

flat_set<int> s;
...
std::vector<int> buf=s.get_data(); // move, s becomes empty
for(...)buf.push_back(...); // populate
s.accept_data(buf); // move and sort

This is maximally efficient as the data is moved rather than copied, and 
flat_set invariant
(namely its elements are sorted) is kept all the time, so there's no 
need to sort on begin()
etc.

Just my two cents,

Joaquín M López Muñoz