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

小开

You can omit the copying of 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);
}

小开

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.

小开

Keys in STL maps are required to be immutable.

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.

小开

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?

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 would let you change the key anyway.

小开

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

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

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

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.

Update

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

小开

最佳答案

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

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

小开

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_cast to change the key, like in unsafeUpdateMapKeyInPlace below:

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