做网站公司联系方式页面,个人网银登录入口,个人网站作品欣赏,创建网站向导和模板set和map基础#xff1a;【C进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客
前言#xff1a; 在上篇的学习中#xff0c;我们已经学习了如何使用C语言来实现二叉搜索树#xff0c;在C中#xff0c;我们是有现成的封装好的类模板来实现二叉搜索树…set和map基础【C进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客
前言 在上篇的学习中我们已经学习了如何使用C语言来实现二叉搜索树在C中我们是有现成的封装好的类模板来实现二叉搜索树的——set和map,这也是我们今天要讲的重点 目录 一、容器
二、set和multiset
一、set与multiset概述
二、set与multiset的基本操作
三、高级特性
四、set与multiset的选择
三、map和multimap
1. map与multimap的区别
2. map与multimap的使用场景
3. 基本操作
4. 注意事项
5. 示例代码
四、总结 一、容器 在前面我们经常提到容器这个东西比如stack、queue等许多类模板都称之为容器其实今天要讲的set和map也是容器的一种容器这个东西我会在下一章进行单独讲解有兴趣的可以关注一下 二、set和multiset
在C标准模板库STL中set和multiset是两种关联容器它们在处理有序集合数据时非常有用。
一、set与multiset概述 set 是一种关联容器它存储唯一不重复的元素并且这些元素会根据特定的排序规则自动排序。set内部通常采用红黑树实现保证了元素的对数时间复杂度的插入、删除和查找操作。 multiset 与set类似但它允许存储重复的元素。multiset同样基于红黑树实现其操作的时间复杂度特性与set相同。 二、set与multiset的基本操作
在使用set或multiset之前需要包含相应的头文件
#include set
#include multiset
以下是一些基本操作
构造函数
setT s; // 默认构造函数
multisetT ms; // 默认构造函数
// 可以通过比较函数和分配器进行自定义构造
插入元素
s.insert(key); // set插入元素
ms.insert(key); // multiset插入元素 insert 方法用于向set或multiset中添加元素如果插入成功set 的insert方法返回pairiterator, bool这个东西后面会讲其中bool指示是否插入成功。multiset 的insert方法返回指向插入元素的迭代器。 删除元素
s.erase(key); // 删除特定元素set
ms.erase(key); // 删除特定元素multiset
// 删除操作在multiset中会删除所有匹配的元素
查找元素
auto it s.find(key); // 查找元素set
auto it ms.find(key); // 查找元素multiset
// find返回指向元素的迭代器如果未找到则返回end()
统计元素个数
s.count(key); // set中元素个数总是1或0
ms.count(key); // multiset中元素个数可能是大于0的整数
大小和容量
s.size(); // 返回元素数量
ms.size(); // 返回元素数量
s.empty(); // 判断是否为空
ms.empty(); // 判断是否为空
三、高级特性
迭代器 set和multiset都提供迭代器支持前向和后向遍历。 for (auto it s.begin(); it ! s.end(); it) {// 遍历set中的元素
}
排序规则 默认情况下set和multiset使用小于操作符进行排序但可以通过自定义比较函数来改变排序规则。 struct CustomCompare {bool operator()(const T a, const T b) const {// 自定义比较逻辑}
};
setT, CustomCompare s; // 使用自定义比较函数
multisetT, CustomCompare ms; // 使用自定义比较函数
性能考虑 由于set和multiset基于二叉搜索树实现它们的插入、删除和查找操作通常具有O(log n)的时间复杂度。 四、set与multiset的选择 选择使用set还是multiset取决于是否需要存储重复元素。如果需要存储唯一的元素集合则应该使用set。如果允许集合中存在重复元素那么应该选择multiset。 三、map和multimap
在C的STL标准模板库中map和multimap是两种关联容器它们用于存储键值对。这些容器使用红黑树作为底层数据结构以确保高效的插入、查找和删除操作。
1. map与multimap的区别 唯一性map存储的是唯一键值对即每个键只能对应一个值。而multimap允许相同的键对应多个值提供了一种更灵活的数据存储方式。排序两者都按照键的自然顺序进行排序通常为升序。可以通过自定义比较函数来改变排序规则。 2. map与multimap的使用场景 map通常用于需要确保键的唯一性且需要对键进行排序的场景。例如统计不同类别的数据数量、实现字典等。multimap则适用于需要处理多个值与相同键关联的场景如记录用户在不同时间段的登录记录。 3. 基本操作
下面这些操作与上面set和multiset的操作基本一致就不再写了 构造与初始化可以通过构造函数直接初始化map或multimap也可以使用std::make_map或std::make_multimap辅助函数。自定义排序可以通过传递比较函数来实现。插入与删除使用insert方法插入键值对erase方法删除键值对。erase方法还可以用于删除指定范围内的元素。查找find方法用于查找键值对返回指向匹配元素的迭代器lower_bound和upper_bound方法用于查找键的范围适用于处理多个相同键的值。 4. 注意事项 迭代器的失效删除元素后所有指向被删除元素的迭代器都会失效。在迭代时需要确保迭代器的有效性。键的类型键的类型必须支持比较操作通常需要有定义的比较运算符或提供一个比较函数。性能插入、查找和删除操作的时间复杂度为O(log n)基于红黑树的高效性。值类型值的类型可以是任何类型但通常选择有意义的数据类型如整型、浮点型或字符串等。 5. 示例代码
#include iostream
#include map
#include string
using namespace std;int main() {// 使用map存储唯一键值对mapstring, int fruitCounts {{apple, 10},{banana, 15},{cherry, 5}};// 使用multimap存储多个值与相同键关联multimapstring, int logins {{Alice, 1001},{Bob, 2001},{Alice, 1003}};// 查找和打印map中的元素auto it fruitCounts.find(banana);if (it ! fruitCounts.end()) {cout Found banana: it-second endl;}// 查找和打印multimap中的元素auto range logins.equal_range(Alice);for (auto it range.first; it ! range.second; it) {cout Login for Alice: it-second endl;}return 0;
}
运行结果 四、总结 以上就是C中set和map的全部内容其实底层逻辑就是二叉搜索树或者准确来说叫红黑树其中有一些小的知识点会在下一节再提一下 感谢各位大佬观看创作不易还请各位大佬点赞支持一下
