CKTIS / C++
Recherche hétérogène avec un comparateur transparent
Interrogez un conteneur associatif ordonné avec un type différent de celui de sa clé, sans construire de clé temporaire. Découvrez comment `std::less<>` active les surcharges de recherche et pourquoi les comparaisons mixtes doivent respecter l’ordre des clés.
Version : ISO C++23; implementation support may vary
Syntaxe
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 recherche hétérogène accepte une valeur recherchée de type K, différent du type Key des clés stockées. Dans std::map, std::multimap, std::set et std::multiset, les surcharges hétérogènes de find, count, lower_bound, upper_bound et equal_range existent depuis C++14, et celle de contains depuis C++20. Le type des clés stockées ne change pas.
Le find ordinaire prend un const Key&. La surcharge générique find(const K&) ne participe à la résolution de surcharge que si Compare::is_transparent est valide et désigne un type. std::less<>, fourni par <functional>, est std::less<void> : il expose ce marqueur et applique < aux opérandes fournis, qui peuvent être de types différents. Le comparateur par défaut de la map, std::less<Key>, n’a pas ce marqueur. Avec lui, pour rechercher parmi des clés std::string à partir d’un std::string_view, il faut construire explicitement une clé, par exemple avec find(std::string{query}).
Le marqueur ne valide pas la comparaison. Pour find, la clé et la valeur recherchée doivent être comparables dans les deux sens, en cohérence avec l’ordre faible strict des clés. Une correspondance vérifie !comp(key, query) && !comp(query, key), et non key == query. Ne comparez pas les clés entre elles en tenant compte de la casse et les paires mixtes en l’ignorant : les comparaisons mixtes risqueraient de ne pas partitionner les clés triées en plages cohérentes. std::less<> utilise le même ordre lexicographique pour std::string et std::string_view.
La recherche avec la vue ne construit pas de std::string temporaire. La vue ne possède pas les caractères : ils doivent rester valides pendant tout l’appel, et find ne conserve pas la vue. find a une complexité logarithmique en fonction du nombre d’éléments et renvoie un itérateur vers une correspondance ou end() ; vérifiez le résultat avant de le déréférencer. Périmètre : ISO C++23 ; la prise en charge peut varier selon l’implémentation. L’exemple utilise std::string_view, introduit en C++17, et nécessite au moins C++17.
Exemples
#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");
}Résultat
pear: 7 plum: not found
La map stocke des clés `std::string`. La première vue ne couvre que les quatre premiers caractères de `pear tart` : la recherche trouve `pear` et affiche `pear: 7`. Pour `plum`, `find` renvoie `end()` et le programme affiche `plum: not found`.
Leçons associées
- C++ · Leçon 31 · Avancé · 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