文章详细介绍了四种常用的关联式容器：Map、Multimap、Set、MultiSet。每种容器的核心特点、复杂度分析以及代码示例均清晰明了。

在开始内容前需要明白，这四种容器的实现的核心均为红黑树，这是一种实现极其复杂的数据结构。

能手搓红黑树并进行实际应用的一定是大咖级别。为了清晰明了的学 习，将不会过于深入。

所以本文章的深度不会太大，更关心他们是什么，有什么用。
具体用法——C++Map、Set

知识点

先看名字，既然是关联式容器，那么该数据结构侧重的是谁和谁有关系。 实际上浅显的说，关联容器是为了达到里面有没有，我要访问的是谁，它和谁有关系这一目标。 共有四种:

• Map
• Multimap
• Set
• MultiSet

给大家简单举个例子

• 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，每种容器都有其独特的用途和优势。