База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

Хетерогенно търсене с прозрачен компаратор

Търси в подреден асоциативен контейнер със стойност от тип, различен от типа на ключа, без да създаваш временен ключ. Виж как `std::less<>` прави претоварванията достъпни и защо смесените сравнения трябва да спазват реда на ключовете.

Версия: ISO C++23; implementation support may vary

Синтаксис

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;

Хетерогенното търсене позволява аргументът за търсене да е от тип K, различен от типа Key на съхранявания ключ. В std::map, std::multimap, std::set и std::multiset хетерогенните претоварвания на find, count, lower_bound, upper_bound и equal_range са налични от C++14, а това на contains — от C++20. Типът на съхраняваните ключове не се променя.

Обикновената версия на find приема const Key&. Шаблонът find(const K&) участва в избора на претоварване само ако Compare::is_transparent е валидно име на тип. std::less<> от <functional> е std::less<void>: предоставя този маркер и прилага < върху подадените операнди, които могат да са от различни типове. Компараторът по подразбиране на картата, std::less<Key>, няма такъв маркер. При него търсенето сред ключове std::string с аргумент std::string_view изисква явно създаване на ключ, например с find(std::string{query}).

Маркерът не проверява сравнението. За find ключът и търсената стойност трябва да могат да се сравняват в двете посоки в съответствие със строгата слаба наредба на ключовете. Съвпадение означава !comp(key, query) && !comp(query, key), а не key == query. Не сравнявай ключовете с отчитане на главни и малки букви, ако при смесените двойки пренебрегваш тази разлика: смесените сравнения може да не разделят подредените ключове на съгласувани диапазони. std::less<> използва един и същ лексикографски ред за std::string и std::string_view.

Търсенето с изглед не създава временен std::string. Изгледът не притежава символите: те трябва да останат валидни през цялото извикване, а find не запазва изгледа. Сложността на find е логаритмична спрямо броя на елементите; функцията връща итератор към намерен елемент или end(), затова провери резултата преди дерефериране. Обхват: ISO C++23; поддръжката може да се различава според реализацията. Примерът използва std::string_view от C++17 и изисква поне C++17.

Примери

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

Резултат

pear: 7
plum: not found

Картата съхранява ключове от тип `std::string`. Първият изглед обхваща само първите четири символа на `pear tart`, затова търсенето намира `pear` и извежда `pear: 7`. За `plum` функцията `find` връща `end()` и програмата извежда `plum: not found`.

Свързани уроци

  • C++ · Урок 31 · Напреднало · Версия: 3

Източници