Boost logo

Boost :

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

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()

Just my two cents,

Joaquín M López Muñoz

Boost list run by bdawes at, gregod at, cpdaniel at, john at