STL中vector，Map，Set的实现原理

vector的数据安排以及操作方式，与array非常类似，两者唯一的区别是空间运用的灵活性，array是静态空间，一旦配置了就不能改变，如果你想要大一点的空间，就必须首先配置一块新空间，然后将原来的元素一一复制进来，再把原来的空间释放给系统。但是vector是动态空间，随着元素的增加，它的内部机制会自行扩充空间以容纳新元素，因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始要求一个大块头的array了，我们可以安心使用vector，随便使用多大空间都可以

vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector的旧有空间满载，如果客户端每新增一个元素，vector的内部只是扩充一个元素的空间，实为不智，因为所谓扩充空间，都是配置新空间，复制原来内容，释放旧空间所需要的时间很多，那么应该怎样配置空间呢，接下来再说。

并且vector维护的是一个连续线性空间，所以支持vector随机存取

注意：

vector动态增加大小时，并不是在原空间之后持续新空间（因为根本无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间，因此，一旦引起空间重新配置，指向原vector的所有迭代器都失效了，这是程序员易犯的一个错误，务必小心

Map

Map是关联容器，以键值对的形式进行存储，方便进行查找，关键词起到索引的作用，值则表示与索引相关联的数据，以红黑树的结构实现，插入删除等操作都可以在O(log n)时间内完成

Map基本操作：

1.map<int ,string> a; map<string,int>;支持多种类型

2.添加数据：map1.insert(pair<int,string>(102,"wobeitianjia"));

map1.insert(map<int,string>::value_type(102,"tianjia"));

map1[102]="string";

3.元素查找：map1.find(key)  返回一个迭代器指向键值为key的元素，如果没有找到，返回指向map尾部的迭代器

4.元素删除：先查找元素，map<int ,string>::iterator it=map1.find(key); 找到之后map1.erase(it);

5.map中的swap函数，交换的是两个容器而不是一个容器中的元素交换

6.sort函数，因为map中key按照升序进行排列的，所以不能使用sort函数

set

Set是关联容器，set中每个元素都只包含一个关键字，set支持高效的关键字查询操作---检查每一个给定的关键字是否在set中，set是以红黑树的平衡二叉检索树结构实现的，支持高效插入删除，插如元素的时候会自动调整二叉树的结构，使得每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值，另外还得保证左子树和右子树的高度相等

平衡二叉检索树使用中序遍历算法，检索效率高于vector，deque，list等容器，另外使用中序遍历可将键值按照从小到大遍历出来

构造set集合的主要目的是为了快速检索，不可直接去修改键值

常用操作：

1.元素插入：insert

2.中序遍历：类似vector遍历（用迭代器）

3.反向遍历：利用反向迭代器reverse_iterator

set<int> s;  set<int>::reverse_iterator rit;  for(rit=s.rbegin();rit!=s.rend();rit++)

4.元素的删除：s.erase(2);  s.clear();

5.元素的检索：find(),若找到，返回该值迭代器的位置，否则返回最后一个元素后面一个位置s.end()

it=s.find(5); if(it==s.end()) cout<<"not find"<<endl;else cout<<*it<<endl;