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