关于关联容器的理解感悟
文章详细介绍了四种常用的关联式容器：Map、Multimap、Set、MultiSet。每种容器的核心特点、复杂度分析以及代码示例均清晰明了。
在开始内容前需要明白，这四种容器的实现的核心均为红黑树，这是一种实现极其复杂的数据结构。
能手搓红黑树并进行实际应用的一定是大咖级别。为了清晰明了的学 习，将不会过于深入。
所以本文章的深度不会太大，更关心他们是什么，有什么用。
具体用法——C++Map、Set
知识点
先看名字，既然是关联式容器，那么该数据结构侧重的是谁和谁有关系。 实际上浅显的说，关联容器是为了达到里面有没有，我要访问的是谁，它和谁有关系这一目标。 共有四种:
MapMultimapSetMultiSet
给大家简单举个例子
Map是一个 成绩表,例如(小明,99),(小红,99),(小蓝,100)。同一人只能有一个分数,即前者不能重复。Set是一个名单,例如(小红,小蓝,小明)。不允许重名。MultiSet是另一类名单，允许重名。Multmap允许重复，即同一人有多个分数。
现在详细说说这些内容
1. set
-
定义: 存储唯一元素的集合，不能有重复元素。
-
唯一性: set 不允许重复元素。如果你尝试插入一个已经存在的元素，它不会发生任何变化。例如，如果你有一个 set 包含 3，再插入 2，那么 set 仍然是 3。
-
复杂度:
- 插入: O(log n)
- 查找: O(log n)
- 删除: O(log n)
2. map
- 定义: 存储键值对，键是唯一的，不能有重复键。
格式为(key,value)，前者名“键”，后者为“值”。
- 键的唯一性: 在 map 中，键必须是唯一的，但值可以重复。每个键只能对应一个值。例如，你可以有多个人的年龄相同，但是每个人的名字（键）必须是唯一的：
{"Alice": 30}
{"Bob": 30}
- 复杂度:
- 插入: O(log n)
- 查找: O(log n)
- 删除: O(log n)
3. multiset
-
定义: 允许存储重复元素的集合，可以有多个相同的元素。
-
允许重复: multiset 允许存储多个相同的元素，这意味着可以插入重复的值。例如，你可以有 3，其中 1 重复了两次。适合需要记录多次出现的元素的场景。
-
复杂度:
- 插入: O(log n)
- 查找: O(log n)
- 删除: O(log n)
4. multimap
-
定义: 允许存储重复键的映射，可以有多个相同键的键值对。
-
允许重复键: 在 multimap 中，键可以重复，但每个键可以对应多个值。这意味着你可以存储相同的键，但每个键可以有不同的值。例如：
{"Fruit": "Apple"}
{"Fruit": "Banana"}
{"Fruit": "Apple"}（允许重复键）
- 复杂度:
- 插入: O(log n)
- 查找: O(log n)
- 删除: O(log n)
总结
关联容器在C++ STL中非常重要，适用于各种需要存储和查找关联数据的场景。通过理解它们的特点和复杂度，可以更有效地选择合适的容器来解决实际问题。无论是需要保证唯一性的set和map，还是允许重复的multiset和multimap，每种容器都有其独特的用途和优势。