结合C++标准库进行快速开发

# 1. C++标准库简介

C++标准库是一个庞大且功能强大的库集合，它为C++编程语言提供了广泛的工具和组件。它包含了各种数据结构、算法、输入/输出流以及其他实用程序，使开发人员能够轻松高效地构建复杂的应用程序。

C++标准库由ANSI/ISO C++标准委员会维护，它确保了库在所有符合标准的C++编译器中的一致性。这使得开发人员可以放心地使用标准库，而不必担心兼容性问题。

标准库的优势包括：

- **跨平台兼容性：**C++标准库在所有符合标准的C++编译器中都可用，这使得开发人员可以轻松地跨平台移植他们的代码。
- **代码可重用性：**标准库提供了许多预先构建的组件，这可以节省开发人员编写自己的代码的时间和精力。
- **性能优化：**标准库中的组件经过高度优化，以确保高效的性能。

# 2. 容器类库

容器类库是 C++ 标准库中用于存储和组织数据的核心组件。它提供了各种容器类型，每种类型都具有不同的特性和用途。本章将深入探讨 C++ 标准库中的容器类库，重点介绍序列容器、关联容器和无序容器。

### 2.1 序列容器

序列容器是一种有序容器，其中元素按插入顺序存储。它们支持高效的元素访问和遍历。序列容器包括：

#### 2.1.1 vector

`vector` 是一个动态数组，它可以自动调整大小以容纳新元素。它提供快速元素访问（O(1)）和插入（O(1) 平均情况）。

// 创建一个 vector
vector<int> numbers;

// 添加元素
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);

// 访问元素
cout << numbers[0] << endl; // 输出 1

#### 2.1.2 deque

`deque` 是一种双端队列，它允许从两端高效地插入和删除元素。它比 `vector` 更灵活，但访问元素和插入元素的效率较低。

// 创建一个 deque
deque<int> numbers;

// 添加元素
numbers.push_front(1);
numbers.push_back(2);

// 访问元素
cout << numbers.front() << endl; // 输出 1

#### 2.1.3 list

`list` 是一种双向链表，它允许高效地插入和删除元素。它比 `vector` 和 `deque` 更灵活，但访问元素的效率较低。

// 创建一个 list
list<int> numbers;

// 添加元素
numbers.push_front(1);
numbers.push_back(2);

// 访问元素
list<int>::iterator it = numbers.begin();
cout << *it << endl; // 输出 1

### 2.2 关联容器

关联容器是一种有序容器，其中元素按键值存储。它们支持高效的元素查找和插入。关联容器包括：

#### 2.2.1 map

`map` 是一个关联数组，它将键映射到值。它提供快速元素查找（O(log n)）和插入（O(log n)）。

// 创建一个 map
map<string, int> ages;

// 添加元素
ages["John"] = 25;
ages["Mary"] = 30;

// 查找元素
cout << ages["John"] << endl; // 输出 25

#### 2.2.2 set

`set` 是一个关联集合，它存储唯一元素。它提供快速元素查找（O(log n)）和插入（O(log n)）。

// 创建一个 set
set<int> numbers;

// 添加元素
numbers.insert(1);
numbers.insert(2);

// 查找元素
cout << numbers.count(1) << endl; // 输出 1

### 2.3 无序容器

无序容器是一种无序容器，其中元素不按任何特定顺序存储。它们支持高效的元素查找和插入。无序容器包括：

#### 2.3.1 unordered_map

`unordered_map` 是一个无序关联数组，它将键映射到值。它比 `map` 更快，但元素查找和插入的效率较低（O(1) 平均情况）。

// 创建一个 unordered_map
unordered_map<string, int> ages;

// 添加元素
ages["John"] = 25;
ages["Mary"] = 30;

// 查找元素
cout << ages["John"] << endl; // 输出 25

#### 2.3.2 unordered_set

`unordered_set` 是一个无序关联集合，它存储唯一元素。它比 `set` 更快，但元素查找和插入的效率较低（O(1) 平均情况）。

// 创建一个 unordered_set
unordered_set<int> numbers;

// 添加元素
numbers.insert(1);
numbers.insert(2);

// 查找元素
cout << numbers.count(1) << endl; // 输出 1

### 容器类库比较

下表总结了不同容器类型的特性：

| 容器类型 | 有序 | 查找效率 | 插入效率 | 访问效率 |
|---|---|---|---|---|
| vector | 是 | O(1) | O(1) 平均情况 | O(1) |
| deque | 是 | O(1) | O(1) | O(1) |
| list | 是 | O(n) | O(1) | O(n) |
| map | 是 | O(log n) | O(log n) | O(log n) |
| set | 是 | O(log n) | O(log n) | O(log n) |
| unordered_map | 否 | O(1) 平均情况 | O(1) 平均情况 | O(1) |
| unordered_set | 否 | O(1) 平均情况 | O(1) 平均情况 | O(1) |

# 3. 算法类库

### 3.1 排序算法

C++标准库提供了丰富的排序算法，包括：

- `sort`：对容器中的元素进行升序排序。
- `stable_sort`：对容器中的元素进行升序排序，并保持相等元素的相对顺序。

#### 3.1.1 sort

`sort`函数原型：

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

- 参数：
- `first`：指向容器第一个元素的迭代器。
- `last`：指向容器最后一个元素的迭代器之后一个位置的迭代器。

- 逻辑分析：
`sort`函数使用快速排序算法对容器中的元素进行升序排序。快速排序算法将容器划分为两个子容器：左子容器包含小于或等于基准元素的元素，右子容器包含大于基准元素的元素。然后递归地对两个子容器进行排序。

#### 3.1.2 stable_sort

`stable_sort`函数原型：

temp