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


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

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 24

      0

      Идея хорошая, но как всегда есть одно "но". Если автор кода с контейнером не предусмотрел сравнение с нужным вам типом, фича не работает.

        +1
        так смысл в том что возможно подставить свой компаратор, при чем тут предусмотрен он автором или нет? до 14 стандарта чтоб найти string_view или любое другое представление строки в set<std::string> нужно всегда аллоцировать std::string, с геттерогенным копаратором этого делать не обязательно
        +1

        Как пользоваться гетерогенным поиском в set/map/… просто и давно известно — передаешь std::less<> вторым/третьим шаблонным аргументом и все само заработает, это все кому было интересно с 2014-го уже узнали. А вот, про unordered контейнеры информация
        1) свежая и поэтому пока малоизвестная,
        2) более сложная — просто передать std::-что-нибудь не получится,
        но, к сожалению, именно про это в статье ничего — ни примеров, ни теории, нет.

          –1

          Согласен, стоило бы дописать пример с неупорядоченными контейнерами, но зная о такой возможности после прочтения заметки можно найти нужные примеры.

            +2

            У меня на практике возникла потребность чтобы unordered_set и unordered_map работали и с char* и string_view и string.
            я решил эту проблему аналогично как в статье и поделился на вопросе на stackoverflow.


            Если вкратце то нужно создать два функтора hash и equal


            struct string_equal {
                using is_transparent = std::true_type ;
            
                bool operator()(std::string_view l, std::string_view r) const noexcept
                {
                    return l == r;
                }
            };
            
            struct string_hash {
                using is_transparent = std::true_type ;
            
                auto operator()(std::string_view str) const noexcept {
                    return std::hash<std::string_view>()(str);
                }
            };

            Для unordered_set код будет выглядеть так:


            std::unordered_set<std::string, string_hash, string_equal>;

            С мапой будет аналогично, только тип ключа ещё будет.

              +2

              Достаточно одного функтора (в качестве компаратора подойдет std::equal_to<>), и его можно сделать однострочным:


              struct string_hash : std::hash<std::string_view> {
                  using is_transparent = std::true_type;
              };
              
              std::unordered_set<std::string, string_hash, std::equal_to<>>;

              В общем-то мой комментарий был к тому, что "зная о такой возможности после прочтения заметки можно найти нужные примеры" немножко не правда, пока что именно про unordered containers качественных материалов нет, и даже самая свежая версия proposal-а P0919 отличается от того что в итоге попало в стандарт.

                0

                Здорово, я как то не додумался до такого простого варианта

                0
                Это не должно работать, т.к. find у unordered_map/unordered_set не имеет перегрузку ниже для find:
                template< class K > iterator find( const K& x );


                Поправка:
                в c++20 должно работать
                  0

                  А вот для unordered_set<unique_ptr<T>> будет немного сложнее:


                  struct Equal {
                      using is_transparent = void;
                      template<class U, class S>
                      bool operator()(const U& lhs, const S& rhs) const { 
                          return std::to_address(lhs) == std::to_address(rhs); 
                      }
                  };
                  
                  struct Hash {
                      using is_transparent = void;
                      template<class U>
                      size_t operator()(const U& ptr) const {
                          return std::hash<U>{}();
                      }
                  }
                  
                  template<class T>
                  using UnorderedSetOfUniquePtrs = std::unordered_set<std::unique_ptr<T>, Hash, Equal>;

                  https://stackoverflow.com/q/64243246/261217
                  https://www.coursera.org/learn/c-plus-plus-brown/supplement/TtrLN/unordered-set-unique-ptr

                +1
                Но если мы зададим компаратор в шаблоне, то тип контейнера изменится. Из-за этого придется таскать везде свой компаратор. Есть ли какое нибудь решение этой проблемы?
                  0

                  Полиморфных компараторов ещё не завезли и вряд ли завезут :-) Так что темплейтный using как решение вполне себе работает.

                  –1
                  Ценность от гетерогенного поиска в set ограничена тем, что возвращается const reference. Поменять объект без const_cast невозможно. Представить себе сценарий при котором я хочу использовать гетерогенный поиск и не менять возвращаемый объект мне лично непросто. Ваш пример с хранением тредов из этой серии — красиво только на картинке.
                    +1

                    Сценарий проверки наличия чего-либо в контейнере, например. Весь этот гетерогенный поиск в равной степени относится и к “map”, просто на set’е показывать удобнее.

                      0
                      Во-первых, возвращается iterator. Во-вторых, у std::set он всегда был определен как синоним к const_iteraror, то есть данное поведение обычно и от вида поиска не зависит. std::set вообще именно для этого и существует. Применительно к данному случаю, пример с тредами (которые non-copyable) в принципе жизненный и решает совершенно конкретную проблему.

                      Идея же принудительно кастить константную ссылку на индексный объект в множестве — весьма богатая. Действительно, непросто сказать, когда бы такое действие было необходимо и не являлось грубой ошибкой.
                        0

                        В C++17 можно манипулировать узлами node-based контейнеров — извлечь, поменять ключ/значение и вставить назад (или в другой контейнер того же типа)


                        https://en.cppreference.com/w/cpp/container/set/extract


                        std::set<int> cont{1, 2, 3};
                        auto nh = cont.extract(1);
                        nh.value() = 4; 
                        cont.insert(move(nh));
                          0
                          Это, конечно, лучше чем erase/insert, т.к. экономит аллокацию памяти, но не избавляет от необходимости ребалансировки контейнера при вставке и удалении узла.
                        0

                        А в
                        std::forward<T>(t) < std::forward<U>(u);
                        нужны оба форварда? Почему не получится
                        t < std::forward<U>(u);?

                          0

                          Просто упрощённая калька требований стандарта к обобщённой(!) специализации этого функционального объекта.


                          // 20.14.7.4 Class template less
                          
                          template<>
                          struct less<void> {
                            using is_transparent = unspecified;
                          
                            template<class T, class U>
                            constexpr auto operator()(T&& t, U&& u) const
                              -> decltype(std::forward<T>(t) < std::forward<U>(u));
                          };
                          
                          // Returns: std::forward<T>(t) < std::forward<U>(u).
                            0

                            А, спасибо

                              0
                              кажется что было бы логичнее указать в виде возвращаемого типа convertible_to&ltbool&gt, потому что иначе чушь получается — что бы там operator&lt ни возвращал, нас интересует лишь можем ли мы это подставить в if
                                0

                                я не настолько прошарен, я бы bool поставил :|

                                  0
                                  ну нам нужно что-то что мы можем засунуть внутрь if (...)
                                  0

                                  Зачем operator< возвращать что-то отличное от bool?

                                    0
                                    ну была например библиотека которая с помощтью операторов больше/меньше и прочего формировала XML документы и проверяла их консистентность в compile-time. Естественно эти операторы возвращали хитрые прокси-объекты, а не bool. В большинстве случаев конечно это не нужно, и ретроспективно кажется, что операторам в с++ надо было вводить ограничения на типы возвращаемых значений

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое