现在的位置: 首页 > 综合 > 正文

map 效率问题

2013年09月10日 ⁄ 综合 ⁄ 共 1727字 ⁄ 字号 评论关闭

当关乎效率时应该在map::operator[]和map-insert之间仔细选择

class Widget {

public:

Widget();

Widget(double weight);

Widget& operator=(double weight);

...

}

map<int, Widget> m;

m[1] = 1.50;

 

表达式m[1]是m.operator[](1)的简化,所以这是一个map::operator[]的调用。那个函数必须返回一个Widget的

引用,因为m 的映射类型是Widget。在这里,m里面还没有任何东西,所以键1在map里没有入口。因此

operator[]默认构造一个Widget来作为关联到1的值,然后返回到那个Widget的引用。最后,Widget成为赋值目

标:被赋值的值是1.50。

换句话说,这个语句

m[1] = 1.50;

功能上等价于这个:

typedef map<int, Widget> IntWidgetMap; // 方便的

// typedef

pair<IntWidgetMap::iterator, bool> result = // 用键1建立新

m.insert(IntWidgetMap::value_type(1, Widget())); // 映射入口

// 和一个默认构造的

// 值对象;

// 看下面对于

// value_type的

// 注释

result.first->second = 1.50; // 赋值给

// 新构造的

条款24:当关乎效率时应该在map::operator[]和map-insert之间仔细选择

// 值类型

现在已经很清楚为什么这种方法可能降低性能了。我们先默认构造一个Widget,然后我们立即赋给它新值。

如果用想要的值构造Widget比默认构造Widget然后进行赋值显然更高效,我们就应该用直截了当的insert调用

来替换operator[]的使用(包括它的构造加赋值):

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

这与上面的那些代码有相同的最终效果,除了它通常节省了三次函数调用:一个建立临时的默认构造Widget

对象,一个销毁那个临时的对象和一个对Widget的赋值操作。那些函数调用越昂贵,你通过使用map-insert代

替map::operator[]就能节省越多。

上面的代码利用了每个标准容器都提供的value_type typedef。这typedef没有什么特别重要的,但对于map和

multimap(以及非标准容器的hash_map和hash_multimap——参见条款25),记住它是很重要的,容器元素的

类型总是某种pair。

我早先谈及的operator[]被设计为简化“添加或更新”功能,而且现在我们理解了当“增加”被执行时,insert

比operator[]更高效。当我们做更新时,情形正好相反,也就是,当一个等价的键(参见条款19)这已经在

map里时。为了看出为什么情况是这样,看看我们的更新选项:

m[k] = v; // 使用operator[]

// 来把k的值

// 更新为v

m.insert(

IntWidgetMap::value_type(k, v)).first->second = v; // 使用insert

// 来把k的值

// 更新为v

语法本身也许会让你信服地支持operator[],但在这里我们关注于效率,所以我们将忽略它。insert的调用需要

IntWidgetMap::value_type类型的实参(即pair<int, Widget>),所以当我们调用insert时,我们必须构造和析构

一个那种类型的对象。那耗费了一对构造函数和析构函数,也会造成一个Widget的构造和析构,因为

pair<int, Widget>本身包含了一个Widget对象,operator[]没有使用pair对象,所以没有构造和析构pair和

Widget。

因此出于对效率的考虑,当给map添加一个元素时,我们断定insert比operator[]好;而从效率和美学考虑,当

更新已经在map里的元素值时operator[]更好。如果STL提供一个两全其美的函数,即,在句法上吸引人的包

中的高效的“添加或更新”功能。

抱歉!评论已关闭.