在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功能允许您更改密钥.
例:

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

Answer 2

我在18个月前提出了关联容器的算法:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839

寻找标记的评论:[2009-09-19霍华德补充道:].

当时,我们太过接近FDIS来考虑这种变化.但是我认为它非常有用(你显然同意),我想把它送到TR2.也许您可以通过查找并通知您的C++ National Body代表,这是您希望看到的功能.

更新

这不确定,但我认为我们很有可能会在C++ 17中看到这个功能!:-)

Answer 3

你可以省略复制价值 ;

const int oldKey = 33;
const int newKey = 22;
const iterator it = m.find(oldKey);
if (it != m.end()) {
  // Swap value from oldKey to newKey, note that a default constructed value 
  // is created by operator[] if 'm' does not contain newKey.
  std::swap(m[newKey], it->second);
  // Erase old key-value from map
  m.erase(it);
}

Answer 4

STL映射中的键必须是不可变的.

似乎不同的数据结构或结构可能更有意义,如果你在配对的关键方面有那么大的波动性.

Answer 5

你不能.

正如你所注意到的那样,这是不可能的.组织地图以便您可以有效地更改与密钥关联的值,但不能相反.

您可以查看Boost.MultiIndex,特别是它的Emulating Standard Container部分.Boost.MultiIndex容器具有高效的更新功能.