Все знают про наличие в std::map/unordered_map методов find. Но, наверное, не все знают, что у этого find-а есть несколько вариантов. Кроме старого и привычного:
|
iterator find( const Key& key ); |
В std::map начиная с C++14 есть еще и:
|
template< class K > iterator find( const K& x ); |
А в std::unordered_map второй вариант find-а был добавлен в C++20.
Что же следует из того, что в find можно передать не Key, которым мы параметризовали свой map/unordered_map, а какой-то другой тип?
Следует то, что мы можем сделать поиск в map/unordered_map более эффективным если тип Key дорог в конструировании, например, когда внутри Key есть std::string-и или другие типы, динамически выделяющие и освобождающие память.
Недавно мне довелось столкнуться с ситуацией, когда ключом поиска был тип вроде вот такого:
|
using full_key_t = std::pair<std::size_t, std::string>; |
Соответственно, поиск выполнялся как-то так:
|
const auto id = get_id(...); const std::string & description = get_description(...); if(const auto it = _map.find(full_key_t{id, description}); it != _map.end()) { ... } |
Проблема в том, что экземпляр full_key_t нужно полностью сконструировать. А значит нужно сделать полную копию description и поместить эту копию в новый объект full_key_t. Что недешево. И, что особенно обидно, объект full_key_t разрушается сразу после завершения поиска. Т.е. мы создаем временный ключ, тратим на это время, а затем тупо выбрасываем временный ключ за ненадобностью.
К счастью, упомянутые выше "новые" варианты find-а позволяют нам избежать создания "тяжелых" экземпляров full_key_t. Теперь в C++ можно делать вот так:
|
using light_key_t = std::pair<std::size_t, const std::string*>; ... const auto id = get_id(...); const std::string & description = get_description(...); if(const auto it = _map.find(light_key_t{id, &description}); it != _map.end()) { ... } |
Однако, чтобы это работало, нужно сделать несколько дополнительных телодвижений. Давайте рассмотрим их на примере std::unordered_map.
Первое, что нам потребуется -- это такой тип хэш-функции, который будет применим как к full_key_t, так и к light_key_t. Поскольку обычно хэш для unordered_map -- это структура со специально написанным operator(), то мы можем просто сделать несколько перегрузок operator():
|
struct special_hash_t { using is_transparent = void; std::size_t operator()(const full_key_t & k) const noexcept { return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 + std::hash<std::string>{}(second_key_part(k)); } std::size_t operator()(const light_key_t & k) const noexcept { return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 + std::hash<std::string>{}(second_key_part(k)); } }; |
Где second_part_key -- это вспомогательные функции вида:
|
[[nodiscard]] const std::string & second_key_part(const full_key_t & k) noexcept { return k.second; } [[nodiscard]] const std::string & second_key_part(const light_key_t & k) noexcept { return *(k.second); } |
Внутри special_hash_t можно было обойтись и без них, но вот на следующем шаге они нам сильно помогут.
А следующим шагом будет определение собственного компаратора, который может сравнивать full_key_t и light_key_t на равенство. Этот компаратор мы подсунем std::unordered_map в качестве параметра шаблона KeyEqual. Для нашего примера компаратор может выглядеть так:
|
struct special_equal_to_t { using is_transparent = void; template<typename K1, typename K2> bool operator()(const K1 & k1, const K2 & k2) const noexcept { return (k1.first == k2.first) && (second_key_part(k1) == second_key_part(k2)); } }; |
За счет того, что в special_equal_to_t у нас operator() -- это шаблон метода, то он может принимать разные сочетания: как full_key_t с light_key_t, так и light_key_t с full_key_t. Здесь функции second_key_part помогают избежать дублирования кода.
Ключевой момент в этом всем -- это наличие определения is_transparent в special_key_t и special_equal_to_t. Без такого вложенного типа вся обсуждаемая машинерия с "новыми" find работать не будет. Причем, если забыть определить is_transparent, то компилятор может выдать такую простыню невнятных сообщений об ошибках, что причина проблемы будет совершенно непонятна (тут, конечно же от степени вменяемости компилятора зависит).
Далее остается просто определить тип нужного нам unordered_map:
|
using values_map_t = std::unordered_map< full_key_t, your_value_type, special_hash_t, special_equal_to_t>; |
Какой же выигрыш дает этот трюк и дает ли вообще?
Если строковые ключи поиска короткие, т.е. срабатывает small string optimization (SSO), то практически не дает. Но вот если строчки достаточно длинные, чтобы SSO остался не у дел, то разница почти в два раза по моим замерам.
Под катом полнофункциональная программка, которая демонстрирует данный подход. Так вот, на i7-8550U с VC++ из VisualStudio 17.4.0 она выдает, например, следующие результаты:
*** find_by_full_key: 1512721us ***
values found: 10000000
*** find_by_light_key: 844164us ***
values found: 10000000
Тогда как MinGW 13.2.0 на той же машине показывает время чуть получше и все равно с почти что двухкратным разрывом:
*** find_by_full_key: 1137556us ***
values found: 10000000
*** find_by_light_key: 557952us ***
values found: 10000000
Так что трюк вполне себе рабочий. Но есть с ним две небольшие проблемки:
- про него легко забыть, особенно когда голова забита решением прикладных проблем, а глаз уже "замылился";
- нужно помнить про вложенный тип is_transparent, без него не работает, а компилятор своими сообщениями может только запутать.
Собственно, данный пост возник для того, чтобы зафиксировать этот трюк в склерознике (в особенности его часть про is_transparent).
|
#include <array> #include <chrono> #include <iostream> #include <string> #include <unordered_map> #include <utility> namespace test { using full_key_t = std::pair<std::size_t, std::string>; using light_key_t = std::pair<std::size_t, const std::string*>; [[nodiscard]] const std::string & second_key_part(const full_key_t & k) noexcept { return k.second; } [[nodiscard]] const std::string & second_key_part(const light_key_t & k) noexcept { return *(k.second); } struct special_hash_t { using is_transparent = void; std::size_t operator()(const full_key_t & k) const noexcept { return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 + std::hash<std::string>{}(second_key_part(k)); } std::size_t operator()(const light_key_t & k) const noexcept { return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 + std::hash<std::string>{}(second_key_part(k)); } }; struct special_equal_to_t { using is_transparent = void; template<typename K1, typename K2> bool operator()(const K1 & k1, const K2 & k2) const noexcept { return (k1.first == k2.first) && (second_key_part(k1) == second_key_part(k2)); } }; using values_map_t = std::unordered_map< full_key_t, int, special_hash_t, special_equal_to_t>; #if 1 const std::array<std::string, 10> strings{ "a rather long string value to avoid small string optimization 001", "a rather long string value to avoid small string optimization 002", "a rather long string value to avoid small string optimization 003", "a rather long string value to avoid small string optimization 004", "a rather long string value to avoid small string optimization 005", "a rather long string value to avoid small string optimization 006", "a rather long string value to avoid small string optimization 007", "a rather long string value to avoid small string optimization 008", "a rather long string value to avoid small string optimization 009", "a rather long string value to avoid small string optimization 010" }; #else const std::array<std::string, 10> strings{ "str 001", "str 002", "str 003", "str 004", "str 005", "str 006", "str 007", "str 008", "str 009", "str 010" }; #endif const std::size_t map_size = 1000; const std::size_t insertions = 10'000'000; [[nodiscard]] values_map_t make_values() { values_map_t result; int value = 0; for(std::size_t i = 0; i != map_size; ++i, ++value) { const std::string & sk = strings[i % std::size(strings)]; result.emplace(full_key_t{ i, sk }, value); } return result; } [[nodiscard]] std::pair<std::size_t, const std::string &> keys_from_i(std::size_t i) { return { i % map_size, strings[i % std::size(strings)] }; } std::size_t find_by_full_key( values_map_t & values) { std::size_t result{}; for(std::size_t i = 0; i != insertions; ++i) { const auto keys = keys_from_i(i); if(const auto it = values.find( full_key_t{ keys.first, keys.second }); it != values.end()) { ++result; } } return result; } std::size_t find_by_light_key( values_map_t & values) { std::size_t result{}; for(std::size_t i = 0; i != insertions; ++i) { const auto keys = keys_from_i(i); if(const auto it = values.find( light_key_t{ keys.first, std::addressof(keys.second) }); it != values.end()) { ++result; } } return result; } } /* namespace test */ class duration_meter { const char * _name; const std::chrono::high_resolution_clock::time_point _started_at; public: duration_meter( const char * name ) : _name{ name } , _started_at{ std::chrono::high_resolution_clock::now() } {} ~duration_meter() { const auto f = std::chrono::high_resolution_clock::now(); std::cout << "*** " << _name << ": " << std::chrono::duration_cast<std::chrono::microseconds>( f - _started_at ).count() << "us *** " << std::endl; } }; template<typename Lambda> decltype(auto) measure( const char * name, Lambda && lambda ) { duration_meter meter{ name }; return lambda(); } using namespace test; int main() { auto values = make_values(); const auto r1 = measure( "find_by_full_key", [&values]() { return find_by_full_key(values); }); std::cout << "values found: " << r1 << std::endl;; const auto r2 = measure( "find_by_light_key", [&values]() { return find_by_light_key(values); }); std::cout << "values found: " << r2 << std::endl;; } |
Комментариев нет:
Отправить комментарий