Гетерогенный поиск в ассоциативных контейнерах на C++

[TargetSan]

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

[Arenoros]

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

[AndDav]

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

[MATov]

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

[avdosev]

У меня на практике возникла потребность чтобы 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>;

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

[AndDav]

Достаточно одного функтора (в качестве компаратора подойдет 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 отличается от того что в итоге попало в стандарт.

[avdosev]

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

[ksergey01]

Это не должно работать, т.к. find у unordered_map/unordered_set не имеет перегрузку ниже для find:

template< class K > iterator find( const K& x );

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

[mmatrosov]

А вот для 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

[amf1k]

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

[MATov]

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

[kostja]

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

[MATov]

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

[basil_pivovarov]

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

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

[demp]

В 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));

[kostja]

Это, конечно, лучше чем erase/insert, т.к. экономит аллокацию памяти, но не избавляет от необходимости ребалансировки контейнера при вставке и удалении узла.

[frobeniusfg]

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

[MATov]

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

// 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).

[frobeniusfg]

А, спасибо

[Antervis]

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

[frobeniusfg]

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

[Antervis]

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

[Playa]

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

[Antervis]

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