Heterogeneous Lookup in C++ Associative Containers

Heterogeneous lookup, introduced in C++14 for ordered containers and expanded in C++20 to unordered containers, enables associative containers such as std::map, std::set, and std::unordered_map to perform search operations using types different from the stored key type. By accepting lookup keys that can be compared directly to the stored key without type conversion, this feature completely eliminates the creation and destruction of expensive temporary objects—such as dynamic memory allocations caused by converting const char* or std::string_view to std::string.

The Traditional Lookup Problem

In earlier C++ standards, container search member functions—including find(), count(), lower_bound(), and equal_range()—required an argument matching the container's key_type:

iterator find(const Key& key);

When an associative container used std::string as its key, querying that container required an instance of std::string. If a developer queried the container using a string literal (const char*) or a std::string_view:

std::set<std::string> my_set;
// ...
auto it = my_set.find("query_string");

The compiler was forced to construct an implicit temporary std::string from the string literal to satisfy the parameter type const std::string&. Even with Small String Optimization (SSO), constructing this temporary object incurs overhead, including calculating the string length and copying character buffers. If the string exceeds the SSO threshold, it triggers dynamic heap allocation and deallocation on every lookup call.

The Mechanism of Heterogeneous Lookup

Heterogeneous lookup replaces the fixed-type parameter with a templated member function overload:

template <typename K>
iterator find(const K& x);

Instead of requiring an instance of Key, the member function accepts any type K that the container's comparator knows how to compare against Key.

To prevent ambiguous conversions or unintended behaviors, this feature is opt-in. A comparator signals support for heterogeneous lookup by defining a nested type alias named is_transparent. When the container detects Compare::is_transparent, it enables the templated lookup overloads via SFINAE (std::enable_if).

Ordered Containers (C++14)

For ordered associative containers (std::set, std::multiset, std::map, std::multimap), heterogeneous lookup requires using a transparent comparison functor. The standard library provides transparent versions of its standard functors when invoked with void (the default template argument in C++14):

#include <set>
#include <string>
#include <string_view>

// Enable heterogeneous lookup using std::less<>
std::set<std::string, std::less<>> names = {"Alice", "Bob", "Charlie"};

std::string_view target = "Bob";

// Directly compares std::string_view to std::string without allocating a temporary std::string
auto it = names.find(target);

Because std::less<void> provides overloaded comparison operators that accept mixed operand types (operator()(const std::string&, std::string_view)), the container compares the stored element with the input reference directly.

Unordered Containers (C++20)

In C++20, heterogeneous lookup was extended to unordered associative containers (std::unordered_set, std::unordered_map, etc.). Unordered containers require both a transparent hash function and a transparent equality predicate.

To use heterogeneous lookup in an unordered container:

  1. The hasher must define is_transparent and provide operator() overloads for both the stored key type and the search key types.
  2. The key equal predicate must define is_transparent (such as std::equal_to<>).
#include <unordered_set>
#include <string>
#include <string_view>

struct StringHash {
    using is_transparent = void; // Mark hasher as transparent

    size_t operator()(std::string_view sv) const {
        return std::hash<std::string_view>{}(sv);
    }
};

// Container setup with transparent hash and transparent equality
std::unordered_set<std::string, StringHash, std::equal_to<>> dict;

void lookup(std::string_view sv) {
    // Calculates hash of std::string_view and compares directly to std::string
    // Zero heap allocations occur
    auto it = dict.find(sv); 
}

Summary of Benefits

  1. Zero Temporary Allocations: Queries matching strings, raw pointers, or slices execute without heap allocations or buffer copies.
  2. Improved Cache Locality: Eliminating intermediate temporary objects reduces cache pollution and minimizes stack traffic.
  3. Drop-in Optimization: In ordered containers, switching from std::set<std::string> to std::set<std::string, std::less<>> activates the optimization without requiring any changes to lookup call sites.