c++之STL模板，set与map

为什么把set与map放在一起呢，因为里面有很多一样的特性与结构；

一，set集合

原理：

　　set里面的数据存放，不是数组模式，也不是指针链表模式，而是二叉树模式，和map也是二叉树模式，所以把set和map放在一起，这个二叉树，不是简单的二叉树，就查找二叉树与平衡二叉树的结合题，红黑树！

　　查找二叉树（BST）：左儿子的值比我小，而右儿子的值比我大，宏观，我的左子树的值，都比我小，我的右子树的值都比我大；这样定义的用途是方便查询，达到二分查找的效果；

　　平衡二叉树（AVL）：左右两边的深度，相差不多；

　　而两者都各有优点，缺点，设想，如果查找二叉树中，根结点成为最大的值，那么其他的结点，都在该结点的左边，这样就达不到快速查找的效果，为了解决这个问题，就把查找二叉树和平很二叉树结合起来，到底如何保持树的平衡呢？于是引入颜色来辨别树是否歪曲；

　　给红黑树四个原则，遵守这四个原则就可以构建红黑树：

　　（1）根节点为黑色；

　　（2）叶子结点为空值的黑色结点；

　　（3）红色结点的两个子节点必须为黑色（红黑红黑树）

　　（4）所有叶子结点到根结点的路径中，黑色结点个数要一样；

 　　由原则3知道，不会有两个连续的红色结点；由原则4可知，红黑树中最短的路径就是全黑色的结点，而最远的路径就是“黑-红-黑-红-黑-红‘，那么如果假设黑色结点个数为：n,那么最短路径长为n-1,最长为2*n-1，这样就确保了红黑树中，最长的路径不会超过最短路径的两倍；

　　那么在插入和删除结点的过程中，会影响红黑树的结构，甚至打破平衡，在插入的时候，默认为红色结点，进行原则判断，不满足原则，则改变颜色，如果还不满足条件，则进行子树选择，右选择和左选择，与AVL选择一样；

　　而查找和修改结点的值，则是与普通二叉树相同，指针指向这个值进行读取（但是修改，结点的位置可能发生改变，所以，化归，改变一个值，就是删除原来的点，然后增加一个新的结点，有的编译器支持修改，有的不支持修改）！

　　了解了set的底层数据结构红黑树后，我们介绍set的具体使用；

迭代器原理：新增一个头节点，left指向最小的红黑树中值最小的结点，而right指向红黑树中值最大的结点，parent指向根结点，头节点之际的地址存为end()，所以，正向访问和逆向访问，都是从begin()，或者rbegin()，都是从头节点的左右指针出发，最后返回来自己本身；那么++和--操作就是指针的移动，采用中序遍历，返回到父节点（细节划分，可以分为4种情况）

特性

　　与其他STL模板相比，该数据结构特点在于，插入的值，会自动形成顺序，所以你不用关心插入的位置在哪里，它会自动安排，然后就是不允许插入重复的值（multiset允许插入相同的值）

　　综上所诉，两个特性：（1）自动排序（从小到大）;(2)不允许重复值

功能

　　传统方法：增加，删除，查找；

　　set<int> p;

　　增加：p.insert(i);直接放入值就可以；

　　删除：p.erase(i)删除值为i的结点，也可以放入指针指向的值；本质相同（底部原理都是通过find找到再处理）返回结果为0或者1，1为删除成功，0为删除失败，未找到；

　　查找：p.find(i)放入要查找的目标值，返回结果为指针，如果未找到就是返回p.end()指针了，找到了，就是返回指向这个值的指针；

小实验：

 1 #include<iostream>
 2 #include<set>
 3 using namespace std;
 4 int main() {
 5     set<int> p;    //声明
 6     //插入；（10个）
 7     for (int i = 0; i < 10; i++) {
 8         p.insert(i);
 9     }
10     //遍历查看；因为set是链表，所以不能用下标访问；只能用迭代器指针；
11     for (auto it = p.begin(); it != p.end(); it++) {
12         cout << " " << *it;
13     }cout << endl;
14     //删除   参数是里面的值，如何这个值不存在会出现什么？
15     cout <<"删除8返回值："<< p.erase(8) << endl;
16     cout << "删除100（不存在）返回值："<<p.erase(100) << endl;
17     for (auto it = p.begin(); it != p.end(); it++) {
18         cout << " " << *it;
19     }cout << endl;
20     cout << *p.find(9) << endl;//返回的是指向这个值的指针；
21     system("pause");
22     return 0;
23 }

set增删查操作

优点：查询快 自动排序 避免重复值

缺点：不能动态删除；（删除后，结构会发生变化，迭代器指向的位置，发生偏移） 不能索引访问，

二，map集合

原理：底层原理和set一样；不同之处就是data域，set的data域是个单独的类型，而map的是通过pair打包形成一个结构体，是键：值的结构，而map的排序，是默认键从小到大排序的；而且在构建的时候，键对应的值默认为0；

特性：set拥有的特性，map全都有，而且因为特殊的结构，还重载了[ ]方便用户操作，[]的底层其实就是find()，找到了就可以进去修改，如果没有找到，可以通过[]插入新的值，删除功能同样是给出具体的值，然后查找，再删除，而线性的数组式结构，就不能使用具体的值查找删除，而是直接随机访问删除，因为数组访问起来比较慢，（！）

　　　而sort算法也是只对线性数组结构有效（vector,string)所以，对map进行另外的排序时，要通过vector的构建特性，把map导入vector,通过vector进行sort排序；

！<如何手写实现set与map>