Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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