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

> Decide between absl btree_map vs flat_hash_map in C++ Learn when to use btree_map for sorted order and range queries versus flat_hash_map for O1 average lookups when order doesnt matter

- Repository: [Abseil/abseil-cpp](https://github.com/abseil/abseil-cpp)
- Tags: best-practices
- Published: 2026-07-11

---

**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`](https://github.com/abseil/abseil-cpp/blob/main/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`](https://github.com/abseil/abseil-cpp/blob/main/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`](https://github.com/abseil/abseil-cpp/blob/main/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`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/btree.h) handles node splitting and balancing automatically, making it suitable for algorithms that rely on key ordering.

```cpp
#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`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_map.h) provides excellent performance for hash-based retrieval without the memory indirection of node-based containers.

```cpp
#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`](https://github.com/abseil/abseil-cpp/blob/main/btree_map.h) and [`flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/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`](https://github.com/abseil/abseil-cpp/blob/main/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`](https://github.com/abseil/abseil-cpp/blob/main/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.