相关疑难解决方法(0)

我理解为什么不能这样做的原因(重新平衡和东西):

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. 重新平衡

特定

std::map<int,std::string> myMap;
fillMyMapWithStuff(myMap);

// modify key values - I need to add a constant value to each key
for (std::map<int,std::string>::iterator mi=myMap.begin(); mi != myMap.end(); ++mi)
{
    // ...
}

什么是一个好方法应用一些重新索引？我必须删除旧条目并使用新密钥和旧值添加新条目吗？