Efficient way to move elements from a map to another

Question

I must find a efficient solution for this problem. I have two map. I must move some elements from map1 to map2 (namely erase from map1 and put into map2). I have the keys through which I find the elements in map1 namely i'm doing for now:

bool temp;
temp = map1[key1];
map2[key1]=temp;
map1.erase(key1)

I do it for each key(in a loop)

My question is if there is a less expensive solution of my (I use C++11 compiler)

Answer 1

The ideal solution has only become possible with C++17: map::extract()

Std::map is typically implemented as a binary tree, and a binary tree stores one key-value entry per memory object. That makes it possible to move an entry by simply exchanging the ownership of that piece of memory. This is done by just flipping some internal pointers (including rebalancing the two trees, which has to be done anyway if the end result is to have changed both trees).

This avoids not only moving the object around in memory, but any memory allocation and deallocation (which has unpredictable worst case performance).

Example:

// Before Darwin, it was thought that whales were fish.
std::map<int, std::string> fish{{1,"whaleshark"}, {2,"whale"}, {3,"shark"}};
std::map<int, std::string> mammalia{{1,"cat"}, {2,"dog"}};

// Oops, the whale belongs to mammalia.
auto whale = fish.extract(2);
whale.key() = 3;
mammalia.insert(std::move(whale));

Before C++17, you had to implement your own map in order to do this.