CPP标准模版库

STL标准模版库

C++的STL（Standard Template Library，标准模板库）程序库，包含了一系列容器（containers）、迭代器（iterators）、算法（algorithms）、函数对象（function objects）等模板类和函数，用于实现各种常见的数据结构和算法，为程序开发提供了高效、灵活且易于使用的工具。

STL的特点：

• 泛型编程: STL通过模板实现，使代码不依赖于特定的数据类型，大大提高了代码的通用性和复用性。
• 效率: STL组件设计精良，很多实现都针对性能进行了优化，能提供高效的内存管理和算法执行。

STL的三大核心组件：

一、vector

std::vector（向量）是C++中最常用的容器之一，是一个动态数组容器，本质是一个类模板，它提供了数组的便利性，同时又具备动态调整大小的能力。

vector通过向其后端（通过push_back方法）进行元素的添加，并且可以通过索引或迭代器进行随机访问元素。适合于需要快速访问元素且主要在容器尾部进行插入和删除操作的场景。

关键特性：

1、创建vector对象

使用std::vector容器，包含<vector>头文件。

构造函数：

std::vector<type> name;//创建一个空的vector对象
std::vector<type> name(size); //创建大小为size的vector
std::vector<type> name(size, value);//创建大小为size的vector，并且把每个元素的值都初始化为 value。

int main()
{
vector<int> v1;
vector<int> v2(10);
vector<int> v3(5, 1);
cout << "v1 size:" << v1.size() << endl;
cout << "v2 size:" << v2.size() << endl;
cout << "v3 size:" << v3.size() << endl;
return 0;
}

创建vector对象的其他方式：

std::vector vec = {初始化列表...};
或
vector vec {初始化列表...};

上两种创建方法可以省略类型：

C++11/14 → 必须写类型

C++17+ → 可以省略类型，由编译器推导

int main()
{
vector<int> v1;
vector<int> v2(10);
vector<int> v3(5, 1);
vector<int> v4 = { 100, 200 ,300 };
vector<int> v5 { 1,2,3,4,5 };
cout << "v1 size:" << v1.size() << endl;
cout << "v2 size:" << v2.size() << endl;
cout << "v3 size:" << v3.size() << endl;
cout << "v4 size:" << v4.size() << endl;
cout << "v5 size:" << v5.size() << endl;
return 0;
}

能省略类型：初始化列表 {…} 或直接给具体元素 → 编译器能从元素类型推导

不能省略类型：构造函数参数里只有数量、容量等信息 → 编译器推不出来

2、添加元素

（1）添加元素

push_back()方法用于在容器的末尾添加一个元素。

std::vector<int> vec;
vec.push_back(100);

（2）下标运算符 []

std::vector<int> vec;
vec[0] = 100;

• v[i] 不会检查 i 是否越界，如果越界会导致未定义行为。
• 使用 v.at(i) 会抛出 std::out_of_range 异常，如果越界。

3、访问元素

（1）at() 成员函数

std::vector<int> v = {1, 2, 3};
int firstElement = v.at(0); // 获取第一个元素，同时检查下标是否有效

（2）front() 和 back() 成员函数

front()返回第一个元素的引用，而back()返回最后一个元素的引用。这两种方式不需要传入下标，适用于访问vector的首尾元素。

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

int main() {
vector<int> v = {10, 20, 30, 40, 50};

// 访问第一个元素
cout << "第一个元素: " << v.front() << endl; // 10

// 访问最后一个元素
cout << "最后一个元素: " << v.back() << endl; // 50

// 修改首尾元素
v.front() = 100;
v.back() = 500;

cout << "修改后第一个元素: " << v.front() << endl; // 100
cout << "修改后最后一个元素: " << v.back() << endl; // 500

return 0;
}

• 不需要下标，代码更简洁。
• 返回的是 引用，所以可以直接修改元素。
• 如果 vector 为空，调用 front() 或 back() 会导致未定义行为（UB），需要先判断 v.empty()。

（3）下标运算符 []

下标运算符是最直接的访问元素的方式，提供随机访问。

std::vector<int> v = {1, 2, 3};
int firstElement = v[0]; // 获取第一个元素

（4） 使用范围for循环

C++11起，可以更简洁地遍历容器，无需手动管理迭代器。

for(auto& element : v) {
std::cout << element << " ";
}

4、容量大小

• size()返回当前存储在vector中的元素数量。
• capacity()返回vector当前分配的内存能容纳多少元素。容量是指vector在不需要重新分配内存的情况下可以容纳的元素数量。

int main()
{
vector<int> vec{ 10, 20, 30, 40, 50 };
cout << "size:" << vec.size() << endl;
cout << "capacity:" << vec.capacity() << endl; //5
vec.push_back(100);
cout << "capacity:" << vec.capacity() << endl; //7
}

• size() = 实际“用掉的空间”
• capacity() = 已经分配的“总空间”

5、迭代器

迭代器是访问容器元素的工具，能够遍历容器中的元素。

每个标准容器（如vector、list、map等）都定义了自己的迭代器类型，并通过成员函数begin()和end()提供对这些迭代器的访问。

例如，std::vector<int>::iterator 是一个指向整数向量的迭代器。

//迭代器是模板类型
std::vector<int> vec;
std::vector<int>::iterator iter = vec.begin();

• 每个容器都定义了自己的迭代器类型，例如：

std::vector<int>::iterator

这里的 iterator 是一个类类型，内部封装了指向元素的指针或类似机制，并实现了访问元素和移动迭代器的操作（解引用、加减、比较等）。

• 当你声明迭代器变量时，就生成了一个迭代器对象：

std::vector<int> v = {1,2,3};
std::vector<int>::iterator it = v.begin(); // it 是 iterator 类型的对象

• it 就是一个迭代器对象，指向 vector 的第一个元素
• 可以通过 *it 访问元素，通过 ++it 移动到下一个元素

begin()返回指向容器第一个元素的迭代器，end()返回指向容器末端的迭代器，即超出最后一个元素的位置。

std::vector<int>::iterator 是 vector 的迭代器类型，它本质上是一个 指向 vector 元素的对象，可以用来遍历或操作 vector 内部元素。

（1）使用迭代器

使用迭代器访问元素时，需要解引用迭代器。

std::vector<int> vec = {1, 2, 3};
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " "; // 解引用迭代器访问元素
}

• ++it 和 it++：前置和后置递增操作，使迭代器指向容器中的下一个元素
• –it 和 it–：前置和后置递减操作，使迭代器指向容器中的上一个元素
• *it：解引用操作，获取迭代器当前指向的元素的值。

或者使用C++11引入的auto关键字简化类型声明：

for(auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}

（2）使用反向迭代器

从容器的末尾向前遍历，可以使用反向迭代器。

for(auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
std::cout << *rit << " ";
}

• vec.rbegin() → 指向 最后一个元素
• vec.rend() → 指向 第一个元素的前一个位置
• 递增运算 ++rit → 在容器逻辑上 向前移动（从末尾向开头）
• 递减运算 –rit → 在容器逻辑上 向后移动（从开头向末尾）

也就是说，虽然是“逆向遍历”，但逆向迭代器的 ++ 操作是向容器前方走，符合 C++ 设计的一致性：++ 总是前进，– 总是后退。

普通迭代器：

• ++it → 从前往后
• –it → 从后往前

逆向迭代器：

• ++rit → 从后往前（逆向遍历）
• –rit → 从前往后（逆向移动）

注：

//std::cout << it << std::endl;//错
std::cout << &*it << std::endl;//地址

迭代器是一种 “行为类似指针的对象”，但不能直接用 cout 打印，需要通过解引用（ * it）获取元素值，或通过 & *it 获取元素地址。

6、插入删除元素

• insert()和erase()方法可以用于在容器的任意位置添加或删除元素，但请注意，除了在末尾进行的插入和删除，这些操作涉及元素的移动，可能导致性能下降。

（1）insert()函数

可以在指定的位置插入一个或多个元素。

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

int main() {
vector<int> v = {10, 20, 30};

// 在末尾插入元素（效率高）
v.push_back(40); // 等价于 v.insert(v.end(), 40)

// 在开头插入元素（效率低，因为要移动所有元素）
v.insert(v.begin(), 5);

// 在中间插入元素
v.insert(v.begin() + 2, 15); // 在索引2位置插入15

// 插入多个相同元素
v.insert(v.end(), 3, 50); // 在末尾插入3个50

// 遍历输出
for (auto e : v) cout << e << " ";
return 0;
}

（2）pop_back()函数

用于删除vector的最后一个元素。

#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3};
vec.pop_back(); // 删除最后一个元素
// 打印vector的内容
for (int i : vec) {
std::cout << i << ' ';
}
std::cout << std::endl;
return 0;
}

（3）erase()函数

用于删除指定位置的元素或一个范围内的元素。

// 删除开头元素
v.erase(v.begin()); // 删除第一个元素

// 删除中间元素
v.erase(v.begin() + 2); // 删除索引2的元素

// 删除一段范围
v.erase(v.begin() + 1, v.begin() + 4); // 删除索引1~3的元素（左闭右开）"[)"

• erase 函数的行为是删除 [起始迭代器，结束迭代器) 范围内的元素（即包含起始位置，不包含结束位置）

二、deque容器

std::deque（发音为 “deck”）(音标：Dɛk)，全称为 double-ended queue双端队列，是C++标准库中的另一种顺序容器，它提供了对序列两端元素的高效插入和删除操作。与std::vector相比，deque在设计上更侧重于在序列两端进行快速的插入和删除，同时也支持随机访问。

以下是关于deque容器的一些关键特点和操作：

特点：

1、创建deque

使用std::deque容器，包含<deque>头文件。

使用默认的构造函数可以创建一个空的std::deque容器，或者通过提供一个初始值列表来创建并初始化std::deque容器。

std::deque<int> emptyDeque; // 创建一个空的deque
std::deque<int> intDeque = {1, 2, 3, 4, 5}; // 创建一个包含初始元素的deque

2、添加元素

使用push_front()和push_back()成员函数在std::deque的前端和后端添加元素。

intDeque.push_front(0); // 在deque的前端添加元素0
intDeque.push_back(6); // 在deque的后端添加元素6

3、删除元素

使用pop_front()和pop_back()成员函数删除std::deque的前端和后端的元素

if (!intDeque.empty()) {
intDeque.pop_front(); // 删除deque的前端元素
intDeque.pop_back(); // 删除deque的后端元素
}

4、访问元素

使用front()和back()成员函数访问std::deque的前端和后端元素，或者使用operator[]或at()进行随机访问（通常不建议在deque上进行随机访问，效率不如vector）。

if (!intDeque.empty()) {
int frontElement = intDeque.front(); // 访问deque的前端元素
int backElement = intDeque.back(); // 访问deque的后端元素
// 注意：随机访问不是deque的强项，但在需要时可以使用
int middleElement = intDeque[intDeque.size() / 2]; // 访问中间元素（仅作为示例，不推荐）
}

5、迭代器

使用迭代器来遍历std::deque中的元素。

for (std::deque<int>::iterator it = intDeque.begin(); it != intDeque.end(); ++it) {
std::cout << *it << ' ';
}
std::cout << std::endl;

或者使用基于范围的for循环（C++11及以后）：

for (const auto& element : intDeque) {
std::cout << element << ' ';
}
std::cout << std::endl;

6、插入和删除特定位置的元素

使用insert()和erase()成员函数在std::deque的特定位置插入或删除元素。

intDeque.insert(intDeque.begin() + 2, 7); // 在索引为2的位置插入元素7
intDeque.erase(intDeque.begin() + 2); // 删除索引为2的元素

7.deque和vector的对比

std::deque 和 std::vector 都是 顺序容器（sequence container），以下是一些常用的函数：

三、list容器

std::list是一种双向链表容器，它提供了高效地在序列的任何位置进行插入和删除操作的能力。

std::list容器适用于频繁进行插入和删除操作，特别是在序列的中间位置，而对随机访问的需求不高的场景。

以下是关于std::list的几个关键特性：

• 双向链表结构：list中的每个元素都存储在独立的节点中，每个节点包含数据和两个指针，分别指向前一个节点和后一个节点，形成双向链表结构。这种结构支持插入和删除操作，但不支持随机访问。
• 动态内存管理：list在需要时动态地分配和释放内存，当插入新元素时，只需改变相邻节点的指针即可，无需移动元素，使得在序列中间插入和删除元素非常高效。
• 迭代器：由于链表的非连续内存布局，list提供了双向迭代器（而非随机访问迭代器），允许从任一方向遍历列表，但不能通过索引直接访问元素。
• 排序与合并：虽然list不支持像vector那样的随机访问迭代器，因而不能直接使用std::sort，但它提供了自己的成员函数sort()进行排序。此外，list还提供了merge()函数，可以合并两个已排序的list。
• 空间效率：相比连续内存的容器（如vector），list在插入和删除操作上更加高效，因为它不需要移动元素。但每个节点额外存储了指针，因此在内存使用上不如vector紧凑。

1、创建 list 容器

包含 <list> 头文件来使用 std::list。

创建一个空的 std::list 容器，或者用一个初始元素集来创建它：

std::list<int> emptyList; // 创建一个空的 list 容器
std::list<int> intList = {1, 2, 3, 4, 5}; // 创建一个包含初始元素的 list 容器

2、插入元素

使用 push_front、push_back 或 insert 方法添加元素：

std::list<int> myList;
myList.push_front(1); // 在列表前端插入元素 1
myList.push_back(2); // 在列表后端插入元素 2
// 使用 insert 在指定位置插入元素
auto it = myList.begin(); // 获取迭代器指向列表的第一个元素
std::advance(it, 1); // 将迭代器移动一个位置，现在指向元素 2。
myList.insert(it, 100); // 在元素 2 之前插入元素 100

• std::advance 是 C++ 标准库 <iterator> 中提供的一个工具函数，用于 让迭代器向前或向后移动指定的步数。

template <class InputIterator, class Distance> void advance(InputIterator& it, Distance n);

• it：要移动的迭代器（引用传递，会修改原迭代器）
• n：要移动的步数，可以为正（向前）或负（向后）
• 作用：将迭代器 it 向前或向后移动 n 个位置

⚠️ 注意：std::advance 并不返回新迭代器，而是 直接修改传入的迭代器。

std::advance 适用于 所有类型的迭代器（list、vector、deque 等）

如果只是向前或向后移动一两步，直接 it++ 就够

如果移动步数不固定或很大，用 std::advance 更简洁

注意：

std::list<T>容器的迭代器不支持随机访问操作，不能直接对迭代器使用算术运算符来进行位置的计算，比如 myList.begin() + 1。这是因为std::list内部是通过双向链表实现的，没有像数组那样的连续内存布局。

• list 迭代器不能像vector和deque一样 it + n，因为不支持随机访问
• 但 可以使用 it++/it– 单步移动
• 也可以用 std::advance(it, n) 一次性移动 n 步，这是官方推荐做法

it++和it+1的区别：

严格来说，it++ 不是算术运算 +1，虽然效果上看起来像“向下一个元素移动一位”。

1️⃣ it++ 的本质

• it++ 是 迭代器的自增操作，由迭代器类重载的 operator++() 实现
• 对不同类型的迭代器，它的实现方式不同：
  • vector / deque：内部是数组，it++ 实际就是指针加一（类似 ptr = ptr + 1）
  • list：内部是双向链表，it++ 实际是跳到当前节点的 next 指针所指向的节点
• 所以 it++ 表现像加一，但它 不是直接算术加法
• 它实际上是：让迭代器指向当前节点的下一个节点（沿链表的 next 指针走一步）。所以它只能单步移动，不能一次性跳 n 步，也不能写 it + n。

2️⃣ 为什么 list 不能 it + n

• list 内部不是连续内存，不能通过 it + n 跳到第 n 个元素
• 如果写 it + n，编译器会报错，因为 list 的迭代器 不支持算术运算
• 但 it++ 每次移动一个元素是合法的，因为它走的是链表指针
• it++：只能 移动一步
• std::advance(it, n)：可以 **一次性移动 n 步**，内部对 list 会循环调用 ++it或–it
• 本质上 advance 是封装了循环迭代器移动的工具函数，让代码更简洁

3️⃣ 总结对比

3、访问元素

使用迭代器或成员函数 front() 和 back() 来访问 std::list 中的元素：

std::list<int> myList = {1, 2, 3, 4, 5};
// 使用 front 和 back 访问第一个和最后一个元素
int first = myList.front(); // first 是 1
int last = myList.back(); // last 是 5
// 使用迭代器遍历所有元素
for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " "; // 输出列表中的每个元素
}
std::cout << std::endl;

4、删除元素

使用 pop_front()、pop_back() 或 erase() 方法来从 std::list 中删除元素：

std::list<int> myList = {1, 2, 3, 4, 5};
myList.pop_front(); // 删除第一个元素（现在列表是 {2, 3, 4, 5}）
myList.pop_back(); // 删除最后一个元素（现在列表是 {2, 3, 4}）
// 使用 erase 删除指定位置的元素
auto it = myList.begin();
std::advance(it, 1); // 将迭代器指向第二个元素（值为 3）
myList.erase(it); // 删除该元素（现在列表是 {2, 4}）

auto startIt = myList.begin();
std::advance(startIt, 1); // startIt 指向第二个元素（值为 4），myList = {2, 4}

auto endIt = myList.end();
std::advance(endIt, –2); // endIt 指向倒数第二个元素之前的位置，即第一个元素（值为 2），myList = {2, 4}

// 删除从 startIt 到 endIt 之间的元素（不包括 endIt 指向的元素）
myList.erase(startIt, endIt); // 此时 startIt 在 4，endIt 在 2

• startIt = 4,endIt = 2,[startIt, endIt) 是空范围 → 什么也没删除
• 区间为空或逆序 → 不删除

erase(startIt, endIt) 仅当 startIt < endIt 时才会删除元素；若 startIt == endIt，区间为空，不执行任何删除操作。

5、遍历 list

除了使用迭代器进行显式遍历之外，还可以使用 C++11 引入的基于范围的 for循环来遍历 std::list：

// 使用基于范围的 for循环遍历所有元素（C++11及以后）
for (const auto& elem : myList) {
std::cout << elem << " "; // 输出列表中的每个元素
}
std::cout << std::endl;

6、排序和反转

// 对list进行排序，从大到小
myList.sort();
// 反转list的元素顺序
myList.reverse();

#include <iostream>
#include <list>

int main() {
std::list<int> myList = {4, 1, 3, 5, 2};

std::cout << "原始列表: ";
for (auto n : myList) std::cout << n << " ";//原始列表: 4 1 3 5 2
std::cout << std::endl;

// 对list进行排序（默认升序）
myList.sort();
std::cout << "排序后（升序）: ";
for (auto n : myList) std::cout << n << " ";//排序后（升序）: 1 2 3 4 5
std::cout << std::endl;

// 自定义排序（降序）
myList.sort([](int a, int b){ return a > b; });
std::cout << "排序后（降序）: ";
for (auto n : myList) std::cout << n << " ";//排序后（降序）: 5 4 3 2 1
std::cout << std::endl;

// 反转list元素顺序
myList.reverse();
std::cout << "反转后: ";
for (auto n : myList) std::cout << n << " ";//反转后: 1 2 3 4 5
std::cout << std::endl;

return 0;
}

• myList.sort() 默认升序排列
• myList.sort(自定义比较函数) 可以实现降序或其他排序规则
• myList.reverse() 直接把元素顺序反过来
• [] 是 C++ 的 Lambda 表达式（匿名函数） 的语法标记，作用是定义一个 临时函数对象。
  • [捕获列表](参数列表) -> 返回类型 { 函数体 }
  • []：捕获列表（Capture List），用于捕获外部作用域的变量
    • 空 [] 表示 不捕获任何外部变量
    • (参数列表)：函数的参数
    • -> 返回类型：可选，指定返回类型
    • { 函数体 }：函数具体实现

总结

std::list容器因其动态内存管理和链表结构，擅长于频繁的插入和删除操作，尤其是在序列中间的操作，而不需要像vector那样移动大量元素。不支持随机访问

四、list和vector、deque的对比

✅ 总结：

• vector：像动态数组，适合随机访问，尾部操作快
• deque：像两端可扩展的数组，首尾操作都快，随机访问也可
• list：像链表，中间插入/删除快，随机访问慢