C++ Reference ยท Containers
Heterogeneous lookup in C++ containers
Look up keys in map, set and unordered containers without building a temporary key: transparent comparators, is_transparent, and C++20 unordered support.
Normally find, count, contains, lower_bound and equal_range take the container's exact key_type. If your map is keyed by std::string and you call m.find("hello"), the compiler first builds a temporary std::string from the literal, which may allocate memory just to compare it and throw it away.
Heterogeneous lookup lets you search with any type that the comparator knows how to compare against the key, such as std::string_view or a const char*. You enable it by giving the container a transparent comparator: one that has a nested type named is_transparent. The standard function objects std::less<>, std::greater<> and std::equal_to<> (with the void default) are transparent.
std::map<std::string, int, std::less<>> m; // transparent comparator m.find(std::string_view("key")); // no temporary std::string
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
// Ordered containers: the comparator provides is_transparent template<class K> iterator find(const K& x); template<class K> size_type count(const K& x) const; template<class K> bool contains(const K& x) const; // C++20 template<class K> iterator lower_bound(const K& x); template<class K> iterator upper_bound(const K& x); template<class K> pair<iterator, iterator> equal_range(const K& x); // Unordered containers (C++20): both Hash and KeyEqual must be transparent
| Name | Description |
|---|---|
K |
Any type the comparator (or hash and equality) can handle together with key_type. The template overload takes part in overload resolution only when Compare::is_transparent (and for unordered containers Hash::is_transparent and Pred::is_transparent) exists. |
x |
The value to look up. |
Returns: the same as the non-template overload.
Undefined behavior: a transparent comparator whose results for K are inconsistent with its results for key_type (it must order K values and keys the same way) breaks the container's invariants.
Usage notes
- Ordered containers since C++14 (
find,count,lower_bound,upper_bound,equal_range;containssince C++20). Unordered containers gained the same lookups in C++20. - Insertion is not covered.
insert,operator[]andemplacestill need a realkey_type. C++26 adds heterogeneousoperator[],at,eraseandtry_emplacein the standard library, but check your compiler before relying on it. - Why it helps. It avoids constructing temporary keys: a
std::stringfrom a literal orstring_view, or a heavyweight record just to carry an ID. std::less<>(with no template argument) forwards tooperator<of both arguments, so any pair of comparable types works.- Hash consistency. For unordered containers, equal values of different types must produce the same hash, or lookups silently miss.
- Common mistake: writing
std::map<std::string, int>and expectingfind(string_view)to compile; the defaultstd::less<std::string>is not transparent.