On Wed, 12 Feb 2025 at 13:13, Jonathan Wakely <cxx@kayari.org> wrote:


On Wed, 12 Feb 2025 at 13:13, Sebastian Wittmeier via Std-Proposals <std-proposals@lists.isocpp.org> 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@lists.isocpp.org>
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@gmail.com>;
CC: Jonathan Wakely <cxx@kayari.org>; C++ Proposals <std-proposals@lists.isocpp.org>; Bo Persson <bo@bo-persson.se>;
--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals