[PR #15089] [MERGED] Introduce til::linear_flat_set #30400

Open
opened 2026-01-31 09:40:37 +00:00 by claunia · 0 comments
Owner

📋 Pull Request Information

Original PR: https://github.com/microsoft/terminal/pull/15089
Author: @lhecker
Created: 4/3/2023
Status: ✅ Merged
Merged: 4/4/2023
Merged by: @lhecker

Base: main ← Head: dev/lhecker/til-flat-set


📝 Commits (7)

  • 567550a Introduce til::linear_flat_set
  • 42d6bd2 Vastly simplified the code
  • 0bde3b0 Address feedback
  • c0e12c0 Merge remote-tracking branch 'origin/main' into dev/lhecker/til-flat-set
  • 837a6d3 Fix spelling
  • 535ce8f Fix x86 build
  • 3b8eb13 Use std::hash

📊 Changes

6 files changed (+222 additions, -0 deletions)

View changed files

📝 .github/actions/spelling/expect/expect.txt (+1 -0)
➕ src/inc/til/flat_set.h (+141 -0)
➕ src/til/ut_til/FlatSetTests.cpp (+68 -0)
📝 src/til/ut_til/til.unit.tests.vcxproj (+1 -0)
📝 src/til/ut_til/til.unit.tests.vcxproj.filters (+1 -0)
📝 tools/ConsoleTypes.natvis (+10 -0)

📄 Description

til::linear_flat_set is a primitive hash map with linear probing.
The implementation is slightly complicated due to the use of templates.
I've strongly considered just writing multiple copies of this class,
by hand since the code is indeed fairly trivial but ended up deciding
against it, because this templated approach makes testing easier.

This class is in the order of 10x faster than std::unordered_map.


🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.

## 📋 Pull Request Information **Original PR:** https://github.com/microsoft/terminal/pull/15089 **Author:** [@lhecker](https://github.com/lhecker) **Created:** 4/3/2023 **Status:** ✅ Merged **Merged:** 4/4/2023 **Merged by:** [@lhecker](https://github.com/lhecker) **Base:** `main` ← **Head:** `dev/lhecker/til-flat-set` --- ### 📝 Commits (7) - [`567550a`](https://github.com/microsoft/terminal/commit/567550a6f9d4bb03c4a252efecd5885894a326e2) Introduce til::linear_flat_set - [`42d6bd2`](https://github.com/microsoft/terminal/commit/42d6bd2378bcfd8358b022f730b158bc906a8a09) Vastly simplified the code - [`0bde3b0`](https://github.com/microsoft/terminal/commit/0bde3b0e43802249ba98bf3b79e2ed5834349e6c) Address feedback - [`c0e12c0`](https://github.com/microsoft/terminal/commit/c0e12c0da7692a1197e1d6afc1e846a9f235287f) Merge remote-tracking branch 'origin/main' into dev/lhecker/til-flat-set - [`837a6d3`](https://github.com/microsoft/terminal/commit/837a6d37267cee6e42b5623393b930fb6853a44e) Fix spelling - [`535ce8f`](https://github.com/microsoft/terminal/commit/535ce8f8cbb2498612807d821df3e01972b346a5) Fix x86 build - [`3b8eb13`](https://github.com/microsoft/terminal/commit/3b8eb13c25eaebf366738e91d4a3d97b9c982926) Use std::hash ### 📊 Changes **6 files changed** (+222 additions, -0 deletions) <details> <summary>View changed files</summary> 📝 `.github/actions/spelling/expect/expect.txt` (+1 -0) ➕ `src/inc/til/flat_set.h` (+141 -0) ➕ `src/til/ut_til/FlatSetTests.cpp` (+68 -0) 📝 `src/til/ut_til/til.unit.tests.vcxproj` (+1 -0) 📝 `src/til/ut_til/til.unit.tests.vcxproj.filters` (+1 -0) 📝 `tools/ConsoleTypes.natvis` (+10 -0) </details> ### 📄 Description `til::linear_flat_set` is a primitive hash map with linear probing. The implementation is slightly complicated due to the use of templates. I've strongly considered just writing multiple copies of this class, by hand since the code is indeed fairly trivial but ended up deciding against it, because this templated approach makes testing easier. This class is in the order of 10x faster than `std::unordered_map`. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>
claunia added the pull-request label 2026-01-31 09:40:37 +00:00
Sign in to join this conversation.
No Label pull-request
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: starred/terminal#30400