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-27 05:40:09

On 2017-03-27 10:54, Andrey Semashev wrote:
> 
>>> 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!)

1. There does not have to be "internal locking would just waste 
performance":

void sort_()
{
     if (sorted) return;
     lock
     if (sorted) return;
     ...do actual sorting
}

2. Still, I am not sure how we managed to this point -- std::vector or 
other containers do not provide any MT guarantees. I would not expect 
sorted_vector to be that different.

> I think flat_set and similar containers work quite well in cases they
> are targeted for.

I am not sure I see my use-case as so special. Quite the opposite. 
That's why from the set-go I was wondering if flat_set behavior was 
correct -- it was not performing in my (seemingly standard) use-case.

> 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.

Again, I honestly do not understand what so special about my use-case. 
My container's main usage is traversal and search. That's why I deployed 
flat_set in the first place. I only "started to care about the container 
initialization" after it popped up in the profiler list... Very much 
unexpectedly so. :-)

> Just propose a better
> alternative for your case.

Indeed, the more I think of it the less I am comfortable with 
"flat_set". The intention was probably good to mimic a set. However, 
vector's ears still keep sticking out. So, it seems that sorted_vector 
might be a more honest and not misleading name... And given the benefits 
it offers over a set, it seems quite needed. However, from the 
experience "proposing" is such a daunting one-sided battle. Everyone 
knows how it should be done... but it's you implementing it... and your 
implementation always seems done incorrectly. :-) I am not sure I am up 
for such a battle any more.