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

What is the fastest way to change a key of an element inside std::map

提问by Peter Jankuliak

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. traverses the tree three times (+ balance) instead of twice (+ balance)
2. one more unnecessary copy of the value
3. unnecessary deallocation and then re-allocation of a node inside of the tree

1. 遍历树三次（+ balance）而不是两次（+ balance）
2. 另一个不必要的值副本
3. 不必要的解除分配，然后重新分配树内的节点

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?

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

UPDATE: 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. find the node in the tree whose key I want to change.
2. detach if from the tree (don't deallocate)
3. rebalance
4. change the key inside the detached node
5. insert the node back into the tree
6. rebalance

1. 在树中找到我想要更改其键的节点。
2. 如果从树中分离（不要解除分配）
3. 再平衡
4. 更改分离节点内的键
5. 将节点插入回树中
6. 再平衡

采纳答案by 21koizyd

In C++17, the new map::extractfunction lets you change the key.
Example:

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

回答by Howard Hinnant

I proposed your algorithm for the associative containers about 18 months ago here:

大约 18 个月前，我在这里提出了您的关联容器算法：

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

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

Look for the comment marked: [ 2009-09-19 Howard adds: ].

查找标记为：[ 2009-09-19 Howard 补充：] 的评论。

At the time, we were too close to FDIS to consider this change. However I think it very useful (and you apparently agree), and I would like to get it in to TR2. Perhaps you could help by finding and notifying your C++ National Body representative that this is a feature you would like to see.

当时，我们离 FDIS 太近了，无法考虑这种变化。但是我认为它非常有用（你显然同意），我想把它加入 TR2。也许您可以通过查找并通知您的 C++ 国家机构代表这是您希望看到的功能来提供帮助。

Update

更新

It is not certain, but I think there is a good chance we will see this feature in C++17! :-)

不确定，但我认为我们很有可能会在 C++17 中看到这个特性！:-)

回答by Viktor Sehr

You can omit the copying of value;

您可以省略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);
}

回答by Joe

Keys in STL maps are required to be immutable.

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

Seems like perhaps a different data structure or structures might make more sense if you have that much volatility on the key side of your pairings.

如果配对的关键方面具有如此大的波动性，那么似乎不同的数据结构或结构可能更有意义。

回答by Matthieu M.

You cannot.

你不能。

As you noticed, it is not possible. A map is organized so that you can change the value associated to a key efficiently, but not the reverse.

正如您所注意到的，这是不可能的。地图是经过组织的，因此您可以有效地更改与键关联的值，但反过来不行。

You have a look at Boost.MultiIndex, and notably its Emulating Standard Container sections. Boost.MultiIndex containers feature efficient update.

您可以查看 Boost.MultiIndex，尤其是它的Emulating Standard Container 部分。Boost.MultiIndex 容器具有高效的更新功能。

回答by Bo Persson

You should leave the allocation to the allocator. :-)

您应该将分配留给分配器。:-)

As you say, when the key changes there might be a lot of rebalancing. That's the way a tree works. Perhaps 22 is the first node in the tree and 33 the last? What do we know?

正如您所说，当密钥发生变化时，可能会有很多重新平衡。这就是树的工作方式。也许 22 是树中的第一个节点，而 33 是​​最后一个？我们知道什么？

If avoiding allocations is important, perhaps you should try a vector or a deque? They allocate in larger chunks, so they save on number of calls to the allocator, but potentially waste memory instead. All the containers have their tradeoffs and it is up to you to decide which one has the primary advantage that you need in each case (assuming it matters at all).

如果避免分配很重要，也许您应该尝试使用向量或双端队列？它们以更大的块分配，因此它们节省了对分配器的调用次数，但可能会浪费内存。所有容器都有其权衡，由您决定在每种情况下哪个具有您需要的主要优势（假设它很重要）。

For the adventurous:
If you know for sure that changing the key doesn't affect the order and you never, ever make a mistake, a little const_cast wouldlet you change the key anyway.

对于
喜欢冒险的人：如果您确定更改密钥不会影响顺序并且您永远不会犯错误，那么一点 const_cast无论如何都会让您更改密钥。

回答by yairchu

If you know that the new key is valid for the map position (changing it wo't change the ordering), and you don't want the extra work of removing and adding the item to the map, you can use a const_castto change the key, like in unsafeUpdateMapKeyInPlacebelow:

如果您知道新键对地图位置有效（更改它不会更改排序），并且您不希望删除项目并将其添加到地图中的额外工作，您可以使用 aconst_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;
}

If you want a solution that only changes in-place when that's valid, and otherwise changes the map structure:

如果您想要一个仅在有效时就地更改的解决方案，否则会更改地图结构：

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));
}