Краткий ответ

Используйте прозрачный компаратор, например std::less<>, и выполняйте гетерогенный поиск по std::string_view. Такой компаратор сообщает контейнеру, что сравнение допустимо не только между объектами типа ключа, поэтому временный std::string для поиска создавать не требуется.

Исторический контекст

Обычные ассоциативные контейнеры изначально ориентировались на поиск объектом того же типа, что и ключ. Для ключей std::string это могло приводить к созданию временной строки при поиске по другому представлению текста, например по массиву символов.

Гетерогенный поиск появился как расширение интерфейса ассоциативных контейнеров: контейнер по-прежнему хранит ключи одного типа, но операции поиска могут принимать совместимый тип. Это особенно полезно для дорогих ключей и часто выполняемых запросов.

Постановка проблемы

Рассмотрим std::map со строковыми ключами. Если поиск принимает только const std::string&, передача std::string_view может потребовать неявного создания std::string, а значит, потенциально — выделения памяти и копирования символов.

У стандартного компаратора std::less<std::string> тип аргументов фактически привязан к std::string. Поэтому даже наличие подходящего сравнения между строкой и std::string_view само по себе не гарантирует гетерогенный перегруженный вызов find.

Подробное решение

std::less<> — это прозрачный компаратор. Его специализация не фиксирует тип сравниваемых объектов и содержит маркер is_transparent. Благодаря этому std::map предоставляет шаблонную перегрузку поиска, если компаратор способен корректно сравнивать ключ контейнера и тип запроса в обоих необходимых направлениях.

#include <map>
#include <string>
#include <string_view>

int main() {
    std::map<std::string, int, std::less<>> users{
        {"alice", 1}, {"bob", 2}
    };

    std::string_view name = "bob";
    auto it = users.find(name);
}

В примере ключи хранятся как std::string, а запрос выполняется как std::string_view. Поиск сохраняет логарифмическую сложность дерева — O(log n), но не обязан создавать временный std::string.

Прозрачность компаратора не означает автоматическую поддержку любого типа. Для типа запроса должны существовать корректные сравнения, совместимые с порядком контейнера. Если сравнения неоднозначны или нарушают требования строгого слабого порядка, поведение контейнера может стать некорректным.

Преимущество проявляется именно в операциях поиска, проверки наличия и получения диапазона: find, contains, count, lower_bound, upper_bound и equal_range. Тип ключа контейнера при этом не меняется, а найденный элемент нельзя модифицировать через ключевой интерфейс.

Ситуация из практики

В сервисе хранятся настройки пользователей в std::map<std::string, Config>, а входные запросы уже представлены как std::string_view. Вариант с обычным std::less<std::string> прост, но может создавать временную строку на каждом поиске. Это увеличивает стоимость горячего пути и создаёт лишнюю нагрузку на распределитель памяти.

Можно явно преобразовывать std::string_view в std::string. Плюс такого решения — предсказуемость и совместимость с любым компаратором; минус — возможное выделение памяти и копирование. Можно хранить ключи как std::string_view, но это опасно: контейнер не владеет данными, и их время жизни должно гарантированно превышать время жизни контейнера.

Практичное решение — оставить владеющие ключи std::string, заменить компаратор на std::less<> и искать по std::string_view. Это сохраняет безопасность владения и устраняет ненужное временное создание строки. Перед применением следует проверить профилированием, действительно ли аллокации поиска заметны для конкретной нагрузки.

Что кандидаты часто упускают

Вопрос: Достаточно ли заменить компаратор на std::less<>, если для типа запроса нет совместимых операторов сравнения?

Ответ: Нет. Прозрачный компаратор только разрешает контейнеру рассматривать разные типы; он не создаёт правила сравнения автоматически. Между типом ключа и типом запроса должны быть доступны корректные операции сравнения, задающие тот же строгий слабый порядок. Иначе шаблонная перегрузка поиска не будет доступна либо сравнение окажется некорректным.

Вопрос: Меняет ли гетерогенный поиск сложность поиска в std::map?

Ответ: Нет, асимптотическая сложность остаётся O(log n), поскольку поиск проходит по сбалансированному дереву. Меняется стоимость подготовки запроса: можно избежать создания временного ключа, аллокации и копирования. Для std::unordered_map существует аналогичный подход с прозрачными хешером и функцией сравнения, но там дополнительно требуется корректное одинаковое хеширование эквивалентных ключей.

Вопрос: Почему нельзя безусловно считать отсутствие временного std::string гарантией отсутствия аллокаций?

Ответ: Гетерогенный поиск не создаёт временный ключ, но сам компаратор или пользовательский тип запроса может выполнять дополнительные действия. Например, пользовательский хешер может выделять память, а преобразование входных данных может быть дорогим. Кроме того, сравнение строк требует просмотра символов и в худшем случае занимает время, пропорциональное длине сравниваемых строк; устранение аллокации не делает поиск бесплатным.