CKTIS / C++
Heterogénne vyhľadávanie s transparentným komparátorom
Vyhľadávaj v usporiadanom asociatívnom kontajneri pomocou iného typu, než je typ kľúča, bez vytvárania dočasného kľúča. Zisti, ako `std::less<>` sprístupňuje preťaženia a prečo zmiešané porovnania musia rešpektovať usporiadanie kľúčov.
Verzia: ISO C++23; implementation support may vary
Syntax
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;Heterogénne vyhľadávanie umožňuje odovzdať argument typu K, ktorý sa líši od typu uloženého kľúča Key. V std::map, std::multimap, std::set a std::multiset sú heterogénne preťaženia funkcií find, count, lower_bound, upper_bound a equal_range dostupné od C++14 a preťaženie contains od C++20. Typ uložených kľúčov sa nemení.
Bežné find prijíma const Key&. Šablóna find(const K&) sa zúčastní na výbere preťaženia, len ak je Compare::is_transparent platný názov typu. std::less<> z <functional> je std::less<void>: poskytuje túto typovú značku a použije < na odovzdané operandy, ktoré môžu mať rôzne typy. Predvolený komparátor mapy, std::less<Key>, túto značku nemá. Ak s ním vyhľadávaš medzi kľúčmi std::string pomocou std::string_view, musíš explicitne vytvoriť kľúč, napríklad find(std::string{query}).
Značka nekontroluje správnosť porovnania. Pre find musí byť možné porovnať kľúč a hľadanú hodnotu v oboch smeroch v súlade s prísnym slabým usporiadaním kľúčov. Zhoda znamená !comp(key, query) && !comp(query, key), nie key == query. Neporovnávaj kľúče s rozlišovaním veľkých a malých písmen a zmiešané dvojice bez neho: zmiešané porovnania potom nemusia rozdeliť zoradené kľúče na konzistentné rozsahy. std::less<> používa pre std::string a std::string_view rovnaké lexikografické usporiadanie.
Pri vyhľadávaní pomocou pohľadu sa nevytvára dočasný std::string. Pohľad znaky nevlastní: musia zostať platné počas celého volania a find si pohľad neuchováva. find má logaritmickú zložitosť vzhľadom na počet prvkov a vráti iterátor na nájdený prvok alebo end(); pred dereferencovaním výsledok skontroluj. Rozsah: ISO C++23; podpora sa môže líšiť podľa implementácie. Príklad používa std::string_view zavedený v C++17 a vyžaduje aspoň C++17.
Príklady
#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");
}Výsledok
pear: 7 plum: not found
Mapa ukladá kľúče typu `std::string`. Prvý pohľad zahŕňa len prvé štyri znaky z `pear tart`, takže vyhľadávanie nájde `pear` a vypíše `pear: 7`. Pre `plum` vráti `find` hodnotu `end()` a program vypíše `plum: not found`.
Súvisiace lekcie
- C++ · Lekcia 31 · Pokročilá · Verzia: 3
Zdroje
- 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