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