新人须知
新人须知

STL 模板

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

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

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

模板

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

什么是模板

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

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

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

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

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

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

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

函数模板

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

定义函数模板

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

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

#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 的具体类型，然后生成（实例化）一个针对该类型的函数版本。

#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> 来定义类模板。

#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 来代表待定的数据类型。

使用（实例化）类模板

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

#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 函数用于找出两个或多个值中的最小值。

示例

#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 函数用于找出两个或多个值中的最大值。

示例

#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 定义

#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 初始化

// 方法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 会更灵活一些。

添加和删除元素

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。

#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 中的所有元素。

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(): 对链表进行排序 (链表自己的成员函数，因为不支持随机访问)。

适用场景

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

示例

#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) 的非递归实现。

示例

#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)。

示例

#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 中的一些基础内容，掌握基础知识，可以帮助我们写出更简洁、高效的代码，在算法竞赛和实际开发中都能发挥重要作用。

ON THIS PAGE