我理解为什么不能只这样做（重新平衡等）的原因：
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;
}
这对我来说看起来相当低效，还有以下原因：
遍历树三次（+平衡）而不是两次（+平衡）
多余复制了一个值
在树内部进行不必要的释放和重新分配节点
我认为从这三个问题中，分配和释放是最糟糕的。我是否漏掉了什么或者是否有更高效的方法做到这一点？
我认为，理论上应该是可能的，所以我认为没有必要为了改变数据结构而做出改变。以下是我心中的伪算法：
找到想要更改键的节点。
将其从树上分离（不要释放）
重新平衡
更改已分离节点内的键
将节点重新插入树中
重新平衡
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" } }
你可以省略对value的复制操作；
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);
}
value_type是一个性能问题，那么应该专门为std::swap<value_type>进行特化，以比m[22] = it->second;中的单个赋值更加高效。 - aschepler大约18个月前，我在此处提交了关于关联容器的算法提议：
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839
查找标记为：“[2009-09-19 Howard adds：]”的评论。
当时，我们离FDIS太近，无法考虑这种变化。 然而，我认为它非常有用（您显然也同意），我想将其加入到TR2中。 也许您可以帮助找到并通知您的C ++国家机构代表，这是您想要看到的功能。
更新
尚不确定，但我认为我们很有可能在C ++17中看到此功能！ :-)
erase会销毁映射中的对象，并释放持有该对象的节点。emplace_hint会分配一个新节点，并从emplace_hint的参数中构造一个新对象。这些成员函数都是独立定义的，它们无法知道在您指定的组合中使用时的情况。这是关于此问题的最新提案，新版本将在几周内发布：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r1.pdf - Howard HinnantSTL maps中的键必须是不可变的。
如果您的键值对中的键具有较高的不稳定性，则似乎使用不同的数据结构可能更合适。
你应该把分配留给分配器。 :-)
正如你所说，当键值改变时，可能会有很多重新平衡的操作。这就是树的工作方式。也许22是树中的第一个节点，33是最后一个节点？我们知道什么呢？
如果避免分配很重要，也许你应该尝试使用vector或deque？它们以更大的块进行分配，因此可以节省调用分配器的次数，但可能会浪费内存。所有容器都有它们的权衡，取决于你在每种情况下需要哪个主要优势（假设这真的很重要）。
对于冒险者：
如果你确定更改键不会影响顺序，并且你永远不会犯错，那么一点const_cast就可以让你更改键。
如果您知道新键对于地图位置是有效的（更改它不会改变排序），并且您不想删除和添加项目到地图中，您可以使用const_cast来更改键，就像下面的unsafeUpdateMapKeyInPlace一样：
template <typename K, typename V, typename It>
bool isMapPositionValidForKey (const std::map<K, V>& m, It it, K key)
{
if (it != m.begin() && std::prev (it)->first >= key)
return false;
++it;
return it == m.end() || it->first > key;
}
// Only for use when the key update doesn't change the map ordering
// (it is still greater than the previous key and lower than the next key).
template <typename K, typename V>
void unsafeUpdateMapKeyInPlace (const std::map<K, V>& m, typename std::map<K, V>::iterator& it, K newKey)
{
assert (isMapPositionValidForKey (m, it, newKey));
const_cast<K&> (it->first) = newKey;
}
template <typename K, typename V>
void updateMapKey (const std::map<K, V>& m, typename std::map<K, V>::iterator& it, K newKey)
{
if (isMapPositionValidForKey (m, it, newKey))
{
unsafeUpdateMapKeyInPlace (m, it, newKey);
return;
}
auto next = std::next (it);
auto node = m.extract (it);
node.key() = newKey;
m.insert (next, std::move (node));
}
end()，不需要进行任何遍历。 - Tony Delroyfind，有一个遍历（traversal）的过程，然后erase(i)以迭代器作为参数（而不是要删除的值），避免了另一个遍历，但最终的insert需要进行第二次遍历来找到新位置插入（因为当键改变时，它可能在一个无关的位置 - 如果你知道新插入应该非常靠近树中的旧插入，可以提供插入提示）。 - Tony Delroy