拓冰网站定制 )
前言关于容器的使用在C专栏里的stringvector那两篇文章里讲的很详细这里简单的带过重点是去模拟底层相关一些关于数据结构的知识(这部分也是偏向于讲解底层对概念有选择的说明)。二叉搜索树二叉搜索树是一个不太完美的结构很容易出现类似于单枝树的形态时间复杂度就由O(logN)退化成O(N)。二叉搜索树也叫二叉排序树因为对它进行中序便利就会得到升序的序列。注由于map和set的底层是二叉搜索树所以本文先以底层模拟实现的方式带大家快速回忆二叉搜索树其具体概念本身比较简单就不过多介绍了。二叉搜索树key的模拟实现二叉搜索树key不支持修改因为一旦修改就不是二叉搜索树了。//结点---key templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; BSTNode(const K key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} }; templateclass K class BSTree { typedef BSTNodeK Node; public: bool Insert(const K key) { //先考虑二叉树为空的情况 if (_root nullptr) { _root new Node(key);//BSTNodeK(key) return true; } //二叉树不为空根据二叉搜索树的性质来插入(这里默认树里是没有相同元素的) //从根节点的位置开始往下一一比对大的往右边小的往左边 //找到合适的空结点位置插入 Node* parent nullptr;//parent记录插入结点位置的父亲结点 Node* cur _root; //走到为空的位置停下 //注如果二叉树存着相同的值 //在插入这里处理的方式就是key的往右边走key的往左边走 //其他地方的处理方式下边说 while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else//这里是cur-key key { return false; } } //注意这里的cur是局部变量出作用域直接销毁了parent的作用显示出来了 //cur-_key key; cur new Node(key); //这里不用去考虑parent-_key key的情况因为在上边已经考虑过了 //这里只是看看要插入的位置是在parent的左边还是右边 if (parent-_key key) { parent-_left cur; } else if (parent-_key key) { parent-_right cur; } return true; } //递归版本的插入 bool InsertR(const K key) { _InsertR(_root, key); } bool Find(const K key) { //从根节点开始往后一一比对 Node* cur _root; while (cur) { if (cur-_key key) { cur cur-_left; } else if (cur-_key key) { cur cur-_right; } else { return true; } } return false; } bool Erase(const K key) { //先查找元素所在的位置 Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else { //找到了准备删除key结点有以下这些情况 //注左右都为空 的情况已经包含在 左为空右不为空 的情况里了 //左为空父亲指向我右孩子 if (cur-_left nullptr) { //有可能要删除的是根结点需要特殊处理一下 //因为根结点没有父亲parent就一直为nullptr //走原来的逻辑就会发生空指针解引用 if (cur ! _root) { //要删除的结点有可能在parent的右边也有可能在左边 if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } else { _root cur-_right;//修改根结点原来的根也就是cur直接delete } delete cur; } //右为空父亲指向我左孩子 else if (cur-_right nullptr) { if (cur ! _root) { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } else { _root cur-_left; } delete cur; } else { //左右都不为空---目的就是在cur的左右子树中找到一个结点去满足BST树的结构 //这里是找其(cur)右子树的最小结点(右子树的最左子结点) //还可以找其左子树的最大结点(左子树的最右结点) //去替代被删除掉的结点 /* 注意1有可能右子树的最小结点就是minNode自己 * 因为minNode有可能没有左结点 * 此时会出现minNodeParent的空指针解引用问题 * 因为while循环条件不成立minNodeParent依旧是nullptr * 后边会导致空指针的解引用 * 解决方法minNodeParent初始化为cur */ Node* minNodeParent cur; Node* minNode cur-_right; while (minNode-_left) { minNodeParent minNode; minNode minNode-_left; } //找到右子树的最小结点之后跟要删除的cur做key值的交换 //只交换key值就可以不改变原来的指针指向结构 //此时要删除的结点变成了minNode swap(minNode-_key, cur-_key); //注意2 //由注意1知右子树的最小结点有可能就是初始化时的minnode自己 //此时minnode在minnodeparent的右边 //除了上述情况minnode一直在minnodeparent的左边所以下边要判断一下 //minnode的左子树必为空因为它是右子树的最左结点那它左边肯定为空 //minnode的右子树为不为空不知道反正左为空父指向右 if(minNodeParent-_left minNode) minNodeParent-_left minNode-_right; else minNodeParent-_right minNode-_right; delete minNode; } return true;//别忘了写返回值 } } return false;//没找到返回false } void InOrder() { _InOrder(_root); cout endl; } private: //这里加引用是为了方便后边直接给空结点new值 //用传引用传参解决了寻找要插入的结点是父亲的左结点还是右结点 //画画递归图就能理解了 bool _InsertR(Node* root, const K key) { if (root nullptr) { root new Node(key); return true; } if (root-_key key) return _InsertR(root-_right, key); else if (root-_key key) return _InsertR(root-_left, key); else return false; } //中序便利---升序 //这里不能直接用_Inorder(Node* root)这个函数 //因为_root是private没法直接在类外传参使用 void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout (root-_key) ; _InOrder(root-_right); } private: Node* _root nullptr; };(Erase)删除情况3补充cur的左右孩子均不为空二叉搜索树key/value的模拟实现key/value还是利用key去构建二叉搜索树的只不过每个结点在原来基础上增加了一个value值。一些变化结点里需要增加一个模板参数表示value。插入的时候由原来插入一个值变成两个值。查找的时候是需要返回key对应的value因此干脆返回一个结点。中序便利的时候key和value都要便利。templateclass K, class V struct BSTNode { K _key; V _value; BSTNodeK, V* _left; BSTNodeK, V* _right; BSTNode(const K key, const V value) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} }; templateclass K, class V class BSTree { typedef BSTNodeK, V Node; public: bool Insert(const K key, const V value) { if (_root nullptr) { _root new Node(key, value); return true; } Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else { return false; } } cur new Node(key, value); if (parent-_key key) { parent-_left cur; } else if (parent-_key key) { parent-_right cur; } return true; } Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_key key) { cur cur-_left; } else if (cur-_key key) { cur cur-_right; } else { return cur; } } return nullptr; } bool Erase(const K key) { Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else { if (cur-_left nullptr) { if (cur ! _root) { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } else { _root cur-_right; } delete cur; } else if (cur-_right nullptr) { if (cur ! _root) { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } else { _root cur-_left; } delete cur; } else { Node* minNodeParent cur; Node* minNode cur-_right; while (minNode-_left) { minNodeParent minNode; minNode minNode-_left; } swap(minNode-_key, cur-_key); if (minNodeParent-_left minNode) minNodeParent-_left minNode-_right; else minNodeParent-_right minNode-_right; delete minNode; } return true; } } return false; } void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout (root-_key) : (root-_value); _InOrder(root-_right); } private: Node* _root nullptr; };setset底层就是二叉搜索树key且set里边不能含有重复的元素(set可以拿来去重)。关于set的结构(如下图)唯一要说的就是它支持传仿函数仿函数的本质就是为了去比较大小因为构建二叉搜索树是需要比较大小的但是有的时候可能因为传的类型(比如说指针)用库里默认的比较方式去比较会有问题亦或者我们想按照自己的想法去比较大小此时就可以自己传一个仿函数过去。构造函数和迭代器构造函数这里稍微总结一下基本对于每一个容器的构造函数来说的话一般就重点关注几个无参的迭代器区间的拷贝构造Initializer_list构造。迭代器set是关联容器其迭代器不管是普通的还是const的都不支持修改set里元素的内容(文档里也有说明)这也很好理解set底层是红黑树一旦数据修改逻辑结构就马上不对了。想实现set的修改只能间接通过删除数据插入新数据的方式。迭代器便利走的是中序所以是有序的这也表示begin()指向的就是set里最小的那个元素end()的前一个位置就是set里最大的那个元素再由于set本身不支持存重复的元素所以set还可以用来去重。set里自带的find跟algorithm库里边find的区别使用int main() { setint s { 5,1,5,3,4,2,6,83,9,10,22 }; //auto it1 s.find(3); auto it1 find(s.begin(), s.end(), 3);//algorithm if (it1 ! s.end()) { cout 找到了 endl; } else { cout 没找到 endl; } return 0; }对比set里自带的find效率比较高利用红黑树的查找逻辑大的往右走小的往左走时间复杂度为O(logN)而算法库里的是泛型模板函数可以传任意容器的迭代器过去时间复杂度为O(N)(具体怎么实现的可以直接去文档里看)。N越大时间花销相差越大比如说N10002^101024所以logN大概就是10次左右查10次就找到了而N就要查1000次。countcount用于统计数据出现的次数在set里的数据都是只出现0或1次为什么还需要返回值因为需要跟multiset等其他容器里的count保持一致性multiset里的数据不止出现一次count的返回值就有了意义。另外count也起到了用来查找set里数据在不在的作用。int main() { //count在一定程度上也简化了代码用find相对麻烦一点 setint s { 5,1,5,3,4,2,6,83,9,10,22 }; if (s.count(3)) { cout 存在 endl; } else { cout 不存在 endl; } return 0; }lower_bound和upper_bound需求删除数组里值在[3,9]的所有数字。使用erase删除区间要求是左闭右开并且[3, 9]这个区间里的所有数字并不是全都真实的在这个区间里所以就需要有这么两个函数去帮我们查找一段真实有效的子区间或者就是区间[3, 9]且保证是左闭右开的来让我们更好的去调用erase函数。int main() { setint s { 5,1,5,3,4,2,6,83,9,10,22 }; auto it1 s.lower_bound(3);//返回3的最小数据的迭代器 auto it2 s.upper_bound(9);//返回9的最小数据的迭代器若9就是set里的最后一个元素那么此时upper_bound返回的迭代器就是end() //一般容器的各种接口都是左闭右开区间 //因为容器迭代器一般不支持大小比较只能进行!比较 //不支持的原因就在于迭代器指向的底层数据可能是不连续的 //要删除的区间变成[it1, it2) //正是由于迭代器不支持大小比较所以只有左闭右开的区间才能实现这种便利的场景 //试想一下如果区间是两边闭合的又不支持大小比较那没法搞 //千万别说可以写成it ! it2 1迭代器不支持直接加上一个数字的迭代器不是真指针呀 for (auto it it1; it ! it2; it) { cout *it ; } cout endl; //s.erase(it1, it2); erase删除的是左闭右开区间 return 0; }multiset的使用multiset底层也是二叉搜索树key它跟set的接口可以说完全一样就是multiset里的数据可以重复。void Print(const multisetint m) { for (auto e : m) { cout e ; } cout endl; } int main() { //有序 multisetint ms { 5,1,5,3,4,2,6,83,5,5,9,9,22 }; Print(ms); //使用erase传的是值的时候其会有一个返回值返回的是删除的数据个数 //erase会将所有的5全部删掉 cout erase的返回值: ms.erase(5) endl; Print(ms); //count的返回值有意义了 cout count的返回值: ms.count(5) endl; //如果multiset里有多个相同的值find的返回值返回的是中序便利的第一个 //以下代码验证的是find是否返回的是中序便利的第一个值的迭代器 //也可以是用来获取一段相同的区间里的所有值 //只有pos初始时是中序的第一个x时才能将multiset里所有等于x的值拿到 int x; cin x; auto pos ms.find(x); while (pos ! ms.end() *pos x) { cout *pos ; pos; } cout endl; return 0; }简单说一下find的原理拿下边那棵搜索树举例搜索树里有三个5和set一样multist底层是红黑树实现的之后的博客会说这里先说一下红黑树是二叉搜索树的一种在二叉搜索树的基础上加了一点其他条件。multiset中find查找的一定是中序便利的第一个假设现在查找的是5根据搜索树的性质比根大往右走比根小往左走从而找到了第一个5此时先别着急返回中序便利是左根右所以再接下去去5的左子树里递归式的找5如果左子树里没有找到就说明当前这个5就是中序便利的第一个如果左子树里还有5就继续递归下去直至左子树里找不到此时的5一定是中序便利的第一个。mapmap的底层就是二叉搜索树key/value。pairpair就是一个类模板这个类的成员变量就是两个值first和second对于map来说key和value不是分开的而是就直接存在pair里一般first代表keysecond代表value。具体这个pair怎么用就在下文结合map一起说。templateclass T1, class T2struct pair{T1 first;T2 second;}map的简单使用map里的接口很多都是用pair作为参数的。你仔细去看文档里map的各种接口它们的参数都有一个value_type这个value_type就是pair类型的别名。void test_map1() { //1.写一个字典 pairstring, string pr1(sort, 排序);//pair的构造函数 pairstring, string pr2(left, 左边); pairstring, string pr3(right, 右边); //注意以下这种写法是隐式类型转化如果类有相应的构造支持就可以隐式类型转化 //构造只有一个参数就直接传构造不止一个参数就用花括号传注意这里不是initializer_list pairstring, string pr4 { ok, 好的 }; //map的initializer_list的构造构造拷贝构造mp1 mapstring, string mp1 { pr1, pr2, pr3, pr4 }; //上述pair的隐式类型转化map的initializer_list构造一结合就有了下边的写法 //{english, 英语}等先隐式类型转化为pair然后再调用map的构造函数最后拷贝构造给mp2 mapstring, string mp2 { {english, 英语}, {chinese, 语文}, {maths, 数学} }; //2.insert mapstring, string mp3; mp3.insert(pairstring, string(directory, 用法));//匿名对象 //make_pair是pair的一个成员函数它是inline函数底层是return一个pair的匿名对象 /* template class T1,class T2 pairT1,T2 make_pair (T1 x, T2 y) { return ( pairT1,T2(x,y) ); } */ mp3.insert(make_pair(const, 常量属性)); mp3.insert({ ok, 好 });//隐式类型转换 //3.map的便利 mapstring, string::iterator it1 mp3.begin(); while (it1 ! mp3.end()) { //对于const迭代器肯定是无法修改 //对于非const迭代器不可以修改key因为破坏了key就破坏了二叉搜索树的结构但可以改value it1-second x; //迭代器相当于是指向结点的指针解引用迭代器获取pair cout (*it1).first : (*it1).second endl; //迭代器重载了operator-跟list的很相似it1-first本质上就是it1.operator-()-first; //operator-()函数底层返回的是结点里pair的地址 cout it1-first : it1-second endl;//推荐这种写法 it1; } cout endl; //一定要加引用因为范围for底层是转化为迭代器的基本上全是深拷贝 //如果不加以修改的话还可以加上const for (const auto e : mp3) { cout e.first : e.second endl; } }补充语法结构化绑定C17新出语法一般现在的编译器默认不支持以vs2022来说可以自己去修改属性。void test() { pairint, int pr(1, 1); //pair里有两个值结构化绑定就是将结构体的属性(pair里的两个属性值)依次拷贝给x, y如果有更多参数就在[x, y....]里继续往后写 auto [x1, y1] pr; //由于拷贝有深拷贝影响效率所以加上引用 auto [x2, y2] pr; cout x2 : y2 endl; mapstring, string mp1 { {const, 常量属性}, {ok, 好的} }; for (auto [x, y] : mp1) { cout x : y endl; } }除了以pair为参数的map里还有许多就以key为参数的接口比如说像erasefindcount....只需要仔细去看文档就知道哪些是传的key哪些是传的pair了用法都是和set几乎一样的。equal_range这个接口返回的是map里和key值相等的左闭右开的一段区间返回的是一个pairpair的模板类型参数是iterator本质就是返回的一段区间。但map里不支持存重复的值所以这个接口在multimap里才会用到。operator[]void test_map2() { //统计每个水果出现的次数 string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 }; mapstring, int countMap; //法一: //for (auto e : arr) //{ // mapstring, int::iterator it countMap.find(e); // //说明没找到 // if (it countMap.end()) // { // countMap.insert({e, 1}); // } // else // { // it-second; // } //} //法二:利用operator[] for (auto e : arr) { countMap[e]; } for (auto [x, y] : countMap) { cout x : y endl; } }通过上边的例子我们首先明确感觉到使用operator[]的简洁性接下来具体说说这个[]重载通过官网给出的解释key不在map中operator[]就会插入。key在map中operator[]就可以做查找修改的工作。operator[]是传key返回value通过下图中圈出的一句话这个方法等同于一长串貌似好像是调用的insert并还利用了它的返回值。由此我们先来看看insert的返回值。insert的返回值很明显operator[]底层使用的insert是上图中圈出来的那一个版本返回值为pairiterator, boolbool表示的就是是否插入成功iterator指向的是新插入的结点或者指向跟要插入结点的key值相等的结点。如果插入的结点的key是map里没有bool就为true如果在map里已有bool就返回false。这也由此说明insert只看key同样的key就算value不同还是无法插入。(这段话翻译自官网第一手资料可以直接去官网里看英文版的)。总结一下insert的返回值pair里的iterator始终指向跟insert参数里value_type里的key相同的结点。所以如果要插入的结点的key在map里已经有了insert就充当了查找的作用。接下来回过头去看operator[]里的那句话。调用operator[]就等价于下边这段代码。注意下文里那段代码里边有两个pair一个pair是insert的返回值一个pair是对insert的返回值的那个pair里的iterator解引用后得到的树结点里存key/value的pair。(*((this-insert(make_pair(k, mapped_type()))).first)).second如果insert插入的pair里的key在map里已经有了insert返回值的iterator就会指向map里值为该key的结点此时insert的功能相当于就是查找反之就是插入新结点并且insert返回值的iterator指向的就是该新结点。正是由于operator[]底层利用了insert以及它的返回值这才造就了operator[]的两种功能。还有一个细节上文在统计每种水果出现的次数的时候如果该key在map里没有就会插入新节点那插入结点的key我知道了value是多少呢答案还是在上边的那串代码里mapped_type()本质在typedef前就表示的T()就是调用的默认构造对于自定义类型比如说像int()值就是0。所以countMap[e]先返回的是map里key对应的value值0并且operator[]返回的value是传引用返回所以之后就直接改成了1。 STL---map/set... “家族“详解(从使用到底层)
前言关于容器的使用在C专栏里的stringvector那两篇文章里讲的很详细这里简单的带过重点是去模拟底层相关一些关于数据结构的知识(这部分也是偏向于讲解底层对概念有选择的说明)。二叉搜索树二叉搜索树是一个不太完美的结构很容易出现类似于单枝树的形态时间复杂度就由O(logN)退化成O(N)。二叉搜索树也叫二叉排序树因为对它进行中序便利就会得到升序的序列。注由于map和set的底层是二叉搜索树所以本文先以底层模拟实现的方式带大家快速回忆二叉搜索树其具体概念本身比较简单就不过多介绍了。二叉搜索树key的模拟实现二叉搜索树key不支持修改因为一旦修改就不是二叉搜索树了。//结点---key templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; BSTNode(const K key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} }; templateclass K class BSTree { typedef BSTNodeK Node; public: bool Insert(const K key) { //先考虑二叉树为空的情况 if (_root nullptr) { _root new Node(key);//BSTNodeK(key) return true; } //二叉树不为空根据二叉搜索树的性质来插入(这里默认树里是没有相同元素的) //从根节点的位置开始往下一一比对大的往右边小的往左边 //找到合适的空结点位置插入 Node* parent nullptr;//parent记录插入结点位置的父亲结点 Node* cur _root; //走到为空的位置停下 //注如果二叉树存着相同的值 //在插入这里处理的方式就是key的往右边走key的往左边走 //其他地方的处理方式下边说 while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else//这里是cur-key key { return false; } } //注意这里的cur是局部变量出作用域直接销毁了parent的作用显示出来了 //cur-_key key; cur new Node(key); //这里不用去考虑parent-_key key的情况因为在上边已经考虑过了 //这里只是看看要插入的位置是在parent的左边还是右边 if (parent-_key key) { parent-_left cur; } else if (parent-_key key) { parent-_right cur; } return true; } //递归版本的插入 bool InsertR(const K key) { _InsertR(_root, key); } bool Find(const K key) { //从根节点开始往后一一比对 Node* cur _root; while (cur) { if (cur-_key key) { cur cur-_left; } else if (cur-_key key) { cur cur-_right; } else { return true; } } return false; } bool Erase(const K key) { //先查找元素所在的位置 Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else { //找到了准备删除key结点有以下这些情况 //注左右都为空 的情况已经包含在 左为空右不为空 的情况里了 //左为空父亲指向我右孩子 if (cur-_left nullptr) { //有可能要删除的是根结点需要特殊处理一下 //因为根结点没有父亲parent就一直为nullptr //走原来的逻辑就会发生空指针解引用 if (cur ! _root) { //要删除的结点有可能在parent的右边也有可能在左边 if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } else { _root cur-_right;//修改根结点原来的根也就是cur直接delete } delete cur; } //右为空父亲指向我左孩子 else if (cur-_right nullptr) { if (cur ! _root) { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } else { _root cur-_left; } delete cur; } else { //左右都不为空---目的就是在cur的左右子树中找到一个结点去满足BST树的结构 //这里是找其(cur)右子树的最小结点(右子树的最左子结点) //还可以找其左子树的最大结点(左子树的最右结点) //去替代被删除掉的结点 /* 注意1有可能右子树的最小结点就是minNode自己 * 因为minNode有可能没有左结点 * 此时会出现minNodeParent的空指针解引用问题 * 因为while循环条件不成立minNodeParent依旧是nullptr * 后边会导致空指针的解引用 * 解决方法minNodeParent初始化为cur */ Node* minNodeParent cur; Node* minNode cur-_right; while (minNode-_left) { minNodeParent minNode; minNode minNode-_left; } //找到右子树的最小结点之后跟要删除的cur做key值的交换 //只交换key值就可以不改变原来的指针指向结构 //此时要删除的结点变成了minNode swap(minNode-_key, cur-_key); //注意2 //由注意1知右子树的最小结点有可能就是初始化时的minnode自己 //此时minnode在minnodeparent的右边 //除了上述情况minnode一直在minnodeparent的左边所以下边要判断一下 //minnode的左子树必为空因为它是右子树的最左结点那它左边肯定为空 //minnode的右子树为不为空不知道反正左为空父指向右 if(minNodeParent-_left minNode) minNodeParent-_left minNode-_right; else minNodeParent-_right minNode-_right; delete minNode; } return true;//别忘了写返回值 } } return false;//没找到返回false } void InOrder() { _InOrder(_root); cout endl; } private: //这里加引用是为了方便后边直接给空结点new值 //用传引用传参解决了寻找要插入的结点是父亲的左结点还是右结点 //画画递归图就能理解了 bool _InsertR(Node* root, const K key) { if (root nullptr) { root new Node(key); return true; } if (root-_key key) return _InsertR(root-_right, key); else if (root-_key key) return _InsertR(root-_left, key); else return false; } //中序便利---升序 //这里不能直接用_Inorder(Node* root)这个函数 //因为_root是private没法直接在类外传参使用 void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout (root-_key) ; _InOrder(root-_right); } private: Node* _root nullptr; };(Erase)删除情况3补充cur的左右孩子均不为空二叉搜索树key/value的模拟实现key/value还是利用key去构建二叉搜索树的只不过每个结点在原来基础上增加了一个value值。一些变化结点里需要增加一个模板参数表示value。插入的时候由原来插入一个值变成两个值。查找的时候是需要返回key对应的value因此干脆返回一个结点。中序便利的时候key和value都要便利。templateclass K, class V struct BSTNode { K _key; V _value; BSTNodeK, V* _left; BSTNodeK, V* _right; BSTNode(const K key, const V value) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} }; templateclass K, class V class BSTree { typedef BSTNodeK, V Node; public: bool Insert(const K key, const V value) { if (_root nullptr) { _root new Node(key, value); return true; } Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else { return false; } } cur new Node(key, value); if (parent-_key key) { parent-_left cur; } else if (parent-_key key) { parent-_right cur; } return true; } Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_key key) { cur cur-_left; } else if (cur-_key key) { cur cur-_right; } else { return cur; } } return nullptr; } bool Erase(const K key) { Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else { if (cur-_left nullptr) { if (cur ! _root) { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } else { _root cur-_right; } delete cur; } else if (cur-_right nullptr) { if (cur ! _root) { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } else { _root cur-_left; } delete cur; } else { Node* minNodeParent cur; Node* minNode cur-_right; while (minNode-_left) { minNodeParent minNode; minNode minNode-_left; } swap(minNode-_key, cur-_key); if (minNodeParent-_left minNode) minNodeParent-_left minNode-_right; else minNodeParent-_right minNode-_right; delete minNode; } return true; } } return false; } void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout (root-_key) : (root-_value); _InOrder(root-_right); } private: Node* _root nullptr; };setset底层就是二叉搜索树key且set里边不能含有重复的元素(set可以拿来去重)。关于set的结构(如下图)唯一要说的就是它支持传仿函数仿函数的本质就是为了去比较大小因为构建二叉搜索树是需要比较大小的但是有的时候可能因为传的类型(比如说指针)用库里默认的比较方式去比较会有问题亦或者我们想按照自己的想法去比较大小此时就可以自己传一个仿函数过去。构造函数和迭代器构造函数这里稍微总结一下基本对于每一个容器的构造函数来说的话一般就重点关注几个无参的迭代器区间的拷贝构造Initializer_list构造。迭代器set是关联容器其迭代器不管是普通的还是const的都不支持修改set里元素的内容(文档里也有说明)这也很好理解set底层是红黑树一旦数据修改逻辑结构就马上不对了。想实现set的修改只能间接通过删除数据插入新数据的方式。迭代器便利走的是中序所以是有序的这也表示begin()指向的就是set里最小的那个元素end()的前一个位置就是set里最大的那个元素再由于set本身不支持存重复的元素所以set还可以用来去重。set里自带的find跟algorithm库里边find的区别使用int main() { setint s { 5,1,5,3,4,2,6,83,9,10,22 }; //auto it1 s.find(3); auto it1 find(s.begin(), s.end(), 3);//algorithm if (it1 ! s.end()) { cout 找到了 endl; } else { cout 没找到 endl; } return 0; }对比set里自带的find效率比较高利用红黑树的查找逻辑大的往右走小的往左走时间复杂度为O(logN)而算法库里的是泛型模板函数可以传任意容器的迭代器过去时间复杂度为O(N)(具体怎么实现的可以直接去文档里看)。N越大时间花销相差越大比如说N10002^101024所以logN大概就是10次左右查10次就找到了而N就要查1000次。countcount用于统计数据出现的次数在set里的数据都是只出现0或1次为什么还需要返回值因为需要跟multiset等其他容器里的count保持一致性multiset里的数据不止出现一次count的返回值就有了意义。另外count也起到了用来查找set里数据在不在的作用。int main() { //count在一定程度上也简化了代码用find相对麻烦一点 setint s { 5,1,5,3,4,2,6,83,9,10,22 }; if (s.count(3)) { cout 存在 endl; } else { cout 不存在 endl; } return 0; }lower_bound和upper_bound需求删除数组里值在[3,9]的所有数字。使用erase删除区间要求是左闭右开并且[3, 9]这个区间里的所有数字并不是全都真实的在这个区间里所以就需要有这么两个函数去帮我们查找一段真实有效的子区间或者就是区间[3, 9]且保证是左闭右开的来让我们更好的去调用erase函数。int main() { setint s { 5,1,5,3,4,2,6,83,9,10,22 }; auto it1 s.lower_bound(3);//返回3的最小数据的迭代器 auto it2 s.upper_bound(9);//返回9的最小数据的迭代器若9就是set里的最后一个元素那么此时upper_bound返回的迭代器就是end() //一般容器的各种接口都是左闭右开区间 //因为容器迭代器一般不支持大小比较只能进行!比较 //不支持的原因就在于迭代器指向的底层数据可能是不连续的 //要删除的区间变成[it1, it2) //正是由于迭代器不支持大小比较所以只有左闭右开的区间才能实现这种便利的场景 //试想一下如果区间是两边闭合的又不支持大小比较那没法搞 //千万别说可以写成it ! it2 1迭代器不支持直接加上一个数字的迭代器不是真指针呀 for (auto it it1; it ! it2; it) { cout *it ; } cout endl; //s.erase(it1, it2); erase删除的是左闭右开区间 return 0; }multiset的使用multiset底层也是二叉搜索树key它跟set的接口可以说完全一样就是multiset里的数据可以重复。void Print(const multisetint m) { for (auto e : m) { cout e ; } cout endl; } int main() { //有序 multisetint ms { 5,1,5,3,4,2,6,83,5,5,9,9,22 }; Print(ms); //使用erase传的是值的时候其会有一个返回值返回的是删除的数据个数 //erase会将所有的5全部删掉 cout erase的返回值: ms.erase(5) endl; Print(ms); //count的返回值有意义了 cout count的返回值: ms.count(5) endl; //如果multiset里有多个相同的值find的返回值返回的是中序便利的第一个 //以下代码验证的是find是否返回的是中序便利的第一个值的迭代器 //也可以是用来获取一段相同的区间里的所有值 //只有pos初始时是中序的第一个x时才能将multiset里所有等于x的值拿到 int x; cin x; auto pos ms.find(x); while (pos ! ms.end() *pos x) { cout *pos ; pos; } cout endl; return 0; }简单说一下find的原理拿下边那棵搜索树举例搜索树里有三个5和set一样multist底层是红黑树实现的之后的博客会说这里先说一下红黑树是二叉搜索树的一种在二叉搜索树的基础上加了一点其他条件。multiset中find查找的一定是中序便利的第一个假设现在查找的是5根据搜索树的性质比根大往右走比根小往左走从而找到了第一个5此时先别着急返回中序便利是左根右所以再接下去去5的左子树里递归式的找5如果左子树里没有找到就说明当前这个5就是中序便利的第一个如果左子树里还有5就继续递归下去直至左子树里找不到此时的5一定是中序便利的第一个。mapmap的底层就是二叉搜索树key/value。pairpair就是一个类模板这个类的成员变量就是两个值first和second对于map来说key和value不是分开的而是就直接存在pair里一般first代表keysecond代表value。具体这个pair怎么用就在下文结合map一起说。templateclass T1, class T2struct pair{T1 first;T2 second;}map的简单使用map里的接口很多都是用pair作为参数的。你仔细去看文档里map的各种接口它们的参数都有一个value_type这个value_type就是pair类型的别名。void test_map1() { //1.写一个字典 pairstring, string pr1(sort, 排序);//pair的构造函数 pairstring, string pr2(left, 左边); pairstring, string pr3(right, 右边); //注意以下这种写法是隐式类型转化如果类有相应的构造支持就可以隐式类型转化 //构造只有一个参数就直接传构造不止一个参数就用花括号传注意这里不是initializer_list pairstring, string pr4 { ok, 好的 }; //map的initializer_list的构造构造拷贝构造mp1 mapstring, string mp1 { pr1, pr2, pr3, pr4 }; //上述pair的隐式类型转化map的initializer_list构造一结合就有了下边的写法 //{english, 英语}等先隐式类型转化为pair然后再调用map的构造函数最后拷贝构造给mp2 mapstring, string mp2 { {english, 英语}, {chinese, 语文}, {maths, 数学} }; //2.insert mapstring, string mp3; mp3.insert(pairstring, string(directory, 用法));//匿名对象 //make_pair是pair的一个成员函数它是inline函数底层是return一个pair的匿名对象 /* template class T1,class T2 pairT1,T2 make_pair (T1 x, T2 y) { return ( pairT1,T2(x,y) ); } */ mp3.insert(make_pair(const, 常量属性)); mp3.insert({ ok, 好 });//隐式类型转换 //3.map的便利 mapstring, string::iterator it1 mp3.begin(); while (it1 ! mp3.end()) { //对于const迭代器肯定是无法修改 //对于非const迭代器不可以修改key因为破坏了key就破坏了二叉搜索树的结构但可以改value it1-second x; //迭代器相当于是指向结点的指针解引用迭代器获取pair cout (*it1).first : (*it1).second endl; //迭代器重载了operator-跟list的很相似it1-first本质上就是it1.operator-()-first; //operator-()函数底层返回的是结点里pair的地址 cout it1-first : it1-second endl;//推荐这种写法 it1; } cout endl; //一定要加引用因为范围for底层是转化为迭代器的基本上全是深拷贝 //如果不加以修改的话还可以加上const for (const auto e : mp3) { cout e.first : e.second endl; } }补充语法结构化绑定C17新出语法一般现在的编译器默认不支持以vs2022来说可以自己去修改属性。void test() { pairint, int pr(1, 1); //pair里有两个值结构化绑定就是将结构体的属性(pair里的两个属性值)依次拷贝给x, y如果有更多参数就在[x, y....]里继续往后写 auto [x1, y1] pr; //由于拷贝有深拷贝影响效率所以加上引用 auto [x2, y2] pr; cout x2 : y2 endl; mapstring, string mp1 { {const, 常量属性}, {ok, 好的} }; for (auto [x, y] : mp1) { cout x : y endl; } }除了以pair为参数的map里还有许多就以key为参数的接口比如说像erasefindcount....只需要仔细去看文档就知道哪些是传的key哪些是传的pair了用法都是和set几乎一样的。equal_range这个接口返回的是map里和key值相等的左闭右开的一段区间返回的是一个pairpair的模板类型参数是iterator本质就是返回的一段区间。但map里不支持存重复的值所以这个接口在multimap里才会用到。operator[]void test_map2() { //统计每个水果出现的次数 string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 }; mapstring, int countMap; //法一: //for (auto e : arr) //{ // mapstring, int::iterator it countMap.find(e); // //说明没找到 // if (it countMap.end()) // { // countMap.insert({e, 1}); // } // else // { // it-second; // } //} //法二:利用operator[] for (auto e : arr) { countMap[e]; } for (auto [x, y] : countMap) { cout x : y endl; } }通过上边的例子我们首先明确感觉到使用operator[]的简洁性接下来具体说说这个[]重载通过官网给出的解释key不在map中operator[]就会插入。key在map中operator[]就可以做查找修改的工作。operator[]是传key返回value通过下图中圈出的一句话这个方法等同于一长串貌似好像是调用的insert并还利用了它的返回值。由此我们先来看看insert的返回值。insert的返回值很明显operator[]底层使用的insert是上图中圈出来的那一个版本返回值为pairiterator, boolbool表示的就是是否插入成功iterator指向的是新插入的结点或者指向跟要插入结点的key值相等的结点。如果插入的结点的key是map里没有bool就为true如果在map里已有bool就返回false。这也由此说明insert只看key同样的key就算value不同还是无法插入。(这段话翻译自官网第一手资料可以直接去官网里看英文版的)。总结一下insert的返回值pair里的iterator始终指向跟insert参数里value_type里的key相同的结点。所以如果要插入的结点的key在map里已经有了insert就充当了查找的作用。接下来回过头去看operator[]里的那句话。调用operator[]就等价于下边这段代码。注意下文里那段代码里边有两个pair一个pair是insert的返回值一个pair是对insert的返回值的那个pair里的iterator解引用后得到的树结点里存key/value的pair。(*((this-insert(make_pair(k, mapped_type()))).first)).second如果insert插入的pair里的key在map里已经有了insert返回值的iterator就会指向map里值为该key的结点此时insert的功能相当于就是查找反之就是插入新结点并且insert返回值的iterator指向的就是该新结点。正是由于operator[]底层利用了insert以及它的返回值这才造就了operator[]的两种功能。还有一个细节上文在统计每种水果出现的次数的时候如果该key在map里没有就会插入新节点那插入结点的key我知道了value是多少呢答案还是在上边的那串代码里mapped_type()本质在typedef前就表示的T()就是调用的默认构造对于自定义类型比如说像int()值就是0。所以countMap[e]先返回的是map里key对应的value值0并且operator[]返回的value是传引用返回所以之后就直接改成了1。