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-26 23:03:43

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:
>
>>>>> No, this won't work in general because these methods are not supposed
>>>>> to modify the container. In particular, they don't invalidate
>>>>> iterators or references, and calling these methods concurrently is
>>>>> thread-safe.
>>>> 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?
> ...
>>> Also, as I mentioned, multiple threads may me calling begin() or find()
>>> concurrently. These methods must also have const-qualified versions 
>>> to be
>>> able to be used on non-mutable containers.
>> I can't see any of it as a fundamental problem. They all addressed in
>> implementation:
>>
>> template<typename T, typename Sort>
>> struct aux::sorted_vector
>> { ...
>>      iterator       begin ()       { sort_(); return all_.begin(); }
>>      iterator         end ()       { sort_(); return all_.end(); }
>>      const_iterator begin () const { sort_(); return all_.begin(); }
>>      const_iterator   end () const { sort_(); return all_.end(); }
>>      ...
>>
>> the sort_() takes care of sorting (if/when needed) and MT safety.
> 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.).

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?