更改 std::map 中元素键的最快方法是什么

2021-12-10 00:00:00 dictionary performance binary-tree c++ std

我理解人们不能这样做的原因(重新平衡和其他东西):

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

相关文章