将元素从地图移动到另一个地图的有效方法

Question

我必须为这个问题找到一个有效的解决方案。我有两张地图。我必须将一些元素从 map1 移动到 map2（即从 map1 中删除并放入 map2）。我有我在 map1 中找到元素的键，即我现在正在做的事情：

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

我为每个键做它（在一个循环中）

我的问题是我的（我使用 C++11 编译器）是否有更便宜的解决方案

原文由 Nick 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

只有使用 C++17 才能实现理想的解决方案： map::extract()

Std::map 通常实现为二叉树，二叉树为每个内存对象存储一个键值条目。在这种假设下，可以通过简单地交换那块内存的所有权来移动一个条目。这是通过翻转一些内部指针来完成的（包括重新平衡两棵树，如果最终结果是改变两棵树，无论如何都必须这样做）。

这不仅避免了在内存中移动对象，而且避免了任何内存分配和释放（具有不可预测的最坏情况性能）。

例子：

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

在 C++17 之前，您必须实现自己的地图才能被允许这样做。

原文由 user2394284 发布，翻译遵循 CC BY-SA 4.0 许可协议