|
Ассоциативные контейнеры в 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 (если компилятор не догадается или не будет иметь возможности вычислить длину строки во время компиляции). В худшем же случае придётся заплатить по полной: выделением и освобождением памяти из кучи для временного ключа на ровном, казалось бы, месте, а это уже может быть сопоставимо с самим временем поиска. |
Главная 
