Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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