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)
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.
extract? Something along the lines of std::string whale = std::move(fish.extract(2));. –
Cuthbertson node_handle you should be able to do std::string whale = std::move(fish.extract(2).mapped()); –
Standstill std::map documentation : http://www.cplusplus.com/reference/map/map/
for (auto key : keys) // keys of elements to move
{
try {
map2[key] = std::move(map1.at(key)); // here is the C++ 11 optimization you looked for
map1.erase(key);
}
// handle error if map1 does not store any element with current key
catch (std::out_of_range & ex) {
// TODO handle error
}
}
you can do this with std::map's extract function come with c++17.
here is the explanation and examples https://en.cppreference.com/w/cpp/container/map/extract
Well your temporary variable is pointless; just write:
map2[key1] = map1[key1];
map1.erase(key1);
… though your compiler was already likely to make that "optimisation" for you.
Concerning the value itself, a bool is already about as atomic as it gets — there are no magic tricks that can make copying one any faster.
You can (as long as map1[key1] assuredly already exists) is to eliminate one of the map lookups and a zero-initialisation:
auto it = map1.find(key1);
assert(it != map1.end());
map2.insert(std::make_pair(key1, it->second));
map1.erase(it);
But look how less expressive this is! Don't do it unless you really have a performance problem.
If the value_type has a default constructor, there's a good thing in the STL named std::swap that you don't need C++11 move semantic.
std::swap(map1[key], map2[key]);
map1.erase(key);
In your case, I think it's find just to copy the bool value. But if what slows your program is copying the key_type I'm afraid there seems no way but to use both maps without moving entries between them, because the key_type is always const qualified so that not movable.
Insert the entire map through iterators, and then clear the original.
map2.insert(map1.begin(), map1.end());
map1.clear();
Based on @RCYR's answer, I would propose the following:
auto& itToRemove = map1.find(key); //perform the search in map1 only once
map2.emplace( key, std::move(itToRemove->second); //map2 entry is init with the map1 one without default initialization
map1.erase(itToRemove ); //go straight to the map1 entry an remove it.
Basically, I removed one search in the map for each entry deleted and a default initialization of the map2 entry.
© 2022 - 2024 — McMap. All rights reserved.