Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

Pesquisa heterogénea com um comparador transparente

Pesquisa num contentor associativo ordenado com um tipo diferente do das chaves, sem construir uma chave temporária. Vê como `std::less<>` disponibiliza as sobrecargas e por que motivo as comparações mistas têm de respeitar a ordenação das chaves.

Versão: ISO C++23; implementation support may vary

Sintaxe

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;

A pesquisa heterogénea permite usar um argumento de tipo K diferente do tipo Key das chaves armazenadas. Em std::map, std::multimap, std::set e std::multiset, as sobrecargas heterogéneas de find, count, lower_bound, upper_bound e equal_range existem desde C++14, e a de contains desde C++20. O tipo das chaves armazenadas não muda.

O find comum recebe const Key&. O modelo de função find(const K&) só participa na resolução de sobrecargas se Compare::is_transparent for válido e designar um tipo. std::less<>, de <functional>, é std::less<void>: disponibiliza esse marcador e aplica < aos operandos recebidos, que podem ser de tipos diferentes. O comparador predefinido do mapa, std::less<Key>, não tem esse marcador. Com ele, pesquisar entre chaves std::string a partir de um std::string_view exige construir explicitamente uma chave, como em find(std::string{query}).

O marcador não valida a comparação. Para find, a chave e o argumento de pesquisa têm de ser comparáveis nos dois sentidos, de forma coerente com a ordenação fraca estrita das chaves. Há correspondência quando se verifica !comp(key, query) && !comp(query, key), não key == query. Não faças comparações entre chaves que distinguem maiúsculas de minúsculas e comparações mistas que ignoram essa distinção: estas últimas podem não dividir as chaves ordenadas em intervalos coerentes. std::less<> usa a mesma ordenação lexicográfica para std::string e std::string_view.

A pesquisa com a vista não constrói um std::string temporário. A vista não é proprietária dos caracteres: estes têm de permanecer válidos durante toda a chamada, e find não guarda a vista. find tem complexidade logarítmica em relação ao número de elementos e devolve um iterador para uma correspondência ou end(); verifica o resultado antes de o desreferenciar. Âmbito: ISO C++23; o suporte pode variar consoante a implementação. O exemplo usa std::string_view, introduzido em C++17, e requer pelo menos C++17.

Exemplos

#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

O mapa armazena chaves `std::string`. A primeira vista abrange apenas os primeiros quatro caracteres de `pear tart`, pelo que a pesquisa encontra `pear` e escreve `pear: 7`. Para `plum`, `find` devolve `end()` e o programa escreve `plum: not found`.

Lições relacionadas

  • C++ · Lição 31 · Avançado · Versão: 3

Fontes