問題描述
我理解人們不能這樣做的原因(重新平衡和其他東西):
I understand the reasons why one can't just do this (rebalancing and stuff):
iterator i = m.find(33);
if (i != m.end())
i->first = 22;
但到目前為止，更改鍵的唯一方法(我知道)是從樹中完全刪除節(jié)點，然后使用不同的鍵插入值:
But so far the only way (I know about) to change the key is to remove the node from the tree alltogether and then insert the value back with a different key:
iterator i = m.find(33);
if (i != m.end())
{
value = i->second;
m.erase(i);
m[22] = value;
}
出于更多原因，這對我來說似乎效率很低:
This seems rather inefficient to me for more reasons:
遍歷樹三次(+ balance)而不是兩次(+ balance)
Traverses the tree three times (+ balance) instead of twice (+ balance)
另一個不必要的值副本
不必要的解除分配然后重新分配樹內(nèi)的節(jié)點
Unnecessary deallocation and then re-allocation of a node inside of the tree
我發(fā)現(xiàn)分配和釋放是這三個中最差的.我是不是遺漏了什么，或者有更有效的方法嗎?
I find the allocation and deallocation to be the worst from those three. Am I missing something or is there a more efficient way to do that?
我認為，理論上應該是可能的，所以我認為針對不同的數(shù)據(jù)結(jié)構(gòu)進行更改是不合理的.這是我想到的偽算法:
I think, in theory, it should be possible, so I don't think changing for a different data structure is justified. Here is the pseudo algorithm I have in mind:
在樹中找到我想要更改其鍵的節(jié)點.
Find the node in the tree whose key I want to change.
如果從樹中分離(不要解除分配)
Detach if from the tree (don't deallocate)
重新平衡
更改分離節(jié)點內(nèi)的密鑰
將節(jié)點插入回樹
重新平衡
推薦答案
在 C++17 中，新的 map::extract 函數(shù)可讓您更改密鑰.
示例:
In C++17, the new map::extract function lets you change the key.
Example:
std::map<int, std::string> m{ {10, "potato"}, {1, "banana"} };
auto nodeHandler = m.extract(10);
nodeHandler.key() = 2;
m.insert(std::move(nodeHandler)); // { { 1, "banana" }, { 2, "potato" } }
這篇關(guān)于更改 std::map 中元素鍵的最快方法是什么的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！