item_24.html
来自「制作本书的目的是为了方便大家的阅读。转载时请保持本电子书的完整性。 前言、」· HTML 代码 · 共 136 行
HTML
136 行
<?xml version="1.0" encoding="gb2312"?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>条款24：当关乎效率时应该在map::operator[]和map-insert之间仔细选择</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><link href="css/all.css" rel="stylesheet" type="text/css" /><link rel="stylesheet" href="http://stl.winterxy.com/styles-site.css" type="text/css" /><link rel="alternate" type="application/rss+xml" title="RSS" href="http://stl.winterxy.com/index.rdf" /><link rel="EditURI" type="application/rsd+xml" title="RSD" href="http://stl.winterxy.com/rsd.xml" /></head><body><div id="banner"><h1><a href="http://stl.winterxy.com/" accesskey="1">Center of STL Study</a> </h1><span class="description">——最优秀的STL学习网站<script language="javascript" src="http://www.winterxy.com/cgi-bin/js/webstats.js"></script></span></div><h2>条款24：当关乎效率时应该在map::operator[]和map-insert之间仔细选择</h2> <p>让我们假设有一个支持默认构造函数以及从一个double构造和赋值的Widget类：</p><pre>class Widget {public: Widget(); Widget(double weight); Widget& operator=(double weight); ...}</pre> <p>现在让我们假设我们想建立一个从int到Widget的map，而且我们想有初始化有特定值的映射。这可以简化为：</p><pre>map<int, Widget> m;m[1] = 1.50;m[2] = 3.67;m[3] = 10.5;m[4] = 45.8;m[5] = 0.0003;</pre> <p>实际上，简化掉的唯一事情是忘了实际上的进行了什么操作。那很糟糕，因为实际进行的会造成一个相当大的性能冲击。</p><p>map的operator[]函数是个奇怪的东西。它与vector、deque和string的operator[]函数无关，也和内建的数组operator[]无关。相反，map::operator[]被设计为简化“添加或更新”功能。即，给定</p><pre>map<K, V> m;</pre> <p>这个表达式</p><pre>m[k] = v; </pre> <p>检查键k是否已经在map里。如果不，就添加上，以v作为它的对应值。如果k已经在map里，它的关联值被更新成v。</p><p>这项工作的原理是operator[]返回一个与k关联的值对象的引用。然后v赋值给所引用（从operator[]返回的）的对象。当要更新一个已存在的键的关联值时很直接，因为已经有operator[]可以用来返回引用的值对象。但是如果k还不在map里，operator[]就没有可以引用的值对象。那样的话，它使用值类型的默认构造函数从头开始建立一个，然后operator[]返回这个新建立对象的引用。</p><p>让我们再次地看看原先例子的第一部分：</p><pre>map<int, Widget> m;m[1] = 1.50; </pre> <p>表达式m[1]是m.operator[](1)的简化，所以这是一个map::operator[]的调用。那个函数必须返回一个Widget的引用，因为m 的映射类型是Widget。在这里，m里面还没有任何东西，所以键1在map里没有入口。因此operator[]默认构造一个Widget来作为关联到1的值，然后返回到那个Widget的引用。最后，Widget成为赋值目标：被赋值的值是1.50。</p><p>换句话说，这个语句</p><pre>m[1] = 1.50; </pre> <p>功能上等价于这个：</p><pre>typedef map<int, Widget> IntWidgetMap; // 方便的 // typedefpair<IntWidgetMap::iterator, bool> result = // 用键1建立新 m.insert(IntWidgetMap::value_type(1, Widget())); // 映射入口 // 和一个默认构造的 // 值对象； // 看下面对于 // value_type的 // 注释result.first->second = 1.50; // 赋值给 // 新构造的 // 值类型</pre> <p>现在已经很清楚为什么这种方法可能降低性能了。我们先默认构造一个Widget，然后我们立即赋给它新值。如果用想要的值构造Widget比默认构造Widget然后进行赋值显然更高效，我们就应该用直截了当的insert调用来替换operator[]的使用（包括它的构造加赋值）：</p><pre>m.insert(IntWidgetMap::value_type(1, 1.50)); </pre> <p>这与上面的那些代码有相同的最终效果，除了它通常节省了三次函数调用：一个建立临时的默认构造Widget对象，一个销毁那个临时的对象和一个对Widget的赋值操作。那些函数调用越昂贵，你通过使用map-insert代替map::operator[]就能节省越多。</p><p>上面的代码利用了每个标准容器都提供的value_type typedef。这typedef没有什么特别重要的，但对于map和multimap（以及非标准容器的hash_map和hash_multimap——参见<a href="item_25.html">条款25</a>），记住它是很重要的，容器元素的类型总是某种pair。</p><p>我早先谈及的operator[]被设计为简化“添加或更新”功能，而且现在我们理解了当“增加”被执行时，insert比operator[]更高效。当我们做更新时，情形正好相反，也就是，当一个等价的键（参见<a href="item_19.html">条款19</a>）这已经在map里时。为了看出为什么情况是这样，看看我们的更新选项：</p><pre>m[k] = v; // 使用operator[] // 来把k的值 // 更新为vm.insert( IntWidgetMap::value_type(k, v)).first->second = v; // 使用insert // 来把k的值 // 更新为v</pre> <p>语法本身也许会让你信服地支持operator[]，但在这里我们关注于效率，所以我们将忽略它。insert的调用需要IntWidgetMap::value_type类型的实参（即pair<int, Widget>），所以当我们调用insert时，我们必须构造和析构一个那种类型的对象。那耗费了一对构造函数和析构函数，也会造成一个Widget的构造和析构，因为pair<int, Widget>本身包含了一个Widget对象，operator[]没有使用pair对象，所以没有构造和析构pair和Widget。</p><p>因此出于对效率的考虑，当给map添加一个元素时，我们断定insert比operator[]好；而从效率和美学考虑，当更新已经在map里的元素值时operator[]更好。如果STL提供一个两全其美的函数，即，在句法上吸引人的包中的高效的“添加或更新”功能。例如，很容易可以想象一个像这样的调用接口：</p><pre>iterator affectedPair = // 如果键k不再map m中；高效地 efficientAddOrUpdate(m, k, v); // 把pair(k, v)添加到m中；否则 // 高效地把和k关联 // 的值更新为v。返回一个 // 指向添加或修改的 // pair的迭代器</pre> <p>但是，在STL内没有像这样的函数，正如下面的代码所演示的，自己写一个并不难。那些注释总结了正在做什么，而且随后的段落也提供了一些附加的解释。</p><pre>template<typename MapType, // map的类型 typename KeyArgType, // KeyArgType和ValueArgtype typename ValueArgtype> // 是类型参数 // 的原因请看下面typename MapType::iterator efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgtype& v){ typename MapType::iterator Ib = // 找到k在或应该在哪里； m.lower_bound(k); // 为什么这里 // 需要“typename” // 参见第7页 if(Ib != m.end() && // 如果Ib指向一个pair !(m.key_comp()(k, Ib->first))) { // 它的键等价于k... Ib->second = v; // 更新这个pair的值 return Ib; // 并返回指向pair的 } // 迭代器 else{ typedef typename MapType::value_type MVT; return m.insert(Ib, MVT(k, v)); // 把pair(k, v)添加到m并 } // 返回指向新map元素的} // 迭代器</pre> <p>执行一个高效的增加或更新，我们需要能找出k的值是否在map中；如果是这样，那它在哪里；如果不是，它该被插入哪里。这个工作是为low_bound（参见<a href="item_45.html">条款45</a>）量身定做的，所以在这里我们调用那个函数。确定lower_bound是否用我们要寻找的键找到了一个元素，我们对后半部分进行一个等价测试（参见<a href="item_19.html">条款19</a>），一定要对map使用正确的比较函数：通过map::key_comp提供的比较函数。等价测试的结果告诉我们应该进行增加还是更新。</p><p>如果是更新，代码很直截了当。插入分支更有趣，因为它使用了insert的“提示”形式。结构m.insert(Ib， MVT(k，v))“提示”了Ib鉴别出了键等价于k的新元素正确的插入位置，而且标准保证如果提示正确，那么插入将在分摊的常数时间内发生，而不是对数时间。在efficientAddOrUpdate里，我们知道Ib鉴别出了适当的插入位置，因此insert的调用被保证为是一次常数时间操作。</p><p>这个实现的一个有趣方面是KeyArgType和ValueArgType不必是储存在map里的类型。它们只需要<em>可以转换</em>到储存在map里的类型。一个可选的方法是去掉类型参数KeyArgType和ValueArgType，改为使用MapType::key_type和MapType::mapped_type。但是，如果我们那么做，在调用时我们可能强迫发生不必要的类型转换。例如，再次看看我们在本条款的例子里使用的map定义：</p><pre>map<int, Widget> m; // 同前</pre> <p>别忘了Widget接受从一个double赋值：</p><pre>class Widget { // 也同前public: ... Widget& operator=(double weight); ...};</pre> <p>现在考虑efficientAddOrUpdate的调用：</p><pre>efficientAddOrUpdate(m, 10, 1.5); </pre> <p>假设是一次更新操作，即，m已经包含键是10的元素。那样的话，上面的模板推断出ValueArgType是double，函数体直接把1.5作为double赋给与10相关的那个Widget。那是通过调用Widget::operator(double)完成的。如果我们用了MapType::mapped_type作为efficientAddOrUpdate的第3个参数的类型，在调用时我们得把1.5转化成一个Widget，那样的话我们就得花费本来不需要的一次Widget构造（以及随后的析构）。</p><p>efficientAddOrUpdate实现中的细节可能很有趣，但它们没有本条款的要点重要，也就是当关乎效率时应该在map::operator[]和map-insert之间仔细选择。如果你要更新已存在的map元素，operator[]更好，但如果你要增加一个新元素，insert则有优势。</p></body></html>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?