On Wed, 12 Feb 2025 at 13:13, Jonathan Wakely <cxx_at_[hidden]> wrote:

>
>
> On Wed, 12 Feb 2025 at 13:13, Sebastian Wittmeier via Std-Proposals <
> std-proposals_at_[hidden]> wrote:
>
>> Hi Jonathan,
>>
>> are the additional 18 comparisons by MSVC expected or at least not
>> unexpected?
>>
>
> It's still O(log(n)), so I don't see a problem and didn't bother looking
> into it.
>

Maybe their equal_range does:

return { lower_bound(k), upper_bound(k) };

which gives the right answer, but would actually be 2 x O(log(n)). But it's
still logarithmic, not linear.

After finding the lower bound, the search for the upper bound doesn't need
to consider the entire container, it only needs to search in
[lower_bound(k), end).





>
>
>
>>
>>
>> -----Ursprüngliche Nachricht-----
>> *Von:* Jonathan Wakely via Std-Proposals <std-proposals_at_[hidden]>
>> *Gesendet:* Mi 12.02.2025 13:46
>> *Betreff:* Re: [std-proposals] A Proposal to Add a New Multiset
>> container Method to the Standard Library Technical Report
>> *An:* Александр Поваляев <apovalyaev_at_[hidden]>;
>> *CC:* Jonathan Wakely <cxx_at_[hidden]>; C++ Proposals <
>> std-proposals_at_[hidden]>; Bo Persson <bo_at_[hidden]>;
>>
>>
>> https://godbolt.org/z/E1E5T6daM
>>
>> --
>> Std-Proposals mailing list
>> Std-Proposals_at_[hidden]
>> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>>
>