【C++】Vector、Map、Set的原理

Vector

    Vector的数据安排以及操作方式，与array非常类似，两者唯一的区别是空间运用的灵活性，array是静态空间，一旦配置了就不能改变，如果你想要大一点的空间，就必须首先配置一块新空间，然后将原来的元素一一复制进来，再把原来的空间释放给系统。但是vector是动态空间，随着元素的增加，它的内部机制会自行扩充空间以容纳新元素，因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助。
    vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector的旧有空间满载，如果客户端每新增一个元素，vector的内部只是扩充一个元素的空间，实为不智，因为所谓扩充空间，都是配置新空间，复制原来内容，释放旧空间。因为vector维护的是一个连续线性空间，所以支持vector随机存取
    vector动态增加大小时，并不是在原空间之后持续新空间（因为根本无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间，因此，一旦引起空间重新配置，指向原vector的所有迭代器都失效了，这是程序员易犯的一个错误，务必小心

Map

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

Map基本操作：
1.初始化：支持多种类型

map<int ,string> a;
map<string,int>;

添加数据：

map1.insert(pair<int,string>(102,"wobeitianjia")); 
map1.insert(map<int,string>::value_type(102,"tianjia"));
map1[102]="string";

元素查找：map1.find(key) 返回一个迭代器指向键值为key的元素，如果没有找到，返回指向map尾部的迭代器
元素删除：先查找元素，map<int ,string>::iterator it=map1.find(key); 找到之后map1.erase(it);
map中的swap函数，交换的是两个容器而不是一个容器中的元素交换
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;

List

List是顺序容器的一种，是一个线性双向链表结构，它的数据由若干个节点构成。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。List按照元素插入顺序存储。

优点：

不使用连续内存完成动态操作。
在内部方便的进行插入和删除操作
可在两端进行push、pop

缺点：

不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
相对于verctor占用内存多