Effective STL 学习笔记 Item 21:Comparison Function 相关
Effective API Design

Effective STL 学习笔记: Item 22 ~ 24

tubo posted @ 2014年9月03日 00:12 in 未分类 , 252 阅读
Effective STL 学习笔记: Item 22 ~ 24

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: }

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter