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

On 03/27/2017 09:20 AM, Andrey Semashev wrote:

On Mon, Mar 27, 2017 at 12:01 AM, Vladimir Batov via Boost 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 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?