Skip to content

<flat_set>, <flat_map>: compare for equality instead of equivalence for usual types#6024

Merged
StephanTLavavej merged 14 commits intomicrosoft:feature/flat_mapfrom
AlexGuteniev:usual-unique-things
Jan 20, 2026
Merged

<flat_set>, <flat_map>: compare for equality instead of equivalence for usual types#6024
StephanTLavavej merged 14 commits intomicrosoft:feature/flat_mapfrom
AlexGuteniev:usual-unique-things

Conversation

@AlexGuteniev
Copy link
Contributor

@AlexGuteniev AlexGuteniev commented Jan 18, 2026

Resolves #6020

⚙️ Optimization

For usual types, compare for equality, instead of equivalence:

  • For integers this allows using vectorization path for <flat_set>
  • For strings this allows way cheaper comparison, as suggested by @StephanTLavavej
  • For anything if ranges::less or ranges::greater are 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 unique algorithm for that.

⏱️ Benchmark results

Benchmark Before After
flat_map_strings 773 ns 639 ns
flat_set_strings 450 ns 358 ns
flat_map_integers 99.6 ns 100 ns
flat_set_integers 48.0 ns 47.5 ns

🥈 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_map of 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_set of 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.

@AlexGuteniev AlexGuteniev requested a review from a team as a code owner January 18, 2026 09:56
@github-project-automation github-project-automation bot moved this to Initial Review in STL Code Reviews Jan 18, 2026
@cpplearner
Copy link
Contributor

If the comparator is ranges::less or ranges::greater, I think we can assume that _Equivalence_is_equality is true.

(This is because the ranges comparators require the argument types to model totally_ordered_with, which requires that exactly one of bool(a < b), bool(a > b), or bool(a == b) is true and that bool(t < u) is equal to bool(u > t).)

@frederick-vs-ja
Copy link
Contributor

@frederick-vs-ja suggested to take advantage of sorted range, and always perform only one comparison. But we need other unique algorithm for that.

Opened #6027 to track this.

@StephanTLavavej StephanTLavavej removed their assignment Jan 20, 2026
@StephanTLavavej StephanTLavavej moved this from Initial Review to Merging in STL Code Reviews Jan 20, 2026
@StephanTLavavej StephanTLavavej merged commit f7961e7 into microsoft:feature/flat_map Jan 20, 2026
45 checks passed
@github-project-automation github-project-automation bot moved this from Merging to Done in STL Code Reviews Jan 20, 2026
@StephanTLavavej
Copy link
Member

♟️ 🐘 🤴

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

flat_meow C++23 container adaptors performance Must go faster

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants