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:
>>> 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;
>>>>>>> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk