Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

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?

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

like image 831
Peter Jankuliak Avatar asked Apr 21 '11 11:04

Peter Jankuliak


People also ask

How do I change the key-value of a map in C++?

To update an existing value in the map, first we will find the value with the given key using map::find() function. If the key exists, then will update it with new value.

How do I change the map key?

To change a HashMap key, you look up the value object with get, then remove the old key and put it with the new key. To change the fields in a value object, look the value object up by key with get, then use its setter methods. To replace the value object in its entirely, just put a new value object at the old key.

Can a map have 2 Keys C++?

Implement a MultiKeyMap in C++ A MultiKeyMap is a map that offers support for multiple keys. It is exactly the same as a normal map, except that it needs a container to store multiple keys. A simple solution to implement a MultiKeyMap in C++ is using std::pair for the key.

What is a multimap C++?

Multimaps are part of the C++ STL (Standard Template Library). Multimaps are the associative containers like map that stores sorted key-value pair, but unlike maps which store only unique keys, multimap can have duplicate keys. By default it uses < operator to compare the keys.


6 Answers

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" } }
like image 93
21koizyd Avatar answered Oct 23 '22 07:10

21koizyd


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! :-)

like image 42
Howard Hinnant Avatar answered Oct 23 '22 09:10

Howard Hinnant


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);
}
like image 45
Viktor Sehr Avatar answered Oct 23 '22 09:10

Viktor Sehr


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.

like image 27
Joe Avatar answered Oct 23 '22 08:10

Joe


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.

like image 29
Matthieu M. Avatar answered Oct 23 '22 09:10

Matthieu M.


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.

like image 31
Bo Persson Avatar answered Oct 23 '22 08:10

Bo Persson