Перенос объекта в map - C/C++. Прикладные вопросы

Привет,

прошу совета знатоков стандарта.
Какой стандарто-безопасный метод изменить ключ объекта в std::map<int, object> с минимальным оверхедом? Что-то типа

nodes.emplace(newKey, nodes.extract(oldKey).second);

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

pva>Привет,

pva>прошу совета знатоков стандарта.
pva>Какой стандарто-безопасный метод изменить ключ объекта в std::map<int, object> с минимальным оверхедом? Что-то типа
pva>

nodes.emplace(newKey, nodes.extract(oldKey).second);

А чем вариант из примера не подходит?

std::map<int, std::string> m{{1, "mango"}, {2, "papaya"}, {3, "guava"}};
auto nh = m.extract(2);
nh.key() = 4;
m.insert(std::move(nh));
// m == {{1, "mango"}, {3, "guava"}, {4, "papaya"}}

Ну или твой вариант будет так выглядить

nodes.emplace(newKey, nodes.extract(oldKey).mapped());

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

I>А чем вариант из примера не подходит?
I>

I>auto nh = m.extract(2);
I>nh.key() = 4;
I>m.insert(std::move(nh));
I>

Сейчас так и сделал, но это ж не one-liner.

I>Ну или твой вариант будет так выглядить
I>

nodes.emplace(newKey, nodes.extract(oldKey).mapped());

А вот здесь меня смущает обсуждение похожего топика на reddit. Хотя, лично я не вижу здесь технически места для UB или еще какой гадости.

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

I>>Ну или твой вариант будет так выглядить
I>>

nodes.emplace(newKey, nodes.extract(oldKey).mapped());

pva>А вот здесь меня смущает обсуждение похожего топика на reddit. Хотя, лично я не вижу здесь технически места для UB или еще какой гадости.
Так там другое обсуждают,

(foo.key, std::move(foo))

с твоим newKey, oldKey всё должно быть хорошо.

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

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

I>>А чем вариант из примера не подходит?
pva>Сейчас так и сделал, но это ж не one-liner.

Оберни в функцию.

I>>Ну или твой вариант будет так выглядить
I>>

nodes.emplace(newKey, nodes.extract(oldKey).mapped());

pva>А вот здесь меня смущает ...

Тебя должно в этом коде смущать совсем другое: он не только содержит в себе лишнюю работу с динамической памятью (создаёт и удаляет узлы дерева), но даже пользователький тип значения (mapped) не перемещает, а копирует. Даже без использования node-handle и extract можно было бы с меньшими накладными расходами реализовать операцию.
Делай лучше, как в примере написано.

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

W>Тебя должно в этом коде смущать совсем другое: он не только содержит в себе лишнюю работу с динамической памятью (создаёт и удаляет узлы дерева).
А конкретней? Или ты имеешь в виду что можно было бы перегрузить дерево и похачить перемещение узла прямо во внутренностях?

W>но даже пользователький тип значения (mapped) не перемещает, а копирует.
Я в семантику mapped не заглядывал. Доверился предыдущему отвечающему что оно по итогу прокинется через move.

W>Даже без использования node-handle и extract можно было бы с меньшими накладными расходами реализовать операцию.
А именно?

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

pva>А конкретней? Или ты имеешь в виду что можно было бы перегрузить дерево и похачить перемещение узла прямо во внутренностях?

Именно так. Вот тебе небольшая демонстрашка:

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

#include <iostream>
#include <map>
#include <string>

struct A {
    std::string name;

    explicit A(const std::string& name) : name(name){}

    A(const A&) = delete;
    A(A&&) = delete;
};

using Map = std::map<int, A>;

void replaceKey(Map& map, int oldKey, int newKey) {
    if (oldKey != newKey) {
        auto&& node = map.extract(oldKey);
        node.key() = newKey;
        map.insert(std::move(node));
    }
}

int main() {
    Map map;
    
    map.emplace(1, "one");
    map.emplace(2, "ten");
    map.emplace(3, "three");

    replaceKey(map, 2, 10);
    
    for(auto&&[key, a] : map) {
        std::cout << key << ", " << a.name << std::endl;
    }
}

Обрати внимание на удалённые конструкторы копирования и перемещения в классе A.

P.S. Само название node-handle намекает на то, что extract возвращает некую обёртку над узлом дерева, а не сам узел.

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

pva>>А конкретней? Или ты имеешь в виду что можно было бы перегрузить дерево и похачить перемещение узла прямо во внутренностях?
R>Именно так. Вот тебе небольшая демонстрашка:
Ну, это ты повторил пример с cppreference. Здесь все было понятно без лишних слов.

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

pva>>>А конкретней? Или ты имеешь в виду что можно было бы перегрузить дерево и похачить перемещение узла прямо во внутренностях?
R>>Именно так. Вот тебе небольшая демонстрашка:
pva>Ну, это ты повторил пример с cppreference. Здесь все было понятно без лишних слов.

Ну из примера на cppreference вовсе не очевидно, что при перемещении node-handle не происходит ни перемещения, ни копирования пользовательских данных. У меня акцент был сделан на этом.

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

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

R>мне не совсем понятно, к чему относятся твои вопросы.
1) Я слабо ориентируюсь в стандартной библиотеке и стандарте как таковом. Была мысль, что есть какая-то стандартная операция или функция в <algorithms>. Плюс встретил упомянутое выше обсуждение на reddit. Впрочем, там ясно что порядок вычисления аргументов может влиять.
2) watchmaker также написал что однострочник с mapped() копирует пользовательский объект, хотя по коду библиотеки я такого, вроде, не наблюдаю (добрался таки до IDE).
extract() возвращает тот же самый handler, mapped() возвращает ref, а emplace реализует movable семантику. В каком месте происходит копирование — для меня пока загадка.
addon. 3) стало интересно как можно было бы "без использования node-handle и extract ... с меньшими накладными расходами реализовать операцию". Впрочем, очевидно перегрузив map и реализовав перенос ключа. Хотя это и прибивало бы код гвоздями к конкретной реализации map.

Вот и спросил для уверенности.

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

pva>extract() возвращает тот же самый handler, mapped() возвращает ref, а emplace реализует movable семантику. В каком месте происходит копирование — для меня пока загадка.

emplace обеспечивает конструирование объекта "по месту" — в соответствии с фактическими параметрами, передаваемыми конструктору. В данном случае параметром для конструирования объекта является lvalue ссылка, которую вернул mapped. Соответственно конструирование "по месту" будет выполнено через конструктор копирования (даже не перемещения).

pva>addon. 3) стало интересно как можно было бы "без использования node-handle и extract ... с меньшими накладными расходами реализовать операцию". Впрочем, очевидно перегрузив map и реализовав перенос ключа. Хотя это и прибивало бы код гвоздями к конкретной реализации map.

Ну, максимум, чего можно было бы добиться — это замены копирования на перемещение, обернув mapped в move:

nodes.emplace(newKey, std::move(nodes.extract(oldKey).mapped()));

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

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

R>emplace обеспечивает конструирование объекта "по месту" — в соответствии с фактическими параметрами, передаваемыми конструктору. В данном случае параметром для конструирования объекта является lvalue ссылка, которую вернул mapped. Соответственно конструирование "по месту" будет выполнено через конструктор копирования (даже не перемещения).
А, чорт. В этом направлении я даже не подумал. Спасибо за подробности. Я считал что move для ссылки переносит исключительно саму ссылку, не трогая объект. Соответственно, std::move поэтому избыточен и deprecated.

	От:	pva
	Дата:	03.06.25 06:31
	Оценка:

	От:	Igore
	Дата:	03.06.25 06:51
	Оценка:	2 (1)

	От:	pva
	Дата:	03.06.25 08:43
	Оценка:

	От:	Igore
	Дата:	03.06.25 09:00
	Оценка:	+1

	От:	watchmaker
	Дата:	03.06.25 11:47
	Оценка:	11 (2)