目录

前言：

1 set使用

2 map使用

3 set /map 迭代器特性

4 map 和 set 的封装

5 源码

前言：

std::set、std::map底层都是红黑树（平衡二叉搜索树），元素默认按键从小到大排序，键不可修改，插入、删除、查找时间复杂度 O(log n)。

• set<T>：只存值，值即是键，容器内元素唯一；
• map<K,V>：存储键‑值对pair<const K, V>，key唯一，value 可以重复；

关联式容器

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的
键值对，在数据检索时比序列式容器效率更高。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
表键值，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) {} };

pair<k,v> _kv;

1 set使用

C++的set是标准库提供的关联式容器，它自动维护唯一元素的有序集合。

简单使用

#include<iostream> #include<set> using namespace std; void test_set1() { //排序+去重 set<int> s1; s1.insert(1); s1.insert(1); //这里的1先当于没有插入 s1.insert(12); s1.insert(2); s1.insert(3); s1.insert(4); //这里的迭代器使用的是中序 set<int>::iterator it = s1.begin(); while (it != s1.end()) { //set的普通迭代器不允许修改 cout << *it<<" "; ++it; } cout << endl; } int main() { test_set1(); return 0; }

打印结果：

我们发现这里插入后打印有排序和去重的效果

核心成员函数

set<int> 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默认是从小到大；传greater<int>实现降序：

set<int,greater<int>> s = {1,3,2}; //内部实现 3，2，1

值得注意的是：对于自定义结构体放入set, 必须重载<运算符

struct Person { int age; bool operator<(const Person& other) const { return age < other.age; } }; set<Person> st;

multiset ： 排序 不去重复 允许冗余

2 map使用

map 里面存的是pair<const K, V>，key是const类型，不能修改。

定义与插入元素

map<string,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

// pair<const string, int> for(auto& item : mp){ cout << item.first << " " << item.second << endl; }

map自定义排序

//按键降序排列 map<int,string,greater<int>> mp;

3 set /map 迭代器特性

• 迭代器是双向迭代器，只支持++、--，不支持it + 5；
• set 里面*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:

• vector：erase 之后后面所有迭代器全部失效，因为元素会整体前移；
• set/map（红黑树）：仅仅被删除节点对应的迭代器失效；剩下迭代器依旧可用；
• unordered_set：删除元素大概率不会失效，但发生 rehash 的时候全部迭代器失效。

避免迭代器失效的写法：

方式 1：erase 之前提前保存下一个迭代器

auto it = s.find(5); if(it != s.end()) { auto next_it = std::next(it); //先拿到下一个位置 s.erase(it); it = next_it; //让it指向有效迭代器 }

方式 2：利用 erase 返回值（C++11 之后）

//set的erase(迭代器) 返回值类型是void //list,unordered_set的erase会返回下一个迭代器 it = s.erase(it); //set-erase 返回void，编译报错! list<int> li; it = li.erase(it); //list可以，erase返回后继迭代器 set<int> 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是pair<K,V> 需要返回 kv.first

//set仿函数 struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; //map仿函数 struct SetMapOfT { const K& operator()(const pair<K,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; }

如果是已经示例化的类模板：

set<int>::iterator it = s.begin();

对于没有实例化的类模板，要去里面取类嵌类型的时候（因为类模板没有实例化，不知道是静态成员变量还是类型）这里要加上typename

typedef typename RBTree<K, K, SetKeyOfT>::Iterator iterator;

详细分析：

Q : 为什么要加上typename?

A: RBTree<K, K, SetKeyOfT>::Iterator 主要是依赖模板参数的嵌套类型，这里的编译器在实例化之前分不清楚： Iterator 成员变量，还是类型名。

这里typename作用： 告诉编译器，Iterator是一个类型，不是成员变量。

template 和 typename ：

template： 后面跟模板参数

typename:

1 在模板参数列表等价于class,例如 template<typename 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类型的缺省值 pair<iterator,bool> ret = _t.Insert(make_pair(key,V())); return ret.first->second; }

5 源码

set 和 map实现源码 请猛戳