Effective STL 学习笔记： Item 22 ~ 24
*/-->
div.org-src-container {
font-size: 85%;
font-family: monospace;
}
Table of Contents
1 避免 \(set \& multiset\) 在原位改变 Key
set, multiset, map, multimap 都是有序的容器，如果直接在原位改变 key 的值，则很有可能容器不有序，后续对该容器的算法会失效。
2 Consider replacing associative containers with sorted vectors
Associative Container 中的每个 Node 除了保存真正对象外，还需要维护指向 Parent, Previous,
Next 的三个指针，相比 vector 来说，更占用内存，范文时间为 O(logn)。 而 vectors，如果配合合适的 Hash Function ，则既省时间又省空间，但不足之处是需要自己始终维持 vector 在有序的状态。
3 Choose carefully between map::operator[] and map-insert
map::operator[] 会返回 Value 的一个引用，而如果对应的 Key 在 Map 中没有 Value， map 会调用
Default Constructor 来创建一个新的，加到 Map 中，然后再将新的 Value 返回出来，例如，下面的代码中：
1: class Widget
2: {
3: public:
4: Widget(){}
5: Widget(double d):m_value(d){}
6: virtual ~Widget(){}
7: private:
8: double m_value;
9: };
10:
11: map<int, Widget> m;
12: m[1] = 1.50;
第 12 行一行代码实际上和下面的代码是等效的：
13: pair<map<int, Widget>::iterator, bool> result =
14: m.insert(map<int, Widget>::value_type(1, Widget()));
15: result.first->second = 1.50;
实际上，我们可以用下面的一行代码来完成所需操作，避免无谓的默认构造：
m.insert(map<int, Widget>::value_type(1, 1.50));
但如果我们想更新已有的 Key， 则 [ ] 更简单一些。
书中最后给出了一个例子，用于高效的添加或者更新 map:
1: template <typename MapType,
2: typename KeyType,
3: typename ValueType>
4: typename MapType::iterator
5: efficientAddOrUpdate(MapType& map,
6: cons KeyType& k,
7: const ValueType& v)
8: {
9: typename MapType::iterator lb = m.lower_bound(k);
10: if (lb != m.end() && !(m.key_comp()(k, lb->first)))
11: {
12: lb->second = v;
13: return lb;
14: }
15: else
16: {
17: typedef typename MapType::value_type MVT;
18: return m.insert(lb, MVT(k,v));
19: }
20: }
（转载请注明出处，使用许可：署名-非商业性使用-相同方式共享 3.0 *许可协议 。）