C++容器：set与multiset的排序与查找

# 章节一：C 关联容器概述

## 1.1 关联容器介绍

关联容器是C++标准库中的一种重要容器类型，它们允许存储唯一的元素，并且能够根据元素的键值进行排序和快速查找。在C++中，有多种不同类型的关联容器，其中最常用的就是set和multiset。

关联容器与顺序容器（如vector和list）不同，顺序容器中的元素按照它们在容器中的位置进行排序，而关联容器中的元素是根据特定的键值进行排序的。关联容器的实现通常基于平衡二叉树（如红黑树），这使得它们能够高效地支持插入、删除和查找操作。

## 1.2 关联容器的特性和应用

关联容器具有以下特性和应用：

- 存储唯一的元素：关联容器不允许出现重复的元素，每个元素都必须是唯一的。这使得关联容器非常适合存储需要排重的数据。
- 排序功能：关联容器根据元素的键值进行排序，这使得元素在容器中以一定的顺序存储，便于进行有序的遍历和查找操作。
- 快速的查找：由于关联容器内部使用了高效的数据结构（如红黑树），它们可以在O(log n)的时间复杂度内进行元素的查找操作，这比顺序容器的线性查找要快得多。
- 广泛应用于算法和数据结构：关联容器在算法和数据结构领域有着广泛的应用，例如用于实现字典、索引、缓存等。

在接下来的章节中，我们将深入探讨set和multiset这两种常用的关联容器，包括它们的特点、使用场景以及排序和查找操作等。
## 章节二：理解set和multiset

在C++中，set和multiset是两种常见的关联容器。它们都允许存储唯一的元素，并且可以进行排序和查找操作。在本章中，我们将深入理解set和multiset，比较它们之间的区别，并分析它们的适用场景。
### 3. 章节三：set排序和查找操作

#### 3.1 set容器的排序原理

在C++中，`set`容器是一种基于红黑树实现的关联容器，它的特点是存储唯一的元素，并且能够自动按照元素的键值进行排序。当我们向`set`容器中添加元素时，容器会自动根据元素的值将其插入到适当的位置，以保持容器中元素的有序状态。

#include <iostream>
#include <set>

int main() {
  std::set<int> mySet;

  mySet.insert(10);
  mySet.insert(5);
  mySet.insert(8);
  mySet.insert(3);
  mySet.insert(12);

  for (int num : mySet) {
    std::cout << num << " ";
  }

  return 0;
}

输出结果：

3 5 8 10 12

在上面的例子中，我们创建了一个`set`容器，并将一些整数元素插入容器中。可以看到，最终输出的结果是按照元素的升序进行排列的。

#### 3.2 set容器中元素的插入和查找

`set`容器提供了成员函数`insert()`用于向容器中插入元素，并且可以通过调用`find()`成员函数来查找容器中是否存在指定的元素。

#include <iostream>
#include <set>

int main() {
  std::set<int> mySet;

  mySet.insert(10);
  mySet.insert(5);
  mySet.insert(8);
  mySet.insert(3);
  mySet.insert(12);

  if (mySet.find(8) != mySet.end()) {
    std::cout << "Element found in set" << std::endl;
  } else {
    std::cout << "Element not found in set" << std::endl;
  }

  return 0;
}

输出结果：

Element found in set

在上面的例子中，我们先插入一些整数元素到`set`容器中，然后使用`find()`成员函数查找是否存在值为8的元素。由于容器中存在值为8的元素，因此输出结果显示元素已经被找到。

#### 3.3 set容器中的遍历操作

我们可以使用迭代器或者范围循环语句来遍历`set`容器中的元素。

#include <iostream>
#include <set>

int main() {
  std::set<int> mySet;

  mySet.insert(10);
  mySet.insert(5);
  mySet.insert(8);
  mySet.insert(3);
  mySet.insert(12);

  // 使用迭代器遍历
  std::cout << "Using iterator: ";
  for (std::set<int>::iterator it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << " ";
  }