Гетерогенный поиск в ассоциативных контейнерах на 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.

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