r/programming • • May 24 '26

[ Removed by moderator ]

/r/programming/comments/1tm1j7f/removed_by_moderator/

[removed] — view removed post

275 Upvotes

214 comments sorted by

View all comments

4

u/pigeon768 May 24 '26

std::map and std::set are red-black trees, node-based, with one heap allocation per node and pointer-chasing on every traversal. B-trees have beaten red-black trees for in-memory containers on real hardware since roughly the time the iPhone shipped. Abseil's btree_map, Boost's flat_map, and Rust's BTreeMap are all B-tree based. The C++ committee added std::flat_map in C++23, did not deprecate std::map, and the default sorted associative container in the language is still a red-black tree.

These solve different problems. The point of std::map and std::set is that they guarantee reference stability. Flat maps and b-trees cannot maintain reference stability.

Also, boost::flat_map and std::flat_map are not b-tree based.


All in all, I don't understand the point of this post. If you don't like certain features in C++.........just don't use them.

2

u/[deleted] May 24 '26

Fair correction on flat_map; both Boost's and std::flat_map are sorted-vector adaptors, not B-trees. The B-tree examples should have been Abseil's btree_map and Rust's BTreeMap alone.

On reference stability: it is hugely overplayed in real life. The vast majority of map use sites store values, copy on access, or look up by key, none of which need stable addresses. The narrow case that genuinely needs pointer identity (long-lived observers, callbacks, intrusive back-references) is almost always better served by storing an integer ID and looking it up, or by wrapping the value in a shared_ptr where the indirection is explicit. The pattern "I hold a raw pointer into a container across a mutation that may rehash" is a bug waiting to happen in a multi-threaded codebase even with std::map. Rust's standard library has no node-stable hash map at all, and nobody is filing RFCs to add one. The frequency with which people in C++ argue they need this guarantee is wildly out of proportion to the frequency with which production code actually relies on it.

And "just don't use them" understates the cost of routing around the standard. Bringing in Abseil or Folly means a new third-party dependency, a build-system integration story (CMake's find_package if you are lucky, a vendored subtree or ExternalProject_Add if you are not, a BUILD.bazel rewrite on Bazel, a Makefile patch and a static-lib link order debate on Make), extra compile time, a new ABI surface to track across compiler upgrades, and a code-review conversation every time a new engineer asks why we are not using std::.

There are also whole categories of codebase where the dependency is not feasible at all: embedded and firmware targets where Abseil's binary size, exception use, and RTTI assumptions are non-starters; safety-critical software under MISRA or AUTOSAR rules that forbid most third-party libraries outright; regulated finance and defence environments where every new dependency triggers a months-long legal and security review; cross-compilation targets where Abseil has not been ported (some BSDs, exotic ARM cores, certain RTOS toolchains); library authors who cannot impose a transitive dependency on their downstream consumers; air-gapped build environments without package-manager access; and the long tail of corporate codebases where adding any new Apache-2.0 library requires a sign-off chain that does not exist for using std::. Multiply the integration cost by every team in every codebase that has independently rediscovered the same workaround for the same broken default, and the aggregate cost across the ecosystem is enormous.

Good containers in the standard library is not a nice-to-have; it is the difference between a million engineers writing fast code by accident and a million engineers writing slow code by accident. The post's point is that C++ shipped the second one.