Effortless Performance Improvements in C++: std:unordered_map
In spite of some technically incorrect statements this is a generally <i>very</i> useful observation and not just in C++: it’s easy to pay for traversal properties you don’t need in an associative data structure. Hash tables and red black trees shine in different applications :)<p>Still pretty low-effort but slightly higher cost and benefit is to switch to more modern data structures that have to break a <i>little</i> backwards compatibility to get big wins. Things like Folly’s F14 and Abseil’s collections (Abseil has both faster hash tables <i>and</i> faster tree-style maps).<p>I think languages like Rust with a little less backwards compatibility burden are shipping with cache-aware and SIMD-exploiting data structures “out of the box” these days, but but my knowledge of e.g. Rust stops short of “read the standard library a bunch of times” so check with someone who has :)