CKTIS / C++
Búsqueda heterogénea con un comparador transparente
Busca en un contenedor asociativo ordenado con un tipo distinto del de sus claves, sin construir una clave temporal. Descubre cómo `std::less<>` habilita las sobrecargas y por qué las comparaciones mixtas deben respetar el orden de las claves.
Versión: ISO C++23; implementation support may vary
Sintaxis
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;La búsqueda heterogénea permite usar un argumento de tipo K distinto del tipo de clave almacenada Key. En std::map, std::multimap, std::set y std::multiset, las sobrecargas heterogéneas de find, count, lower_bound, upper_bound y equal_range existen desde C++14, y la de contains desde C++20. El tipo de las claves almacenadas no cambia.
El find ordinario recibe const Key&. La plantilla find(const K&) solo participa en la resolución de sobrecargas si Compare::is_transparent es válido y designa un tipo. std::less<>, de <functional>, es std::less<void>: expone ese marcador y aplica < a los operandos recibidos, que pueden ser de tipos distintos. El comparador predeterminado del mapa, std::less<Key>, no tiene ese marcador. Con él, para buscar entre claves std::string a partir de un std::string_view hay que construir explícitamente una clave, como en find(std::string{query}).
El marcador no valida la comparación. Para find, la clave y el argumento deben poder compararse en ambos sentidos de forma coherente con el orden débil estricto de las claves. Hay coincidencia si se cumple !comp(key, query) && !comp(query, key), no si se cumple key == query. No distingas mayúsculas y minúsculas al comparar claves entre sí para luego ignorar esa distinción en los pares mixtos: las comparaciones mixtas podrían no dividir las claves ordenadas en rangos coherentes. std::less<> usa el mismo orden lexicográfico para std::string y std::string_view.
Buscar con la vista no construye un std::string temporal. La vista no es propietaria de los caracteres: estos deben seguir siendo válidos durante toda la llamada, y find no guarda la vista. find tiene complejidad logarítmica respecto al número de elementos y devuelve un iterador al elemento encontrado o end(); comprueba el resultado antes de desreferenciarlo. Ámbito: ISO C++23; la compatibilidad puede variar según la implementación. El ejemplo usa std::string_view, introducido en C++17, y requiere al menos C++17.
Ejemplos
#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");
}Resultado
pear: 7 plum: not found
El mapa almacena claves `std::string`. La primera vista solo abarca los cuatro primeros caracteres de `pear tart`, así que la búsqueda encuentra `pear` e imprime `pear: 7`. Para `plum`, `find` devuelve `end()` y el programa imprime `plum: not found`.
Lecciones relacionadas
- C++ · Lección 31 · Avanzado · Versión: 3
Fuentes
- 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