When to Use `absl::btree_map` vs `absl::flat_hash_map` in C++: A Complete Guide

You should choose absl::btree_map when you need sorted order and range queries, and absl::flat_hash_map when you need O(1) average lookups with no ordering requirements.

The Abseil C++ library provides two high-performance alternatives to standard associative containers: absl::btree_map and absl::flat_hash_map. Both implement the map interface, but they differ fundamentally in their underlying data structures, algorithmic guarantees, and memory layouts. Understanding these differences is critical for selecting the right container for your specific performance and functionality requirements.

Fundamental Differences Between btree_map and flat_hash_map

Data Structure and Ordering

absl::btree_map implements a B-tree structure that maintains keys in sorted order, enabling in-order traversal and range-based queries. According to the source code in absl/container/btree_map.h (lines 19-30), this container serves as "a more efficient replacement for std::map" while preserving lexicographic ordering.

In contrast, absl::flat_hash_map uses a Swiss-table hash map implementation that stores elements in an unordered, flat array. As noted in absl/container/flat_hash_map.h (lines 19-23), this is designed as "a more efficient replacement for std::unordered_map" with no guarantees about iteration order.

Algorithmic Complexity

absl::btree_map provides O(log N) complexity for insert, erase, and lookup operations due to the B-tree's logarithmic height. This predictable performance makes it ideal for latency-sensitive applications where worst-case guarantees matter.

absl::flat_hash_map offers amortized O(1) average complexity for the same operations, though degenerate cases with hash collisions can degrade to O(N). The implementation in absl/container/internal/raw_hash_map.h optimizes for cache locality when performing point lookups.

Cache Locality and Memory Layout

absl::btree_map stores elements in nodes of approximately 256 bytes each (the default node size), reducing pointer chasing compared to red-black trees while still requiring a few cache misses per operation. This makes it more efficient than std::map but less cache-friendly than hash-based alternatives.

absl::flat_hash_map stores key-value pairs contiguously in a single array, providing exceptional cache locality especially for small POD types. The Swiss-table design minimizes per-element overhead while maintaining probing efficiency.

When to Choose absl::btree_map

Select absl::btree_map when your workload requires any of the following capabilities:

• Sorted iteration over keys
• Range queries using lower_bound(), upper_bound(), or equal_range()
• Deterministic ordering for serialization or reproducible testing
• Stable lexicographic ordering for merging sorted data streams

The implementation in absl/container/internal/btree.h handles node splitting and balancing automatically, making it suitable for algorithms that rely on key ordering.

#include "absl/container/btree_map.h"
#include <iostream>
#include <string>

void range_query_example() {
  absl::btree_map<int, std::string> ordered;
  ordered.emplace(10, "ten");
  ordered.emplace(5, "five");
  ordered.emplace(20, "twenty");

  // Sorted iteration: guaranteed order 5, 10, 20
  for (const auto& kv : ordered) {
    std::cout << kv.first << " => " << kv.second << '\n';
  }

  // Efficient range query: find all keys in [6, 15)
  auto it = ordered.lower_bound(6);    // points to key 10
  auto end = ordered.upper_bound(15); // points to key 20
  
  for (; it != end; ++it) {
    std::cout << "In range: " << it->first << '\n';
  }
}

When to Choose absl::flat_hash_map

Choose absl::flat_hash_map for workloads dominated by point lookups and fast insertion where ordering is irrelevant:

• High-frequency key lookups with O(1) average performance
• Small key/value types that benefit from tight packing in contiguous memory
• Minimal per-element overhead requirements
• Workloads with many insert/erase operations where average-case speed matters

The Swiss-table implementation in absl/container/internal/raw_hash_map.h provides excellent performance for hash-based retrieval without the memory indirection of node-based containers.

#include "absl/container/flat_hash_map.h"
#include <iostream>
#include <string>

void fast_lookup_example() {
  absl::flat_hash_map<std::string, int> dict;
  dict["apple"] = 3;
  dict["banana"] = 5;
  dict.emplace("cherry", 2);  // O(1) average insert

  // Fast O(1) average lookup
  if (auto it = dict.find("banana"); it != dict.end()) {
    std::cout << "Banana count: " << it->second << '\n';
  }

  // Reserve space to avoid rehashing during bulk inserts
  dict.reserve(10000);
}

Iterator Invalidation and Reference Stability

Understanding iterator invalidation rules is crucial for long-lived references:

absl::btree_map: Insertion or deletion operations invalidate all iterators, pointers, and references to elements. This occurs because B-tree rebalancing may move elements between nodes.

absl::flat_hash_map: Rehashing invalidates all iterators, pointers, and references when the table grows. However, erase() operations do not invalidate other iterators—only the erased element's iterator becomes invalid.

If your application requires stable references to elements while modifying the container, neither container provides full stability, but flat_hash_map offers more granular invalidation semantics during erasure.

Summary

• Choose absl::btree_map when you need sorted order, range queries, or deterministic iteration for algorithms that rely on key comparison.
• Choose absl::flat_hash_map when you need O(1) average lookups, minimal memory overhead for small types, and high cache locality for unordered data.
• Both containers live in absl/container/ (btree_map.h and flat_hash_map.h respectively) and provide STL-compatible interfaces for easy migration.
• For hybrid workloads requiring both fast lookups and occasional sorting, maintain a flat_hash_map as the primary store and create temporary btree_map snapshots when ordering is required.

Frequently Asked Questions

Can I replace std::map with absl::btree_map as a drop-in replacement?

Yes, absl::btree_map is designed as a direct replacement for std::map according to the class comment at line 19 of absl/container/btree_map.h. It provides the same interface including lower_bound, upper_bound, and ordered iteration, but with better cache efficiency due to B-tree node packing. Simply change the type name and include the Abseil header—most code will compile without modification.

Is absl::flat_hash_map thread-safe?

No, absl::flat_hash_map is not thread-safe by default. Like the standard library containers, concurrent read operations are safe, but any concurrent write (insert, erase, or clear) requires external synchronization. The underlying Swiss-table implementation in absl/container/internal/raw_hash_map.h does not provide internal locking mechanisms, so you must use mutexes or other synchronization primitives for concurrent access.

How do I choose between btree_map and flat_hash_map for a hybrid workload?

If your application primarily performs point lookups but occasionally requires sorted output, use absl::flat_hash_map as the primary container and construct a temporary absl::btree_map when ordering is needed. This approach leverages the O(1) lookup speed for your hot path while accepting the O(N log N) cost of building the ordered view only when necessary. Avoid using btree_map for the primary store if fewer than 10% of operations require range queries.

What is the memory overhead difference between these containers?

absl::btree_map incurs per-node overhead (metadata for each 256-byte node) but can be more space-efficient for large payloads because multiple elements share node space. absl::flat_hash_map has minimal per-element metadata but allocates extra slots for deleted/empty entries to maintain open addressing, which inflates capacity by approximately 12.5-50% depending on load factor. For small POD types (under 16 bytes), flat_hash_map typically uses less total memory, while btree_map scales better with larger value types.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}