CKTIS / C++
Heterogeneous lookup with a transparent comparator
Search an ordered associative container with a different type from its key, without constructing a temporary key. Learn why `std::less<>` enables the lookup overloads and why mixed comparisons must agree with the key order.
Version: ISO C++23; implementation support may vary
Syntax
using Index = std::map<std::string, int, std::less<>>;
// Heterogeneous std::map::find member overloads (shown inside the class):
template<class K> iterator find(const K& x);
template<class K> const_iterator find(const K& x) const;With heterogeneous lookup, the query can have a type K different from the stored key type Key. In std::map, std::multimap, std::set, and std::multiset, heterogeneous overloads of find, count, lower_bound, upper_bound, and equal_range date from C++14; contains dates from C++20. The stored key type does not change.
Ordinary find takes const Key&. The templated find(const K&) participates in overload resolution only if Compare::is_transparent is valid and names a type. std::less<> from <functional> is std::less<void>: it exposes that marker and applies < to the supplied operands, which can have different types. The default map comparator, std::less<Key>, has no such marker. With that default, searching std::string keys with a std::string_view requires explicitly constructing a key, as in find(std::string{query}).
The marker does not validate the comparison. For find, the key and query must be comparable in both directions, consistently with the strict weak ordering of the keys. A match means !comp(key, query) && !comp(query, key), not key == query. Do not compare keys case-sensitively but mixed pairs case-insensitively: the mixed comparisons may not partition the sorted keys into consistent ranges. std::less<> uses the same lexicographic order for std::string and std::string_view.
Searching with the view does not construct a temporary std::string. The view does not own its characters: they must stay valid throughout the call, and find does not retain the view. find is logarithmic in the number of elements and returns an iterator to a match or end(); check before dereferencing. Scope: ISO C++23; implementation support may vary. The example uses std::string_view from C++17 and requires at least C++17.
Examples
#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <string_view>
int main() {
const std::map<std::string, int, std::less<>> stock{
{"apple", 3}, {"pear", 7}
};
const auto report = [&stock](std::string_view query) {
if (const auto it = stock.find(query); it != stock.end()) {
std::cout << it->first << ": " << it->second << '\n';
} else {
std::cout << query << ": not found\n";
}
};
report(std::string_view{"pear tart", 4});
report("plum");
}Result
pear: 7 plum: not found
The map stores `std::string` keys. The first view spans only the first four characters of `pear tart`, so the search finds `pear` and prints `pear: 7`. For `plum`, `find` returns `end()` and the program prints `plum: not found`.
Related lessons
- C++ · Lesson 31 · Advanced · Version: 3
Sources
- C++ working draft — General associative container requirements [associative.reqmts.general]
- C++ working draft — Class template less [comparisons.less]
- C++ working draft — Class template map overview [map.overview]
- Feature-testing recommendations for C++
- C++ working draft — String view non-member comparison functions [string.view.comparison]
- C++ working draft — String accessors [string.accessors]
- C++ working draft — Class template basic_string_view [string.view.template]
- P0254R1 — Integrating std::string_view and std::string
- C++ Draft International Standard (C++20) — N4860