---
title: "STL 模板"
description: "从环境准备到 STL，系统学习 C++ 编程的基础知识。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# STL 模板

![](https://img.dailyup.xyz/originals/8208463145082-016f62ce-0e23-4b47-ab75-d90ccee74da0.png)

C++ 的**标准模板库 (Standard Template Library, 简称 STL)**。STL 是 C++ 标准库的一个重要组成部分，它提供了一系列通用、高效的数据结构和算法，极大地提高了 C++ 的编程效率和代码质量。

你可以把 STL 看作一个精心设计的“工具箱”，里面包含了各种常用的数据结构（比如动态数组、链表、树、哈希表）和操作这些数据结构的算法（比如排序、查找、计数）。而且这些工具是“通用”的，你可以用它们来处理不同的数据类型，甚至你自己定义的复杂对象。

在算法竞赛中，STL 也是解决问题的利器，不过这个“工具箱”的内容非常多，我们在本章节中只是介绍其中一些简单的内容。

## 模板

STL 其中的 T 是指的模板（Templates），理解模板是理解 STL 的基础，因为 STL 的所有组件（容器、算法、迭代器、函数对象）都是用模板实现的。

### 什么是模板

假设你需要编写一个函数来交换两个变量的值。如果变量是 `int` 类型，你可能会这样写：

```cpp
void swap_int(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}
```

如果变量是 `double` 类型呢？你需要再写一个几乎完全相同的函数：

```cpp
void swap_double(double& a, double& b) {
    double temp = a;
    a = b;
    b = temp;
}
```

实际也还可能交换两个 `string` 类型变量的值，也有可能要交换的这两个变量是你自定义的结构体类型。你需要为每种类型都写一个重复的函数！这显示太繁琐了，代码也冗余。

有没有办法写一种“通用”的函数，独立于具体的数据类型？

模板就是 C++ 用来实现这种需求的工具，基于模板的编程我们通常称为泛型编程（Generic Programming），这里的泛其实就可以理解为“通用”。

### 函数模板

函数模板用于创建可以处理多种数据类型的函数。

**定义函数模板**

使用 `template <typename T>`来定义函数模板。`T` 是一个**模板参数**，代表一个待定的数据类型。

对于前面的交换两个变量的值的函数，我们可以这样写：

```cpp
#include <bits/stdc++.h>
using namespace std;

// 定义一个函数模板，可以交换任意类型 T 的变量
template <typename T> // T 是一个类型参数
void swap_template(T& a, T& b) {
    T temp = a; // 使用类型参数 T
    a = b;
    b = temp;
}

int main() {
    // 这里是使用函数模板的地方
    return 0;
}
```

- `template <typename T>`：声明这是一个模板，`T` 是一个类型参数。`typename` 和 `class` 在这里是等价的。
- 在函数签名和函数体中，可以使用 `T` 来代表待定的数据类型。

**使用（实例化）函数模板**

当你调用一个函数模板时，编译器会根据你传入的实参的类型，**自动推断**出模板参数 `T` 的具体类型，然后生成（实例化）一个针对该类型的函数版本。

```cpp
#include <bits/stdc++.h>
using namespace std;

template <typename T>
void swap_new(T& a, T& b) {
  T temp = a;
  a = b;
  b = temp;
}

int main() {
  int a1 = 10, a2 = 20;
  swap_new(a1, a2); // 编译器推断 T 为 int，生成 swap_new<int>
  cout << "a1:" << a1 << ", " << "a2:" << a2 << endl;
  
  // 你也可以显式指定模板参数的类型
  // swap_new<int>(a1, a2); // 显式实例化

  double b1 = 1.1, b2 = 2.2;
  swap_new(b1, b2); // 编译器推断 T 为 double，生成 swap_new<double>
  cout << "b1:" << b1 << ", " << "b2:" << b2 << endl;

  string s1 = "hello", s2 = "world";
  swap_new(s1, s2); // 编译器推断 T 为 string，生成 swap_new<string>
  cout << "s1:" << s1 << ", " << "s2:" << s2 << endl;

  return 0;
}
```

> **注意：** 编译器只有在实际使用（调用）函数模板时才会进行实例化。如果你只定义了模板但从未使用它，编译器不会为它生成任何代码。

除了单个模板参数，C++ 还支持多个模板参数。另外，模板参数除了可以是类型，还可以是其它非类型（如整数、枚举值、指针等），这里就不一一细讲了，感兴趣的可以查阅相关资料。

### 类模板

类模板用于创建可以处理多种数据类型的类。STL 中的容器（如 `vector`, `list`, `map`）都是类模板。

**定义类模板**

使用 `template <typename T>` 或 `template <class T>` 来定义类模板。

```cpp
#include <bits/stdc++.h>
using namespace std;

// 定义一个简单的栈类模板
template <typename T> // T 是一个类型参数
class Stack {
private:
  vector<T> elements; // 使用类型参数 T 定义成员变量的类型
public:
  void push(T value) { // 使用类型参数 T 定义参数类型
    elements.push_back(value);
  }
  void pop() {
    if (!elements.empty()) {
        elements.pop_back();
    }
  }
  T top() { // 使用类型参数 T 定义返回类型
    return elements.back();
  }
  bool empty() const {
    return elements.empty();
  }
};

int main() {
  // 这里是使用类模板的地方
  return 0;
}
```

- `template <typename T>`：声明这是一个模板，`T` 是一个类型参数。
- 在类定义中，可以使用 `T` 来代表待定的数据类型。

**使用（实例化）类模板**

使用类模板时，**必须显式指定**模板参数的具体类型。编译器会根据指定的类型生成（实例化）一个针对该类型的类版本。

```cpp
#include <bits/bits/stdc++.h>
using namespace std;

template <typename T>
class Stack {
private:
  vector<T> elements;
public:
  void push(T value) { elements.push_back(value); }
  void pop() { if (!elements.empty()) elements.pop_back(); }
  T top() { return elements.back(); }
  bool empty() const { return elements.empty(); }
};

int main() {
  // 实例化一个存储 int 的 Stack 类
  Stack<int> intStack;
  intStack.push(10);
  intStack.push(20);
  cout << "Int stack top: " << intStack.top() << endl; // 输出 20

  // 实例化一个存储 string 的 Stack 类
  Stack<string> stringStack;
  stringStack.push("hello");
  stringStack.push("world");
  cout << "String stack top: " << stringStack.top() << endl; // 输出 world

  return 0;
}
```

- `Stack<int>`：显式指定模板参数 `T` 为 `int`，编译器会生成一个 `Stack<int>` 类。
- `Stack<string>`：显式指定模板参数 `T` 为 `string`，编译器会生成一个 `Stack<string>` 类。

> **注意：** 与函数模板不同，类模板的模板参数通常不能由编译器自动推断，需要显式指定（除了 C++17 引入的类模板参数推导）。

## 算法模板库常见函数

我们来看几个 STL 算法模板库 `<algorithm>` 中非常基础且常用的函数：`min`、`max`、`swap`、`sort` 。

### `min` 函数

`min` 函数用于找出两个或多个值中的**最小值**。

**示例**

```cpp
#include <bits/stdc++.h>
using namespace std;

bool cmp(const string& s1, const string& s2) {
  return s1.size() < s2.size();
}

int main() {
  int a = 10, b = 20;
  cout << min(a, b) << endl; // 输出 10

  double d1 = 3.14, d2 = 2.71;
  cout << min(d1, d2) << endl; // 输出 2.71

  string s1 = "apple", s2 = "banana";
  // 字符串按字典序比较
  cout << min(s1, s2) << endl; // 输出 apple

  // 使用自定义比较函数 (例如，按字符串长度比较)
  cout << min(s1, s2, cmp) << endl; // 输出 apple (长度 5 < 6)

  // 比较多个值 (C++11)
  cout << min({5, 2, 8, 1, 9}) << endl; // 输出 1

  return 0;
}
```


### `max` 函数

`max` 函数用于找出两个或多个值中的**最大值**。

**示例**

```cpp
#include <bits/stdc++.h>
using namespace std;

bool cmp(const string& s1, const string& s2) {
  return s1.size() < s2.size();
}

int main() {
  int a = 10, b = 20;
  cout << max(a, b) << endl; // 输出 10

  double d1 = 3.14, d2 = 2.71;
  cout << max(d1, d2) << endl; // 输出 2.71

  string s1 = "apple", s2 = "banana";
  // 字符串按字典序比较
  cout << max(s1, s2) << endl; // 输出 apple

  // 使用自定义比较函数 (例如，按字符串长度比较)
  cout << max(s1, s2, cmp) << endl; // 输出 banana (长度 5 < 6)

  // 比较多个值 (C++11)
  cout << max({5, 2, 8, 1, 9}) << endl; // 输出 1

  return 0;
}

```

### `swap` 函数


### `sort` 函数


好的，我们来详细介绍一下 C++ STL 模板库中的几个核心容器：**栈 (stack)**、**队列 (queue)**、**链表 (list)** 和**向量 (vector)**。它们是 STL 中最常用的数据结构，每种容器都有其特定的特点和适用场景。

---

## 常见容器

容器是 STL 中用来存储和管理数据的类模板。它们提供了组织数据的方式以及访问和操作数据的方法。所有 STL 容器都遵循一些共同的接口约定（比如都有 `begin()`, `end()`, `size()`, `empty()` 等成员函数），但具体实现和性能特点各不相同。

容器都是**类模板**，这意味着在使用时需要指定它们存储的数据类型，例如 `vector<int>` 表示存储整数的向量，`list<string>` 表示存储字符串的链表。

### 向量 (vector)

`vector` 是一个**动态数组**。它在内存中是**连续存储**的，类似于普通数组，但它的**大小是可变的**。当需要存储更多元素时，`vector` 会自动重新分配更大的内存空间，并将现有元素复制过去。

**`vector` 定义**

```cpp
#include <vector> // 要使用 vector，需要引入相应的头文件

// 定义一个 vector，名字是 v，未初始化
vector<int> v;

// 定义一个未初始化的 vector，然后将 vector 长度调整为 5
vector<int> v;
v.resize(5);

// 定义长度为 5 的 vector，
vector<int> v(5);

// 定义并初始化，初始化后，vector 长度为 3
vector<int> v = {1, 2, 3};
```

**`vector` 初始化**

```cpp
// 方法1 
vector<int> v= {1, 2, 4};

// 方法2
// 定义一个长度为 10 的 vector，并将里面所有元素的值设为 1
vector<int> v(10, 1);

// 方法3
vector<int> v(10);
fill(v.begin(), v.end(), 1) // 将 vector 全部填充 1
```

基本上，使用 `array` 去完成的操作，在 `vector` 中都可以完成，而且使用 `vector` 会更灵活一些。

**添加和删除元素**

```cpp
vector<int> v;
v.push_back(5); // 在 v 尾部增加元素 5
v.emplace_back(8); // 在 v 尾部增加元素 8
v.pop_back(); // 删除 v 最的一个元素
```

这里的 `emplace_back()` 是 C++ 11 标准新增加的，如果要兼容之前的版本，就使用 `push_back()`，也比较好记。11 标准以后，推荐使用 `emplace_back() `。

> `emplace_back()`，`push_back()` 的主要区别在于底层实现的机制不同。`push_back()` 在向容器尾部添加元素时，首先会创建这个元素，然后再将创建出的元素拷贝或移动到容器；而 `emplace_back` 则是直接在容器尾部创建这个元素，省去了拷贝和移动的过程。`emplace_back()` 执行效率更高一些。

**`vector` 遍历**

既然 Vector 可以看作是一种动态数组，你可以像数组那样利用循环去遍历 Vector。

```cpp
#include <iostream>
#include <vector>
using namespace std;

// vector 遍历
int main() {
    vector<int> v = {2, 1, -3, 8, -15};
    
    for (int i = 0; i < v.size(); i++) {
      cout << v[i] << " ";
    }
    
    return 0;
}
```

这里的 `v.size()` 是用来获取 Vector 的长度（也就是元素的个数），其它的操作与遍历数组是完全一样的。

> 也可以使用 `v.length()` 去获取 Vector 的长度，与 `v.size()` 是同样的效果，`v.size()` 是为了兼容 STL 容器的操作在 C++ 11 后加入的。

与数组一样，也可以直接使用 `Ranged for` 来遍历 Vector 中的所有元素。

```cpp
for (const int& i : v) {
  cout << i << " ";
}
```

**`vector` 适用场景**

*   需要频繁在末尾添加或删除元素。
*   需要快速随机访问元素。
*   元素数量不确定，需要动态调整大小。
*   作为其他容器适配器（如 `stack`, `queue`）的底层容器。


### 链表 (list)

`list` 是一个**双向链表**。每个元素都包含指向前一个元素和后一个元素的指针。元素在内存中不是连续存储的。

**特点**

*   **非连续存储：** 元素分散在内存中。
*   **快速插入/删除：** 在链表的任意位置插入或删除元素的时间复杂度是 O(1)（前提是已经有了指向该位置的迭代器）。
*   **不支持随机访问：** 不能通过下标直接访问元素，需要从头或尾遍历，访问第 n 个元素的时间复杂度是 O(n)。
*   **迭代器支持：** 提供双向迭代器。
*   **额外的内存开销：** 每个元素都需要额外的空间来存储前后指针。

**常用成员函数**

*   `list<T> l`: 默认构造一个空 list。
*   `l.push_back(value)`: 在末尾添加元素。
*   `l.push_front(value)`: 在开头添加元素。
*   `l.pop_back()`: 删除末尾元素。
*   `l.pop_front()`: 删除开头元素。
*   `l.size()`: 返回元素个数 (O(n) 或 O(1) 取决于实现，C++11 后通常是 O(1))。
*   `l.empty()`: 判断是否为空。
*   `l.begin()`: 返回指向第一个元素的迭代器。
*   `l.end()`: 返回指向最后一个元素之后位置的迭代器。
*   `l.insert(pos, value)`: 在指定位置 `pos` 前插入一个元素。
*   `l.erase(pos)`: 删除指定位置 `pos` 的元素。
*   `l.clear()`: 清空所有元素。
*   `l.sort()`: 对链表进行排序 (链表自己的成员函数，因为不支持随机访问)。

**适用场景**

*   需要频繁在链表的中间位置进行插入或删除操作。
*   不需要快速随机访问元素。

**示例**

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  list<string> words; // 声明一个 string 类型的 list

  words.push_back("world");
  words.push_front("hello"); // 在开头添加

  cout << "List elements: ";
  for (const string& word : words) {
      cout << word << " ";
  }
  cout << endl; // 输出: List elements: hello world

  auto it = words.begin();
  advance(it, 1); // 将迭代器向前移动 1 位，指向 "world"

  words.insert(it, "beautiful"); // 在 "world" 前插入 "beautiful"
  cout << "After insert: ";
  for (const string& word : words) {
      cout << word << " ";
  }
  cout << endl; // 输出: After insert: hello beautiful world

  it = words.begin();
  advance(it, 1); // 将迭代器向前移动 1 位，指向 "beautiful"
  words.erase(it); // 删除 "beautiful"
  cout << "After erase: ";
  for (const string& word : words) {
      cout << word << " ";
  }
  cout << endl; // 输出: After erase: hello world

  return 0;
}
```
###  栈 (stack)

`stack` 是一个**容器适配器**。它不是一个独立的容器，而是基于现有的底层容器（默认是 `deque`，也可以是 `vector` 或 `list`）提供了一个**后进先出 (LIFO)** 的接口。

你可以想象一个栈就是一摞盘子，你只能在最上面放盘子或拿盘子。

**特点**

*   **LIFO (Last-In, First-Out):** 最后进入的元素最先出来。
*   **接口受限：** 只提供 `push` (入栈)、`pop` (出栈)、`top` (查看栈顶元素)、`empty` (判断是否为空)、`size` (获取大小) 等操作。不能访问栈底或中间的元素。
*   **底层容器：** 默认使用 `deque` 作为底层容器，也可以指定为 `vector` 或 `list`。

**常用成员函数**

*   `stack<T> s`: 默认构造一个空栈 (底层使用 deque)。
*   `stack<T, vector<T>> s_vec`: 构造一个底层使用 vector 的栈。
*   `s.push(value)`: 将元素压入栈顶。
*   `s.pop()`: 移除栈顶元素。
*   `s.top()`: 返回栈顶元素的引用 (不移除)。
*   `s.empty()`: 判断栈是否为空。
*   `s.size()`: 返回栈中元素个数。

**适用场景**

*   需要实现后进先出逻辑的场景，例如：
    *   函数调用栈。
    *   表达式求值（中缀转后缀）。
    *   括号匹配。
    *   深度优先搜索 (DFS) 的非递归实现。

**示例**

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> myStack; // 声明一个 int 类型的栈 (底层默认 deque)

    myStack.push(10); // 入栈
    myStack.push(20);
    myStack.push(30);

    cout << "Stack elements (LIFO): ";
    while (!myStack.empty()) {
        cout << myStack.top() << " "; // 查看栈顶
        myStack.pop(); // 出栈
    }
    cout << endl; // 输出: Stack elements (LIFO): 30 20 10
    return 0;
}
```

### 队列 (queue)

`queue` 也是一个**容器适配器**。它基于现有的底层容器（默认是 `deque`，也可以是 `list`）提供了一个**先进先出 (FIFO)** 的接口。

你可以想象一个队列就是排队买票的人群，第一个排队的人最先买到票离开。

**特点**

*   **FIFO (First-In, First-Out):** 最先进入的元素最先出来。
*   **接口受限：** 只提供 `push` (入队)、`pop` (出队)、`front` (查看队头元素)、`back` (查看队尾元素)、`empty` (判断是否为空)、`size` (获取大小) 等操作。不能访问队列中间的元素。
*   **底层容器：** 默认使用 `deque` 作为底层容器，也可以指定为 `list`。

**常用成员函数**

*   `queue<T> q`: 默认构造一个空队列 (底层使用 deque)。
*   `queue<T, list<T>> q_list`: 构造一个底层使用 list 的队列。
*   `q.push(value)`: 将元素添加到队尾。
*   `q.pop()`: 移除队头元素。
*   `q.front()`: 返回队头元素的引用 (不移除)。
*   `q.back()`: 返回队尾元素的引用 (不移除)。
*   `q.empty()`: 判断队列是否为空。
*   `q.size()`: 返回队列中元素个数。

**适用场景**

*   需要实现先进先出逻辑的场景，例如：
    *   任务调度。
    *   消息队列。
    *   广度优先搜索 (BFS)。

**示例**

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<string> myQueue; // 声明一个 string 类型的队列 (底层默认 deque)

    myQueue.push("first"); // 入队
    myQueue.push("second");
    myQueue.push("third");

    cout << "Queue elements (FIFO): ";
    while (!myQueue.empty()) {
        cout << myQueue.front() << " "; // 查看队头
        myQueue.pop(); // 出队
    }
    cout << endl; // 输出: Queue elements (FIFO): first second third
    return 0;
}
```

### 如何选择合适的容器？

*   如果需要**快速随机访问**，并且主要在**末尾**进行添加/删除，选择 `vector`。
*   如果需要频繁在**任意位置**进行添加/删除，并且不需要快速随机访问，选择 `list`。
*   如果只需要实现**后进先出**的逻辑，选择 `stack`。
*   如果只需要实现**先进先出**的逻辑，选择 `queue`。

理解这些容器的底层实现和性能特点，是高效使用 STL 的关键。在解决问题时，根据数据的访问模式和操作需求，选择最合适的容器。

## 总结

本章介绍了 C++ STL 中的一些基础内容，掌握基础知识，可以帮助我们写出更简洁、高效的代码，在算法竞赛和实际开发中都能发挥重要作用。

Source: https://cppguide.xyz/basic/stl/index.mdx