Effective STL 学习笔记： Item 22 ~ 24

时间：2022-05-21 08:04:08

Effective STL 学习笔记： Item 22 ~ 24

*/-->

div.org-src-container {
font-size: 85%;
font-family: monospace;
}

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

相关文章