# Node handles and heterogeneous lookup

> Node handles (C++17) let you take a node out of a map or set, change its key or move its value, and put it back or into another container without copying or allocating. Heterogeneous lookup (C++14 ordered, C++20 unordered) lets you search by a type other than the key, so no temporary key has to be built.

- **Source:** C++ Atlas (https://cppatlas.com/topics/node-handles-and-heterogeneous-lookup)
- **Track:** Containers and strings
- **Estimated reading time:** 12 minutes
- **ISO C++ clauses:** [container.node] (https://eel.is/c++draft/container.node), [container.insert.return] (https://eel.is/c++draft/container.insert.return), [associative.reqmts] (https://eel.is/c++draft/associative.reqmts), [unord.req] (https://eel.is/c++draft/unord.req)
- **cppreference links:** [Node handle](https://en.cppreference.com/w/cpp/container/node_handle), [std::map::extract](https://en.cppreference.com/w/cpp/container/map/extract), [std::map::merge](https://en.cppreference.com/w/cpp/container/map/merge), [std::map::insert](https://en.cppreference.com/w/cpp/container/map/insert), [std::map::find](https://en.cppreference.com/w/cpp/container/map/find), [std::unordered_map::find](https://en.cppreference.com/w/cpp/container/unordered_map/find), [std::map::erase](https://en.cppreference.com/w/cpp/container/map/erase)
- **Prerequisites:** associative-and-unordered-containers, iterator-invalidation, allocators-and-pmr

## The one idea

The associative containers are node-based: each element lives in its own allocation. Two features exploit that, and both are about not doing work you do not need to do.

A **node handle** is an owning pointer to one detached node. You can pull a node out of a container, edit it, and push it into the same or another container by relinking pointers. No element is copied, moved, or reallocated.

**Heterogeneous lookup** is the other direction: the container's comparison or hash is allowed to accept an argument of a type other than the key, so `find("literal")` does not have to build a `std::string` just to throw it away.

> **Mental model.** A node handle is a `unique_ptr` to a map or set node, and it stops being a view of the container the moment it is extracted. Heterogeneous lookup is a promise that comparing a key with a foreign type gives the same answers as comparing keys.

## Extracting and inserting nodes

`extract` takes an iterator or a key. It unlinks the node, with no allocation and no element move, and returns a handle of type `node_type`. If the key is absent it returns an empty handle. The handle is move-only, and if it is destroyed while holding a node, it destroys the element and frees the node.

The reason this matters for maps: a `map` key is `const`, so there is normally no way to rename an element short of erasing it and inserting a copy. With a node handle the key is accessible and writable.

```cpp
#include <map>
#include <string>

void rename_key() {
  std::map<int, std::string> m{{1, "a"}, {2, "b"}};
  auto nh = m.extract(1);       // unlinked; m is now {2:"b"}
  nh.key() = 3;                 // non-const access to the key
  m.insert(std::move(nh));      // relinked at the position for 3; no allocation
  // m is {2:"b", 3:"a"}
}
```

Sets get the same benefit, since `set` elements are also `const`. A set node's `value()` is a mutable reference, so you can move an element out of a set, which nothing else allows.

```cpp
#include <memory>
#include <set>

std::unique_ptr<int> take(std::set<std::unique_ptr<int>>& s) {
  return std::move(s.extract(s.begin()).value());
}
```

> **Standardese.** [container.node] describes a node handle as owning an element and its allocator, and being empty after a move. Extraction invalidates only iterators to the extracted element. Pointers and references to it remain valid but may not be used to access the element while a handle owns it. They become usable again if the element is inserted into a container.

That last sentence is easy to misread as a promise that references are always fine. They are fine only before extraction and after reinsertion, not in between.

The node handle's `key()` and `mapped()` exist only for map nodes, and `value()` only for set nodes. All three have undefined behavior on an empty handle, and so does `get_allocator()`. Use `empty()` or `explicit operator bool` to check.

## The result of inserting a node

For a unique container (`map`, `set`, and their unordered cousins), inserting a node can fail if an equivalent key is already present. `insert(node_type&&)` returns an `insert_return_type`, an aggregate with three members: `position`, an iterator; `inserted`, a bool; and `node`, a node handle.

- If the handle was empty: `inserted` is false, `position` is `end()`, and `node` is empty.
- If insertion happened: `inserted` is true, `position` points at the new element, and `node` is empty.
- If it failed because of a duplicate: `inserted` is false, `position` points at the element that blocked it, and `node` **still owns the element you tried to insert**.

```cpp
#include <set>

void dup() {
  std::set<int> s{1, 2};
  auto nh = s.extract(1);
  s.insert(1);                        // someone else took key 1
  auto r = s.insert(std::move(nh));
  // r.inserted == false; *r.position == 1; r.node is not empty: it still owns the extracted 1
}
```

That third case is why the return type carries the node: otherwise a failed insertion would destroy the element you extracted, silently. Multiset and multimap cannot fail on duplicates, so their `insert(node_type&&)` returns a plain iterator. The hinted overload `insert(hint, nh)` also returns an iterator, and if insertion fails, the argument handle keeps ownership.

## Merging containers

`a.merge(b)` extracts every element of `b` whose key does not already exist in `a` and inserts it into `a`, using `a`'s comparator or hash. Elements with duplicate keys stay in `b`. No element is copied or moved, and pointers and references to the transferred elements remain valid, but refer into `a`. Do not keep using iterators to the transferred elements.

```cpp
#include <map>
#include <string>

void merging() {
  std::map<int, std::string> m1{{1, "a"}, {2, "b"}};
  std::map<int, std::string> m2{{2, "X"}, {3, "c"}};
  m1.merge(m2);
  // m1 is {1:"a", 2:"b", 3:"c"}; m2 is {2:"X"}: the duplicate stayed behind
}
```

The two containers may differ in comparison or hash, and a `map` can merge from a `multimap` and the reverse, as long as key, mapped type, and allocator types match. The same compatibility lets you insert a node extracted from a `std::map` into a `std::multimap`.

## Allocators

A node handle carries a copy of its source container's allocator, because it needs it for destruction. Inserting a node, and merging, requires the allocators to compare equal. The behavior is undefined otherwise, even though the code compiles.

This bites in practice with `std::pmr` containers: two `pmr::map` objects backed by different memory resources have unequal allocators, so moving a node between them is undefined behavior, even though each is a `pmr::map<int, int>`. Copy the element in that case. With the default `std::allocator`, which is always equal, the problem does not arise.

> **Pitfall.** `extract` plus `insert` across containers is a pointer splice, which only works if the node's memory can legally be freed by the destination container. Unequal allocators violate that, and the standard declares it undefined instead of making the container reallocate.

## Heterogeneous lookup

`std::map<std::string, int>` uses `std::less<std::string>`. Calling `find("a literal")` converts the argument to a `std::string`, and a long text means a heap allocation, to do one comparison. Passing a `std::string_view` does not compile at all, since there is no implicit conversion from it to `std::string`.

Since C++14, ordered containers support lookup with another type when the comparator is **transparent**: it has a nested type named `is_transparent`. `std::less<>`, which is `std::less<void>`, is transparent and forwards to `operator<` on whatever types it is given.

```cpp
#include <map>
#include <string>
#include <string_view>

void lookup() {
  std::map<std::string, int> plain;
  std::map<std::string, int, std::less<>> open;
  std::string_view key = "needle";
  // plain.find(key);          // ill-formed: no overload takes string_view
  open.find(key);              // OK: compares string_view with string directly
  open.count("literal");       // OK: no temporary std::string
}
```

The overloads that gain a template form are `find`, `count`, `contains`, `lower_bound`, `upper_bound` and `equal_range`. Declaring the map with `std::less<>` changes its type, so it cannot be assigned to `std::map<std::string, int>`.

### Unordered containers (C++20)

The unordered containers need two transparent parts: a hash and an equality predicate. `std::hash<std::string>` is not transparent, so you write your own, and the hash must give the same value for a `string_view` as for the equal `std::string`. The simple way is to hash through `string_view`:

```cpp
#include <functional>
#include <string>
#include <string_view>
#include <unordered_map>

struct StrHash {
  using is_transparent = void;
  std::size_t operator()(std::string_view s) const {
    return std::hash<std::string_view>{}(s);
  }
};

using Table = std::unordered_map<std::string, int, StrHash, std::equal_to<>>;

int get(const Table& t, std::string_view k) {
  auto it = t.find(k);                 // OK since C++20: no std::string built
  return it == t.end() ? 0 : it->second;
}
```

### Erase and extract (C++23), insertion (C++26)

C++23 added template overloads of `erase` and `extract` that take a transparent key, so `m.erase("abc"sv)` and `m.extract("abc"sv)` work. They are excluded if the argument converts to `iterator` or `const_iterator`, so `m.erase(it)` still means what it did. C++26 adds the remaining ones, `operator[]`, `at`, `try_emplace` and `insert_or_assign`.

Library support is uneven. g++-16 provides erase and extract in C++23 mode and the insertion overloads in C++26 mode. libc++ 21, bundled with Homebrew clang 21, provides the C++14 and C++20 lookup but neither of the later additions.

## Pitfalls with inconsistent comparators

Transparency is a claim, and the container takes your word for it. Three failure modes follow.

First, the comparator must accept both argument orders: lookup needs `comp(key, other)` and `comp(other, key)`. A comparator written for one order does not compile as soon as you use it for lookup.

Second, the ordering of foreign values must agree with the ordering of keys. If `comp(a, b)` says one thing about a `string_view` against a key and a different thing from the key-to-key comparison, the tree can lie about where an element would be and `find` misses elements that are present. The standard requires this partitioning, and a violation is undefined behavior, not a wrong answer.

Third, hashing: if `h("abc")` for a `const char*` is a pointer hash while `h(std::string("abc"))` hashes characters, equal keys land in different buckets and lookups fail. Make every overload of the hash agree on equal values.

## What to remember

- `extract` unlinks a node with no allocation; the handle is move-only, owns the element, and frees it if never reinserted.
- `nh.key()` is the only way to change a map key without copying; sets allow moving elements out through `value()`.
- Pointers and references to an extracted element are not usable while the handle holds it, and are usable again after reinsertion.
- `insert(node_type&&)` into a unique container returns `{position, inserted, node}`, and on a duplicate the node keeps the element.
- `merge` leaves duplicate-key elements in the source, copies nothing, and requires equal allocators.
- Inserting or merging a node across unequal allocators is undefined, as with two `pmr` containers on different resources.
- Ordered heterogeneous lookup needs a transparent comparator such as `std::less<>`; unordered needs a transparent hash and equality (C++20).
- C++23 adds heterogeneous `erase` and `extract`, and C++26 adds `operator[]`, `at`, `try_emplace` and `insert_or_assign`.
- Foreign-type comparisons and hashes must be consistent with the key ones, or lookup is undefined.

## Concept Map Outline

- **Node handles and heterogeneous lookup:** Splice nodes between containers and search without building keys.
  - **Node handles (C++17):** Move-only owners of one detached node.
    - **extract:** Unlinks a node by iterator or key with no allocation; a missing key gives an empty handle.
    - **Edit the key:** nh.key() is mutable, the only way to rename a map key without copying.
    - **Move out of a set:** nh.value() is mutable, so an element can be moved out of a set.
    - **Reference validity:** References to an extracted element are unusable while owned, valid again after insertion.
  - **Inserting nodes:** Reinsertion is a relink, not a copy.
    - **insert_return_type:** Holds position, inserted and node; the node keeps the element after a duplicate failure.
    - **Empty handle insert:** No effect: inserted is false, position is end(), node is empty.
    - **Multi containers:** Insertion cannot fail on duplicates and returns a plain iterator.
  - **merge:** Splice every non-conflicting node from another container.
    - **Duplicates stay behind:** Elements whose key exists in the destination remain in the source.
    - **Compatible containers:** Comparator or hash may differ, and map and multimap interchange.
  - **Allocator rules:** The node carries its container's allocator.
    - **Equal allocators needed:** insert and merge across unequal allocators are undefined.
    - **pmr resources differ:** Two pmr maps on different resources have unequal allocators.
  - **Heterogeneous lookup:** Search with a type other than the key.
    - **Transparent comparator:** std::less<> or any comparator with is_transparent enables template find overloads.
    - **Unordered (C++20):** Needs a transparent hash and equality, and hashes must agree across types.
    - **Erase and extract (C++23):** Template overloads take transparent keys; excluded for iterator-convertible types.
    - **Insertion forms (C++26):** operator[], at, try_emplace and insert_or_assign gain heterogeneous overloads.
  - **Pitfalls:** Transparency is a promise the container trusts.
    - **Both argument orders:** The comparator must accept key-versus-other and other-versus-key.
    - **Consistent ordering:** Foreign comparisons must agree with key ordering, or lookup is undefined.
    - **Library support:** g++-16 has C++23 erase and extract; libc++ 21 lacks them.

## Standardese Quiz Questions

### Question 1 [warmup] ([container.node], [associative.reqmts])

What does this program print?

```cpp
#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> m{{1, "a"}, {2, "b"}};
  auto nh = m.extract(1);
  nh.key() = 3;
  m.insert(std::move(nh));
  for (const auto& [k, v] : m) std::cout << k << v << ' ';
  std::cout << '\n';
}
```

A. `1a 2b `
B. `3a 2b `
C. `2b 3a `
D. Ill-formed: a map key is const and cannot be modified

**Answer (C):** `2b 3a `

**Why:** A node handle exposes the key as a mutable `key_type&`, which is the only way to change a map key without copying. After the key becomes 3, `insert` links the node at the position for 3, so iteration visits 2 and then 3. The key being `const` inside the map is why the last option is tempting, but the handle sits outside the map.

### Question 2 [warmup] ([associative.reqmts])

Which line is ill-formed in C++20?

```cpp
#include <map>
#include <string>
#include <string_view>
using namespace std::literals;

void f() {
  std::map<std::string, int> plain;
  std::map<std::string, int, std::less<>> open;
  plain.find("abc");     // (1)
  plain.find("abc"sv);   // (2)
  open.find("abc"sv);    // (3)
  open.find("abc");      // (4)
}
```

A. (1)
B. (2)
C. (3)
D. (4)

**Answer (B):** (2)

**Why:** With `std::less<std::string>`, `find` takes a `const std::string&`. A `const char*` converts implicitly to `std::string`, so (1) compiles, though it builds a temporary. A `string_view` does not convert implicitly to `std::string`, so (2) has no viable overload. Lines (3) and (4) use the transparent `std::less<>`, which enables the template overload of `find`.

### Question 3 [warmup] ([associative.reqmts], [container.node])

What does this program print?

```cpp
#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> m1{{1, "a"}, {2, "b"}};
  std::map<int, std::string> m2{{2, "X"}, {3, "c"}};
  m1.merge(m2);
  for (const auto& [k, v] : m1) std::cout << k << v << ' ';
  std::cout << "| ";
  for (const auto& [k, v] : m2) std::cout << k << v << ' ';
  std::cout << '\n';
}
```

A. `1a 2X 3c | `, because the source overwrites
B. `1a 2b | 2X 3c `, because merge stops at the first duplicate
C. `1a 2b 3c | `, because the duplicate is destroyed
D. `1a 2b 3c | 2X `

**Answer (D):** `1a 2b 3c | 2X `

**Why:** `merge` moves every node whose key is not already present and leaves the others in the source. Key 2 exists in `m1`, so that element stays in `m2` and `m1` keeps its own value `b`. Nothing is overwritten and nothing is destroyed, and merging continues past the duplicate.

### Question 4 [tricky] ([container.insert.return], [associative.reqmts])

What does this program print?

```cpp
#include <iostream>
#include <set>

int main() {
  std::set<int> s{1, 2};
  auto nh = s.extract(1);
  s.insert(1);
  auto r = s.insert(std::move(nh));
  std::cout << r.inserted << r.node.empty() << *r.position << '\n';
}
```

A. `111`
B. `012`
C. `011`
D. `001`

**Answer (D):** `001`

**Why:** Key 1 was inserted again before the node came back, so the second insertion fails: `inserted` is false and `position` refers to the existing element, whose value is 1. The returned `node` still owns the element that was not inserted, so `empty()` is false. That is the point of `insert_return_type`: a failed insertion does not destroy the element you extracted.

### Question 5 [tricky] ([container.node], [associative.reqmts])

What does this program print?

```cpp
#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> m{{1, "a"}};
  std::string& r = m.at(1);
  auto nh = m.extract(1);
  m.insert(std::move(nh));
  r += "!";
  std::cout << m.at(1) << '\n';
}
```

A. `a!`
B. `a`, because extraction copied the element
C. Undefined behavior, because `extract` invalidated `r`
D. Ill-formed

**Answer (A):** `a!`

**Why:** Extraction invalidates only iterators to the element; pointers and references to it stay valid, and they may not be used while a node handle owns the element. Once the element is inserted again, they are usable and refer to the same object, so `r += "!"` modifies it. The program would have undefined behavior only if `r` were used between the `extract` and the `insert`.

### Question 6 [tricky] ([associative.reqmts])

In C++23, what is the status of this program?

```cpp
#include <iostream>
#include <map>
#include <string>
#include <string_view>
using namespace std::literals;

int main() {
  std::map<std::string, int, std::less<>> m{{"abc", 1}};
  std::cout << m.erase("abc"sv) << '\n';
}
```

A. Ill-formed: `erase` takes only a key or an iterator
B. Well-formed and prints `1`
C. Undefined behavior: the key types differ
D. Well-formed, but it prints `0` because `string_view` never equals `string`

**Answer (B):** Well-formed and prints `1`

**Why:** C++23 (P2077) added a template `erase(K&&)` overload to the associative containers, enabled when the comparator is transparent. In C++20 the call would be ill-formed, which is why the first option is tempting. The view compares equal to the stored string by value, so one element is erased. Some library versions, such as libc++ 21, did not yet implement it.

### Question 7 [standardese] ([container.insert.return], [associative.reqmts])

What does the standard say this program prints?

```cpp
#include <iostream>
#include <set>

int main() {
  std::set<int> s{1, 2};
  std::set<int>::node_type empty;
  auto r = s.insert(std::move(empty));
  std::cout << r.inserted << (r.position == s.end()) << r.node.empty() << '\n';
}
```

A. Undefined behavior: an empty node handle has no key to compare
B. `111`
C. `011`
D. `000`

**Answer (C):** `011`

**Why:** Inserting an empty node handle is specified: it has no effect and returns `inserted == false`, `position == end()` and an empty `node`. It is the accessors `key()`, `value()` and `get_allocator()` on an empty handle that are undefined. `111` is tempting for those who expect a successful no-op to report success.

### Question 8 [standardese] ([associative.reqmts], [container.node])

What is the status of the transfer of a node between these two maps?

```cpp
#include <map>
#include <memory_resource>

int main() {
  char b1[1024], b2[1024];
  std::pmr::monotonic_buffer_resource r1(b1, sizeof b1), r2(b2, sizeof b2);
  std::pmr::map<int, int> a(&r1), b(&r2);
  b[1] = 1;
  a.insert(b.extract(b.begin()));
}
```

A. Undefined behavior: the allocators do not compare equal
B. Well-formed: the node is reallocated from `a`'s resource
C. Ill-formed: `pmr::map` has no `extract`
D. Well-formed: allocators are never consulted when inserting a node

**Answer (A):** Undefined behavior: the allocators do not compare equal

**Why:** `insert(node_type&&)` requires the node handle's allocator to compare equal to the container's. A `polymorphic_allocator` compares equal only when both use the same memory resource, and these use different ones, so the precondition is violated. Nothing is reallocated: node transfer relinks the existing node, which is why the allocators must agree.
