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

Subject: Re: [boost] [flat_set] When to sort?
From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2017-03-26 23:54:11

On Mon, Mar 27, 2017 at 2:03 AM, Vladimir Batov via Boost
<boost_at_[hidden]> wrote:
>
> On 03/27/2017 09:20 AM, Andrey Semashev wrote:
>>
>> On Mon, Mar 27, 2017 at 12:01 AM, Vladimir Batov via Boost
>> <boost_at_[hidden]> wrote:
>>
>>>>> I do not feel those begin() et al will invalidate anything because the
>>>>> first call to, say, begin() will sort the underlying container once.
>>>>> After that it all works as usual, right?
>>>>
>>>> No, not quite.
>>>>
>>>>    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
>>>
>>> Well, I do understand that insertion into a std::vector invalidates the
>>> iterators. I thought you argued (when you said "No, this won't work in
>>> general because...") that "my" approach (of only sorting on when-needed
>>> basis) had different to the flat_set behavior.
>>
>> I did, and the example above shows where your proposed change breaks
>> the previously valid code.
>
>
> I have to disagree with your "proposed change breaks the previously valid
> code" statement. Indeed, given we know the implementation of flat_set, we
> can say that the above code does work with the current flat_set
> implementation. However, the code is not guaranteed to work with the current
> flat_set.  I just re-read flat_set documentation and it does not provide
> such guarantees for emplace() and insert(). IMO there is a difference
> between happens-to-work and guaranteed/valid code. Don't you agree?

Hmm, I've just checked the flat_set reference [1], and this is what it says:

<quote>
flat_set is similar to std::set but it's implemented like an ordered
vector. This means that inserting a new element into a flat_set
invalidates previous iterators and references
</quote>

It does say it invalidates iterators (BTW, the word "previous" here is
misleading; at first I interpreted it as "iterators pointing to
previous elements") but it also says the container works like a
vector. For vector the standard guarantees that if no reallocation
happens on insert then iterators pointing to the elements before the
insertion position are not invalidated ([vector.modifiers]/1). I think
the flat_set documentation is inaccurate and needs to be corrected.

>> How does sort_() handle thread safety? Are you proposing to add a
>> mutex to the container?
>
> Yes, I am/was... Is it a problem? I can't see it being a bottle neck as it
> all will be optimized inside sort_() (no unnecessary locks, etc.).

I'm sorry, but that is a no-go. Too often containers are used with
external locking, and internal locking would just waste performance,
especially in such a hot spot as begin(). BTW, I don't believe any
compiler is able to optimize away unnecessary locking (thank god!)

> In the end I am not trying to say flat_set is broken or anything. My point
> is really simple. IMO I was using flat_set in a fairly conventional way and
> incurred an unexpected and considerable construction overhead. So much so
> that I had to replace flat_set. I personally find it unfortunate. I have
> quite a few more places where I use flat_set in a similar setting -- a
> lengthy elaborate construction followed by much lengthier deployment. My
> use-case seems fairly straightforward... but I had to replace flat_set. If
> so, then I am questioning now where I might need flat_sets? That feels
> hugely unfortunate that a whole chunk of Boost functionality/code (seemingly
> designed for this very purpose) can't be used. Isn't it a concern? Don't you
> agree?

I think flat_set and similar containers work quite well in cases they
are targeted for. The fact that you started to care about the
container initialization simply means that your case is not the one
flat_set is tailored for. That's fine. Just propose a better
alternative for your case.

[1]: http://www.boost.org/doc/libs/1_63_0/doc/html/boost/container/flat_set.html