如何在 Map/Multimap 中更新 Const Key 字段

引言

这不是一篇典型的 C++/STL 文章。相反，它是我在职业编程生涯中遇到的一个观察。这个想法很简单，但效果/影响是广泛的。在这里，我将提供一个小实用工具，它可以让你在做同样的事情时省下很大的精力。

背景

是什么使 Map/Multimap 变得漂亮？是的，你猜对了 - 一个键值字段类型的容器。如果你看看 STL Map/Multimap 的定义，你会发现类似这样的东西

template <typename K, typename V,
          typename Compare = less<K>,
          typename Allocator = allocator<pair<const K, V> > >
class map; 

template <typename K, typename V,
          typename Compare = less<K>,
          typename Allocator = allocator<pair<const K, V> > >
class multimap;

所以定义看起来非常相似，唯一的区别是 Map 永远不允许有重复的键，而 Multimap 允许。

另一个观察/约束是 Map/Multimap 中的 Key 字段始终是常量。一旦填充，你无法以传统方式更改/更新 Key 字段，并且这背后有一个很好的理由

因为 Map/Multimap 根据它们的键进行排序（以及排序仿函数（默认为 std::less，但是你可以自由地将其更改为 std::greater 或者你自己的仿函数）），并将键分配到内部的红黑树结构中，如果你或任何通用算法更新了键字段，那么红黑树将变为无效。整个树可能需要重新洗牌，这是一个相当耗时的过程。这就是 STL 设计者做出以下决定的原因：

你不能以传统方式更新 map/multimap 的键字段。

你不能使用 map/multimap 作为更新容器的通用算法的目标。

但是，如果你需要更新 map/multimap 的键字段怎么办？有时这确实是必要的。假设你最初有一个像这样的 Multimap

键	值
Allen	100
Betty	200
Allen	200
Betty	300
John	500
Allen	900

现在你需要将键 "Allen" 更新为 "Gary"。你将如何做到？

你只剩下一个选择：

要修改元素的键，你必须删除具有旧键的元素，并插入一个具有新键和旧值的新元素。

那么，你如何使用通用函数来实现这一点呢？

Using the Code

通用函数很好，特别是当你使它从容器中分离出来时。为了解决上述问题，我的策略是编写一个像这样的通用函数

namespace My_Utility{
template <typename CONTAINER>
    void replace_key(CONTAINER& container,
                     const typename CONTAINER::key_type& oldKey,
                     const typename CONTAINER::key_type& newKey)
    {
        if(!container.key_comp()(oldKey,newKey) && !container.key_comp()(newKey,oldKey)){
	    return;} //Thanks to Graham for this Fix
        typename CONTAINER::iterator begin(container.find(oldKey));
        for(;;){
            if(begin != container.end()){
                container.insert(typename CONTAINER::value_type(newKey, begin->second));
                container.erase(begin); // Thanks to Graham for this potential fix
                begin = container.find(oldKey);
            }
            else{
                return;
            }
        }
    }
}

这纯粹是一个通用函数。下面是它的描述：

1. 模板定义采用一个名为 CONTAINER 的单个模板参数（它可以是 Map 或 Multimap）。
2. 参数列表采用一个 Container、一个 const 旧键和一个 const 新键，请注意旧键和新键的类型都是从模板类型中获取的。所以这是纯粹通用的。
3. 首先检查并返回 Old key 和 New Key 是否相等，在这种情况下我们不需要更新任何东西。
4. 如果 Old key 和 New key 不同，则该函数执行以下操作：

   它找到旧键存在的第一个迭代器位置，然后启动一个无限循环，当迭代器包含值 container.end() 时，该循环会中断。请记住，如果 find() 算法没有找到任何内容，则返回 cont.end()，如果搜索成功，则返回第一个迭代器位置。

   如果 begin!=container.end()，则该函数插入一个新行。请仔细看代码。

   然后它擦除旧行。请看代码。它是

   container.erase(begin);

   然后再调用 find()。

当你需要解决类似的问题时，请使用此代码。

历史

• 2009 年 5 月 11 日：首次发布