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

Question

我理解为什么一个人不能这样做(再平衡和其他东西):

iterator i = m.find(33);

if (i != m.end())
  i->first = 22;

但到目前为止，更改键的唯一方法(我知道)是从树中删除节点，然后用不同的键插入值:

iterator i = m.find(33);

if (i != m.end())
{
  value = i->second;
  m.erase(i);
  m[22] = value;
}

这对我来说似乎相当低效，原因有很多:

1. 遍历树三次(+平衡)而不是两次(+平衡)

2. 值的另一个不必要的拷贝

3. 不必要的释放，然后重新分配树内的节点

我发现分配和释放是这三个中最差的。我错过了什么还是有更有效的方法来做到这一点？

我认为，理论上应该是可能的，所以我认为改变不同的数据结构是不合理的。这是我想到的伪算法:

1. 在树中找到我要更改其键的节点。

2. 如果从树中分离(不要释放)

3. 再平衡

4. 更改分离节点内的键

5. 将节点重新插入树中

6. 再平衡

Answer 1

在 C++17 中，新的 map::extract功能可让您更改 key 。
示例:

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