Recent searches
Search options
The standard library provides two unordered containers: std::unordered_map and std::unordered_set (and their multi_ variants that allow multiple instances of the same key).
These containers provide average O(1) complexity for find, insert and erase operations.
Both containers are node-based, typically providing worse performance than 3rd party flat-hash-map implementations.
Compiler Explorer link: https://compiler-explorer.com/z/1sdh7YEx7
@simontoth I think big-O notation isn't entirely useful in anything different container types, specifically because of modern hardware architecture. An O(n) find will likely be consistently faster than an O(1) find *if* the containers are decently small.
There's also runtime performance vs memory performance; sure, hash maps have a constant runtime, but have a significantly increased memory scaling trade-off which I don't think you touched on.