Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

Heterogeno pretraživanje s transparentnim komparatorom

Pretražuj uređeni asocijativni spremnik vrijednošću tipa različitog od tipa ključa, bez stvaranja privremenog ključa. Saznaj kako `std::less<>` omogućuje preopterećenja i zašto mješovite usporedbe moraju poštovati poredak ključeva.

Verzija: ISO C++23; implementation support may vary

Sintaksa

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;

Heterogeno pretraživanje omogućuje da argument za pretraživanje ima tip K različit od tipa pohranjenog ključa Key. U spremnicima std::map, std::multimap, std::set i std::multiset heterogena preopterećenja funkcija find, count, lower_bound, upper_bound i equal_range dostupna su od C++14, a preopterećenje contains od C++20. Tip pohranjenih ključeva ne mijenja se.

Obični find prima const Key&. Predložak find(const K&) sudjeluje u odabiru preopterećenja samo ako je Compare::is_transparent valjan naziv tipa. std::less<> iz <functional> jest std::less<void>: izlaže tu oznaku i primjenjuje < na predane operande, koji mogu imati različite tipove. Zadani komparator mape, std::less<Key>, nema tu oznaku. Ako s njim pretražuješ ključeve std::string pomoću std::string_view, moraš izričito konstruirati ključ, primjerice s find(std::string{query}).

Oznaka ne provjerava ispravnost usporedbe. Za find ključ i tražena vrijednost moraju biti usporedivi u oba smjera, u skladu sa strogim slabim poretkom ključeva. Podudaranje znači !comp(key, query) && !comp(query, key), a ne key == query. Nemoj kombinirati usporedbe ključeva koje razlikuju velika i mala slova s mješovitim usporedbama koje tu razliku zanemaruju: mješovite usporedbe tada možda neće podijeliti sortirane ključeve u dosljedne raspone. std::less<> koristi isti leksikografski poredak za std::string i std::string_view.

Pretraživanje pomoću pogleda ne stvara privremeni std::string. Pogled nije vlasnik znakova: moraju ostati valjani tijekom cijelog poziva, a find ne zadržava pogled. Složenost find logaritamska je u odnosu na broj elemenata; vraća iterator na pronađeni element ili end(), pa provjeri rezultat prije dereferenciranja. Opseg: ISO C++23; podrška se može razlikovati ovisno o implementaciji. Primjer koristi std::string_view uveden u C++17 i zahtijeva najmanje C++17.

Primjeri

#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");
}

Rezultat

pear: 7
plum: not found

Mapa pohranjuje ključeve tipa `std::string`. Prvi pogled obuhvaća samo prva četiri znaka niza `pear tart`, pa pretraživanje pronalazi `pear` i ispisuje `pear: 7`. Za `plum` funkcija `find` vraća `end()`, a program ispisuje `plum: not found`.

Povezane lekcije

  • C++ · Lekcija 31 · Napredno · Verzija: 3

Izvori