O(1) or O(no-no-no)
Mastering the unordered_map
In modern C++, std::vector is king. We reach for it as our default, cache-friendly, contiguous sequence. But what happens when your problem doesn't fit a simple array? What is the next container you should reach for?
Lets dives into the data that proves std::unordered_map is the #2 container in modern C++. Its dominance signifies a fundamental shift in application design: the performance-critical need for O(1) average-case key-value lookups.
Join as we move beyond "just use a hash map" and explore the critical, real-world implications of this choice. We'll start by benchmarking the classic std::map (red-black tree) against std::unordered_map (hash table) to understand exactly what you gain—and what you might lose.
However this power comes with risks. An average-case O(1) can quickly degrade to a catastrophic O(n) without warning. We will profile and dissect the actual costs of using a hash map:
- The Hash: What makes a good hash function? We'll go beyond std::hash and see how to write effective, fast hasher.
- The Collision: How do different collision-handling strategies impact performance and memory?
- The Re-hash: What is "load factor," and when does the hidden cost of a full table re-hash destroy your performance gains?
We'll conclude with a practical decision-making framework for when to choose std::unordered_map, when to fall back on the ordered std::map, and how std::string—the container we often forget is a container—fits into this modern landscape.
You will leave this session knowing precisely which data structure to deploy for maximum performance.
Kevin Carpenter
Kevin Carpenter is a Software Engineering Manager at EPX, where he oversees the architecture of real-time transaction processing systems. With 17+ years of deep C++ experience, Kevin has spent the last decade in the financial sector, moving from stochastic financial modeling to low-latency payment networks.
He specializes in the "art of modernization"—evolving established C++ architectures to interoperate seamlessly with new Go-based microservices and emerging payment technologies like Apple Tap to Pay. A passionate advocate for technical excellence, Kevin served as the Technical Editor for C++ Memory Management (Packt) and frequently speaks on tooling and best practices. He is also the Conference Director of SwiftCraft and a key volunteer leader for CppConand C++ on Sea, working to connect developers across the globe.