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

Subject: Re: [boost] [flat_set] When to sort?
From: Oswin Krause (Oswin.Krause_at_[hidden])
Date: 2017-03-27 21:08:18

On 2017-03-27 22:27, Vladimir Batov via Boost wrote:
> On 03/28/2017 03:15 AM, Steven Watanabe via Boost wrote:
>> AMDG
>> 
>> On 03/26/2017 05:03 PM, Vladimir Batov via Boost wrote:
>>> On 03/27/2017 09:20 AM, Andrey Semashev wrote:
>>>> On Mon, Mar 27, 2017 at 12:01 AM, Vladimir Batov via Boost
>>>> 
>>>>>>     flat_set< int > fs;
>>>>>>     fs.reserve(5);
>>>>>>     fs.insert(10);
>>>>>>     auto it1 = fs.begin();
>>>>>>     auto it2 = fs.insert(42).first;
>>>>>>     auto it3 = f2.begin(); // invalidates it1 and it2
>>>>> ...
>> Invalidating it1 may be fine.  Invalidating
>> it2 is a definitely not okay.
> 
> Indeed, nits like the above convince me that taking an ordered vector
> and calling it a set was probably a good-intentions-driven mistake.
> That set-oriented mindset then influenced the set-like api and
> behavior too much (IMO) that in turn affected the performance... the
> original goal of the flat_set.

Could you elaborate? From my point of view the semantics and runtime 
characteristics are exactly what I would expect from a flattened binary 
tree(okay, personally i could do with a different, more cache friendly 
ordering of elements, but my use cases are special). I would find any 
other behaviour surprising.