Pointer Stability Guarantees for Abseil Hash Containers: flat vs node vs linked

Abseil's flat_hash_set and flat_hash_map invalidate all pointers, references, and iterators during rehashing, while node_hash_set, node_hash_map, linked_hash_set, and linked_hash_map guarantee stable pointers that remain valid across insertions, erasures, and rehashes.

Understanding pointer stability guarantees is essential when choosing between Abseil's high-performance hash containers in the abseil/abseil-cpp repository. Pointer stability determines whether addresses of stored elements remain valid when the container grows or mutates, directly impacting how you design data structures that hold external references to container elements. Each container variant makes distinct trade-offs between memory locality, performance, and pointer stability guarantees.

flat_hash_set and flat_hash_map: No Pointer Stability

The absl::flat_hash_set and absl::flat_hash_map containers provide no pointer stability guarantees. Any insertion that triggers a rehash—including growth-triggered inserts—invalidates all pointers, references, and iterators to existing elements.

According to the source code comments in [absl/container/flat_hash_set.h](https://github.com/abseil/abseil-cpp/blob/master/absl/container/flat_hash_set.h) (lines 69–71), these containers store elements in-place inside a contiguous backing array. Because this array may be relocated to a new memory address during rehashing, the addresses of elements change unpredictably. This design maximizes cache locality and minimizes memory overhead, but requires treating stored pointers as ephemeral.

node_hash_set and node_hash_map: Guaranteed Pointer Stability

The absl::node_hash_set and absl::node_hash_map containers provide full pointer stability. Pointers, references, and iterators remain valid across insertions, erasures (except for the erased element itself), and rehashes.

The header file [absl/container/node_hash_set.h](https://github.com/abseil/abseil-cpp/blob/master/absl/container/node_hash_set.h) explicitly states on lines 28–30: "if you need pointer stability… a node_hash_set should be your preferred choice." The implementation uses a node-allocated layout via NodeHashSetPolicy, where each element lives in its own heap-allocated node. Relocating the hash table rearranges pointers to nodes rather than moving the nodes themselves, ensuring element addresses remain constant.

linked_hash_set and linked_hash_map: List-Backed Stability

The absl::linked_hash_set and absl::linked_hash_map containers also provide stable pointers and iterators, leveraging an internal std::list to maintain insertion order while providing hash-based lookup.

As documented in [absl/container/linked_hash_set.h](https://github.com/abseil/abseil-cpp/blob/master/absl/container/linked_hash_set.h) (lines 25–27), "Iterators point into the list and should be stable in the face of mutations, except for an iterator pointing to an element that was just deleted." Because std::list nodes never relocate in memory, pointers to elements remain valid until the specific element is erased. This makes linked hash containers ideal when you need both insertion-order iteration and pointer stability.

raw_hash_set Implementation Details

At the foundation of Abseil's hash containers lies absl::container_internal::raw_hash_set, which provides weak pointer stability guarantees. The comment in [absl/container/internal/raw_hash_set.h](https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h) (lines 45–48) explicitly warns: "the pointer to element and iterator stability guarantees are weaker: all iterators and pointers are invalidated after a new element is inserted."

This low-level building block deliberately prioritizes performance over stability. Higher-level containers like flat_hash_set and node_hash_set inherit these characteristics or override them through their specific policies—flat containers expose the instability, while node containers add an indirection layer to provide stability.

Practical Examples: Testing Pointer Stability

The following code demonstrates the behavioral differences between flat, node, and linked hash containers regarding pointer invalidation:

#include "absl/container/flat_hash_set.h"
#include "absl/container/node_hash_set.h"
#include "absl/container/linked_hash_set.h"
#include <iostream>

int main() {
  // -------- flat_hash_set: pointers become invalid after rehash ----------
  absl::flat_hash_set<int> flat;
  flat.reserve(2);
  flat.insert(1);
  const int* p_flat = &*flat.begin();
  std::cout << "flat before rehash: " << *p_flat << "\n";

  flat.insert(2);  // May trigger rehash; p_flat is now dangling!
  // Accessing *p_flat here is undefined behavior.

  // -------- node_hash_set: pointers stay valid across rehash -------------
  absl::node_hash_set<int> node;
  node.reserve(2);
  node.insert(1);
  const int* p_node = &*node.begin();
  std::cout << "node before rehash: " << *p_node << "\n";

  node.insert(2);  // May rehash, but p_node remains valid
  std::cout << "node after rehash: " << *p_node << "\n";

  // -------- linked_hash_set: iterator stability via std::list ------------
  absl::linked_hash_set<int> linked;
  linked.insert(1);
  auto it = linked.begin();
  std::cout << "linked initial: " << *it << "\n";

  linked.insert(2);  // New element does not invalidate existing iterators
  std::cout << "linked after insert: " << *it << "\n";

  linked.erase(2);   // Erasing different element leaves it valid
  std::cout << "linked after unrelated erase: " << *it << "\n";
  
  // Erasing the element itself invalidates only that specific iterator
}

In this example, the flat_hash_set pointer becomes dangling after insertion, while the node_hash_set pointer and linked_hash_set iterator remain valid through mutations.

Summary

• flat_hash_set / flat_hash_map: Offer maximum performance and cache locality but invalidate all pointers, references, and iterators during rehashing operations.
• node_hash_set / node_hash_map: Guarantee pointer stability through node-based allocation, making them ideal for large objects or when external code holds element addresses.
• linked_hash_set / linked_hash_map: Provide pointer stability and insertion-order iteration via an internal std::list backbone.
• raw_hash_set: The underlying implementation explicitly invalidates all pointers and iterators on insertion, with higher-level containers determining whether to expose or override this behavior.

Frequently Asked Questions

Does flat_hash_map invalidate pointers on every insertion?

No, flat_hash_map only invalidates pointers when an insertion triggers a rehash (typically when the load factor exceeds the maximum). Insertions that do not require table growth leave existing pointers valid. However, since you cannot predict which insertions trigger rehashing, you must assume any insertion may invalidate pointers.

When should I choose node_hash_map over flat_hash_map?

Choose node_hash_map when you require pointer stability for elements—such as when storing large, non-movable objects, or when other data structures hold pointers into the container. Choose flat_hash_map when you need maximum performance and memory efficiency and either do not need pointer stability or can refresh pointers after mutations.

Are linked_hash_set iterators stable during rehash?

Yes, linked_hash_set iterators and pointers remain stable during rehashing because the container stores elements in a std::list whose nodes never move in memory. Only erasing the specific element invalidates iterators pointing to that element; other operations, including rehashing and inserting new elements, leave existing iterators valid.

What is the performance cost of pointer stability?

Pointer stability in node_hash_set and node_hash_map comes from heap-allocating individual nodes and storing pointers in the hash table, which reduces cache locality and increases memory overhead compared to the contiguous storage of flat_hash_set. For linked_hash_set, maintaining the doubly-linked list adds pointer overhead per node and slightly slower iteration compared to flat containers, though lookup remains O(1).

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