Boost logo

Boost :

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?


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk