Здравствуйте, rg45, Вы писали:

R>Но это не вытекает из требований стандарта (прямо или косвенно)? Почему-то именно этот вопрос меня беспокоит больше всего

Можно посмотреть обсуждение вокруг https://cplusplus.github.io/LWG/issue2362

В текущем стандарте общее решение для emplace-без-создания-ноды не получается реализовать. Было желание подправить требования для emplace, чтобы можно было написать эффективную реализацию, но там пока тоже не получилось что-то сделать.

И чтобы хоть как-то обойти эту проблему, пошли по пути добавления нового метода в ассоциативные контейнеры.

Всем спасибо за ответы. Вроде все понятно и все заработало!

Здравствуйте, watchmaker, Вы писали:

W>Но тут, конечно же всё ломается из-за неперемещаемых типов:

struct U {
W>    U(int);
W>    U(const U&) = delete; // oops
W>    friend bool operator==(const U&, const U&);
W>};
W>

W>а сейчас такой emplace валидный.

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

W>А если и это множество типов игнорировать, то сломается на типах, значение hash у которых зависит от this (как в python) (может кто-то безумный элементы DSU хранит в hash-map). И опять без знаний об внутреннем устройстве контcруктора эту проблему не обойти.

мне кажется это не валидно в принципе, т.к. как вы его искать планируете?

Здравствуйте, saf_e, Вы писали:

_>Здравствуйте, watchmaker, Вы писали:

W>>Но тут, конечно же всё ломается из-за неперемещаемых типов:

struct U {
W>>    U(int);
W>>    U(const U&) = delete; // oops
W>>    friend bool operator==(const U&, const U&);
W>>};
W>>

W>>а сейчас такой emplace валидный.

_>Сразу напрашивается создавать сначала только ключ, а потом ноду )

И это даже не скомпилируется с тем классом, который ты так предусмотрительно процитировал в сообщении.


_> т.к. обычно обьект ключа легковесный, а вся жесть в значении )

Да, но отчасти это ещё и из-за того, что стандартная библиотека С++ довольно бедна контейнерами и структурами данных. А существующие вынуждают делать ключи именно такими.
Если бы в стандарте было что-то похожее на boost.bimap или boost.multi_index, то такое разделение на лёгкие ключи и тяжелые значения встречалось бы чуть реже.


W>>А если и это множество типов игнорировать, то сломается на типах, значение hash у которых зависит от this (как в python) (может кто-то безумный элементы DSU хранит в hash-map). И опять без знаний об внутреннем устройстве конструктора эту проблему не обойти.

_>мне кажется это не валидно в принципе, т.к. как вы его искать планируете?

Отлично ищется: https://godbolt.org/z/cTP6ccqT1
В чём проблема?
Тут, конечно, игрушечный пример, но например, во всяких графах такое встречается, когда вершины уникальные (и поэтому для нет необходимости вводить идентификаторы, а достаточно уже гарантированно уникального this), а ребра определяются связями между вершинами.

Также метод find и прочие не про просто так сделаны гетерогенными: можно делать поиск не конструируя ключ. Например, если у тебя есть множество умных указателей, то в нём можно найти элемент по указываемому адресу (т.е. по сырому указателю), не конструируя из него другой умный указатель.

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, saf_e, Вы писали:

_>>Здравствуйте, watchmaker, Вы писали:

W>>>Но тут, конечно же всё ломается из-за неперемещаемых типов:

struct U {
W>>>    U(int);
W>>>    U(const U&) = delete; // oops
W>>>    friend bool operator==(const U&, const U&);
W>>>};
W>>>

W>>>а сейчас такой emplace валидный.

W>И это даже не скомпилируется с тем классом, который ты так предусмотрительно процитировал в сообщении.

Не совсем понял почему, я наверное что-то упустил, но если можно создать ноду (т.е. ключ+значение в случае мапы) то можно создать и ключ, не? Сет не сильно интересен, т.к. стоимость создания ноды и ключа примерна равна.

_>> т.к. обычно обьект ключа легковесный, а вся жесть в значении )


W>Отлично ищется: https://godbolt.org/z/dhhafr8b1
W>В чём проблема?

namespace std {
    template<>
    struct hash<S> {
        size_t operator()(const S& s) const {
            return reinterpret_cast<uintptr_t>(this);
        }
    };
}

Например этот код показывает что значение хеша всем "до лампочки", т.к. поменяв его на

        size_t operator()(const S& s) const {
            return reinterpret_cast<uintptr_t>(&s);
        }

Или даже:

        size_t operator()(const S& s) const {
            return 12345678;
        }

Твой пример работает )
Главная проблема с хешом зависящим от this — это то что он будет меняться при пересоздании объекта. И если мы не говорим про указатели, то попытка искать такой объект закончиться тем что мы будет искать его с другим хешом, а значит потеряем преимущество хеш-контейнера.

Здравствуйте, saf_e, Вы писали:

_>Не совсем понял почему, я наверное что-то упустил, но если можно создать ноду (т.е. ключ+значение в случае мапы) то можно создать и ключ, не?

Можно создать либо одно, либо другое. Но не вместе — вот в чём проблема.
Если ты уже создал объект ключа (чтобы использовать его для поиска), то создать ноду в правильном состоянии (в котором она должна будет оказаться при успешной вставке) в общем случае не получится.
Наивная реализация "позовём конструктор два раза" сломается уже для простого unordered_map<string, string>, а варианты с перемещением или копированием созданного ключа в ноду также не будут работать в чуть более сложных случаях по разным вышеописанным причинам.


_> т.к. поменяв его на ... reinterpret_cast<uintptr_t>(&s)
Спасибо, что обратил внимание. Выше в примере опечатка. Конечно же имелся ввиду именно такой вариант с addressof хэшируемого объекта. Поправил.



_>Например этот код показывает что значение хеша всем "до лампочки",
_>Или даже: return 12345678
Тривиальная хэш-функция конечно же может использоваться в этих контейнерах. Но она не обеспечит хорошего времени операций.

От хэш-функции требуется возвращать одинаковые значения для равных объектов (это обязательно) и по возможности возвращать разные значения для неравных объектов (это желательно). Если твоя хэш-функция удовлетворяет этим требованиям, то она пригодна для использования в ассоциативных таблицах.

_>Главная проблема с хешом зависящим от this — это то что он будет меняться при пересоздании объекта.
И это замечательно, когда разные объекты имеют разное значение хэша. А тут аж на уровне языка гарантируется отсутствие коллизий. Всем требуется хэш-функция с такими хорошими свойствами.
Это настолько хорошо, что в других языках (например, в java или python) такое поведение вообще сделано поведением по умолчанию.

Другое дело, что не всегда такая функция подходит: возможность одновременного существования равных объектов — самый распространённый вариант, который вынуждает использовать менее эффективные альтернативы.


_>И если мы не говорим про указатели, то попытка искать такой объект закончиться тем что мы будет искать его с другим хешом, а значит потеряем преимущество хеш-контейнера.

Если это тот же объект, то и this у него будет тем же, и хэш, соответственно, тоже. И результат поиска в таблице (успех или неуспех) будет консистентным. Если искать какой-то другой объект, не равный исходному, то он будет иметь другое значение хэша и не сможет из-за этого устроить коллизию — ну это верно и очевидно.
Если ты определил равенство так, что у тебя есть несколько равных объектов, то такая хэш-функция тебе не подходит, надо выбирать другую, — это тоже очевидно.

Только вот unordered_map обязан корректно поддерживать и те, и другие варианты хэш-функций.

Здравствуйте, watchmaker, Вы писали:

W>Наивная реализация "позовём конструктор два раза" сломается уже для простого unordered_map<string, string>
А можно подробнее? До сих пор не вижу проблемы сделать (понятно что пример условный):

key_t key(param1);
node_t node(param1, param2);

W>От хэш-функции требуется возвращать одинаковые значения для равных объектов (это обязательно) и по возможности возвращать разные значения для неравных объектов (это желательно). Если твоя хэш-функция удовлетворяет этим требованиям, то она пригодна для использования в ассоциативных таблицах.

Ну так пример кода который ты привел и будет формально его нарушать за исключением случая когда мы берем объект из мапа.
Как я понимаю именно этот вырожденный кейс мы и рассматриваем?