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