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


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

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 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. В большинстве случаев конечно это не нужно, и ретроспективно кажется, что операторам в с++ надо было вводить ограничения на типы возвращаемых значений

                            Only users with full accounts can post comments. Log in, please.