当关乎效率时应该在map::operator[]和map-insert之间仔细选择
我们知道 这个表达式
m[k] = v;
检查键k是否已经在map里。如果不,就添加上,以v作为它的对应值。如果k已经在map里,它的关联值被更新成v。
举例一:考虑插入一个新值
这个语句
m[1] = 1.50;
功能上等价于这个:
typedef map<int, Widget> IntWidgetMap;
// 用键1建立新映射入口和一个默认构造的值对象;
pair<IntWidgetMap::iterator, bool> result =
m.insert(IntWidgetMap::value_type(1, Widget()));
// 赋值给新构造的值类型
result.first->second = 1.50;
看下面的代码:
m.insert(IntWidgetMap::value_type(1, 1.50));
这与上面的那些代码有相同的最终效果,除了它通常节省了三次函数调用:一个建立临时的默认构造Widget对象,一个销毁那个临时的对象和一个对Widget的赋值操作。那些函数调用越昂贵,你通过使用map-insert代替map::operator[]就能节省越多。
上面的代码利用了每个标准容器都提供的value_type typedef。这typedef没有什么特别重要的,但对于map和multimap(以及非标准容器的hash_map和hash_multimap),记住它是很重要的,容器元素的类型总是某种pair。
举例二:考虑更新值
// 使用operator[]来把k的值更新为v
m[k] = v;
// 使用insert来把k的值更新为v
m.insert( IntWidgetMap::value_type(k, v) ).first->second = v;
语法本身也许会让你信服地支持operator[],但在这里我们关注于效率,所以我们将忽略它。insert的调用需要IntWidgetMap::value_type类型的实参(即pair<int, Widget>),所以当我们调用insert时,我们必须构造和析构一个那种类型的对象。那耗费了一对构造函数和析构函数,也会造成一个Widget的构造和析构,因为pair<int, Widget>本身包含了一个Widget对象,operator[]没有使用pair对象,所以没有构造和析构pair和Widget。
总结:出于对效率的考虑,当给map添加一个元素时,我们断定insert比operator[]好;而从效率和美学考虑,当更新已经在map里的元素值时operator[]更好。
很容易可以想象一个像这样的调用接口:
// map的类型
//KeyArgType和ValueArgtype是类型参数
template<typename MapType,typename KeyArgType, typename ValueArgtype>
typename MapType::iterator
efficientAddOrUpdate(MapType& m,const KeyArgType& k,const ValueArgtype& v){
// 找到k在或应该在哪里
typename MapType::iterator Ib =m.lower_bound(k);
// 如果Ib指向一个pair,它的键等价于k,更新这个pair的值并返回指向pair的迭代器
if(Ib != m.end() &&!(m.key_comp()(k, Ib->first))) {
Ib->second = v;
return Ib;
}
else{
typedef typename MapType::value_type MVT;
// 把pair(k, v)添加到m并返回指向新map元素的迭代器
return m.insert(Ib, MVT(k, v));
}
}
执行一个高效的增加或更新,我们需要能找出k的值是否在map中;如果是这样,那它在哪里;如果不是,它该被插入哪里。这个工作是为low_bound量身定做的,所以在这里我们调用那个函数。确定ower_bound是否用我们要寻找的键找到了一个元素,我们对后半部分进行一个等价测试,一定要对map使用正确的比较函数:通过map::key_comp提供的比较函数。等价测试的结果告诉我们应该进行增加还是更新
如果是更新,代码很直截了当。插入分支更有趣,因为它使用了insert的“提示”形式。结构m.insert(Ib,MVT(k,v))“提示”了Ib鉴别出了键等价于k的新元素正确的插入位置,而且标准保证如果提示正确,那么插入将在分摊的常数时间内发生,而不是对数时间。在efficientAddOrUpdate里,我们知道Ib鉴别出了适当的插入位置,因此insert的调用被保证为是一次常数时间操作。