CKTIS / C++
Ricerca eterogenea con un comparatore trasparente
Cerca in un contenitore associativo ordinato con un tipo diverso da quello delle chiavi, senza costruire una chiave temporanea. Scopri come `std::less<>` abilita gli overload e perché i confronti misti devono rispettare l’ordinamento delle chiavi.
Versione: ISO C++23; implementation support may vary
Sintassi
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 ricerca eterogenea consente di usare un argomento di tipo K diverso dal tipo Key delle chiavi memorizzate. In std::map, std::multimap, std::set e std::multiset gli overload eterogenei di find, count, lower_bound, upper_bound ed equal_range esistono da C++14, quello di contains da C++20. Il tipo delle chiavi memorizzate non cambia.
Il normale find accetta const Key&. Il template find(const K&) partecipa alla risoluzione degli overload solo se Compare::is_transparent è valido e denota un tipo. std::less<> di <functional> è std::less<void>: espone questo marcatore e applica < agli operandi ricevuti, che possono avere tipi diversi. Il comparatore predefinito della mappa, std::less<Key>, non ha questo marcatore. Con il comparatore predefinito, per cercare tra chiavi std::string partendo da uno std::string_view occorre costruire esplicitamente una chiave, ad esempio con find(std::string{query}).
Il marcatore non convalida il confronto. Per find, chiave e argomento di ricerca devono essere confrontabili in entrambi i sensi, in modo coerente con l’ordinamento debole stretto delle chiavi. Una corrispondenza soddisfa !comp(key, query) && !comp(query, key), non key == query. Non distinguere maiuscole e minuscole nei confronti tra chiavi per poi ignorare la distinzione nelle coppie miste: i confronti misti potrebbero non suddividere le chiavi ordinate in intervalli coerenti. std::less<> usa lo stesso ordine lessicografico per std::string e std::string_view.
La ricerca con la vista non costruisce uno std::string temporaneo. La vista non possiede i caratteri: devono restare validi per tutta la chiamata e find non conserva la vista. find ha complessità logaritmica nel numero di elementi e restituisce un iteratore a una corrispondenza oppure end(); controlla il risultato prima di dereferenziarlo. Ambito: ISO C++23; il supporto può variare in base all’implementazione. L’esempio usa std::string_view, introdotto in C++17, e richiede almeno C++17.
Esempi
#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");
}Risultato
pear: 7 plum: not found
La mappa memorizza chiavi `std::string`. La prima vista comprende solo i primi quattro caratteri di `pear tart`, quindi la ricerca trova `pear` e stampa `pear: 7`. Per `plum`, `find` restituisce `end()` e il programma stampa `plum: not found`.
Lezioni correlate
- C++ · Lezione 31 · Avanzato · Versione: 3
Fonti
- 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