#creepy

Heterogeneous Lookup

Что будет, если попытаться вызвать .find()/.contains()/etc. у ассоциативных контейнеров (std::set/std::map/unordered-версии) с ключом, который не совпадает по типу? 🤔

std::map<std::string, int> m;
// ...
if (m.contains("foobar")) { ... }

У std::map есть дефолтный компаратор третьим аргументом в шаблоне - std::less<Key>. Компаратор нужен для поиска в контейнере.

Компаратор это структура, у которой должен быть определен bool operator(); выглядит оно примерно так:

constexpr bool operator()(const Key &lhs, const Key &rhs) const {
    return lhs < rhs;
}

То есть тип аргумента должен совпадать с типом ключа. Возвращаясь к примеру в начале: "foobar" имеет тип const char[7]. Он может "разложиться" в тип const char*, быть преобразован в тип std::string_view или std::string. Поэтому, к сожалению, по overload resolution создается временной объект std::string. 💩

Проверить, что это именно так, можно через строку с кастомным аллокатором (см. определение std::string), который логирует запрос на аллокации.

using traceable_string = std::basic_string<char, std::char_traits<char>, trace_allocator<char>>;

Проверяемые строки должны быть достаточно длинными, чтобы обойти Small String Optimization и вызвать аллокацию, в моем окружении это от 16 символов - код на godbolt.

Но зачем создавать std::string, если разные строковые типы сравниваемы между собой? В C++14 проблему решили лютым костылем 🩼: сделали std::less<> = std::less<void> и переопределили std::less<void> кастомно так:

template <class Key1, class Key2>
constexpr auto operator()(Key1&& lhs, Key2&& rhs) const
    return static_cast<Key1&&>(lhs) < static_cast<Key2&&>(rhs);
}

Теперь для перфоманса нужно помнить этот хак и делать

std::map<std::string, int, std::less<>> m;

тогда лишних аллокаций не будет - код на godbolt. Это называется громким словом heterogeneous lookup.

Я не смог найти причину, почему это не сделали поведением по умолчанию. Я порылся в библиотеках с кастомными контейнерами и вижу два подхода к вопросу:
(1) homogenous lookup по умолчанию (как в STL) - пример boost::container::map
(2) heterogeneous lookup по умолчанию - пример хэш таблицы в Abseil (от Google), аналог std::unordered_map/set

Перф неплохо улучшается, пример расследования для unordered контейнеров - там цифры от 20% до 35%.