問題描述

我理解人們不能這樣做的原因(重新平衡和其他東西):

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:

1. 遍歷樹三次(+ balance)而不是兩次(+ balance)

1. Traverses the tree three times (+ balance) instead of twice (+ balance)

另一個不必要的值副本

不必要的解除分配然后重新分配樹內的節點

Unnecessary deallocation and then re-allocation of a node inside of the tree

我發現分配和釋放是這三個中最差的.我是不是遺漏了什么，或者有更有效的方法嗎?

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?

我認為，理論上應該是可能的，所以我認為針對不同的數據結構進行更改是不合理的.這是我想到的偽算法:

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:

1. 在樹中找到我想要更改其鍵的節點.

1. Find the node in the tree whose key I want to change.

如果從樹中分離(不要解除分配)

Detach if from the tree (don't deallocate)

重新平衡

更改分離節點內的密鑰

將節點插入回樹

重新平衡

推薦答案

在 C++17 中，新的 map::extract 函數可讓您更改密鑰.
示例:

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" } }

這篇關于更改 std::map 中元素鍵的最快方法是什么的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！