- 一、 迭代器区别
- 二、vector
- 三、Map、Set
- 四、vector_map 为什么比map效率高
- 五、如何选择
- 六、容器选择原则
- 七、效率对比
①vector为顺序容器，erase迭代器不仅使所有指向被删元素的迭代器失效，而且使被删元素之后的所有迭代器失效，所以不能使用erase(iter++)的方式，但是erase的返回值为下一个有效的迭代器：可以这样使用：
for( iter = c.begin(); iter != c.end(); ) iter = c.erase(iter);
②erase迭代器只是被删元素的迭代器失效：所以可以这样使用：
for( iter = c.begin(); iter != c.end(); ) c.erase(iter++);
正因为：map erase 会使被删元素的迭代器失效：所以在使用map iterator时候要注意： 一种很常见的错误是：
for ( map::iterator it = str_map.begin(); it!=str_map.end(); it++ ) { if ( some_condition ) str_map.erase(it); }
删除操作会使it乱掉，再使用it++就出错了。正确的做法是：
for (map::iterator it = str_map.begin(); it != str_map.end()😉 { if (some_condition) { str_map.erase(it++); } else { it++; } }
③Map可以通过key查找元素，而vector查找元素也类似，通过值查找；
④对于vector的值得注意的地方，可以对vector调用排序算法，举例如下：
typedef struct { std::string strName; int money; }company_person;
然后可以按照strName进行排序；我在一个项目中用到过这个，在一个项目中，客户端以随机的发送strName，然后在服务端对他们进行重新排序；
⑤map和vector 插入元素的方式不一样，map没有push_back这样的函数，只有insert依次插入元素，或者直接通过构造函数初始化；
二、vector向量 相当于一个数组。在内存中分配一块连续的内存空间进行存储，支持补丁大小的存储。当超过已分配的空间是，会整体重新分配一块内存进行存储。
优点:
- 1、不指定一块连续内存进行存储，可以像数组一样操作。
- 2、随机访问方便，支持下标访问和vector.at()操作。
- 3、节省空间。
缺点:
- 1、在内部进行插入删除，效率较低。
- 2、只能在末端进行pop和push。
- 3、当动态长度超过默认分配大小后，要整体重新分配、拷贝和施放。
-
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性map内部的实现自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能。
-
set是集合，set中不会包含重复的元素，这是和vector的第一个区别，第二个区别是set内部用平衡二叉树实现，便于元素查找，而vector是使用连续内存存储，便于随机存取。
- vector是线性存储，map是二叉树树形，所以vector内存访问的局部性更好。
- vector, 一次分配一个比较大的空间（2^n的分配方式）， map每次都需要 new 或delele 一个树结点, 内存分配是很耗时的。
- vector_map, 可以在数据构造阶段，使用push_back, 填充完，数据后调用一次sort就可以了（快速排序或堆排序）， 而map每次insert都是一次查找和树的旋转操作，整个过程就像是个插入排序。
- vector_map, 中的查找，而二分查找，时间复杂度是稳定的log(n), 而map是在log(n) 和 2* log(n)之间 (因为map是红黑树树实现，不是平衡二差树)。
- vector比map消耗更少的内存，vector内部是数组，辅助数据也很少， map是树形结构，有至少3个指针来维持关系。
当我们需要使用键值对时，我们应该综合考虑内存和效率两方面。以下是本人的一些个人建议： 1.元素为pair的vector 1）当vector不会频繁的在中间或者列表头插入、删除，且列表有序维护的成本低时，可以考虑使用vector，并利用二分查找来查找指定元素； 2）当数据量较大，内存不足以使用unordered_map时，应当使用vector替代； 2.map 1）当数据量不大，并且key的类型无法计算hash值，可以考虑使用map替代vector，以将我们从vector列表有序的维护中解放出来； 2）当数据量不大，且我们需要有序的访问键值对时，可以考虑使用map替代unordered_map； 3.unordered_map 1）在内存允许并且我们不要求有序的访问所有元素的情况下，我们应该尽量使用unordered_map；
六、容器选择原则因此在实际使用时，如何选择这几个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则： 1、如果你需要高效的随机存取，而不在乎插入和删除的效率，使用vector。
2、如果你需要大量的插入和删除，而不关心随机存取，则应使用list。
3、如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque。
4、如果你要存储一个数据字典，并要求方便地根据key找value，那么map是较好的选择。
5、如果你要查找一个元素是否在某集合内存中，则使用set存储这个集合比较好。
七、效率对比基本结论：
1、unordered_map比map快
2、vector查找14次，基本和unordered_map查找一次耗时相当（int和string做key差别不大）
3、string作key，vector查询100次，基本和map查询一次耗时相当；int作key，vector查询28次，基本和map查询一次耗时相当
4、boost的unordered_map和map与STL的效率基本相同
因此：抛弃map，用unordered_map吧。如果明确数据量小，比如小于14个，就用vector或数组，效率更高。
