# Trade-offs Between absl::flat_hash_set and absl::btree_set: Performance and Access Pattern Analysis

> Choosing between absl::flat_hash_set and absl::btree_set? Analyze performance and access patterns. Learn when to use flat_hash_set for O(1) lookups or btree_set for ordered traversal.

- Repository: [Abseil/abseil-cpp](https://github.com/abseil/abseil-cpp)
- Tags: performance
- Published: 2026-07-13

---

**Use `absl::flat_hash_set` for O(1) average lookups and cache-friendly bulk iteration over dense data, and `absl::btree_set` when your workload requires ordered traversal, range queries, or stable iterators across modifications.**

The Abseil C++ library provides high-performance alternatives to standard associative containers, with `absl::flat_hash_set` and `absl::btree_set` serving distinct key access patterns. Understanding the trade-offs between these containers is essential for optimizing applications in the `abseil/abseil-cpp` repository that require either fast random access or ordered key storage. This analysis examines the architectural differences, complexity guarantees, and cache behaviors to help you select the appropriate container for your specific access pattern.

## Core Algorithmic and Memory Layout Differences

### flat_hash_set: Swiss-Table Hashing

In [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h), the container implements a Swiss-table algorithm via `absl::container_internal::RawHashSet`. Keys are stored **contiguously** in a flat array where each slot holds either a key, a deleted marker, or empty state. This layout provides expected **O(1)** average time complexity for lookup, insert, and erase operations, though worst-case performance degrades to O(N) under hash collisions.

The default maximum load factor is approximately **0.8**, meaning the container reserves roughly 1.2–1.5× the raw key size to maintain performance. Full scans iterate over the backing array including empty slots, resulting in **O(capacity)** iteration cost rather than **O(N)**.

### btree_set: B-Tree Node Structure

Defined in [`absl/container/btree_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/btree_set.h), this container builds on `absl::container_internal::BTree` (located in [`absl/container/internal/btree.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/btree.h)). Keys are organized in **nodes** (defaulting to 256 bytes each), with each node storing multiple keys to amortize metadata overhead and reduce pointer chasing. All operations guarantee **O(log N)** worst-case complexity regardless of key distribution.

The node size is tuned to align with CPU cache lines, making range scans significantly more cache-friendly than traditional pointer-based trees like `std::set`. Iteration walks only live keys, maintaining **O(N)** cost proportional to the element count, not allocated capacity.

## Performance Trade-offs for Key Access Patterns

### Point Lookup and Random Access

**flat_hash_set** delivers the fastest point lookups through hash-based addressing, making it ideal for ID caches and membership testing where raw speed dominates. **btree_set** provides logarithmic lookup times but guarantees predictable performance independent of hash quality or collision patterns.

### Iteration Efficiency and Cache Behavior

The flat array of **flat_hash_set** offers superior spatial locality during full container scans, touching approximately one cache line per 8–12 keys depending on key size. This makes it optimal for read-heavy workloads that frequently iterate over the entire set.

**btree_set** traverses node-by-node during iteration, which adds a level of indirection but remains far more cache-efficient than pointer-chasing structures. For sparse sets with many deletions, btree_set iteration is often faster because it skips empty slots, whereas flat_hash_set must check every slot in the backing array.

### Insertion, Deletion, and Rehashing Costs

**flat_hash_set** insertions are cheap provided the load factor remains reasonable, but growth triggers a **full rehash** that copies all elements to a new array and invalidates all iterators and references. **btree_set** insertions and deletions may split or merge nodes but never require global reorganization, limiting iterator invalidation to the affected node only.

## Iterator Stability and Reference Guarantees

Iterator invalidation represents a critical architectural difference for long-running operations. Any rehash or move operation in `flat_hash_set` invalidates **all** iterators and references, as the underlying contiguous array is reallocated in [`absl/container/internal/raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_set.h).

Conversely, `btree_set` maintains iterator stability for unaffected nodes during individual insertions and deletions. Only iterators pointing to the specific node being modified are invalidated, making it suitable for algorithms that traverse and modify containers simultaneously.

## Heterogeneous Lookup Support

Both containers support **heterogeneous lookup** to avoid unnecessary temporary allocations. In `flat_hash_set`, enable this by defining custom `Hash` and `Eq` functors with the `is_transparent` trait. For `btree_set`, use a transparent comparator such as `std::less<>`.

This allows efficient searches using `absl::string_view` against stored `std::string` keys without heap allocations, implemented in both [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h) and [`absl/container/btree_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/btree_set.h).

## Practical Code Examples

### Fast Random Lookups with flat_hash_set

```cpp
#include "absl/container/flat_hash_set.h"
#include <string>
#include <iostream>

int main() {
  absl::flat_hash_set<std::string> cache = {"alpha", "beta", "gamma"};

  // O(1) average lookup
  if (cache.contains("beta")) {
    std::cout << "Found beta\n";
  }

  // Bulk iteration – contiguous storage maximizes cache prefetching
  for (const auto &s : cache) {
    std::cout << s << '\n';
  }

  // Explicitly trigger rehash for capacity planning
  cache.reserve(1000);
}

```

*Key implementation:* [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h) defines `contains()`, `reserve()`, and iteration over the Swiss-table array.

### Ordered Range Queries with btree_set

```cpp
#include "absl/container/btree_set.h"
#include <iostream>

int main() {
  absl::btree_set<int> ids = {5, 1, 9, 3, 7};

  // O(log N) range boundaries
  auto it = ids.lower_bound(4);   // points to 5
  auto end = ids.upper_bound(7);  // points to 9

  std::cout << "Range [4,7]: ";
  for (; it != end; ++it) std::cout << *it << ' ';
  std::cout << '\n';

  // Order-preserving insertion
  ids.insert(6);
}

```

*Key implementation:* [`absl/container/btree_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/btree_set.h) exposes `lower_bound()`, `upper_bound()`, and tree-specific `insert()`.

### Heterogeneous Lookup Implementation

```cpp
#include "absl/container/flat_hash_set.h"
#include "absl/container/btree_set.h"
#include "absl/hash/hash.h"
#include <string>

struct StrHash {
  using is_transparent = void;  // Enables heterogeneous lookup
  size_t operator()(absl::string_view sv) const { return absl::HashOf(sv); }
};

struct StrEq {
  using is_transparent = void;
  bool operator()(absl::string_view lhs, absl::string_view rhs) const {
    return lhs == rhs;
  }
};

// Hash set with transparent lookup
absl::flat_hash_set<std::string, StrHash, StrEq> hset = {"apple", "banana"};
bool has_apple = hset.contains(absl::string_view("apple")); // No allocation

// B-tree with transparent comparator
absl::btree_set<std::string, std::less<>> oset = {"cat", "dog"};
auto it = oset.find(absl::string_view("cat")); // std::less<> is transparent

```

## Key Implementation Files

Understanding the source architecture helps debug performance issues:

- **[`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h)**: Public API wrapper around the Swiss-table implementation, defining the `flat_hash_set` class template and its interface.
- **[`absl/container/internal/raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_set.h)**: Core Swiss-table logic including probing sequences, rehashing strategies, and slot metadata management.
- **[`absl/container/btree_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/btree_set.h)**: Public interface for the B-tree set, inheriting from `btree_set_container`.
- **[`absl/container/internal/btree.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/btree.h)**: Generic B-tree implementation handling node layout (default 256-byte nodes), splitting, merging, and tree balancing.
- **[`absl/container/internal/btree_container.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/btree_container.h)**: Adapter layer providing associative container interfaces (iterators, `find`, `lower_bound`) atop the generic B-tree.
- **[`absl/container/internal/container_memory.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/container_memory.h)**: Shared memory management utilities and allocator handling used by both containers.

## Summary

- **Choose `absl::flat_hash_set`** when your workload demands O(1) point lookups, cache-friendly bulk iteration over dense data, and you can tolerate full rehashes during growth.
- **Choose `absl::btree_set`** when you require ordered traversal, range queries (`lower_bound`, `upper_bound`), predictable O(log N) performance, or stable iterators across modifications.
- **Memory layout** differs fundamentally: flat_hash_set uses contiguous arrays with load factor overhead (~1.2–1.5×), while btree_set uses node-based storage amortized across multiple keys.
- **Iterator invalidation** is total for flat_hash_set during rehash, but localized to affected nodes in btree_set.
- Both containers support **heterogeneous lookup** via transparent functors to minimize allocations during searches.

## Frequently Asked Questions

### When should I choose absl::flat_hash_set over absl::btree_set?

Prefer `absl::flat_hash_set` for random access patterns and bulk iteration where raw lookup speed dominates. Its Swiss-table implementation in [`absl/container/internal/raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_set.h) provides O(1) average access and superior cache locality when scanning dense data sets. However, avoid it if you need ordered traversal or cannot tolerate iterator invalidation during rehashing.

### Does absl::btree_set provide better memory efficiency than absl::flat_hash_set?

For large sets, `absl::btree_set` typically achieves lower per-key overhead because keys are packed into 256-byte nodes amortizing metadata costs. In contrast, `flat_hash_set` maintains a load factor below 0.8, requiring approximately 1.2–1.5× the raw key size to accommodate empty and deleted slots. Small sets may favor flat_hash_set due to node granularity overhead in B-trees.

### What causes iterator invalidation in these containers?

In `flat_hash_set`, any operation triggering a rehash (growth beyond load factor 0.8) or move construction invalidates all iterators and references, as the underlying array is reallocated. In `absl::btree_set`, only iterators pointing to nodes modified by insertion or erasure are invalidated; other iterators remain valid because the tree structure updates localized node pointers without global reorganization.

### Can I use heterogeneous lookup with both containers?

Yes. Both containers support transparent lookups to avoid temporary object construction. For `flat_hash_set`, specialize your hash and equality functors with `using is_transparent = void`. For `btree_set`, use `std::less<>` or a custom transparent comparator. This allows efficient searches using `absl::string_view` against stored `std::string` keys without heap allocations.