Гетерогенный поиск в ассоциативных контейнерах на C++

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

Ассоциативные контейнеры в C++ работают с конкретным типом ключа. Для поиска в них по ключу подобного типа (std::string, std::string_view, const char*) мы можем нести существенные потери в производительности. В этой статье я расскажу как этого избежать с помощью относительно недавно добавленной возможности гетерогенного поиска.


Имея контейнер std::map<std::string, int> с мы должны быть проинформированны о возможной высокой цене при поиске (и некоторых других операциях с ключом в виде параметра) по нему в стиле c.find("hello world"). Дело в том, что по умолчанию все эти операции требуют ключ требуемого типа, в нашем случае это std::string. В результате чего при вызове find нам нужно неявно сконструировать ключ типа std::string из const char*, что будет стоить нам в лучшем случае одного лишнего memcpy (если в нашей реализации стандартной библиотеки есть "small string optimization" и ключ короткий), а также лишнего strlen (если компилятор не догадается или не будет иметь возможности вычислить длину строки во время компиляции). В худшем же случае придётся заплатить по полной: выделением и освобождением памяти из кучи для временного ключа на ровном, казалось бы, месте, а это уже может быть сопоставимо с самим временем поиска.


Мы можем избежать ненужной работы с помощью гетерогенного поиска. Функции для его корректной работы добавлены в упорядоченные контейнеры (set, multiset, map, multimap) во всех подобных местах с С++14 стандарта и в неупорядоченные (unordered_set, unordered_multiset, unordered_map, unordered_multimap) с C++20.


// до C++14 мы имели только такие функции поиска
iterator find(const Key& key);
const_iterator find(const Key& key) const;

// начиная с C++14 мы имеем ещё и вот такие
template < class K > iterator find(const K& x);
template < class K > const_iterator find(const K& x) const;

Но, как и всегда, в C++ в этом месте есть подвох, имя ему дефолтный компаратор. Компаратор по умолчанию для нашего std::map<std::string, int> это std::less<std::string> функция сравнения которого объявлена как:


// где T это тип нашего ключа, т.е. std::string
bool operator()(const T& lhs, const T& rhs) const;

Он не может быть использован для нашего гетерогенного сравнения, так как имеет всё такие же проблемы (нужно конструировать конкретный тип ключа). На помощь приходит специализация std::less<void> которая лишена этих проблем.


template <>
struct less<void> {
    using is_transparent = void;

    template < class T, class U >
    bool operator()(T&& t, U&& u) const {
        return std::forward<T>(t) < std::forward<U>(u);
    }
};

Примерно так выглядит эта специализация, я упустил моменты с constexpr и noexcept для простоты описания.

Пометка is_transparent говорит контейнерам, что этот компаратор умеет гетерогенное сравнение и по ней же становятся доступны новые функции гетерогенного поиска.


Теперь можно объявить контейнер, который будет использовать всё это добро и ключи будут сравниваться напрямую используя operator<(const std::string&, const char*) без неявных преобразований к одному типу:


std::map<std::string, int, std::less<>> c;
c.find("hello world");

Естественно, можно написать и свой компаратор для своих типов, например, когда отсутствует глобальный operator< для них. Иногда мы просто не можем создать такой временный ключ прозрачно и гетерогенный поиск единственная возможность искать что-то в контейнерах по ключу, например, при хранении std::thread в std::set и поиску по std::thread::id.


struct thread_compare {
    using is_transparent = void;

    bool operator()(const std::thread& a, const std::thread& b) const {
        return a.get_id() < b.get_id();
    }

    bool operator()(const std::thread& a, std::thread::id b) const {
        return a.get_id() < b;
    }

    bool operator()(std::thread::id a, const std::thread& b) const {
        return a < b.get_id();
    }
};

// объявляем контейнер с нашим гетерогенным компаратором
std::set<std::thread, thread_compare> threads;

// имеем возможность искать по id
threads.find(std::this_thread::get_id());

Ну и не стоит забывать, что это всё касается не только функции find. Так же это касается функций: count, equal_range, lower_bound, upper_bound и contains.


Счастливого гетерогенного поиска, уважаемый хаброчитатель!

Источник: https://habr.com/ru/post/523668/


Интересные статьи

Интересные статьи

Полгода назад, летом 2020 года я написал скрипт поиска ликвидных облигаций на Мосбирже (статья в закладках у 194 человек, рейтинг +45). Скрипт нужен для поиска облигаций,...
Я недавно сделал маленькую библиотеку для решения задачи поиска кратчайшего пути на 2D карте с выпуклыми препятствиями. В процессе реализации я придумал пару алгоритмов и трюков, описан...
Предыстория Когда-то у меня возникла необходимость проверять наличие неотправленных сообщений в «1С-Битрикс: Управление сайтом» (далее Битрикс) и получать уведомления об этом. Пробле...
Самые простые вещи могут иметь самые необычные и даже неизученные аспекты. С малых лет мы пытаемся понять естество всего, что нас окружает. Как работает лампочка в люстре, почему небо синее, ...
Эта статья посвящена одному из способов сделать в 1с-Битрикс форму в всплывающем окне. Достоинства метода: - можно использовать любые формы 1с-Битрикс, которые выводятся компонентом. Например, добавле...