Re[4]: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 02.08.21 16:55
Оценка: 12 (3)
Здравствуйте, rg45, Вы писали:

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


W>>А сделать реализацию emplace без безусловного выделения памяти и создания временных узлов для разных типов либо невозможно, либо настолько сложно, что авторы реализаций STL тоже этого не делают и делать не будут.


R>Вот тут я не очень понимаю, в чем сложность. Что мешает сначала поискать, а потом выделять память?




Есть простой способ познать безнадёжность — открыть свою версию STL и попробовать добавить туда эту оптимизацию


Есть много разных проблем вроде требования strong exception guarantee, которые сложно поддерживать.
Но тут всё ломается даже без этого: основная проблема в том, что в аргументах emplace передаются совсем не ключ и значение.


Это касается всех ассоциативных контейнеров, но для начала рассмотрим std::unordered_set<std::string>. Для работы нужно уместь считать хеш от строки, и уметь сравнивать две строки на равенство.
А теперь пример:
    const string a5{"aaaaa"};

    unordered_set<string> cc;


    cc.emplace(a5);
    cc.emplace("aaaaa");
    cc.emplace(begin(a5), end(a5));
    cc.emplace(5, 'a');



В первом вызове emplace получает string, во втором — const char*, в третьем — два итератора, а в четвёрном два параметра уже совсем разных типов.


> Что мешает сначала поискать,


А теперь вспоминаем, что чтобы найти что-то в хеш-таблице, то нужно сначала посчитать хеш от ключа, а потом ещё разрешить коллизии через сравнение на равенство.

И значит наш быстрый метод unordered_set<string>::emplace должен уметь считать хеш char* или от пары аргументов (5 и 'a'), и при этом гарантировать, что хеш от (5,'a') будет таким же, как и от "aaaaa". Попробуй написать такую (нетривиальную) хеш-функцию
Дальше ещё нужно научится разрешать коллизии и уметь отвечать, а точно ли уже хранящаяся в контейнере строка string{"collision_string"} совпадёт со строкой, построенной из begin(a5), end(a5)? (и это ещё без всяких заморочек с тем, что begin/end могут быть input_iterator'ами, по которым пройтись нельзя больше одного раза).


То есть проблема в том, что нужно очень глубоко знать детали реализации классов, чтобы понимать, какие параметра конструктора как влияют на его значение.
Это даже для известных STL-типов сложно, а для произвольных — так и подавно.
Разве что с примитивными можно что-то эффективное написать (хотя бы map<int,int> ускорился бы ).


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


Можно, конечно, сказать, что давайте сконструируем сначала ключ, а потом уже значение. То есть в коде
map<U, V> sm;
sm.emplace(4, 5);

сначала создадим U{4} на стеке (мы же от кучи хотим избавится), а потом поищем его в контейнере, и если не найдём, то сделаем move будем конструировать пару из {move(tmpU), V{5}).
Но тут, конечно же всё ломается из-за неперемещаемых типов:
struct U {
    U(int);
    U(const U&) = delete; // oops
    friend bool operator==(const U&, const U&);
};

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


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


Вот и получается, что разве что для примитивных типов ключей можно что-то хорошее придумать.


-----


А try_emplace все эти проблемы перекладывает на вызывающий код. Он должен сам сконструировать ключ и передать его внутрь. Раз есть готовый ключ, то не надо думать как из аргументов конструктора считать хеш или как сравнивать на равенство ещё не созданные объекты.
Да, try_emplace из-за этого не может работать с неперемещаемыми/некопируемыми ключами, но так он и является отдельным методом.
Re[2]: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 02.08.21 09:52
Оценка: 12 (1)
Здравствуйте, rg45, Вы писали:

R> использование метода find в данном случае нецелесообразно, поскольку метод emplace, так же точно как и метод insert, выполняет вставку только в том случае, если элемент с данным ключом отсутствует в контейнере. Если элемент с таким ключом уже существует, то оба эти метода действуют подобно find.


В целом согласен, но хочется заострить внимание, что
с точки зрения эффективности разница есть и эти методы не подобны find по скорости.
Вызов find(key) проверит наличие ключа в контейнере. А вызов emplace(key, value) сначала выделит память под новый узел, потом сконструирует в нём пару ключ-значение, только потом запустит поиск в контейнере, и в случае успешного поиска разрушит этот временный узел.
То есть, по сравнению с find, всегда будет выделение памяти и конструирование копий ключа и значения(!) в нём.

И если ожидается, что ключ должен найтись в ассоциативном контейнере, то может оказаться выгоднее делать два захода: сначала более лёгкий find и лишь в случае его неудачи тяжёлый emplace. Даже несмотря на то, что из-за этого придётся сделать поиск ещё раз. В случае, когда в map'е кешируются какие-то тяжёлые объекты, разница становится очень заметна.

(Тут ещё можно огорчится, что к несчастью интерфейс emplace_hint оказался тоже криво спроектированным в раннем С++ и не может ускорить вставку для хеш-таблиц, убрав необходимость повторного поиска).

А сделать реализацию emplace без безусловного выделения памяти и создания временных узлов для разных типов либо невозможно, либо настолько сложно, что авторы реализаций STL тоже этого не делают и делать не будут.



Конечно, этот дефект в дизайне emplace для ассоциативных контейнеров давно известен. И поэтому в С++17 появился вызов try_emplace c другой семантикой, который как раз позволяет не делать лишней работы, которую делает emplace, если ожидается, что ключ будет найден.

И уж если заменять пару find+emplace, то именно на try_emplace или на operator[] (который теперь определён как тонкая обёртка над try_emplace).
Отредактировано 02.08.2021 15:02 watchmaker . Предыдущая версия .
Re[6]: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 03.08.21 13:57
Оценка: 6 (1)
Здравствуйте, rg45, Вы писали:

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


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

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

И чтобы хоть как-то обойти эту проблему, пошли по пути добавления нового метода в ассоциативные контейнеры.
Re: unorderd_map внутри unordered_map и emplace()
От: rg45 СССР  
Дата: 31.07.21 01:36
Оценка: +1
Здравствуйте, .alex, Вы писали:

A>День добрый. Не знаю на сколько грамотно придумал, может поправите.

A>Пытаюсь сделать сводную таблицу по данным из БД по 4 строкам и структурой в качестве значения.

A>Идея была в том, что при получении очередной записи из БД поочередно искать в мапах ключ/строку и если не нашли, то добавлять новую, что-то типа такого:

A>Подскажите как собственно добавлять новую запись, желательно через emplace()
A>PS. И вообще может есть другие — более элегантные способы сделать сводную таблицу по данным из ДБ (в своем коде). Делать group by запросом не подходит...


Во-первых, вместо нескольких вложенных мап, можно использовать одну с составным ключом. В качестве составного ключа вполне подойдет std::tuple:

using pivot_map_key = std::tuple<std::wstring, std::wstring, std::wstring, std::wstring>;
using pivot_map = std::unordered_map<pivot_map_key, pivot_entry>;


Во-вторых, использование метода find в данном случае нецелесообразно, поскольку метод emplace, так же точно как и метод insert, выполняет вставку только в том случае, если элемент с данным ключом отсутствует в контейнере. Если элемент с таким ключом уже существует, то оба эти метода действуют подобно find. Результатом является пара — итератор и булевское значение по которому можно узнать была ли выполнена вставка нового элемента, или элемент с данным ключом уже существовал:

    const auto [it, inserted] = pm->emplace(pivot_map_key{"one", "two", "three", "four"}, pivot_entry{});
    auto& [key, pivot] = *it;
    if (inserted)
    {
        // Process insertion
    }
    else
    {
        // Update existing entry
    }


В-третьих, если вставка нового элемента и обновление существующего у тебя обрабатываются одинаково, то, возможно, наиболее удобным будет доступ к элементам мапы через оператор []. Вставка и поиск будут выполняться когда нужно и как нужно:

    pivot_entry& pivot = {*pm}[{"one", "two", "three", "four"}];
    // Update new or existing entry...
--
unorderd_map внутри unordered_map и emplace()
От: .alex Ниоткуда  
Дата: 23.07.21 15:42
Оценка:
День добрый. Не знаю на сколько грамотно придумал, может поправите.
Пытаюсь сделать сводную таблицу по данным из БД по 4 строкам и структурой в качестве значения.
Объявил такие типы.
struct pivot_entry
{
    uint32_t nCnt;
    double fSum;
    double fPart;
    std::unordered_map<double, std::wstring> mStrings;
};
typedef std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, pivot_entry>>>> pivot_map;


Идея была в том, что при получении очередной записи из БД поочередно искать в мапах ключ/строку и если не нашли, то добавлять новую, что-то типа такого:
// look for Fld1
auto itFld1 = pm->find(pwszFld1);
if (itFld1 != pm->end())
{
    // look for Fld2
    auto itFld2 = itFld1->second.find(pwszFld2);
    if (itFld2 != itFld1->second.end())
    {
        // look for Fld3
        auto itFld3 = itFld2->second.find(pwszFld3);
        if (itFld3 != itFld2->second.end())
        {
            // look for Fld4
            auto itFld4 = itFld3->second.find(pwszFld4);
            if (itFld4 != itFld3->second.end())
            {
                // pivot_entry already exists - just update it
            }
            else
            {
                // add new pivot_entry from Fld4
            }
        }
        else
        {
            // add new pivot_entry from Fld3
        }
    }
    else
    {
        // add new pivot_enrty from Fld2
    }
}
else
{
    // add new pivot_entry from Fld1
    pm->emplace(pwszFld1, std::unordered_map<pwszFld2, std::unordered_map<pwszFld3, std::unordered_map<pwszFld4, >>>());
}

Подскажите как собственно добавлять новую запись, желательно через emplace()
PS. И вообще может есть другие — более элегантные способы сделать сводную таблицу по данным из ДБ (в своем коде). Делать group by запросом не подходит...
Re: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 23.07.21 16:16
Оценка:
Здравствуйте, .alex, Вы писали:


A>Идея была в том, что при получении очередной записи из БД поочередно искать в мапах ключ/строку и если не нашли, то добавлять новую, что-то типа такого:

A>
A>// look for Fld1
...
A>else
A>{
A>    // add new pivot_entry from Fld1
    pm->>emplace(pwszFld1, std::unordered_map<pwszFld2, std::unordered_map<pwszFld3, std::unordered_map<pwszFld4, >>>());
A>}
A>

Проще будет вместо такой лесенки сделать создание только на верхнем уровне для первого ключа и потом безусловно переходить к проверке следующего уровня. Так не надо будет выписывать все эти вложенные структуры.
Но можно делать ещё короче:
(*pm)[pwszFld1][pwszFld2][pwszFld3][pwszFld4] = new_pivot_entry; // update with replace

Это покроет все случаи с отсутствием ключей на любых уровнях и работать будет быстрее.

A>Подскажите как собственно добавлять новую запись, желательно через emplace()

Ну при желании можешь написать на последнем уровне через emplace.
Re[2]: unorderd_map внутри unordered_map и emplace()
От: .alex Ниоткуда  
Дата: 23.07.21 22:05
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Но можно делать ещё короче:

W>
W>(*pm)[pwszFld1][pwszFld2][pwszFld3][pwszFld4] = new_pivot_entry; // update with replace
W>

W>Это покроет все случаи с отсутствием ключей на любых уровнях и работать будет быстрее.

Спасибо! Выглядит очень хорошо) только не соображу, если мне нужно апдейтить запись если она существует, а не просто перезаписывать новой... Ну т.е. инкрементировать счётчик, увеличивать сумму и пр. Как мене проверить, что по этому "пути" в моих вложенных мапах есть данные?
Re[3]: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 23.07.21 23:53
Оценка:
Здравствуйте, .alex, Вы писали:

A> если мне нужно апдейтить запись если она существует, а не просто перезаписывать новой... Ну т.е. инкрементировать счётчик, увеличивать сумму и пр. Как мене проверить, что по этому "пути" в моих вложенных мапах есть данные?


Если у записи есть разумное значение по умолчанию, как, например, нулевое состояние у разных агрегирующих счётчиков, то можно заранее ничего не проверять, а просто использовать конструктор по умолчанию и всегда идти по пути обновления:
auto& accumulator = (*pm)[pwszFld1][pwszFld2][pwszFld3][pwszFld4]; // это либо существующий аккумулятор, либо только что созданный. Но дальнейший код в любом случае одинаков

accumulator.counter_1 += update.counter_1;
accumulator.sum_2     += update.sum_2;
итд


Если же нужно обязательно вызывать какой-то специфический конструктор для случая отсутствующего агрегатора, то либо использовать на нижнем уровне auto [it, ins] = try_emplace, либо использовать медленную пару find+insert для совсем уж сложных случаев, когда даже аргументы для конструктора подготовить дорого (во многих библиотеках контейнеров есть ещё вариант find+insert with hint, но для std::unordered_map оно не работает, то есть не ускоряет вставку, хотя в интерфейсе такой метод присутствует).
Re: unorderd_map внутри unordered_map и emplace()
От: SuhanovSergey  
Дата: 30.07.21 09:54
Оценка:
Можно индексировать по составному ключу

https://godbolt.org/z/GY6EThrK4
Re[2]: unorderd_map внутри unordered_map и emplace()
От: Chorkov Россия  
Дата: 30.07.21 10:46
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

SS>Можно индексировать по составному ключу


SS>https://godbolt.org/z/GY6EThrK4


Можно проще:
std::unordered_map< std::tuple< std::wstring, std::wstring, std::wstring, std::wstring>, pivot_entry > pivot_map;

pivot_map[{"a", "b", "c", "d"}] = ...


но это дублирование строк (в ключах).
Re[2]: unorderd_map внутри unordered_map и emplace()
От: .alex Ниоткуда  
Дата: 31.07.21 10:06
Оценка:
Здравствуйте, rg45, Вы писали:

R>Во-первых, вместо нескольких вложенных мап, можно использовать одну с составным ключом. В качестве составного ключа вполне подойдет std::tuple:


R>
R>using pivot_map_key = std::tuple<std::wstring, std::wstring, std::wstring, std::wstring>;
R>using pivot_map = std::unordered_map<pivot_map_key, pivot_entry>;
R>



R>В-третьих, если вставка нового элемента и обновление существующего у тебя обрабатываются одинаково, то, возможно, наиболее удобным будет доступ к элементам мапы через оператор []. Вставка и поиск будут выполняться когда нужно и как нужно:


R>
R>    pivot_entry& pivot = {*pm}[{"one", "two", "three", "four"}];
R>    // Update new or existing entry...
R>



Спасибо. Но что-то я вообще про tuple был не в курсе...
пытаюсь объявить все это дело:
struct pivot_entry
{
    uint32_t nCnt;
    double fSum;
    double fPart;
};
using pivot_key = std::tuple<std::wstring, std::wstring, std::wstring, std::wstring>;
using pivot_map = std::unordered_map<pivot_key, pivot_entry>;

Выдается ошибка:

Error C2280 'std::_Uhash_compare<_Kty,_Hasher,_Keyeq>::_Uhash_compare(const std::_Uhash_compare<_Kty,_Hasher,_Keyeq> &)': attempting to reference a deleted function

вилимо нужен оператор расчета хэша для pivot_key, а как его правильно сделать не подскажете?
Re[3]: unorderd_map внутри unordered_map и emplace()
От: rg45 СССР  
Дата: 31.07.21 11:17
Оценка:
Здравствуйте, .alex, Вы писали:

A>пытаюсь объявить все это дело:

A>
A>struct pivot_entry
A>{
A>    uint32_t nCnt;
A>    double fSum;
A>    double fPart;
A>};
A>using pivot_key = std::tuple<std::wstring, std::wstring, std::wstring, std::wstring>;
A>using pivot_map = std::unordered_map<pivot_key, pivot_entry>;
A>

A>Выдается ошибка:
A>

A>Error C2280 'std::_Uhash_compare<_Kty,_Hasher,_Keyeq>::_Uhash_compare(const std::_Uhash_compare<_Kty,_Hasher,_Keyeq> &)': attempting to reference a deleted function

A>вилимо нужен оператор расчета хэша для pivot_key, а как его правильно сделать не подскажете?


Ну да, хэш-функцию нужно определить для этого составного ключа, используя хэш-функции его составных частей. Лучше всего воспользоваться для этого boost::hash_combine. Если библиотека boost недоступна, по каким-то причинам, эту хэш-функцию можно определить и самому, например, так:

http://coliru.stacked-crooked.com/a/fc62543479d51de7

using pivot_map_key = std::tuple<std::wstring, std::wstring, std::wstring, std::wstring>;

struct pivot_map_hash
{
    size_t operator()(const pivot_map_key& key) const
    {
        using str_hash = std::hash<std::wstring>;
        return
            str_hash()(std::get<0>(key)) ^
            (str_hash()(std::get<1>(key)) << 1) ^
            (str_hash()(std::get<2>(key)) << 2) ^
            (str_hash()(std::get<3>(key)) << 3);
    }
};

Ну и использовать этот класс в определении типа мапы:

using pivot_map = std::unordered_map<pivot_map_key, pivot_entry, pivot_map_hash>;
--
Re[4]: unorderd_map внутри unordered_map и emplace()
От: .alex Ниоткуда  
Дата: 02.08.21 08:04
Оценка:
Здравствуйте, rg45, Вы писали:


R>Ну и использовать этот класс в определении типа мапы:


R>
R>using pivot_map = std::unordered_map<pivot_map_key, pivot_entry, pivot_map_hash>;
R>


Да, спасибо. Только еще вопрос. А такой способ будет работать быстрее или медленнее, чем:
std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, pivot_entry>>>> pivot_map?

Или трудно сказать и нужно тестировать и тот и тот на реальных данных?
Re[5]: unorderd_map внутри unordered_map и emplace()
От: rg45 СССР  
Дата: 02.08.21 08:13
Оценка:
Здравствуйте, .alex, Вы писали:

A>Да, спасибо. Только еще вопрос. А такой способ будет работать быстрее или медленнее, чем:

A>std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, pivot_entry>>>> pivot_map?
A>Или трудно сказать и нужно тестировать и тот и тот на реальных данных?

Вот я бы не рискнул с уверенностью отвечать на этот вопрос без данных профайлера. Я склонен думать, что разница, если и будет, то пренебрежимо маленькой. Априори известно, что алгоритмическая сложность у этих двух подходов одинаковая (с точностью до коэффициента) и у подхода с одной мапой и составным ключом существенно проще код. Это уже надежный довод в пользу выбора второго подхода. Преждевременная оптимизация — корень всех зол, как известно.
--
Отредактировано 02.08.2021 8:55 rg45 . Предыдущая версия . Еще …
Отредактировано 02.08.2021 8:15 rg45 . Предыдущая версия .
Отредактировано 02.08.2021 8:14 rg45 . Предыдущая версия .
Re[3]: unorderd_map внутри unordered_map и emplace()
От: rg45 СССР  
Дата: 02.08.21 10:07
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>А сделать реализацию emplace без безусловного выделения памяти и создания временных узлов для разных типов либо невозможно, либо настолько сложно, что авторы реализаций STL тоже этого не делают и делать не будут.


Вот тут я не очень понимаю, в чем сложность. Что мешает сначала поискать, а потом выделять память?
--
Re[3]: unorderd_map внутри unordered_map и emplace()
От: .alex Ниоткуда  
Дата: 02.08.21 14:56
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>И если ожидается, что ключ должен найтись в ассоциативном контейнере, то может оказаться выгоднее делать два захода: сначала более лёгкий find и лишь в случае его неудачи тяжёлый emplace. Даже несмотря на то, что из-за этого придётся сделать поиск ещё раз. В случае, когда в map'е кешируются какие-то тяжёлые объекты, разница становится очень заметна.

Т.е. правильно ли я понял, что метод вставки/редактирования:
pivot_entry& pivot = (*pm)[{"one", "two", "three", "four"}];

будет выделять лишний раз выделять память (если ключ уже присутствует) и оптимальнее перед ним делать find() дабы этого избежать?
Re[3]: unorderd_map внутри unordered_map и emplace()
От: .alex Ниоткуда  
Дата: 02.08.21 15:01
Оценка:
Здравствуйте, Chorkov, Вы писали:

C>Можно проще:

C>
C>std::unordered_map< std::tuple< std::wstring, std::wstring, std::wstring, std::wstring>, pivot_entry > pivot_map;

C>pivot_map[{"a", "b", "c", "d"}] = ... 
C>


C>но это дублирование строк (в ключах).

А можно поподробнее... что такой метод будет использовать больше памяти для хранения данных, чем такой:
typedef std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, pivot_entry>>>> pivot_map;

Так?
Re[4]: unorderd_map внутри unordered_map и emplace()
От: rg45 СССР  
Дата: 02.08.21 15:19
Оценка:
Здравствуйте, .alex, Вы писали:

A>будет выделять лишний раз выделять память (если ключ уже присутствует) и оптимальнее перед ним делать find() дабы этого избежать?


Правильно. Но если ключ отсутсвует, то поиск по карте ты сделаешь дважды — превый раз в find, второй — в emplace. Вопрос сводится к тому, на чем потери меньше — на создании лишнего элемента или на лишнем поиске по карте. На такой маленькой структурке как у тебя, ответ очевидн, по-моему.
--
Отредактировано 02.08.2021 15:23 rg45 . Предыдущая версия .
Re[4]: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 02.08.21 15:35
Оценка:
Здравствуйте, .alex, Вы писали:

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


W>>И если ожидается, что ключ должен найтись в ассоциативном контейнере, то может оказаться выгоднее делать два захода: сначала более лёгкий find и лишь в случае его неудачи тяжёлый emplace. Даже несмотря на то, что из-за этого придётся сделать поиск ещё раз. В случае, когда в map'е кешируются какие-то тяжёлые объекты, разница становится очень заметна.

A>Т.е. правильно ли я понял, что метод вставки/редактирования:
A>
A>pivot_entry& pivot = (*pm)[{"one", "two", "three", "four"}];
A>

A>будет выделять лишний раз выделять память (если ключ уже присутствует) и оптимальнее перед ним делать find() дабы этого избежать?

Нет, не правильно. operator[] уже определён через try_emplace: https://eel.is/c++draft/associative#map.access-1 И поэтому он не создаёт ноду до получения результатов поиска. То есть из этих соображений никакой экономии не выйдет.


Осталась, правда, ещё одна причина заменять operator[]: гетерогенный поиск.
До недавнего времени в С++ с ним всё было очень плохо — он просто не поддерживался. И поэтому разницы не было — всё работало одинаково медленно.
Но теперь, если удастся выразить через него некоторые операции, то такая замена может иметь смысл.


Например, в конструкции (*pm)[{"one", "two", "three", "four"}] у тебя сейчас создаётся tuple из каких-то строк — и если эти строки достаточно длинные, то может потребоваться выделения памяти для их хранения. Потому что opetator[] принимает аргументом ссылку на std::tuple<std::wstring, std::wstring, std::wstring, std::wstring>, а std::wstring — владеющая строка.
А гетерогенный поиск позволит сначала сходить в контейнер с другим типом, который не обязательно требует выделения памяти. Например, с std::tuple<std::wstring_view, std::wstring_view, std::wstring_view, std::wstring_view>, который не хранит в себе строки и поэтому гарантированно не ходит в кучу, а может быть дёшево сконструирован на стеке (формально тут implementation-defined, но на практике так будет везде).


И, как видно, польза от гетерогенного поиска проявляется из-за возможности не конструировать ключ вообще, если с таким же результатом сравнивать можно другие типы.
А замена (*pm)[pivot_map_key{"one", "two", "three", "four"}] на pm->find(pivot_map_key{"one", "two", "three", "four"}) с последующим pm->emplace(pivot_map_key{"one", "two", "three", "four"}, pivot_entry{}) — это, конечно, бесcмысленно.


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

А пока, вызов operator[] — хороший выбор по умолчанию. Он не делает откровенно плохих действий. И если тебя устраивает его семантика, то оставляй его.
Отредактировано 02.08.2021 15:39 watchmaker . Предыдущая версия .
Re[5]: unorderd_map внутри unordered_map и emplace()
От: rg45 СССР  
Дата: 03.08.21 09:12
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>>>А сделать реализацию emplace без безусловного выделения памяти и создания временных узлов для разных типов либо невозможно, либо настолько сложно, что авторы реализаций STL тоже этого не делают и делать не будут.


R>>Вот тут я не очень понимаю, в чем сложность. Что мешает сначала поискать, а потом выделять память?


W>Есть простой способ познать безнадёжность — открыть свою версию STL и попробовать добавить туда эту оптимизацию


Но это не вытекает из требований стандарта (прямо или косвенно)? Почему-то именно этот вопрос меня беспокоит больше всего
--
Отредактировано 03.08.2021 9:12 rg45 . Предыдущая версия .
Re[4]: unorderd_map внутри unordered_map и emplace()
От: Chorkov Россия  
Дата: 03.08.21 09:24
Оценка:
Здравствуйте, .alex, Вы писали:

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


C>>Можно проще:

C>>
C>>std::unordered_map< std::tuple< std::wstring, std::wstring, std::wstring, std::wstring>, pivot_entry > pivot_map;

C>>pivot_map[{"a", "b", "c", "d"}] = ... 
C>>


C>>но это дублирование строк (в ключах).

A>А можно поподробнее... что такой метод будет использовать больше памяти для хранения данных, чем такой:
A>
A>typedef std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, std::unordered_map<std::wstring, pivot_entry>>>> pivot_map;
A>

A>Так?

Какой из вариантов адресации, использует больше памяти — сильно зависит от природы ключей.

Например: мы хотим проверять правильность литературного перевода, и хотим чтобы избежать посылке рецензентам уже проверенных (ими) вариантов перевода текстов:

[tr]
ключ 1 (исходный текст)ключ 2 (перевод)ключ 3 (рецензент)данные
1-я глава войны и мира...1-я глава войны и мира (на французском)"Иванов И. И."Одобрено
1-я глава войны и мира...1-я глава войны и мира (на французском)"Петров П. П."12 замечаний: ...
1-я глава войны и мира...1-я глава войны и мира (на французском) (другой перевод)"Иванов И. И."Одобрено
1-я глава войны и мира...1-я глава войны и мира (на французском) (другой перевод)"Петров П. П."Одобрено
...
Очевидно, что в случае составного ключа "1-я глава войны и мира" будет храниться 4 раза, а если использовать вложенные map-ы — то только один раз.

Если использовать string_view, вместо string, то проблема избежания выделения памяти под дубликаты строк, просто будет перенесена на контейнер, в котором находятся оригинальные строки, хотя часто это решение.
Re: unorderd_map внутри unordered_map и emplace()
От: .alex Ниоткуда  
Дата: 04.08.21 15:33
Оценка:
Всем спасибо за ответы. Вроде все понятно и все заработало!
Re[5]: unorderd_map внутри unordered_map и emplace()
От: saf_e  
Дата: 11.01.22 16:20
Оценка:
Здравствуйте, 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руктора эту проблему не обойти.


мне кажется это не валидно в принципе, т.к. как вы его искать планируете?
Re[6]: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 12.01.22 02:08
Оценка:
Здравствуйте, 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 и прочие не про просто так сделаны гетерогенными: можно делать поиск не конструируя ключ. Например, если у тебя есть множество умных указателей, то в нём можно найти элемент по указываемому адресу (т.е. по сырому указателю), не конструируя из него другой умный указатель.
Отредактировано 13.01.2022 17:24 watchmaker . Предыдущая версия .
Re[7]: unorderd_map внутри unordered_map и emplace()
От: saf_e  
Дата: 13.01.22 09:40
Оценка:
Здравствуйте, 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 — это то что он будет меняться при пересоздании объекта. И если мы не говорим про указатели, то попытка искать такой объект закончиться тем что мы будет искать его с другим хешом, а значит потеряем преимущество хеш-контейнера.
Re[8]: unorderd_map внутри unordered_map и emplace()
От: watchmaker  
Дата: 13.01.22 18:28
Оценка:
Здравствуйте, saf_e, Вы писали:

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


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


_> т.к. поменяв его на ... reinterpret_cast<uintptr_t>(&s)

Спасибо, что обратил внимание. Выше в примере опечатка. Конечно же имелся ввиду именно такой вариант с addressof хэшируемого объекта. Поправил.



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

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

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

_>Главная проблема с хешом зависящим от this — это то что он будет меняться при пересоздании объекта.

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

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


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


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

Только вот unordered_map обязан корректно поддерживать и те, и другие варианты хэш-функций.
Re[9]: unorderd_map внутри unordered_map и emplace()
От: saf_e  
Дата: 14.01.22 09:31
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Наивная реализация "позовём конструктор два раза" сломается уже для простого unordered_map<string, string>

А можно подробнее? До сих пор не вижу проблемы сделать (понятно что пример условный):
key_t key(param1);
node_t node(param1, param2);


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


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