1.关联式容器之前接触的STL中的部分容器比如vectorlistdequeforward_list(C11)等这些统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是keyvalue结构的键值对在数据检索时比序列式容器效率更高。2.键值对用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。3.树形结构的关联式容器STL总共实现了两种不同的关联式容器树形结构与哈希结构。树形结构的关联式容器主要有四种mapsetmultimapmultiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的列。3.1 setset 中只存放 value 值且每个 value 必须唯一。set 中元素不能修改(元素是const)只可以插入删除。插入元素时只需要插入 value不需要构造键值对。set 中元素不可以重复可以使用它进行去重按小于来比较遍历即可得到有序序列。3.2 mapmap 是关联式容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在元素访问时与operator[]类似的操作at()(该函数不常用)函数都是通过key找到与key对应的value然后返回其引用不同的是当key不存在时operator[]用默认value与key构造键值对然后插入返回该默认valueat()函数直接抛异常。3.3 multiset multiset是按照特定顺序的容器其中元素可以重复的。在 multiset 中元素的value也会识别它(因为 multiset 中本身存储的就是value, value组成的键值对因此 value 本身就是 keykey 就是 value类型为 T)multiset 元素的值不能在容器中修改(因为元素总是 const)可以插入删除。set 与 multiset 的接口相同不作展示唯一区别就是可存储重复元素。3.4 multimap同上 multimap 和 map 的唯一不同是map 中 key 值唯一multimap 中 key 是可以重复的。4.底层结构map/multimap/set/multiset 其底层结构都是二叉搜索树实现的但是二叉搜索树有其缺陷假如往树中插入的元素有序便会退化为单支树时间复杂度便会退化为O(N)因此对其进行了平衡处理即二叉平衡树(AVL)。4.1 AVL树一棵AVL树或者是空树或者是左右都是AVL树、左右子树高度差(简称平衡因子)的绝对值不超过1(-1/0/1)的二叉搜索树。AVL树的旋转1新结点插入较高左子树的左侧——左左右单旋2新结点插入较高右子树的右侧——右右左单旋3新结点插入较高左子树右侧——左右先左单旋在右单旋(先旋转再考虑平衡因子更新)4新结点插入较高右子树左侧——右左先右单旋再左单旋AVL树实现#pragma once #include iostream #include assert.h using namespace std; templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _pleft; AVLTreeNodeK, V* _pright; AVLTreeNodeK, V* _parent; int _bf;//平衡因子 AVLTreeNode(const pairK, V kv) :_kv(kv) ,_pleft(nullptr) ,_pright(nullptr) ,_parent(nullptr) ,_bf(0) {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: bool Insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* parent _root; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_pright; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_pleft; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_pleft cur; } else { parent-_pright cur; } cur-_parent parent; //控制平衡 //1.新增在左parent平衡因子减减 //2.新增在右parent平衡因子加加 //3.更新后parent平衡因子 0说明parent所在子树高度不变不会影响祖先 //4.更新后parent平衡因子 -1 or 1说明parent所在子树高度变化会影响祖先需继续沿着到root的路径往上更新 //5.更新后parent平衡因子 -2 or 2说明parent所在子树高度变化且不平衡对parent所在子树进行旋转让它平衡 //更新平衡因子 while (parent)//更新到根节点结束 { if (cur parent-_pleft) { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0) { break;//结束 } else if (parent-_bf -1 || parent-_bf 1) { //继续往上更新 cur parent; parent parent-_parent; } else if (parent-_bf -2 || parent-_bf 2) { //子树不平衡了需要旋转 if (parent-_bf 2 cur-_bf 1)//左单旋 { RotateL(parent); } else if (parent-_bf -2 cur-_bf -1) { RotateR(parent); } else if (parent-_bf 2 cur-_bf -1) { RotateRL(parent); } else if (parent-_bf -2 cur-_bf 1) { RotateLR(parent); } break; } else { assert(false); } } return true; } void RotateL(Node* parent) { Node* cur parent-_pright; Node* curleft cur-_pleft; Node* pparent parent-_parent; parent-_pright curleft; if (curleft) { curleft-_parent parent; } cur-_pleft parent; parent-_parent cur; if (parent _root) { _root cur; cur-_parent nullptr; } else { if (pparent-_pleft parent) { pparent-_pleft cur; } else { pparent-_pright cur; } cur-_parent pparent; } parent-_bf cur-_bf 0; } void RotateR(Node* parent) { Node* cur parent-_pleft; Node* curright cur-_pright; Node* pparent parent-_parent; parent-_pleft curright; if (curright) { curright-_parent parent; } cur-_pright parent; parent-_parent cur; if (parent _root) { cur-_parent nullptr; _root cur; } else { if (pparent-_pleft parent) { pparent-_pleft cur; } else { pparent-_pright cur; } cur-_parent pparent; } parent-_bf cur-_bf 0; } void RotateRL(Node* parent) { Node* cur parent-_pright; Node* curleft cur-_pleft; int bf curleft-_bf; RotateR(cur); RotateL(parent); //右左双旋本质是 孙子结点左子树给祖父结点做右子树右子树给父节点做左子树自己变为根节点 if (bf 0) { parent-_bf 0; cur-_bf 0; curleft-_bf 0; } else if (bf -1) { parent-_bf 0; cur-_bf 1; curleft-_bf 0; } else if (bf 1) { parent-_bf -1; cur-_bf 0; curleft-_bf 0; } else { assert(false); } } void RotateLR(Node* parent) { Node* cur parent-_pleft; Node* curright cur-_pright; int bf curright-_bf; RotateL(cur); RotateR(parent); //左右双旋是 孙子节点左子树给父节点做右子树右子树给祖父节点做左子树自己变成根节点 if (bf 0) { parent-_bf 0; cur-_bf 0; curright-_bf 0; } else if (bf -1) { parent-_bf 1; cur-_bf 0; curright-_bf 0; } else if (bf 1) { parent-_bf 0; cur-_bf -1; curright-_bf 0; } } bool IsBalance() { return _IsBalance(_root); } bool _IsBalance(Node* root) { if (root nullptr) return true; int leftHight Height(root-_pleft); int rightHight Height(root-_pright); return abs(rightHight - leftHight) 2 _IsBalance(root-_pleft) _IsBalance(root-_pright); } int Height(Node* root) { if (root nullptr) { return 0; } int leftHight Height(root-_pleft); int rightHight Height(root-_pright); if (rightHight - leftHight ! root-_bf) { cout 平衡因子异常 root-_kv.first - root-_bf endl; return false; } return leftHight rightHight ? leftHight 1 : rightHight 1; } private: Node* _root nullptr; };4.2红黑树是一种二叉搜索树但每个结点上增加一个存储位表示结点的颜色可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因为是接近平衡的。红黑树的性质1每个结点不是黑色就是红色2根结点是黑色3如果一个结点是红色的则它两个孩子都是黑色的4对于每个结点从该结点到其所有后代叶结点的简单路径均包含相同数目的黑色结点5每个叶子结点都是黑色的(此处叶子节点指的空结点)红黑树的插入操作1按照二叉搜素树规则插入新结点2检测新结点插入后红黑树的性质是否遭到破坏因为新结点的默认颜色是红色因此如果其双亲结点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入结点的双亲结点颜色为红色时就违反了性质三不能有连续红色结点需分情况讨论。(cur 为当前结点p为父结点g为祖父结点u为叔叔结点)1cur 为红p 为红g 为黑u 存在且为红解决方式将p、u 改为黑g 改为红然后把 g 当成 cur继续向上调整。2cur 为红p 为红g 为黑u 不存在/u存在且为黑解决方式p 为 g 的左孩子cur 为 p 的左孩子则进行右单旋转相反p 为 g 的右孩子cur 为 p 的右孩子则进行左单旋最后 p、g 变色——p 变黑g 变红。3cur 为红p 为红g 为黑u 不存在/u存在且为黑解决方式p 为 g 的左孩子cur 为 p 的右孩子则针对 p 做左单旋转相反p 为g 的右孩子cur 为 p 的左孩子则针对 p 做右单旋转最后则转换成了情况2(双旋)。红黑树模拟实现 STL 中的 map 与 set(暂略)