C++

Question

让我们考虑一下这段代码：

std::map< int, char > charMap;
for( auto& i : charMap )
{
    charMap[ i.first + 1 ] = charMap[ i.first ];
    charMap.erase( i.first );
}

假设地图有一些带有随机键的值。我正在尝试将键移动 1。这是行不通的，因为循环会一直持续下去。有没有快速的方法让它工作？

Answer 1

出于两个根本原因，您不能使用这种范围迭代：

第一个原因是 map 的一个基本属性是遍历 map 按键顺序迭代。

您正在遍历地图。因此，如果映射中的第一个键是键 0，则将值复制到键 1。然后，迭代到映射中的下一个键，即您刚刚创建的键 1，然后将其复制到键2. 起泡、冲洗、重复。

有几种方法可以解决这个问题，但是 none 由于地图的第二个基本方面，这很重要：

charMap[1]=charMap[0];

这对应 charMap[0] 到 charMap[1]。它对 charMap[0] 没有任何作用。它仍然在那里。什么也没发生。因此，假设地图中最低的键是 0，并且您正确地移动了键，您在地图中仍然会有一个键为 0 的值。地图中的其他所有内容也是如此。

但假设您通过几种可以解决的方法之一解决了第一个问题。然后，假设您的地图具有键 0、5 和 7 的值。

将 key #0 复制到 key #1，将 key #5 复制到 key #6，将 key #7 复制到 key #8 后，拿纸和笔，找出地图中现在的内容。

答案：它不会是键 1、6 和 8。它将是键 0、1、5、6、7 和 8。

您所做的只是将每个值复制到下一个键。这是因为计算机完全按照您的指示去做，不多也不少。计算机不执行您希望它执行的操作。

最简单的方法是创建一个新地图，然后将旧地图的内容复制到新地图，并更新键值。您仍然可以为此使用范围迭代。然后，用新地图替换旧地图。

当然，如果地图很大，这就变得不切实际了。在那种情况下，仍然可以在不使用第二张地图的情况下执行此操作，但算法会有些复杂。胶囊摘要是：

1) 以相反的顺序遍历键。不能在这里使用范围迭代。

2) 将键复制到映射中的下一个值后，从其原始键中显式删除该值。

Answer 2

在C++17中，可以使用节点提取和拼接（见P0083R3）：

std::map<int, char> tmpMap;

for (auto it = charMap.begin(); it != charMap.end(); )
{
    auto nh = charMap.extract(it++);   // node handle
    ++nh.key();
    tmpMap.insert(tmpMap.end(), std::move(nh));
}

tmpMap.swap(charMap);

循环提取连续的映射节点，对它们进行变异，然后将节点重新插入到 tmpMap 中（现在使用不同的键）。最后，charMap 为空，tmpMap 包含所有元素及其修改后的键，因此我们交换两者。

在 C++17 之前，您必须复制（或移动）值数据来插入具有新键的新元素。

std::map<int, char> tmpMap;

for (auto & p : charMap)
    tmpMap.emplace_hint(tmpMap.end(), p.first + 1, std::move(p.second));

tmpMap.swap(charMap);

不过，这需要为节点分配内存，因此新的基于拼接的解决方案效率更高。

在任何一种情况下，我们都可以使用提示插入，因为我们正在以相同的顺序重建元素，所以最新的元素总是插入到最后。

Answer 3

使用已知对订单的影响的临时解决方案

您可以简单地选择向后迭代，从最后一个元素开始：

for( auto pi = charMap.end(); pi-- != charMap.begin(); pi=charMap.erase( pi ))
    charMap[ pi->first + 1 ] = charMap[ pi->first ];

Online demo

这里不会永远循环，因为您插入的新元素总是在当前元素之后，因此不会一次又一次地重新处理。

更通用的解决方案

对于无法确定对元素排序的影响的更一般的转换，我宁愿选择 std::transform():

std::map<int, char> tmp; 
std::transform(charMap.begin(), charMap.end(), std::inserter(tmp,tmp.begin()), 
                          [](auto e) { return std::make_pair(e.first+1, e.second); });
std::swap(tmp, charMap);    // the old map will be discarded when tmp goes out of scope

Online demo

C++ - 修改所有地图元素的键

C++ - Modifying key for all map elements

stdmap

使用已知对订单的影响的临时解决方案

更通用的解决方案