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

On Mon, Mar 27, 2017 at 2:03 AM, 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 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