<flat_set>, <flat_map>: compare for equality instead of equivalence for usual types#6024
Merged
StephanTLavavej merged 14 commits intomicrosoft:feature/flat_mapfrom Jan 20, 2026
Merged
Conversation
Contributor
|
If the comparator is (This is because the |
This reverts commit 367a29a.
Contributor
Opened #6027 to track this. |
StephanTLavavej
approved these changes
Jan 20, 2026
Member
♟️ 🐘 🤴 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Resolves #6020
⚙️ Optimization
For usual types, compare for equality, instead of equivalence:
<flat_set>ranges::lessorranges::greaterare used, as @cpplearner suggested, other types with string-like situation may benefit too@frederick-vs-ja suggested to take advantage of sorted range, and always perform only one comparison. But we need other
uniquealgorithm for that.⏱️ Benchmark results
🥈 Results interpretation
Most of the time is spent on sorting the inserted data, yet some is spent on making it unique, so the improvement can be observed, but it is limited.
For strings this played out well.
For integers there's no improvement seen with the current benchmark.
flat_mapof integers is not improved, because the compiler is able to replace equivalence with equality on its own; and even if it wouldn't, the difference would be very minor anyway.flat_setof integers goes the vectorized path, but the benchmark needs more pieces to make vectorization beneficial. And with more pieces, the sorting would consume even greater portion of time, due to above-linear complexity.So looks like this is useless for integers, but strings still benefit from this.