如何高效的使用STL：

部分摘取：大CC《高效的使用STL》

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

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

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

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

不可取：

vecttor vt1;

vt1.push_bach(myBigObj);

可取：

vecttor vt2;

vt2.push_bach(new BigObj());

注意事项：

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

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

二 判断容器是否为空时，使用empty()而不是size()==0，因为list的遍历是限行时间，而size()会遍历容器中的没一个元素。

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

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

1 更少的函数调用

2 更少的元素移动

3 更少的内存分配

例：将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());

一、vector：简单，允许随机存储，数据的存取十分灵活，在缺省情况下应该使用。

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

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

3、如果想使用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指向的元素；

//这下编译没问题了！

4、关于reserve和resize的区别：

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

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

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

5、容器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在小数据量(可能千以内吧)时，遍历、查找、添加删除，都是很快的，完全可以选择它。

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

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

三、list：如果经常在容器的中段执行安插，移除和移动元素。但是不支持随机存储。如果需要“每次安插不成功，便无效用”。list erase元素时，需要注意erase返回迭代器，否则list迭代器失效。即:itr=lst.erase(itr);

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

五、map和multimap：使用（key、value）的pair，使用字典，使用关联式数组 e.g“map[key] = value”。复杂度也是对数复杂度，这几乎是最快的，hash也是对数复杂度。map内部是采用平衡二叉树，hash map的查找与数据量无关，复杂度是O（1）。

在不碰撞的前提下，hash map的查找速度是最快的，何为“不碰撞”？所谓不碰撞，就是要有足够好的hash函数，否则的话，可能会和链表一样，复杂度O（N）。

unorder_set/map：的性能优于map和hash map，唯一的问题就是无需排列，如果保存的数据没有序列要求，建议使用。查找的性能尤其突出。

六、list容器中尽量不要使用删除操作，比插入操作多消耗近百倍