24.针对性地使用map::operator[]与map::insert

Posted on | In

问题实例

</br>
假设有一个Widget类：

1
2
3
4
5
6
7
class Widget {
public:
    Widget();
    Widget(double weight);
    Widget& operator=(double weight);
    ...
}

我们试图建立起int、widget之间的映射关联，那么使用使用map是再恰当不过的：
1
2
3
map<int, Widget> m;
m[1] = 1.50;//一一添加映射关系
m[2] = 3.67;

然而这种写法对性能的冲击极大。

map::operator[]与map::insert

map::operator[]的具体实现

map的operator[]与别的容器的operator[]颇有不同，它所执行的功能是“更新或添加”，具体来说，

1
m[k] = v;

上述表达式所执行的操作依次为：

  1. 检查键k是否在map中，如果没有，则insertpair<const k,v>
  2. 有，则更新k所对应的value

operator[]默认返回一个value的引用，这在更新操作中再正常不过，但对于insert操作，它会使用value的默认构造函数构造一个，然后返回这个新建立对象的引用。具体来说，

1
m[1] = 1.50;//m中不存在k==1

等价于
1
2
3
typedef map<int, Widget> IntWidgetMap;
pair<IntWidgetMap::iterator, bool> result = m.insert(IntWidgetMap::value_type(1, Widget()));
result.first->second = 1.50;

用insert直接取代operator[]中的插入操作

显然，上述代码在map中插入了一个pair，其first是我们指定的key，second则是默认初始化的widget，最后再执行了赋值操作。
以value初始化widget自然会比上述代码更加高效，所以，我们应该直接使用insert代替operator[]:

1
m.insert(IntWidgetMap::value_type(1, 1.50));

这种写法一共节约了3次函数调用：

  • 一次建立widget临时对象
  • 一次销毁widget临时对象
  • 一次widget赋值操作

两全其美的方法

</br>
出于对更高效的渴望，我们能否扬长避短，实现如下的功能？

1
2
3
//如果k在m中，调用operator[],否则执行insert
//返回被指向pair的迭代器
iterator affectedPair = efficientAddOrUpdate(m, k, v);

实现该函数实际上并不困难：
1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename MapType,typename KeyArgType, typename ValueArgtype>
typename MapType::iterator //利用typename强调此处是一个类型而非成员
efficientAddOrUpdate(MapType& m,const KeyArgType& k,const ValueArgtype& v){
    typename MapType::iterator Ib = m.lower_bound(k);//找出合理插入位置
    if(Ib != m.end() && !(m.key_comp()(k, Ib->first))) {//关联容器判同
        Ib->second = v; //更新
        return Ib;
    } 
    else{
        typedef typename MapType::value_type MVT;
        return m.insert(Ib, m::value_type(k, v));//常数时间完成插入
    }
}

在上述实例中，keytype与valuetype不必是存储在map里的类型，它们只需要能够完成隐式转换即可。

总结

</br>
本节的重点并不在于如何去实现AddOrUpdate这样的函数，而在于强调operator[]与insert在不同情况下效率的不同，如果我们能明确程序行为，那我们应当谨慎地选用它们中的一个。