Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

Heterogenní vyhledávání s transparentním komparátorem

Vyhledávej v uspořádaném asociativním kontejneru pomocí jiného typu, než je typ klíče, bez vytváření dočasného klíče. Zjisti, jak `std::less<>` zpřístupňuje přetížení a proč musí smíšená porovnání respektovat uspořádání klíčů.

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

Syntaxe

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;

Heterogenní vyhledávání umožňuje předat argument typu K, který se liší od typu uloženého klíče Key. V std::map, std::multimap, std::set a std::multiset jsou heterogenní přetížení funkcí find, count, lower_bound, upper_bound a equal_range dostupná od C++14 a přetížení contains od C++20. Typ uložených klíčů se nemění.

Běžné find přijímá const Key&. Šablona find(const K&) vstupuje do výběru přetížení, jen pokud je Compare::is_transparent platné jméno typu. std::less<> z <functional> je std::less<void>: poskytuje tuto typovou značku a používá < na předané operandy, které mohou být různých typů. Výchozí komparátor mapy, std::less<Key>, tuto značku nemá. Při hledání mezi klíči std::string pomocí std::string_view s ním musíš klíč vytvořit explicitně, například find(std::string{query}).

Značka neověřuje správnost porovnání. Pro find musí být možné porovnat klíč s hledanou hodnotou v obou směrech, v souladu s přísným slabým uspořádáním klíčů. Shoda znamená !comp(key, query) && !comp(query, key), nikoli key == query. Neporovnávej klíče s rozlišením velkých a malých písmen a smíšené dvojice bez něj: smíšená porovnání pak nemusí rozdělit seřazené klíče do konzistentních rozsahů. std::less<> používá pro std::string a std::string_view stejné lexikografické uspořádání.

Při hledání pomocí pohledu nevzniká dočasný std::string. Pohled znaky nevlastní: musí zůstat platné po celou dobu volání a find si pohled neukládá. find má logaritmickou složitost vzhledem k počtu prvků a vrací iterátor na nalezený prvek nebo end(); před dereferencováním výsledek zkontroluj. Rozsah: ISO C++23; podpora se může lišit podle implementace. Příklad používá std::string_view zavedený v C++17 a vyžaduje alespoň C++17.

Pří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ýsledek

pear: 7
plum: not found

Mapa ukládá klíče typu `std::string`. První pohled zahrnuje jen první čtyři znaky z `pear tart`, takže vyhledávání najde `pear` a vypíše `pear: 7`. Pro `plum` vrátí `find` hodnotu `end()` a program vypíše `plum: not found`.

Související lekce

  • C++ · Lekce 31 · Pokročilá · Verze: 3

Zdroje