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
- 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