C++ STL使用，以及注意事项

0x01 缘由

  最近在做产品的开发上发现一个问题，发现对待成熟的库和开源组件时，开发者有两种态度：

  一类：非常崇拜开源组件和STL，盲目的使用；

  二类：喜欢自己去实现一个库，类似造*；

  这两类人我觉得需要把握好一个度：

    1、正确场景使用正确的库；

    2、特殊的场景可以用更精炼、效率更高的实现；

    3、然后一切根据测试数据和性能数据说服对方；

下面简单列举一些STL使用过程中的注意事项：

0x02 当对象很大时，建立指针的容器而不是对象的容器

1.STL基于拷贝的方式的来工作，任何需要放入STL中的元素，都会被复制。

  这也好理解，STL工作的容器是在堆内开辟的一块新空间，而我们自己的变量一般存放在函数栈或另一块堆空间中。为了能够完全控制STL自己的元素，为了能在自己的地盘随心干活，这就涉及到复制。而如果复制的对象很大，由复制带来的性能代价也不小，对于大对象的操作，使用指针来代替对象能消除这方面的代价（内存 + 复制过程）。

2.只涉及到指针拷贝操作，没有额外类的构造函数和赋值构造函数的调用；

对象的复制，存在调用对应复制拷贝函数，效率较低，不可取：

vecttor vt1;
vt1.push_bach(myBigObj); 
直接对这个对象指针进行复制，相对而言效率要高，可取：
vecttor vt2;
vt2.push_bach(new BigObj());

注意事项：

   a.容器销毁前需要自行销毁指针所指向的对象；否则就造成了内存泄漏；

   b.使用排序等算法时，需要构造基于对象的比较函数，如果使用默认的比较函数，其结果是基于指针大小的比较，而不是对象的比较；

0x03 判断容器是否为空

  使用empty()而不是size()==0，因为list的遍历是线性时间，而size()会遍历容器中的没一个元素。

0x04 尽量用区间成员函数代替单元素操作

使用区间成员函数有以下好处：

a.更少的函数调用

b.更少的元素移动

c.更少的内存分配

例:将v2后半部的元素赋值给v1：

单元式操作：（差）

for (vector::const_iterator ci = v2.begin() + v2.size() / 2;
ci != v2.end();++ci)
v1.push_back(*ci)
使用区间成员函数assign()：（优）
v1.assign(v2.begin() + v2.size() / 2, v2.end());

0x04 vector

  有篇博文已经描述，传送（http://blog.csdn.net/pangyemeng/article/details/73277025），简单，允许随机存储，数据的存取十分灵活，在缺省情况下应该使用。

a.在使用vector的时候，需要有一点注意：尽量少使用erase，因为在发生erase的时候，会发生一次拷贝，vector要保持结构的完整性，会把从操作对象后的每一个成员都进行一次拷贝，并前移一位，但是在最后一个成员发生移动的时候，如果成员是一个非常规类型，会发生析构，那该成员以及该成员的拷贝都将被删除；

b.在vector使用reverse_iterator时，很多操作如erase，insert都不允许对reverse_iterator直接操作，需要创建一个iterator(reverse_iterator.base())，然后对iterator进行操作。

c.如果想使用reverse_iterator删除一个容器中的一个元素，优选方法：

vector<int>v;
//向v插入1到5，同上

vecot<int>::reverse_iteratorri=
find(v.rbegin(),v.rend(),3);//同上，ri指向3
v.erase(--ri.base());//尝试删除ri.base()前面的元素；对于vector，一般来说编译不通过

//同上

v.erase((++ri).base());//删除ri指向的元素；

//这下编译没问题了！

d.关于reserve和resize的区别：

reserve只是预留出空间，并不真正的创建元素，所以并不会进行初始化。

resize后，修改容器空间，并初始化元素，这时候可以通过operator[]来进行操作。

vector 的 resize() 动作，会把原内存memset/bzero 0

e.容器clear（）后内存释放与否

C++ STL的vector容器在clear()之后不会释放内存，需要 swap(empty vector)，这是有意为之（C++11 里增加了 shrink_to_fit() 函数）。不要记成了所有STL容器都需要swap(empty one)来释放内存。事实上其他容器（map/set/list/deque）都只需要clear()就能释放内存。只有含 reserve()/capacity() 成员函数的容器才需要用swap来释放空间，而C++里只有vector和string这两个符合条件。实际使用中，vector在小数据量(可能千以内吧)时，遍历、查找、添加删除，都是很快的，完全可以选择它。

0x05 deque

  经常在头部和尾部安插和移除元素，并且存储的容量也比vector大得多。

  PS.关于队列，还有一个queue，这个队列和deque是有区别的，queue是对std容器的封装，采用FIFO的策略，queue没有clear（）函数，这确实会导致效率下降，相比deque，在100000级元素的清除中才会有0.5秒的差距，push（）和push_back（）动作基本一致，queue稍快，但是也要在10w级size的操作才会有0.01秒的区别。

0x06 list

  如果经常在容器的中段执行安插，移除和移动元素。但是不支持随机存储。如果需要“每次安插不成功，便无效用”。list erase元素时，需要注意erase返回迭代器，否则list迭代器失效。即:itr=lst.erase(itr);list容器中尽量不要使用删除操作，比插入操作多消耗近百倍;

  如下使用传送：http://blog.csdn.net/bennyfun79/article/details/14132871

0x07 set和multiset

  经常以某个准则寻找元素，可以使用“以这个准则为排序准则”的set和multiset，在大量的数据情况下，对数复杂度比线性复杂度的效果要好的多。set使用的是二叉树，如果hash table可用，其性能比二叉树高5-10倍，但是hash table并未提供插入元素的排序，如果需要对元素进行排序，则无法使用。

0x08 map和multimap

  使用（key、value）的pair，使用字典，使用关联式数组 e.g“map[key] = value”。复杂度也是对数复杂度，这几乎是最快的，hash也是对数复杂度。map内部是采用RB树，hash map的查找与数据量无关，复杂度是O（1）。在不碰撞的前提下，hash map的查找速度是最快的，何为“不碰撞”？所谓不碰撞，就是要有足够好的hash函数，否则的话，可能会和链表一样，复杂度O（N）。unorder_set/map：的性能优于map和hash map，唯一的问题就是无需排列，如果保存的数据没有序列要求，建议使用。查找的性能尤其突出。

0x09 总结

    文章提取自http://www.jianshu.com/p/52a49ee1b481，作为mark和学习；