Здравствуйте, rg45, Вы писали:
R>Здравствуйте, watchmaker, Вы писали:
W>>А сделать реализацию emplace без безусловного выделения памяти и создания временных узлов для разных типов либо невозможно, либо настолько сложно, что авторы реализаций STL тоже этого не делают и делать не будут.
R>Вот тут я не очень понимаю, в чем сложность. Что мешает сначала поискать, а потом выделять память?
Есть простой способ познать безнадёжность — открыть свою версию STL и попробовать добавить туда эту оптимизацию
Есть много разных проблем вроде требования strong exception guarantee, которые сложно поддерживать.
Но тут всё ломается даже без этого: основная проблема в том, что в аргументах emplace передаются совсем не ключ и значение.
Это касается всех ассоциативных контейнеров, но для начала рассмотрим std::unordered_set<std::string>. Для работы нужно уместь считать хеш от строки, и уметь сравнивать две строки на равенство.
А теперь пример:
В первом вызове 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}).
Но тут, конечно же всё ломается из-за неперемещаемых типов:
А если и это множество типов игнорировать, то сломается на типах, значение hash у которых зависит от this (как в python) (может кто-то безумный элементы DSU хранит в hash-map). И опять без знаний об внутреннем устройстве контcруктора эту проблему не обойти.
Вот и получается, что разве что для примитивных типов ключей можно что-то хорошее придумать.
-----
А try_emplace все эти проблемы перекладывает на вызывающий код. Он должен сам сконструировать ключ и передать его внутрь. Раз есть готовый ключ, то не надо думать как из аргументов конструктора считать хеш или как сравнивать на равенство ещё не созданные объекты.
Да, try_emplace из-за этого не может работать с неперемещаемыми/некопируемыми ключами, но так он и является отдельным методом.
Re[2]: unorderd_map внутри unordered_map и emplace()
Здравствуйте, 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).
Здравствуйте, rg45, Вы писали:
R>Но это не вытекает из требований стандарта (прямо или косвенно)? Почему-то именно этот вопрос меня беспокоит больше всего
В текущем стандарте общее решение для emplace-без-создания-ноды не получается реализовать. Было желание подправить требования для emplace, чтобы можно было написать эффективную реализацию, но там пока тоже не получилось что-то сделать.
И чтобы хоть как-то обойти эту проблему, пошли по пути добавления нового метода в ассоциативные контейнеры.
Здравствуйте, .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...
День добрый. Не знаю на сколько грамотно придумал, может поправите.
Пытаюсь сделать сводную таблицу по данным из БД по 4 строкам и структурой в качестве значения.
Объявил такие типы.
Идея была в том, что при получении очередной записи из БД поочередно искать в мапах ключ/строку и если не нашли, то добавлять новую, что-то типа такого:
// 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 запросом не подходит...
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()
Здравствуйте, watchmaker, Вы писали:
W>Но можно делать ещё короче: W>
W>(*pm)[pwszFld1][pwszFld2][pwszFld3][pwszFld4] = new_pivot_entry; // update with replace
W>
W>Это покроет все случаи с отсутствием ключей на любых уровнях и работать будет быстрее.
Спасибо! Выглядит очень хорошо) только не соображу, если мне нужно апдейтить запись если она существует, а не просто перезаписывать новой... Ну т.е. инкрементировать счётчик, увеличивать сумму и пр. Как мене проверить, что по этому "пути" в моих вложенных мапах есть данные?
Re[3]: unorderd_map внутри unordered_map и emplace()
Здравствуйте, .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 оно не работает, то есть не ускоряет вставку, хотя в интерфейсе такой метод присутствует).
Здравствуйте, rg45, Вы писали:
R>Во-первых, вместо нескольких вложенных мап, можно использовать одну с составным ключом. В качестве составного ключа вполне подойдет std::tuple:
R>
R>В-третьих, если вставка нового элемента и обновление существующего у тебя обрабатываются одинаково, то, возможно, наиболее удобным будет доступ к элементам мапы через оператор []. Вставка и поиск будут выполняться когда нужно и как нужно:
R>
R> pivot_entry& pivot = {*pm}[{"one", "two", "three", "four"}];
R> // Update new or existing entry...
R>
Спасибо. Но что-то я вообще про tuple был не в курсе...
пытаюсь объявить все это дело:
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()
Здравствуйте, .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 недоступна, по каким-то причинам, эту хэш-функцию можно определить и самому, например, так:
Да, спасибо. Только еще вопрос. А такой способ будет работать быстрее или медленнее, чем:
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()
Здравствуйте, .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>Или трудно сказать и нужно тестировать и тот и тот на реальных данных?
Вот я бы не рискнул с уверенностью отвечать на этот вопрос без данных профайлера. Я склонен думать, что разница, если и будет, то пренебрежимо маленькой. Априори известно, что алгоритмическая сложность у этих двух подходов одинаковая (с точностью до коэффициента) и у подхода с одной мапой и составным ключом существенно проще код. Это уже надежный довод в пользу выбора второго подхода. Преждевременная оптимизация — корень всех зол, как известно.
Здравствуйте, watchmaker, Вы писали:
W>А сделать реализацию emplace без безусловного выделения памяти и создания временных узлов для разных типов либо невозможно, либо настолько сложно, что авторы реализаций STL тоже этого не делают и делать не будут.
Вот тут я не очень понимаю, в чем сложность. Что мешает сначала поискать, а потом выделять память?
--
Re[3]: unorderd_map внутри unordered_map и emplace()
Здравствуйте, watchmaker, Вы писали:
W>И если ожидается, что ключ должен найтись в ассоциативном контейнере, то может оказаться выгоднее делать два захода: сначала более лёгкий find и лишь в случае его неудачи тяжёлый emplace. Даже несмотря на то, что из-за этого придётся сделать поиск ещё раз. В случае, когда в map'е кешируются какие-то тяжёлые объекты, разница становится очень заметна.
Т.е. правильно ли я понял, что метод вставки/редактирования:
Здравствуйте, .alex, Вы писали:
A>будет выделять лишний раз выделять память (если ключ уже присутствует) и оптимальнее перед ним делать find() дабы этого избежать?
Правильно. Но если ключ отсутсвует, то поиск по карте ты сделаешь дважды — превый раз в find, второй — в emplace. Вопрос сводится к тому, на чем потери меньше — на создании лишнего элемента или на лишнем поиске по карте. На такой маленькой структурке как у тебя, ответ очевидн, по-моему.
Здравствуйте, .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[] — хороший выбор по умолчанию. Он не делает откровенно плохих действий. И если тебя устраивает его семантика, то оставляй его.
Здравствуйте, watchmaker, Вы писали:
W>>>А сделать реализацию emplace без безусловного выделения памяти и создания временных узлов для разных типов либо невозможно, либо настолько сложно, что авторы реализаций STL тоже этого не делают и делать не будут.
R>>Вот тут я не очень понимаю, в чем сложность. Что мешает сначала поискать, а потом выделять память?
W>Есть простой способ познать безнадёжность — открыть свою версию STL и попробовать добавить туда эту оптимизацию
Но это не вытекает из требований стандарта (прямо или косвенно)? Почему-то именно этот вопрос меня беспокоит больше всего
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>Так?
Какой из вариантов адресации, использует больше памяти — сильно зависит от природы ключей.
Например: мы хотим проверять правильность литературного перевода, и хотим чтобы избежать посылке рецензентам уже проверенных (ими) вариантов перевода текстов:
ключ 1 (исходный текст)
ключ 2 (перевод)
ключ 3 (рецензент)
данные
1-я глава войны и мира...
1-я глава войны и мира (на французском)
"Иванов И. И."
Одобрено
1-я глава войны и мира...
1-я глава войны и мира (на французском)
"Петров П. П."
12 замечаний: ...
1-я глава войны и мира...
1-я глава войны и мира (на французском) (другой перевод)
"Иванов И. И."
Одобрено
1-я глава войны и мира...
1-я глава войны и мира (на французском) (другой перевод)
"Петров П. П."
Одобрено
[tr]
...
Очевидно, что в случае составного ключа "1-я глава войны и мира" будет храниться 4 раза, а если использовать вложенные map-ы — то только один раз.
Если использовать string_view, вместо string, то проблема избежания выделения памяти под дубликаты строк, просто будет перенесена на контейнер, в котором находятся оригинальные строки, хотя часто это решение.
Сразу напрашивается создавать сначала только ключ, а потом ноду ) т.к. обычно обьект ключа легковесный, а вся жесть в значении )
W>А если и это множество типов игнорировать, то сломается на типах, значение hash у которых зависит от this (как в python) (может кто-то безумный элементы DSU хранит в hash-map). И опять без знаний об внутреннем устройстве контcруктора эту проблему не обойти.
мне кажется это не валидно в принципе, т.к. как вы его искать планируете?
Re[6]: unorderd_map внутри unordered_map и emplace()
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>>>Но тут, конечно же всё ломается из-за неперемещаемых типов:
W>>>а сейчас такой emplace валидный.
W>И это даже не скомпилируется с тем классом, который ты так предусмотрительно процитировал в сообщении.
Не совсем понял почему, я наверное что-то упустил, но если можно создать ноду (т.е. ключ+значение в случае мапы) то можно создать и ключ, не? Сет не сильно интересен, т.к. стоимость создания ноды и ключа примерна равна.
_>> т.к. обычно обьект ключа легковесный, а вся жесть в значении )
Твой пример работает )
Главная проблема с хешом зависящим от this — это то что он будет меняться при пересоздании объекта. И если мы не говорим про указатели, то попытка искать такой объект закончиться тем что мы будет искать его с другим хешом, а значит потеряем преимущество хеш-контейнера.
Re[8]: unorderd_map внутри unordered_map и emplace()
Здравствуйте, 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()
Здравствуйте, watchmaker, Вы писали:
W>Наивная реализация "позовём конструктор два раза" сломается уже для простого unordered_map<string, string>
А можно подробнее? До сих пор не вижу проблемы сделать (понятно что пример условный):
key_t key(param1);
node_t node(param1, param2);
W>От хэш-функции требуется возвращать одинаковые значения для равных объектов (это обязательно) и по возможности возвращать разные значения для неравных объектов (это желательно). Если твоя хэш-функция удовлетворяет этим требованиям, то она пригодна для использования в ассоциативных таблицах.
Ну так пример кода который ты привел и будет формально его нарушать за исключением случая когда мы берем объект из мапа.
Как я понимаю именно этот вырожденный кейс мы и рассматриваем?