Exception Safety in `absl::flat_hash_map`: Guarantees and Implementation Mechanisms

Abseil’s flat_hash_map provides a strong exception guarantee for insertions and rehashing, ensuring the container remains unchanged if element construction or allocation fails, while offering no-throw guarantees for swap, move operations, and erasure when destructors are non-throwing.

absl::flat_hash_map is a high-performance hash table implementation in the Abseil C++ library that follows the C++ exception safety guidelines rigorously. This container balances raw speed with predictable failure semantics, making it safe to use in exception-sensitive contexts. Below is a detailed breakdown of the specific guarantees provided and the implementation strategies used to enforce them.

Exception Safety Guarantees by Operation

The Abseil codebase defines distinct exception contracts for each major operation category. These contracts are implemented primarily in absl/container/flat_hash_map.h and the underlying absl/container/internal/raw_hash_set.h.

Construction and Empty States

The default constructor of an empty flat_hash_map is guaranteed not to throw. Because the constructor merely initializes internal pointers without performing any memory allocation, it cannot fail. This no-throw guarantee applies to both the map itself and its internal bucket array initialization.

Insertion Operations (emplace, insert, try_emplace)

Insertions provide a strong exception guarantee: either the element is fully inserted and committed to the container, or the map remains completely unchanged. This is achieved through a two-phase commit strategy:

1. Allocation and Construction Phase: The implementation allocates a new node using std::allocator_traits::allocate and constructs the key/value pair within this temporary node. If allocation fails or the element constructor throws, the temporary node is immediately destroyed and deallocated, leaving the existing bucket array and size counters untouched.

2. Linking Phase: Once construction succeeds, the node is linked into the appropriate bucket. This phase updates only pointer values and cannot throw.

Rehashing and Reserve Operations

Rehashing operations, including those triggered by reserve(), also carry a strong exception guarantee. The implementation in raw_hash_set.h performs the following sequence:

• Allocates a new bucket array without modifying the existing table.
• Moves existing nodes into the new buckets using noexcept move operations (the node type stores only pointers).
• Swaps the new bucket array into place only after all nodes are successfully transferred.

If allocation of the new bucket array throws, the original table remains intact with all elements preserved.

Erasure and Destruction

Erase and clear operations are noexcept, provided that the key and value destructors are noexcept. The implementation unlinks nodes and destroys stored objects without allocating memory. Any exception escaping from a user-provided destructor is not caught by flat_hash_map, consistent with the C++ standard library approach.

Move, Copy, and Assignment

• Move Construction: The move constructor is noexcept (assuming the allocator’s move is noexcept). It transfers internal pointers and size counters without allocating memory or copying elements.

• Copy Construction: The copy constructor can throw. It must allocate a new bucket array and copy each node individually, propagating any allocation or element-construction exceptions.

• Assignment Operator: Implemented via the copy-and-swap idiom, providing a strong guarantee. The right-hand side is copied into a temporary (which may throw), then swapped with the target. The swap itself is noexcept, so the target either receives the new state or retains the original.

Swap Operations

The swap() operation is guaranteed not to throw. It exchanges internal pointers and size counters between two maps. Because all member fields involved are simple POD types, the operation is marked noexcept, enabling optimal code generation and safe usage in other noexcept contexts.

Core Implementation Mechanisms

The exception safety guarantees rely on specific architectural decisions visible in the Abseil source code.

Node-Based Storage Architecture

flat_hash_map stores each key/value pair in a node containing only a pointer to the next node and the payload. This design decouples element storage from the bucket array structure. Nodes are allocated using the map’s configured allocator, allowing the allocator to control exception behavior while the container manages pointer linkage.

Two-Phase Insertion Protocol

As implemented in absl/container/internal/raw_hash_set.h, insertion follows a strict protocol:

• Phase 1: Allocate and construct the element in isolation. Any exception here triggers immediate cleanup of the temporary node.
• Phase 2: Update bucket pointers to include the new node. This is pure pointer manipulation and cannot fail.

This separation ensures that partial insertions cannot corrupt the container’s internal state.

Allocator-Aware Rehashing

During rehashing, the implementation validates each step before committing state changes:

1. Allocate new bucket array (may throw std::bad_alloc).
2. Move nodes using noexcept move semantics.
3. Swap pointer ownership only after successful population.

Because node moves are pointer transfers rather than element copies, they are noexcept, eliminating the risk of rollback complexity during the transfer phase.

Explicit No-Except Specifications

The public API explicitly marks operations that are guaranteed not to throw with noexcept. This includes swap(), the move constructor, and clear(). These specifications enable the compiler to optimize exception handling code and allow the container to be safely used within other noexcept functions or standard library operations that require non-throwing swap semantics.

Practical Code Examples

The following examples demonstrate these guarantees in practice.

Insertion with Strong Guarantee

absl::flat_hash_map<std::string, std::unique_ptr<int>> m;
try {
  // Constructs the pair in a temporary node first.
  // If unique_ptr construction throws, the map remains unchanged.
  m.emplace("answer", std::make_unique<int>(42));
} catch (const std::bad_alloc&) {
  // Allocation failed – map is still empty.
}

Rehashing Without Corruption

absl::flat_hash_map<int, std::string> m;
for (int i = 0; i < 1000; ++i) m[i] = std::to_string(i);

try {
  m.reserve(1'000'000);  // May allocate a large bucket array.
} catch (const std::bad_alloc&) {
  // If allocation fails, m still contains all original elements.
  assert(m.size() == 1000);
}

No-Throw Swap Usage

void process_map(absl::flat_hash_map<int, int> input) noexcept {
  absl::flat_hash_map<int, int> local;
  local.swap(input);  // Guaranteed not to throw.
  // Process local data...
}

Summary

• Insertion (emplace, insert, try_emplace) provides a strong exception guarantee by constructing elements in temporary nodes before linking them into the container.
• Rehash and reserve() operations use a strong guarantee pattern that allocates new storage before abandoning old storage, ensuring no data loss on allocation failure.
• Swap, move construction, and clear are noexcept, enabling safe usage in exception-critical code paths.
• Copy construction and copy assignment may throw during allocation or element copying, but assignment uses copy-and-swap to provide a strong guarantee.
• Erasure is noexcept conditional on the stored types’ destructors being noexcept.

Frequently Asked Questions

What happens if an element constructor throws during insertion?

If the key or value constructor throws, absl::flat_hash_map destroys the partially constructed node and releases its memory without modifying the container’s size or bucket structure. The map remains in exactly the same state as before the insertion attempt, fulfilling the strong exception guarantee.

Is flat_hash_map safe to use in noexcept functions?

Yes, provided you avoid operations that may allocate. Move construction, swap(), clear(), and erase() are explicitly marked noexcept and safe to use. Insertions, copies, and reserve() operations may throw std::bad_alloc or propagate user constructor exceptions, so they should be wrapped in try-catch blocks or avoided in noexcept contexts.

How does Abseil prevent memory leaks if rehashing fails halfway through?

Rehashing is designed as an all-or-nothing operation. The implementation first allocates a completely new bucket array. If this allocation succeeds, it moves existing nodes (which are pointers and cannot throw) into the new structure. Only after all nodes are safely transferred does it swap the new array into place and free the old one. If allocation fails at the start, no nodes are moved and no resources are leaked.

Where are the exception safety guarantees implemented in the Abseil source code?

The primary logic resides in absl/container/internal/raw_hash_set.h, which provides the underlying hash table implementation used by flat_hash_map. The public interface and guarantee specifications are defined in absl/container/flat_hash_map.h. The node management and two-phase insertion protocol are particularly visible in the EmplaceDecomposable and Rehash method implementations within these files.

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