网站主题分析,外贸电商怎么做,上海网站建设公司兴田德润可以不,展馆展示设计公司哪家好关联式容器 在初阶阶段#xff0c;我们已经接触过STL中的部分容器#xff0c;比如#xff1a;vector、list、deque、 forward_list(C11)等#xff0c;这些容器统称为序列式容器#xff0c;因为其底层为线性序列的数据结构#xff0c;里面 存储的是元素本身。那什么是关…关联式容器 在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、 forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面 存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是 key, value 结构的 键值对在数据检索时比序列式容器效率更高 键值对 用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量 key 和 value key 代 表键值 value 表示与 key 对应的信息 。比如现在要建立一个英汉互译的字典那该字典中必然 有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应 该单词在词典中就可以找到与其对应的中文含义。 树形结构的关联式容器
根据应用场景的不桶STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结 构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列.下面一依次介绍每一个容器 set 1. set是按照一定次序存储元素的容器 2. 在set中元素的value也标识它(value就是key类型为T)并且每个 value必须是唯一的 。 set中的元素 不能在容器中修改 (元素总是const)但是可以从容器中插入或删除它们。 3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行 排序。 4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对 子集进行直接迭代。 5. set在底层是用二叉搜索树(红黑树)实现的。 注意 1. 与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放 value但在底层实际存放的是由value, value构成的键值对。 2. set中插入元素时只需要插入value即可不需要构造键值对。 3. set中的元素不可以重复(因此可以使用set进行去重)。 4. 使用set的迭代器遍历set中的元素可以得到有序序列 5. set中的元素默认按照小于来比较 6. set中查找某个元素时间复杂度为 7. set中的元素不允许修改(为什么?) 8. set中的底层使用二叉搜索树(红黑树)来实现 set的使用 set 的构造 函数声明 功能介绍 set (const Compare comp Compare(), const Allocator Allocator() ); 构造空的 set set (InputIterator first, InputIterator last, const Compare comp Compare(), const Allocator Allocator() ); 用 [first, last) 区 间中的元素构造 set set ( const setKey,Compare,Allocator x); set 的拷贝构造 set 的迭代器 函数声明 功能介绍 iterator begin() 返回 set 中起始位置元素的迭代器 iterator end() 返回 set 中最后一个元素后面的迭代器 const_iterator cbegin() const 返回 set 中起始位置元素的 const 迭代器 const_iterator cend() const 返回 set 中最后一个元素后面的 const 迭代器 reverse_iterator rbegin() 返回 set 第一个元素的反向迭代器即 end reverse_iterator rend() 返回 set 最后一个元素下一个位置的反向迭代器 即 begin const_reverse_iterator crbegin()const 返回 set 第一个元素的反向 const 迭代器即 cend const_reverse_iterator crend() const 返回 set 最后一个元素下一个位置的反向 const 迭 代器即 cbegin set 的容量 函数声明 功能介绍 bool empty ( ) const 检测 set 是否为空空返回 true 否则返回 true size_type size() const 返回 set 中有效元素的个数 set 修改操作 函数声明 功能介绍 pairiterator,bool insert ( const value_type x ) 在 set 中插入元素 x 实际插入的是 x, x 构成的 键值对如果插入成功返回 该元素在 set 中的 位置 true, 如果插入失败说明 x 在 set 中已经 存在返回 x 在 set 中的位置 false void 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 中的元素 void clear ( ) 将 set 中的元素清空 iterator find ( const key_type x ) const 返回 set 中值为 x 的元素的位置 size_type count ( const key_type x ) const 返回 set 中值为 x 的元素的个数 补充: lower_bound iterator lower_bound (const value_type val);
const_iterator lower_bound (const value_type val) const;该函数将返回一个指向不小于val的第一个元素的迭代器 upper_bound iterator upper_bound (const value_type val);
const_iterator upper_bound (const value_type val) const; 该函数将返回一个指向大于val的第一个元素的迭代器 multiset 1. multiset是按照特定顺序存储元素的容器其中元素是可以重复的。 2. 在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成 的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器 中进行修改(因为元素总是const的)但可以从容器中插入或删除。 3. 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则 进行排序。 4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭 代器遍历时会得到一个有序序列。 5. multiset底层结构为二叉搜索树(红黑树)。 注意 1. multiset中再底层中存储的是 value, value 的键值对 2. mtltiset的插入接口中只需要插入即可 3. 与set的区别是multiset中的元素可以重复set中value是唯一的 4. 使用迭代器对multiset中的元素进行遍历可以得到有序的序列 5. multiset 中的 元素不能修改 6. 在 multiset 中找某个元素时间复杂度为 7. multiset 的作用可以对元素进行排序 #include set
void TestSet()
{int array[] { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };// 注意multiset在底层实际存储的是int, int的键值对multisetint s(array, array sizeof(array)/sizeof(array[0]));for (auto e : s)cout e ;cout endl;return 0;
} map 1. map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。 2. 在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型 value_type绑定在一起为其取别名称为pair: typedef pairconst key, T value_type; 3. 在内部map中的元素总是按照键值key进行比较排序的。 4. map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。 5. map支持下标访问符即在[]中放入key就可以找到与key对应的value。 6. map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 map的使用 函数声明 功能介绍 map() 构造一个空的 map map(const map x)拷贝构造 map的迭代器 函数声明 功能介绍 begin() 和 end() begin: 首元素的位置 end 最后一个元素的下一个位置 cbegin() 和 cend() 与 begin 和 end 意义相同但 cbegin 和 cend 所指向的元素不 能修改 rbegin() 和 rend() 反向迭代器 rbegin 在 end 位置 rend 在 begin 位置其 和 -- 操作与 begin 和 end 操作移动相反 crbegin() 和 crend() 与 rbegin 和 rend 位置相同操作相同但 crbegin 和 crend 所 指向的元素不能修改 map 的容量与元素访问 函数声明 功能简介 bool empty ( ) const 检测 map 中的元素是否为空是返回 true 否则返回 false size_type size() const 返回 map 中有效元素的个数 mapped_type operator[ ] (const key_type k) 返回 key 对应的 value 问题当key不在map中时通过operator获取对应value时会发生什么问题 注意在元素访问时有一个与 operator[] 类似的操作 at()( 该函数不常用 ) 函数都是通过 key 找到与 key 对应的 value 然后返回其引用不同的是 当 key 不存在时 operator[]用默认 value与key构造键值对然后插入返回该默认value at() 函数直接抛异常 。 //pairK,V
V operator[](const K key)
{// 不管插入成功还是失败pair中iterator始终指向key所在节点的iteratorpairiterator, bool ret insert(make_pair(key, V()));iterator it ret.fisrt;return it-second;
} key存在插入失败 返回 -- pair存在的key所在节点的迭代器false key不存在插入成功 返回 -- pair新插入key所在节点的迭代器true string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉,苹果,草莓, 苹果,草莓 };mapstring, int countMap;for (auto e : arr){countMap[e];//auto it countMap.find(e);//if (it ! countMap.end())//{// it-second;//}//else//{// //const pairstring, int val { e, 1 };// countMap.insert({ e, 1 });//}}for (auto kv : countMap){cout kv.first : kv.second endl;}cout endl; map 中元素的修改 函数声明 功能简介 pairiterator,bool insert ( const value_type x ) 在 map 中插入键值对 x 注意 x 是一个键值 对返回值也是键值对 iterator 代表新插入 元素的位置 bool 代表释放插入成功 void erase ( iterator position ) 删除 position 位置上的元素 size_type erase ( const key_type x ) 删除键值为 x 的元素 void erase ( iterator first, iterator last ) 删除 [first, last) 区间中的元素 void swap ( mapKey,T,Compare,Allocator mp ) 交换两个 map 中的元素 void clear ( ) 将 map 中的元素清空 iterator find ( const key_type x ) 在 map 中插入 key 为 x 的元素找到返回该元 素的位置的迭代器否则返回 end const_iterator find ( const key_type x ) const 在 map 中插入 key 为 x 的元素找到返回该元 素的位置的 const 迭代器否则返回 cend size_type count ( const key_type x ) const 返回 key 为 x 的键值在 map 中的个数注意 map 中 key 是唯一的因此该函数的返回值 要么为 0 要么为 1 因此也可以用该函数来 检测一个 key 是否在 map 中 mapstring, string dict;pairstring, string kv1(sort, 排序);dict.insert(kv1);dict.insert(pairstring, string(left, 左边));dict.insert(make_pair(right, 右边));dict.insert(make_pair(right, xxxx));// 隐式类型转换//pairstring, string kv2 { string, 字符串 };dict.insert({ string, 字符串 });//mapstring, string::iterator it dict.begin();auto it dict.begin();while (it ! dict.end()){// iterator key不能修改 value可以修改// const_iterator key不能修改 value不能修改//it-first x;it-second x;//cout (*it).first : (*it).second endl;cout it-first : it-second endl;//cout it.operator-()-first : it.operator-()-second endl;it;}cout endl;for (auto kv : dict){//auto [x, y] kv;cout kv.first : kv.second endl;}cout endl;/*for (auto [x, y] : dict){cout x : y endl;}cout endl;*///mapstring, string dict2 { {string, 字符串}, {left, 左边},{right, 右边} };mapstring, string dict2 { kv1, {left, 左边},{right, 右边} }; #include string
#include map
void TestMap()
{mapstring, string m;// 向map中插入元素的方式// 将键值对peach,桃子插入map中用pair直接来构造键值对m.insert(pairstring, string(peach, 桃子));// 将键值对peach,桃子插入map中用make_pair函数来构造键值对m.insert(make_pair(banan, 香蕉));// 借用operator[]向map中插入元素/*operator[]的原理是用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中如果key已经存在插入失败insert函数返回该key所在位置的迭代器如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回*/// 将apple, 插入map中插入成功返回value的引用将“苹果”赋值给该引用结果m[apple] 苹果;// key不存在时抛异常
//m.at(waterme) 水蜜桃;cout m.size() endl;// 用迭代器去遍历map中的元素可以得到一个按照key排序的序列for (auto e : m)cout e.first --- e.second endl;cout endl;// map中的键值对key一定是唯一的如果key存在将插入失败auto ret m.insert(make_pair(peach, 桃色));if (ret.second)cout peach, 桃色不在map中, 已经插入 endl;elsecout 键值为peach的元素已经存在 ret.first-first ---ret.first-second 插入失败 endl;// 删除key为apple的元素m.erase(apple);if (1 m.count(apple))cout apple还在 endl;elsecout apple被吃了 endl;
} 【总结】 1. map中的的元素是键值对 2. map中的key是唯一的并且不能修改 3. 默认按照小于的方式对key进行比较 4. map中的元素如果用迭代器去遍历可以得到一个有序的序列 5. map的底层为平衡搜索树(红黑树)查找效率比较高$O(log_2 N)$ 6. 支持[]操作符operator[]中实际进行插入查找。 multimap 1. Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key, value其中多个键值对之间的 key是可以重复的 。 2. 在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内 容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起 value_type是组合key和value的键值对: typedef pairconst Key, T value_type; 3. 在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对 key进行排序的。 4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代 器直接遍历multimap中的元素可以得到关于key有序的序列。 5. multimap在底层用二叉搜索树(红黑树)来实现。 注意multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以 重复的。 multimap中的key是可以重复的。 multimap中的元素默认将key按照小于来比较 使用时与map包含的头文件相同 相关例题
两个数组的交集I
给定两个数组 nums1 和 nums2 返回 它们的 交集 输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {// 先去重setint s1(nums1.begin(),nums1.end()); setint s2(nums2.begin(),nums2.end());// set排过序依次比较小的一定不是交集相等的是交集auto it1 s1.begin();auto it2 s2.begin();vectorint ret;while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){it1;}else if(*it2 *it1){it2;}else{ret.push_back(*it1);it1;it2;}}return ret;}
}; 前K个高频单词 给定一个单词列表 words 和一个整数 k 返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率 按字典顺序 排序。 底层结构 前面对map/multimap/set/multiset进行了简单的介绍在其文档介绍中发现这几个容器有个 共同点是其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中 插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。 AVL 树 二叉搜索树虽可以缩短查找的效率但 如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下 。因此两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右 子树高度之差的绝对值不超过 1( 需要对树中的结点进行调整 ) 即可降低树的高度从而减少平均搜索长度。 一棵 AVL 树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1 如果一棵二叉搜索树是高度平衡的它就是 AVL 树。如果它有 n 个结点其高度可保持在 搜索时间复杂度 AVL 树节点的定义 templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left; // 该节点的左孩子AVLTreeNodeK, V* _right; // 该节点的右孩子AVLTreeNodeK, V* _parent;// 该节点的父亲pairK, V _kv;int _bf; // 该节点的平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr),_kv(kv),_bf(0){}
}; AVL树的插入 AVL 树就是在二叉搜索树的基础上引入了平衡因子因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步 1. 按照二叉搜索树的方式插入新节点 2. 调整节点的平衡因子 1. 先按照二叉搜索树的规则将节点插入到AVL树中 2. 新节点插入后AVL树的平衡性可能会遭到破坏此时就需要更新平衡因子并检测是否破坏了AVL树的平衡性 Cur插入后Parent的平衡因子一定需要调整 在插入之前Parent的平衡因子分为三种情况-10, 1, 分以下两种情况 1. 如果Cur插入到Parent的左侧只需给Parent的平衡因子-1即可 2. 如果Cur插入到Parent的右侧只需给Parent的平衡因子1即可 此时Parent的平衡因子可能有三种情况0正负1 正负2 1. 如果Parent的平衡因子为0说明插入之前Parent的平衡因子为正负1插入后被调整 成0此时满足AVL树的性质插入成功 2. 如果Parent的平衡因子为正负1说明插入前Parent的平衡因子一定为0插入后被更 新成正负1此时以pParent为根的树的高度增加需要继续向上更新 3. 如果Parent的平衡因子为正负2则Parent的平衡因子违反平衡树的性质需要对其进 行旋转处理 AVL树的旋转 如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构 使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种 1. 新节点插入较高左子树的左侧 --- 左左右单旋 上图在插入前AVL树是平衡的新节点插入到30的左子树中30左子树增加了一层导致以60为根的二叉树不平衡要让60平衡只能将60左子树的高度减少一层右子树增加一层即将左子树往上提这样60转下来因为60比30大只能将其放在30的右子树而如果30有右子树右子树根的值一定大于30小于60只能将其放在60的左子树旋转完成后更新节点的平衡因子即可。在旋转过程中 有以下几种情况需要考虑 1. 30节点的右孩子可能存在也可能不存在 2. 60可能是根节点也可能是子树 如果是根节点旋转完成后要更新根节点 如果是子树可能是某个节点的左子树也可能是右子树 2. 新节点插入较高右子树的右侧---右右左单旋 3. 新节点插入较高左子树的右侧 --- 左右先左单旋再右单旋 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再 考虑平衡因子的更新。 4. 新节点插入较高右子树的左侧 --- 右左先右单旋再左单旋 总结 假如以Parent为根的子树不平衡即Parent的平衡因子为2或者-2分以下情况考虑 1. Parent的平衡因子为2说明Parent的右子树高设Parent的右子树的根为SubR 当SubR的平衡因子为1时执行左单旋 当SubR的平衡因子为-1时执行右左双旋 2. Parent的平衡因子为-2说明Parent的左子树高设Parent的左子树的根为SubL 当SubL的平衡因子为-1是执行右单旋 当SubL的平衡因子为1时执行左右双旋 旋转完成后原Parent为根的子树个高度降低已经平衡不需要再向上更新。 templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; // balance factorAVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr),_kv(kv),_bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:// logNbool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//...// 更新平衡因子while (parent){if (cur parent-_left){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){RotateR(parent);}else if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf 2 cur-_bf -1){}else if (parent-_bf -2 cur-_bf 1){}break;}else{// 理论而言不可能出现这个情况assert(false);}}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout endl;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if(subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}parent-_bf subL-_bf 0;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root){_root subR;_root-_parent nullptr;}else{if (ppNode-_right parent){ppNode-_right subR;}else{ppNode-_left subR;}subR-_parent ppNode;}parent-_bf subR-_bf 0;}void RotateRL(Node* parent){RotateR(parent-_right);RotateL(parent);}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}
private:Node* _root nullptr;
};
