什么是更改std :: map内元素的键的最快方法 [英] What is the fastest way to change a key of an element inside std::map
问题描述
我理解为什么不能这样做（重新平衡和东西）的原因：
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;
但是到目前为止，改变键的唯一方法是删除节点然后用不同的键插入值：
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）
- 不必要的解除分配，然后重新分配树内的节点
分配和重新分配是这三者中最糟糕的。我缺少一些东西，还是有更有效的方法来做到这一点？
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?
更新：
我认为，理论上应该是可能的，所以我不要认为改变不同的数据结构是合理的。这里是我想到的伪算法：
UPDATE: 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:
- 在树中找到要更改其键的节点。
- 从树中分离（不解除分配）
- 重新平衡
- 更改分离节点内的键
- 将节点重新插入树状图
- rebalance
- find the node in the tree whose key I want to change.
- detach if from the tree (don't deallocate)
- rebalance
- change the key inside the detached node
- insert the node back into the tree
- rebalance
推荐答案
我在18个月前在这里提出了关联容器的算法：
I proposed your algorithm for the associative containers about 18 months ago here:
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg- closed.html＃839
查找标记的评论：[2009-09-19 Howard added：]。
Look for the comment marked: [ 2009-09-19 Howard adds: ].
当时，我们太接近FDIS考虑这个变化。但我认为它非常有用（和你明显同意），我想得到它TR2。
At the time, we were too close to FDIS to consider this change. However I think it very useful (and you apparently agree), and I would like to get it in to TR2. Perhaps you could help by finding and notifying your C++ National Body representative that this is a feature you would like to see.
更新
这是不确定的，但我认为有一个很好的机会，我们将看到这个功能在C + + 17！ ： - ）
It is not certain, but I think there is a good chance we will see this feature in C++17! :-)
这篇关于什么是更改std :: map内元素的键的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
