目录前言1 set使用2 map使用3 set /map 迭代器特性4 map 和 set 的封装5 源码前言std::set、std::map底层都是红黑树平衡二叉搜索树元素默认按键从小到大排序键不可修改插入、删除、查找时间复杂度 O(log n)。setT只存值值即是键容器内元素唯一mapK,V存储键‑值对pairconst K, Vkey唯一value 可以重复关联式容器关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。键值对用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。template class T1, class T2 struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(): first(T1()), second(T2()) {} pair(const T1 a, const T2 b): first(a), second(b) {} };pairk,v _kv;1 set使用C的set是标准库提供的关联式容器它自动维护唯一元素的有序集合。简单使用#includeiostream #includeset using namespace std; void test_set1() { //排序去重 setint s1; s1.insert(1); s1.insert(1); //这里的1先当于没有插入 s1.insert(12); s1.insert(2); s1.insert(3); s1.insert(4); //这里的迭代器使用的是中序 setint::iterator it s1.begin(); while (it ! s1.end()) { //set的普通迭代器不允许修改 cout *it ; it; } cout endl; } int main() { test_set1(); return 0; }打印结果我们发现这里插入后打印有排序和去重的效果核心成员函数setint s; s.insert(2);//插入元素插入重复的元素直接忽略 s.erase(2); //删除值为3的元素也可以传迭代器 s.count(2); // 存在返回 1 不存在返回0 auto it find(2); //find返回迭代器找不到返回s.end() s.lower_bound(2); // 2的第一个元素 s.upper_bound(2); // 4 的第一个元素 s.size(); s.empty(); s.clear();自定义排序规则set默认是从小到大传greaterint实现降序setint,greaterint s {1,3,2}; //内部实现 321值得注意的是对于自定义结构体放入set, 必须重载运算符struct Person { int age; bool operator(const Person other) const { return age other.age; } }; setPerson st;multiset 排序 不去重复 允许冗余2 map使用map 里面存的是pairconst K, Vkey是const类型不能修改。定义与插入元素mapstring,int mp; //方式1 []运算符 key不存在也会自动创建默认value mp[zhang] 20; //方式2 insert插入pair mp.insert(make_pair(li,21)); mp.insert({wang,18});值得注意的是[ ]有副作用如果只是查询不要使用[ ]因为使用[ ]即使不存在也会插入查询元素//方式1 auto it mp.find(zhang); //方式2 mp.count(wang); //存在返回1不存在返回0删除元素mp.erase(wang); //通过key删除 mp.erase(it); //通过迭代器删除遍历map// pairconst string, int for(auto item : mp){ cout item.first item.second endl; }map自定义排序//按键降序排列 mapint,string,greaterint mp;3 set /map 迭代器特性迭代器是双向迭代器只支持、--不支持it 5set 里面*it是常量禁止修改map 里it‑first常量it‑second可以修改erase 之后被删除的迭代器失效其余迭代器不受影响红黑树结构只有局部调整auto it s.find(5); s.erase(it); // 此处it已经失效不能再使用it //it里存的还是原来节点的旧地址但这块内存已经还给系统变成野指针 //错误用法示例 error auto it s.find(5); s.erase(it); it; //错误it已经野指针程序可能崩溃或者乱值。 int x *it; //未定义行为Q: 为什么链表 vector 和 set 迭代器失效范围差别很大?A:vectorerase 之后后面所有迭代器全部失效因为元素会整体前移set/map红黑树仅仅被删除节点对应的迭代器失效剩下迭代器依旧可用unordered_set删除元素大概率不会失效但发生 rehash 的时候全部迭代器失效。避免迭代器失效的写法方式 1erase 之前提前保存下一个迭代器auto it s.find(5); if(it ! s.end()) { auto next_it std::next(it); //先拿到下一个位置 s.erase(it); it next_it; //让it指向有效迭代器 }方式 2利用 erase 返回值C11 之后//set的erase(迭代器) 返回值类型是void //list,unordered_set的erase会返回下一个迭代器 it s.erase(it); //set-erase 返回void编译报错! listint li; it li.erase(it); //list可以erase返回后继迭代器 setint st; st.erase(it); //void不能接收迭代器失效典型问题错误场景//error for(auto it s.begin(); it ! s.end(); it) { if(*it 5) { s.erase(it); //这里的erase之后it失效后继的it崩溃 } }正确处理场景for(auto it s.begin();it ! s.end(); ) { if(*it 5) { //it s.erase(it); //unordered_set可以这样set不可以 //set版本必须先取next auto tmp next(it); s.erase(it); it tmp; } else { it; } }注意 map容器里的迭代器失效与set 一样4 map 和 set 的封装map 和 set 底层是使用红黑树来实现的借助封装公用一套红黑树模板来实现map和set节点的结构如下因为set 的数据类型 是 key , map是pair , 使用T data 这样就可以公用一套模板。set可以直接使用data进行比较map在这里的插入过程中不能直接使用data进行比较。但是这里希望使用一套模板来达到要求可以使用仿函数来实现仿函数来实现比较set直接返回key即可而map是pairK,V 需要返回 kv.first//set仿函数 struct SetKeyOfT { const K operator()(const K key) { return key; } }; //map仿函数 struct SetMapOfT { const K operator()(const pairK,V kv) { return kv.first; } };对于set和map的Insert也需要进行分别处理区分键和键值对因为set 和 map 公用一套模板实际调用的是底层红黑树中的的插入在插入过程使用的查询不能写成固定不变的因为set可以直接使用key进行比较但是map是pair不能直接使用key进行比较所以这里给出一个使用比较仿函数的解决方法。set 和 map迭代器封装begin一般在最左节点end 一般是最后一个节点的下一个位置//迭代器 标准的是 左闭右开 Iterator Begin() { Node* Minleft _root; while (Minleft Minleft-_left) { Minleft Minleft-_left; } //return Minleft; 使用的是隐式类型的转换 return Iterator(Minleft); //构造匿名对象进行返回 } //end 右开 Iterator End() { return Iterator(nullptr); }map和set迭代器遍历实现迭代器前置 实现中序遍历 遇到根不访问访问左孩子 当前节点的右子树不为空中序下一个访问的节点右子树的最左节点 右为空下一个访问倒着在祖先里找找孩子是父亲左的祖先前置实现1前置实现2参考代码Self operator() //前置 { //1 当前节点的右子树不为空中序下一个访问的节点为右子树的最左节点 if (_node-_right) { Node* Minleft _node-_right; while (Minleft Minleft-_left) { Minleft Minleft-_left; } _node Minleft; } else //2 当前节点右子树为空中序下一个访问的节点为倒着在祖先里找找孩子是父亲左的祖先 { Node* cur _node; Node* parent _node-_parent; while (parent parent-_right cur) { cur parent; parent parent-_parent; } _node parent; //while循环结束后parent节点就是后的节点 } return *this; }迭代器前置-- 实现1迭代器前置-- 实现2迭代器前置-- 实现3参考代码Self operator--() { //1 当前节点的左子树不为空中序上一个访问节点为左子树中序的最后一个节点 if (_node-_left) { Node* Maxright _node-_left; while (Maxright Maxright-_right) { Maxright Maxright-_right; } _node Maxright; } else { //2 当前节点的左子树为空中序上一个访问的节点为 // 找孩子是父亲右的那个祖先节点 Node* cur _node; Node* parent _node-_parent; while (parent parent-_left cur) { cur parent; parent parent-_parent; } _node parent; } return *this; }如果是已经示例化的类模板setint::iterator it s.begin();对于没有实例化的类模板要去里面取类嵌类型的时候因为类模板没有实例化不知道是静态成员变量还是类型这里要加上typenametypedef typename RBTreeK, K, SetKeyOfT::Iterator iterator;详细分析Q : 为什么要加上typename?A: RBTreeK, K, SetKeyOfT::Iterator 主要是依赖模板参数的嵌套类型这里的编译器在实例化之前分不清楚 Iterator 成员变量还是类型名。这里typename作用 告诉编译器Iterator是一个类型不是成员变量。template 和 typename template 后面跟模板参数typename:1 在模板参数列表等价于class,例如 templatetypename K;2 从属类型名前面修饰告诉编译器这是类型。关于拷贝拷贝方法 遇到根拷贝根根拷贝完成递归拷贝左子树遇到空返回递归拷贝右子树Node* Copy(Node* root) { //拷贝构造实现 //遇到空返回空 if (root nullptr) return nullptr; //递归拷贝 Node* newnode new Node(root-_data); newnode-_col root-_col; newnode-_left Copy(root-_left); if (newnode-_left) { newnode-_left-_parent newnode; } newnode-_right Copy(root-_right); if (newnode-_right) { newnode-_right-_parent newnode; } return newnode; }对于map 中的operator[ ] 是通过insert来实现的V operator[](const K key) { // value类型的缺省值 pairiterator,bool ret _t.Insert(make_pair(key,V())); return ret.first-second; }5 源码set 和 map实现源码 请猛戳