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

Subject: Re: [boost] [flat_set] When to sort?
From: Chris Glover (c.d.glover_at_[hidden])
Date: 2017-03-28 14:48:50

>
> We have a component in Boost and I presume a
> lot of effort went into producing it. We want it useful and used... but
> I as a user do not seem to be able to find use for it. I found it
> disappointing and disconcerting.
>
>
I personally use flat_map and flat_set all the time. Most of the use cases
I have involve the set and map being essentially immutable once
constructed, and thereafter being used for many lookups. When I build them,
I do so by buffering into a std::vector, sorting the vector, and then
inserting into the map or set using the ordered_unique_t range overload.

This has always been fast enough and is still O(N log N) in total. The only
optimization left to do is to remove the need to copy the contents into the
flat_map/flat_set and instead have the map or set assume ownership of the
underlying container. But this it not the bottleneck -- sorting is -- so it
would be a small gain.

-- chris