STL | 星光light

简介

C++ 标准模板库（Standard Template Library，STL）是一套功能强大的 C++ 模板类和函数的集合，它提供了一系列通用的、可复用的算法和数据结构。

STL 分为多个组件，包括容器（Containers）、迭代器（Iterators）、算法（Algorithms）、函数对象（Function Objects）和适配器（Adapters）等。

使用 STL 的好处:

代码复用：STL 提供了大量的通用数据结构和算法，可以减少重复编写代码的工作。
性能优化：STL 中的算法和数据结构都经过了优化，以提供最佳的性能。
泛型编程：使用模板，STL 支持泛型编程，使得算法和数据结构可以适用于任何数据类型。
易于维护：STL 的设计使得代码更加模块化，易于阅读和维护。

容器

vector

vector 是 STL 中的动态数组容器，定义在 <vector> 头文件中。

特性：

随机访问：支持随机访问，可以快速访问任意位置的元素。
动态数组：可以动态扩容，可以根据需要增加或减少元素。
连续存储：支持连续内存存储，便于与 C 风格数组交互。

std::vector<int> v;        // 空 vector
std::vector<int> v(10);    // 10 个默认值为 0 的 vector
std::vector<int> v(10, 1); // 10 个值为 1 的 vector
std::vector<int> v1(v2);   // 拷贝 vector v2
std::vector<int> v3(v2.begin(), v2.end()); // 利用范围构造函数

注：vector 的构造函数默认为空。

成员函数

push_back(const T& x)：在 vector 的末尾添加一个元素，\(O(1)\)。
pop_back()：删除 vector 的最后一个元素，\(O(1)\)。
insert(iterator pos, const T& x)：在指定位置的前面插入元素，\(O(n)\)。
insert(iterator pos, size_type n, const T& x)：在指定位置的前面插入 \(n\) 个值为 \(x\) 的元素，\(O(n)\)。
erase(iterator pos)：删除指定位置的元素，\(O(n)\)。
clear()：清空 vector，\(O(n)\)。
swap(vector& x)：交换两个 vector 的内容，大小和容量均可，\(O(1)\)。
assign(size_type n, const T& x)：将 vector 的所有元素赋值为 \(x\)，\(O(n)\)（会先清空 vector，但容量只增不减，其他 assign 同理）。
assign(iterator first, iterator last)：用 \([first, last)\) 填充 vector，\(O(n)\)。
assign({initializer_list<T> il})：将 initializer_list 的内容赋值给 vector，\(O(n)\)。

operator[]：下标访问，不检查越界，\(O(1)\)。
at(size_type n)：访问指定位置的元素，检查越界，越界时会抛出异常，\(O(1)\)。
front()：访问 vector 的第一个元素，\(O(1)\)。
back()：访问 vector 的最后一个元素，\(O(1)\)。

size()：返回 vector 的元素个数，\(O(1)\)。
empty()：判断 vector 是否为空，\(O(1)\)。
capacity()：返回 vector 的容量，\(O(1)\)。
reserve(size_type n)：增加 vector 的容量至 \(n\)。如果当前容量小于 \(n\)，无操作，\(O(n)\)。
resize(size_type n)：调整 vector 的大小，若小于容量可能会删除元素，\(O(n)\)。
shrink_to_fit()：缩减 vector 的容量到当前大小，\(O(n)\)。

begin()：返回指向 vector 第一个元素的迭代器，\(O(1)\)。
end()：返回指向 vector 最后一个元素之后的位置的迭代器，\(O(1)\)。
rbegin()：返回指向 vector 最后一个元素的逆向迭代器，\(O(1)\)。
rend()：返回指向 vector 第一个元素之前的位置的逆向迭代器，\(O(1)\)。

请注意区分容量和大小的概念，vector 实际占用的内存空间相当于容量。

容量：指的是 vector 预留的内存空间大小，可以动态增加或减少。
大小：指的是 vector 中实际存储的元素个数。

释放 vector 内存

vector<T>().swap(v)。
v.clear(), v.shrink_to_fit()。

deque

deque 是 STL 中的双端队列容器，定义在 <deque> 头文件中。

特性：

支持两端高效插入和删除。
随机访问常数较大。

成员函数

push_front(const T& x)：在 deque 的头部添加一个元素，\(O(1)\)。
push_back(const T& x)：在 deque 的尾部添加一个元素，\(O(1)\)。
pop_front()：删除 deque 的第一个元素，\(O(1)\)。
pop_back()：删除 deque 的最后一个元素，\(O(1)\)。
insert(iterator pos, const T& x)：在指定位置插入元素，\(O(n)\)。
insert(iterator pos, size_type n, const T& x)：在指定位置插入 \(n\) 个值为 \(x\) 的元素，\(O(n)\)。
erase(iterator pos)：删除指定位置的元素，\(O(n)\)。

迭代器

算法

函数对象（functional）

函数对象

类名	功能
`plus<T>`	加法
`multiplies<T>`	乘法
`divides<T>`	除法
`modulus<T>`	模运算
`negate<T>`	取负
`equal_to<T>`	等于
`not_equal_to<T>`	不等于
`greater<T>`	大于
`less<T>`	小于
`greater_equal<T>`	大于等于
`less_equal<T>`	小于等于

还有一些，可以自行查阅头文件。

int a = 10, b = 5;
int c = std::plus<int>()(a, b); // 15

vector<int> v = {1,5,3,2,4};
sort(v.begin(), v.end(), std::greater<int>()); // 降序排序

function

一个 通用函数包装器，可以保存函数指针、lambda、函数对象、成员函数指针。

int add(int a, int b) { return a + b; }

int main() {
    function<int(int,int)> f = add; // 保存函数指针
    cout << f(3,4) << endl;         // 输出 7
}

bind

一个 参数绑定器，可以将参数绑定到函数上。

#include <functional>
#include <iostream>
using namespace std;

int add(int a,int b){ return a+b; }

int main() {
    auto f = bind(add, 10, placeholders::_1); // 固定 a=10, b 为参数
    cout << f(5) << endl;                     // 输出 15
}