【C++高阶】高效数据结构的探索（map&&set）

07-21 1621阅读

✨ 人生到处知何似，应似飞鸿踏雪泥 🌏

📃个人主页：island1314

🔥个人专栏：C++学习

🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞

🚀前言：

【C++深度学习】二叉搜索树的全面解析与高效实现-CSDN博客

通过之前对二叉搜索树的学习，我相信大家对set和map也应该有所了解，set就类似于二叉搜索树的K模型，而map就类似于二叉搜索树的KV模型，下面就让我们进入对其的了解吧，踏上这神秘的学习之旅

1. 关联式容器

📒在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、
forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身

📙关联式容器（Associative Containers）是C++标准模板库（STL）中的一类重要容器，主要用于存储和快速检索键值对（key-value pairs）形式的数据。这类容器与序列式容器（如vector、deque、list）的主要区别在于，关联式容器中的元素是按照特定的排序准则（通常是键的大小）进行排序的，从而允许通过键来快速查找、插入和删除元素。

关联式容器：也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高

2. 键值对

概念：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息，比如我们上一篇所提到的kv模型结构存在对应关系

SGI-STL中关于键值对的定义：(示例)

template 
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、multimap、multiset
共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列
📕关联式容器是C++ STL中一类重要的容器，它们通过键值对的形式存储数据，并支持快速的查找、插入和删除操作。常见的关联式容器包括set、multiset、map和multimap等，它们在不同的应用场景下提供了高效的解决方案

4. set && multiset

📜set的概念

概念： set 是 C++ 标准模板库 (STL) 中的一个关联式容器，它包含的元素是唯一的，且默认情况下元素会按照升序排序。set 的内部实现通常使用红黑树来保持其有序性和唯一性
- set是按照一定次序存储元素的容器
- 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的
- set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们
- set默认是升序，但是其内部默认不是按照大于比较，而是按照小于比较，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序
- set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代
  - set在底层是用二叉搜索树(红黑树)实现的
    📙set特征：
    - 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对，
    - set中插入元素时，只需要插入value即可，不需要构造键值对，但是set中可以存储键值对，实例化set时，将set中元素类型设置为pair即可。
    - set中没有重载 [] 运算符
    - 因为set要保证其有序，因此set中元素不能被直接修改，若要修改可以先删除，再插入
    - set中的元素不可以重复(因此可以使用set进行去重)
    - 使用set的迭代器遍历set中的元素，可以得到有序序列
    - set中的元素默认按照小于来比较
    - set中查找某个元素，时间复杂度为： $【C++高阶】高效数据结构的探索（map&&set）$
    - set中的元素不允许修改
    - set中的底层使用二叉搜索树(红黑树)来实现
      
      🎈multiset的概念
      
      概念：multiset 是 C++ 标准库中的一个容器，它允许存储重复的元素。与 set 不同，set 中的元素是唯一的，而 multiset 中的元素可以重复
      
      它与set唯一不同的一点就是 multiset 中的元素可以重复
      
      简单演示一下差别:
```
void test3()
{
	multiset s;
	s.insert(5); s.insert(5);
	s.insert(2); s.insert(2); s.insert(2);
	s.insert(1);
	s.insert(9);
	s.insert(7);
	//set::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout 
```