map和set1. 关联式容器在我们之前接触过的STL中的容器中比如vector、list、deque这些容器统称为序列式容器其底层为线性序列的数据结构存储的是元素本身。关联式容器存储的是key,value结构的键值对在数据检索时比序列式容器效率更高。2. 键值对用来表示一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。SGI-STL中关于键值对的定义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) {} };3. 树形结构的关联式容器STL实现了两种不同结构的管理式容器树型结构和哈希结构。其中树型结构的关联式容器主要有四种map、set、multiset、multimap。这四种容器的共同点是使用平衡搜索树即红黑树作为其底层结构容器中的元素是一个有序的序列。3.1 set3.1.1 介绍set文档介绍1. set中只放value底层实际存放的是value,value构成的键值对2. 插入元素时只需要插入value3. set中的元素不可重复可以用来去重4. set中的元素默认按照小于来比较使用迭代器遍历可以得到有序序列5. 查找元素的时间复杂度是6. set的元素不允许修改7. 底层通常用平衡二叉搜索树红黑树来实现3.1.2 使用1. 模板参数列表Tset中存放元素的类型Compare比较类型定义比较方式默认小于Allocset中元素空间的管理方式使用STL提供的空间配置器2. 构造函数声明功能介绍set (const Compare comp Compare(),const Allocator Allocator() );构造空的setset (InputIterator first, InputIterator last, const Compare comp Compare(), const Allocator Allocator() );用[first, last)区间中的元素构造setset ( const setKey,Compare,Allocator x);set的拷贝构造3. 迭代器函数声明功能介绍iterator begin()返回set中起始位置元素的迭代器iterator end()返回set中最后一个元素后面的迭代器const_iterator cbegin() const返回set中起始位置元素的const迭代器const_iterator cend() const返回set中最后一个元素后面的const迭代器reverse_iterator rbegin()返回set第一个元素的反向迭代器即endreverse_iterator rend()返回set最后一个元素下一个位置的反向迭代器即rbeginconst_reverse_iterator crbegin() const返回set最后一个元素下一个位置的反向const迭代器即crbegin4. 容量函数声明功能介绍bool empty ( ) const检测set是否为空空返回true否则返回truesize_type size() const返回set中有效元素的个数5. 修改操作函数声明功能介绍pairiterator,bool insert ( const value_type x )在set中插入元素x实际插入的是x, x构成的键值对如果插入成功返回该元素在set中的位置true,如果插入失败说明x在set中已经存在返回x在set中的位置falsevoid erase ( iterator position )删除set中position位置上的元素size_type erase ( const key_type x )删除set中值为x的元素返回删除的元素的个数void erase ( iterator first, iterator last )删除set中[first, last)区间中的元素void swap ( setKey,Compare,Allocator st );返回set第一个元素的反向迭代器即endvoid clear ( )将set中的元素清空iterator find ( const key_type x ) const返回set中值为x的元素的位置size_type count ( const key_type x ) const返回set中值为x的元素的个数3.2 map3.2.1 介绍map文档介绍1. map中存放的是键值对keyvalue2. map中的key是唯一的不能修改3. map中的元素默认按照小于的方式对键值key进行比较排序4. map允许按顺序对元素进行迭代可以得到一个有序序列5. map支持下标访问通过key访问对应的valueoperator[]中实际进行插入查找6. 底层通常用平衡二叉搜索树实现3.2.2 使用1. 模板参数列表Key键值对中key的类型T键值对中T的类型Compare比较器类型map中的元素按照key来比较默认按照小于比Alloc通过空间配置器来申请底层空间2.构造函数声明功能介绍map (const Compare comp Compare(),const Allocator Allocator() );构造空的mapmap (InputIterator first, InputIterator last, const Compare comp Compare(), const Allocator Allocator() );用[first, last)区间中的元素构造mapmap ( const mapKey,Compare,Allocator x);map的拷贝构造3. 迭代器函数声明功能介绍begin()和end()begin:首元素的位置 end最后一个元素的下一个位置cbegin()和cend()与begin和end意义相同但cbegin和cend所指向的元素不能修改rbegin()和rend()反向迭代器rbegin在end位置rend在begin位置其和--操作与begin和end操作移动相反crbegin()和crend()与rbegin和rend位置相同操作相同但crbegin和crend所指向的元素不能修改4. 容量与元素访问函数声明功能介绍bool empty ( ) const检测map中的元素是否为空是返回size_type size() const返回map中有效元素的个数mapped_type operator[] (const key_type k)返回去key对应的value5.修改操作函数声明功能介绍pairiterator,bool insert ( const value_type x )在map中插入键值对x注意x是一个键值对返回值也是键值对iterator代表新插入元素的位置bool代表释放插入成功void erase ( iterator position )删除map中position位置上的元素size_type erase ( const key_type x )删除map中值为x的元素返回删除的元素的个数void erase ( iterator first, iterator last )删除set中[first, last)区间中的元素void swap ( setKey,Compare,Allocator st );交换两个map中的元素void clear ( )将map中的元素清空iterator find ( const key_type x ) const在map中插入key为x的元素找到返回该元素的位置的迭代器否则返回endconst_iterator find ( const key_type x ) const在map中插入key为x的元素找到返回该元素的位置的const迭代器否则返回cendsize_type count ( const key_type x ) const返回key为x的键值在map中的个数注意map中key是唯一的因此该函数的返回值要么为0要么为1因此也可以用该函数来检测一个key是否在map中3.3 multisetmultiset文档介绍与set的不同mulitset的元素允许重复其余内容与set基本一致3.4 multimapmultimap文档介绍与map的不同key允许重复不支持下标访问其余内容与map基本一致4. 底层结构4.1 AVL树4.1.1 概念一棵二叉搜索树满足每个节点的左右子树高度差平衡因子的绝对值不超过1即为AVL树4.1.2 定义templateclass T struct AVLTreeNode { AVLTreeNode(const T data) : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr) , _data(data), _bf(0) {} AVLTreeNodeT* _pLeft; // 该节点的左孩子 AVLTreeNodeT* _pRight; // 该节点的右孩子 AVLTreeNodeT* _pParent; // 该节点的双亲 T _data; int _bf; // 该节点的平衡因子 };4.1.3 插入操作插入操作可分为两步1. 按照二叉搜索树的方式插入新节点2. 调整节点的平衡因子插入新节点后可能导致不平衡因此需要调整树的结构根据插入的位置不同分别有四种旋转方式1. 新节点插入较高左子树的左侧——左左右单旋2. 新节点插入较高右子树的右侧——右右左单旋3. 新节点插入较高左子树的右侧——左右先左单旋再右单旋左右双旋4. 新节点插入较高右子树的左侧——右左先右单旋再左单旋右左双旋最后需要验证是否为AVL树可分为两步1. 验证是否为二叉搜索树中序遍历是否得到一个有序队列2. 验证是否为平衡树1. 每个节点子树高度差的绝对值是否不超过12. 节点的平衡因子是否计算正确4.1.4 性能查找的时间复杂度由于需要保持平衡因此进行修改操作时性能低下4.2 红黑树4.2.1 概念一棵二叉搜索树在每个节点上增加一个存储位表示节点的颜色red或black确保没有一条路径会比其他路径长出两倍因而接近平衡即为红黑树4.2.2 性质1. 每个节点不是红色就是黑色2. 根节点时黑色3. 如果一个节点是红色则它的两个孩子节点是黑色的4. 对于每个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点5. 每个叶子节点空节点都是黑色的4.2.3 定义// 节点的颜色 enum Color{RED, BLACK}; // 红黑树节点的定义 templateclass ValueType struct RBTreeNode { RBTreeNode(const ValueType data ValueType()Color color RED) : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr) , _data(data), _color(color) {} RBTreeNodeValueType* _pLeft; // 节点的左孩子 RBTreeNodeValueType* _pRight; // 节点的右孩子 RBTreeNodeValueType* _pParent; // 节点的双亲(红黑树需要旋转为了实现简单给 出该字段) ValueType _data; // 节点的值域 Color _color; // 节点的颜色 };4.2.3 插入操作插入操作可分为两步1. 按照二叉搜索树的方式插入新节点2. 检查新节点插入后红黑树的性质是否遭到破坏新节点的颜色默认为红色当新节点的父节点颜色为红色时即违反了性质三此时需分情况讨论约定cur为当前节点p为父节点g为祖父节点u为叔叔节点情况一cur为红p为红g为黑u存在且为红解决方式将pu改为黑g改为红g作为cur继续向上调整情况二cur为红p为红g为黑u不存在或存在且为黑若p为g的左孩子cur为p的左孩子进行右单旋相反若p为g的右孩子cur为p的右孩子进行左单旋p变黑g变红情况三cur为红p为红g为黑u不存在或存在且为黑若p为g的左孩子cur为p的右孩子进行左单旋相反若p为g的右孩子cur为p的左孩子进行右单旋则转换为情况二验证1. 验证是否为二叉搜索树2. 验证是否满足红黑树的性质4.3 AVL树与红黑树的比较二者都是高效的二叉搜索树增删查改的时间复杂度都是红黑树不追求决定平衡相对而言降低了插入和旋转的次数所有性能比AVL树更优且实现相对简单4.4 红黑树的迭代器begin()和end()begin()放在红黑树中最小节点最左侧节点的位置end()放在最大节点的下一个位置即头节点的位置operator()和operator--() 找迭代器的下一个节点分两种情况情况一右子树存在找左子树中最小的节点即左子树中最小节点情况二右子树不存在向上查找直到当前节点不为其父节点的右子树特殊情况根节点没有右子树-- 找迭代器的上一个节点分三种情况情况一左子树存在找左子树中最大的节点即左子树中最右节点情况二左子树不存在向上查找直到当前节点不为其父节点的左子树情况三 当前在head位置上一个节点指向最大节点位置