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

Subject: Re: [boost] [flat_set] When to sort?
From: Vladimir Batov (Vladimir.Batov_at_[hidden])
Date: 2017-03-27 22:59:10

On 03/28/2017 08:08 AM, Oswin Krause via Boost wrote:
> 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.

Well, indeed. :-) Given the prominence of the "set" word in the name I 
do agree that flat_set behavior is what one "would expect from a binary 
tree"... flattened or not (that's an implementation detail IMO). My 
comments are heavily influenced by my current situation that I probably 
happened to be in due to my laziness. I needed a sorted container so I 
initially plugged-in std::set to get things ticking. I had many 
searches/traversals and flat_set promised to do that much better and it 
did... I just did not know I had to pay so much for the initialization. 
So, in the end I had to discard flat_set in favor of a sorted_vector 
container which still does excellent searches/traversals... but does not 
pretend to be a binary tree and as a result saves me heaps of run-time. 
I have a few more flat_set deployments and I am reviewing them all and, 
in fact, replacing them with sorted_vector (aware of the discussed 
behavioral differences). That raised a question -- if flat_set is no 
good for my (seemingly so standard by-the-book) use-cases, then what 
flat_set is good for? That's not a sneer, irony, sarcasm, criticism. 
That's an honest question. 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.