陵县网站建设,免费自建商城网站,怎么设计logo图片,做一个公司的网站应做哪些准备文章目录一、关联式容器与键值对1、关联式容器2、键值对 pair3、树形结构的关联式容器二、set1、set 的介绍2、set 的使用三、multiset四、map1、map 的介绍2、map 的使用五、multimap一、关联式容器与键值对
1、关联式容器
在C初阶的时候#xff0c;我们已经接触了 STL 中的…
文章目录一、关联式容器与键值对1、关联式容器2、键值对 pair3、树形结构的关联式容器二、set1、set 的介绍2、set 的使用三、multiset四、map1、map 的介绍2、map 的使用五、multimap一、关联式容器与键值对
1、关联式容器
在C初阶的时候我们已经接触了 STL 中的部分容器并进行了模拟实现比如 vector、list、stack、queue 等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身
同样关联式容器也是用来存储数据的但与序列式容器不同的是关联式容器里面存储的是 key, value 结构的键值对因此在数据检索时比序列式容器效率更高。
2、键值对 pair
键值对是用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量 – key 和 value其中 key 代表键值value 代表与 key 对应的信息。
我们在上一节学习二叉搜索树的时候提到的 KV 模型 (key-value 模型) 中的 KV 其实就是键值对我们可以用上一节中提到的英汉互译的例子来理解 key-value 键值对 – 现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。
STL 中键值对的定义如下(SGI 版本)
template class T1, class T2
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first; //keyT2 second; //valuepair() : first(T1()), second(T2()) //默认构造{}pair(const T1 a, const T2 b) : first(a), second(b){}
};可以看到C 中的键值对是通过 pair 类来表示的pair 类中的 first 就是键值 keysecond 就是 key 对应的信息 value那么以后我们在设计 KV 模型的容器时只需要在容器/容器的每一个节点中定义一个 pair 对象即可
这里有的同学可能会有疑问为什么不直接在容器中定义 key 和 value 变量而是将 key、value 合并到 pair 中整体作为一个类型来使用呢这是因为 C 一次只能返回一个值如果我们将 key 和 value 单独定义在容器中那么我们就无法同时返回 key 和 value而如果我们将 key、value 定义到另一个类中那我们就可以直接返回 pair然后再到 pair 中分别去取 first 和 second 即可。
make_pair 函数
由于 pair 是类模板所以我们通常是以 显式实例化 匿名对象 的方式来进行使用但是由于显式实例化比较麻烦所以 C 还提供了 make_pair 函数其定义如下
template class T1, class T2
pairT1, T2 make_pair(T1 x, T2 y)
{return (pairT1, T2(x, y));
}如上make_pair 返回的是一个 pair 的匿名对象匿名对象会自动调用 pair 的默认构造完成初始化但由于 make_pair 是一个函数模板所以模板参数的类型可以根据实参来自动推导完成隐式实例化这样我们就不用每次都显式指明参数类型了。
注由于 make_pair 使用起来比 pair 方便很多所以我们一般都是直接使用 make_pair而不使用 pair。
3、树形结构的关联式容器
根据应用场景的不同STL 总共实现了两种不同结构的关联式容器 – 树型结构与哈希结构树型结构的关联式容器主要有四种 – map、set、multimap、multiset这四种容器的共同点是使用平衡二叉搜索树作为其底层结构容器中的元素是一个有序的序列本文将介绍这四个容器的使用。 二、set
1、set 的介绍
set 是按照一定次序存储元素的容器其底层是一棵平衡二叉搜索树由于二叉搜索树的每个节点的值满足左孩子 根 右孩子并且二叉搜索树中没有重复的节点所以 set 可以用来排序、去重和查找同时由于这是一棵平衡树所以 set 查找的时间复杂度为 O(logN)效率非常高
同时set 是一种 K模型 的容器也就是说set 中只有键值 key而没有对应的 value并且每个 key 都是唯一的set 中的元素也不允许修改因为这可能会破坏搜索树的结构但是 set 允许插入和删除。
总结
set 是K模型的容器所以 set 中插入元素时只需要插入 key 即可不需要构造键值对set中的元素不可以重复因此可以使用set进行去重由于 set 底层是搜索树所以使用 set 的迭代器遍历 set 中的元素可以得到有序序列即 set 可以用来排序set 默认使用的仿函数为 less所以 set 中的元素默认按照小于来比较由于 set 底层是平衡树搜索树所以 set 中查找某个元素时间复杂度为 O(logN)set 中的元素不允许修改因为这可能破坏搜索树的结构set 中的底层使用平衡二叉搜索树 (红黑树) 来实现。
注可能有的同学对 O(logN) 的时间复杂度没有什么具体的概念那么我们可以列举一组数据大家就很清楚了set 从1000个数据找查找某个数据最多找10次从100万个数据中找某一个数据最多找20次从10亿个数据中找某一个数据最多找30次换一种说法如果以身份证号作为 key 值存入 set 中 (假设内存足够)那么我们从地球所有人类中查找某一个身份证号对应的人时最多只用找 31 次相信现在大家对 O(logN) 是什么量级的存在已经有了很清楚的认识了。
2、set 的使用
构造
和传统容器一样set 也支持单个元素构造、迭代器区间构造以及拷贝构造
迭代器
迭代器也一样包括正向迭代器和反向迭代器正向和反向又分为 const 和 非const
修改
set 有如下修改操作
其中 swap 就是交换两棵树的根clear 就是释放树中的所有节点emplace 和 emplace_hint 我们放在 C11 章节中学习大家现在不用管它最重要的修改操作是 insert 和 erase
insert 支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间我们学会第一个即可插入的过程就是二叉搜索树的插入过程需要注意的是 insert 的返回值是 pair 类型pair 中第一个元素代表插入的迭代器位置第二个元素代表是否插入成功 (插入重复节点会返回 false)
erase 也有三种常用的是第一种和第二种删除指定键值的数据和删除指定迭代器位置的数据
操作
set 还有一些其他操作相关的函数
其中比较重要的只有 find由于 set 中不允许出现相同的 key因此在 set 中 count 函数的返回值只有1/0可以说没有什么价值set 中定义 count 主要是因为 count 在 multiset 中有作用这里是为了保持一致lower_bound 和 upper_bound 是得到一个左闭右开的迭代器区间然后我们可以对这段区间进行某些操作但实际中其实没什么人用
find 的作用是在搜索树中查找 key 对应的节点然后返回节点位置的迭代器如果找不到find 会返回 end()
set 使用范例
void set_test() {// 用数组array中的元素构造setint array[] { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };setint s(array, array sizeof(array) / sizeof(array[0]));cout s.size() endl;// 正向打印set中的元素从打印结果中可以看出set可去重for (const auto e : s)cout e ;cout endl;// 使用迭代器逆向打印set中的元素for (auto it s.rbegin(); it ! s.rend(); it)cout *it ;cout endl;// 查找删除setint::iterator pos s.find(9);if (pos ! s.end())s.erase(pos);//输出key为9的节点的个数cout s.count(9) endl;
}如果大家对 set 的使用还有不清楚的地方建议查阅 set 文档set - C Reference (cplusplus.com) 三、multiset
multiset 的介绍
multiset 也是 K模型 的容器它和 set 唯一的区别在于 multiset 中允许存在重复的 key 值节点所以 multiset 可以用来排序和查找但是不能用来去重。
multiset 的使用
multiset 的使用其实和 set 也几乎一样唯一需要注意的是 find 和 count 函数 – 由于 multiset 中允许存在重复 key 值的节点所以 multiset 中 count 函数就有作用了我们可以通过 count 函数来统计同一 key 中在 multiset 中的数量
multiset 中 find 函数的使用也和 set 有所区别 – 由于 set 中没有重复的节点所以 find 时要么返回该节点位置的迭代器要么返回 end()而 multiset 中可能有重复的节点所以 find 时返回的是同一 key 值中的哪一个节点呢实际上 find 返回的是中序遍历过程中第一个匹配的节点位置的迭代器
multiset 使用范例
void multiset_test() {// 用数组array中的元素构造multisetint array[] { 1, 3, 5, 7, 3, 2, 4, 6, 8, 0, 1, 3, 5, 7, 3, 2, 4, 6, 8, 3 };multisetint s(array, array sizeof(array) / sizeof(array[0]));cout s.size() endl;// 正向打印multiset中的元素从打印结果中可以看出multiset允许重复元素的出现for (const auto e : s)cout e ;cout endl;//如果查找的key在multiset中有多个则返回中序遍历中遇到的第一个节点的迭代器multisetint::iterator pos s.find(3);while (pos ! s.end()) {cout *pos ;pos;}cout endl;// 查找删除//输出key为3的节点的个数cout s.count(3) endl;pos s.find(3);if (pos ! s.end())s.erase(pos);cout s.count(3) endl;
}如果大家对 multiset 的使用还有不清楚的地方建议查阅 multiset 文档multiset - C Reference (cplusplus.com) 四、map
1、map 的介绍
map 和 set 一样都是按照一定次序存储元素的容器其底层也是一棵平衡二叉搜索树和 set 不同的是map 是 KV模型 的容器在map 中键值 key 通常用于排序和惟一地标识元素而值 value中 用于存储与此键值 key 关联的内容键值 key 和值value的类型可以不同在 map 内部key-value 通过成员类型 pair 绑定在一起也就是我们文章开始提到的键值对
需要注意的是map 中的元素是按照键值 key 进行比较排序的而与 key 对应的 value 无关同时map 中也不允许有重复 key 值的节点map 也可用于排序、查找和去重且 map 查找的时间复杂度也为 O(logN)。
特别注意map 允许修改节点中 key 对应的 value 的值但是不允许修改 key因为这样可能会破坏搜索树的结构。
2、map 的使用
构造 迭代器 修改 修改中的重点的仍然是 insert 和 eraseswap 为交换两棵树的根clear 为释放树中的每一个节点
和 set 一样map 的 insert 也支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间我们还是学会第一个即可插入的过程就是二叉搜索树的插入过程需要注意的是 insert 的返回值是 pair 类型pair 中第一个元素代表插入的迭代器位置第二个元素代表是否插入成功 (插入重复节点会返回 false)
erase 一样也有三种常用的是第一种和第二种删除指定键值的数据和删除指定迭代器位置的数据
元素访问
需要重点注意的是map 重载了 [] 运算符其函数原型如下
//mapped_type: pair中第二个参数即first
//key_type: pair中第一个参数即second
mapped_type operator[] (const key_type k);函数定义如下
mapped_type operator[] (const key_type k)
{(*((this-insert(make_pair(k, mapped_type()))).first)).second;
}可以看到map 中 operator[] 函数的实现看起来非常复杂我们可以将它拆解一下
V operator[] (const K k)
{pairiterator, bool ret insert(make_pair(k, V()));//return *(ret.first)-second;return ret.first-second;
}可以看到operator[] 函数会先向 map 中插入 k这里插入的结果有两种 – 如果 map 中已经有与该值相等的节点则插入失败返回的 pair 中存放着该节点位置的迭代器和false如果 map 中没有与该值相等的节点则会向 map 中插 key 值等于 k 的节点该节点对应的 value 值为 V 默认构造的缺省值
然后operator[] 会取出 pair 中的迭代器 (ret.first)然后对迭代器进行解引用得到一个 pairk, v 对象最后再返回排 pair 对象中的 second 的引用即 key 对应的 value 的引用所以我们可以在函数外部直接修改 key 对应的 value 的值。
所以map 中的 operator[] 是集插入、查找、修改为一体的一个函数示例如下
注意
这里修改的是 key 对应的 value而并没有修改 key所以并没有破坏搜索树的结构我们上面拆解 operator[] 函数时之所以能将 *(ret.first)-second 改写为 ret.first-second 是因为编译器为了可读性省略了一个 - 操作符实际上应该是 ret.first--second关于这里的细节我在 list 模拟实现 中说过有兴趣的可以去看看。
操作
和 set 一样map 中有 count 函数是因为 multimap 需要count 函数这里是为了保持一致性
map 使用范例
void map_test() {mapstring, string m;//向map中插入元素的方式用pair直接来构造键值对m.insert(pairstring, string(peach, 桃子));//为了方便我们建议直接用make_pair函数来构造键值对m.insert(make_pair(banan, 香蕉));// 借用operator[]向map中插入元素operator[]的原理如下//--------------------------------------------------------------------------------------//// 用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中// 如果key已经存在插入失败insert函数返回该key所在位置的迭代器// 如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器// operator[]函数最后将insert返回值键值对中的value返回// 注意通过[]插入的键值对的value使用默认构造完成初始化我们需要通过修改[]的返回值来对其重新赋值//---------------------------------------------------------------------------------------//// 将apple, 插入map中插入成功返回value的引用将“苹果”赋值给该引用结果m[apple] 苹果;// 用迭代器去遍历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;
}如果大家对 map 的使用还有不清楚的地方建议查阅 map 使用文档map - C Reference (cplusplus.com) 五、multimap
和 set 与 multiset 的关系一样multimap 存在的意义是允许 map 中存在 key 值相同的节点multimap 与map 的区别和 multiset 与 set 的区别一样 – find 返回中序遍历中遇到的第一个节点的迭代器count 返回和 key 值相等的节点的个数 需要注意的是multimap 中并没有重载 [] 运算符因为 multimap 中的元素是可以重复的如果使用 [] 运算符会导致多个元素的 key 值相同无法确定具体访问哪一个元素。
如果大家对 multimap的使用还有不清楚的地方建议查阅 multimap文档multimap - C Reference (cplusplus.com)
