CKTIS / C++
Wyszukiwanie heterogeniczne z transparentnym komparatorem
Przeszukuj uporządkowany kontener asocjacyjny za pomocą argumentu innego typu niż klucz, bez tworzenia tymczasowego klucza. Zobacz, dlaczego `std::less<>` udostępnia odpowiednie przeciążenia i czemu porównania muszą zachować porządek kluczy.
Wersja: ISO C++23; implementation support may vary
Składnia
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;Wyszukiwanie heterogeniczne pozwala przekazać argument typu K innego niż typ przechowywanego klucza Key. W std::map, std::multimap, std::set i std::multiset przeciążenia heterogeniczne funkcji find, count, lower_bound, upper_bound i equal_range są dostępne od C++14, a funkcji contains od C++20. Typ przechowywanego klucza się nie zmienia.
Zwykłe find przyjmuje const Key&. Szablonowe find(const K&) jest brane pod uwagę przy rozstrzyganiu przeciążeń tylko wtedy, gdy Compare::is_transparent jest poprawną nazwą typu. std::less<> z <functional> to std::less<void>: udostępnia ten znacznik i stosuje < do przekazanych argumentów, które mogą mieć różne typy. Domyślny komparator mapy, std::less<Key>, nie ma tego znacznika. Z nim wyszukiwanie za pomocą std::string_view w mapie z kluczami std::string wymaga jawnego utworzenia klucza, np. find(std::string{query}).
Znacznik nie sprawdza poprawności porównania. Przy find trzeba móc porównać klucz z argumentem w obu kierunkach, zgodnie ze ścisłym słabym porządkiem kluczy. Dopasowanie oznacza !comp(key, query) && !comp(query, key), a nie key == query. Nie porównuj kluczy z uwzględnieniem wielkości liter, a par mieszanych bez jej uwzględniania: wyniki porównań mieszanych mogą nie dzielić uporządkowanych kluczy na spójne zakresy. std::less<> zachowuje ten sam porządek leksykograficzny dla std::string i std::string_view.
Wyszukiwanie przez widok nie tworzy tymczasowego std::string. Widok nie jest właścicielem znaków: muszą pozostać ważne przez całe wywołanie, a find nie zachowuje widoku. find ma złożoność logarytmiczną względem liczby elementów i zwraca iterator do dopasowania lub end(); przed dereferencją sprawdź wynik. Zakres opisu: ISO C++23; obsługa zależy od implementacji. Przykład używa std::string_view z C++17 i wymaga co najmniej C++17.
Przykłady
#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");
}Wynik
pear: 7 plum: not found
Mapa przechowuje klucze `std::string`. Pierwszy widok obejmuje tylko cztery znaki ciągu `pear tart`, więc wyszukiwanie znajduje `pear` i wypisuje `pear: 7`. Dla `plum` funkcja `find` zwraca `end()` i program wypisuje `plum: not found`.
Powiązane lekcje
- C++ · Lekcja 31 · Zaawansowany · Wersja: 3
Źródła
- 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