当前位置：首页 > news >正文

C++ STL汇总

news 2025/2/11 13:17:17

一、容器

1. vector(顺序容器)

1.1 概念

vector ：标准库的一个容器类，用于存储动态数组，和数组类似，但其大小(size)可变。

1.2 创建方式

使用默认构造函数创建一个空的 std::vector，初始大小为 0

std::vector<int> vec1; // 创建一个空的 vector

创建一个具有特定大小的 std::vector，所有元素初始化为默认值（对于基本数据类型是 0，对于类类型是默认构造的对象）

std::vector<int> vec2(10); // 创建一个大小为 10 的 vector，所有元素初始化为 0

创建一个具有特定大小的 std::vector，所有元素初始化为指定的值

std::vector<int> vec3(10, 42); // 创建一个大小为 10 的 vector，所有元素初始化为 42

使用另一个容器（如数组、列表、另一个 std::vector 等）初始化 std::vector

int arr[] = {1, 2, 3, 4, 5};
std::vector<int> vec4(arr, arr + 5); // 从数组初始化std::list<int> lst = {1, 2, 3, 4, 5};
std::vector<int> vec5(lst.begin(), lst.end()); // 从 list 初始化

使用大括号 {} 进行列表初始化。

std::vector<int> vec6 = {1, 2, 3, 4, 5}; // 列表初始化
std::vector<int> vec7{1, 2, 3, 4, 5};    // 列表初始化（C++11 及以上）

通过拷贝另一个 std::vector 来创建新的 std::vector

std::vector<int> vec8 = vec6; // 拷贝构造
std::vector<int> vec9(vec6);  // 拷贝构造

通过指定迭代器范围来初始化 std::vector

std::vector<int> vec12(vec7.begin(), vec7.end()); // 使用迭代器范围初始化

使用 std::vector::assign 方法

std::vector<int> vec14;
vec14.assign(5, 42); // 将 vector 的大小设置为 5，所有元素初始化为 42

使用 std::vector::resize 方法

std::vector<int> vec15;
vec15.resize(10, 42); // 将 vector 的大小调整为 10，新元素初始化为 42

1.3 方法

1.3.1 获取迭代器

1.3.2 容量

1.3.3 元素访问

1.3.4 修改器

1.4 vector 用法

1.4.1 遍历

（1）迭代器遍历

//迭代器：vector<int>::iterator
for (vector<int>::iterator it = arr.begin(); it != arr.end(); it++)
{cout << *it << endl;
}
//迭代器：vector<int>::reverse_iterator
for (vector<int>::reverse_iterator it = arr.rbegin(); it != arr.rend(); it++)
{cout << *it << endl;
}

（2）基于范围的for循环

for (const auto &num : arr)
{cout << num << endl;
}

1.4.2 访问元素

std::vector<int> vec {1,2,3,4,5};vec[2] = 0;
vec.at(2) = 0; // 会进行边界检查，如果越界会抛出 std::out_of_range 异常

1.4.3 容量使用

size表示当前有多少个元素，capacity是可容纳的大小。因为vector是顺序存储的，那么和数组一样，有一个初始容量，在vector里就是capacity。capacity必然大于等于size，每次扩容时会改变，具体大小和vector底层实现机制有关。

max_size是可存储的最大容量，和实际的编译器、系统有关，使用的比较少。

empty很好理解，判断vector是否为空，其实就是判断size是否等于0。clear后，size=0

resize改变size的大小，而reserve改变capacity的大小，shrink_to_fit减小capacity到size

注：扩容带来的问题。

当容器需要扩容时，通常会分配一块更大的内存空间，然后将现有元素从旧内存空间复制（或移动）到新内存空间。

一旦 vector 容器的内存被重新分配，则和 vector 容器中元素相关的所有引用、指针以及迭代器，都可能会失效，最稳妥的方法就是重新生成。

1.4.4 vector常用算法

①push_back 和 emplace_back 都是尾部插入元素

emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。对于复杂对象（如 std::string、自定义类等），emplace_back 可以避免不必要的临时对象的构造和析构，从而提高性能。

②pop_back 与 earse

使用pop_back 时，容器会调用其最后一个元素的析构函数来销毁该元素。容器的大小会自动减少1，但容器的容量（即分配的内存大小）通常不会改变（除非容器的大小减少到一定程度，触发内存的重新分配。

earse 用于从容器中移除指定位置的元素或范围内的元素。

注意迭代器失效：在调用 erase 后，返回下一个有效迭代器，指向被移除元素的迭代器以及所有指向被移除元素之后的迭代器都会失效。使用时需要注意。

for (auto it = vec.begin(); it != vec.end(); ) {if (*it == 3) { // 删除值为3的元素it = vec.erase(it); // erase 返回下一个有效迭代器} else {++it;}}

③ insert 和 emplace

insert 函数用于在容器的指定位置插入一个或多个元素，是将一个已经存在的对象复制或移动到容器中。支持多种插入方式，包括插入单个元素、插入多个相同元素、插入一个范围的元素等。

工作原理：std::vector 会在指定位置插入一个或多个元素，并将后续元素向后移动，如果插入操作导致容器的大小超过当前容量，std::vector 会自动重新分配内存，并将所有元素复制到新的内存位置。

时间复杂度：

插入单个元素的时间复杂度为 O(n)，其中 n 是插入位置之后的元素数量。

插入多个元素的时间复杂度为 O(m×n)，其中 m 是插入的元素数量，n 是插入位置之后的元素数量。

emplace 只能插入一个元素，是直接在容器分配的内存中构造对象，避免了临时对象的构造和移动。但是依然会导致元素移动，时间复杂度为O(n)其中 n 是插入位置之后的元素数量。

④ assign

assign的主要功能是清空容器中的所有现有元素，并用新的元素替换它们。时间复杂度O(n)

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.assign(3, 10); // 用 3 个值为 10 的元素替换原有元素

⑤ swap 和 clear

swap 的主要功能是交换两个对象的内容，而不改变它们的地址。时间复杂度为 O(1)，因为只需要交换两个值。

clear 用于清空容器中的所有元素。它不会释放容器所占用的内存，只是将容器的大小（size）设置为零，但容器的容量（capacity）保持不变.

对于每个元素，clear 需要调用其析构函数，因此时间复杂度与容器中的元素数量成正比.

对于基本数据类型（如 int、float 等），析构函数通常是一个空操作，因此时间复杂度接近 O(1).

2. array(顺序容器)

2.1 概念

std::array 用于表示固定大小的数组。std::array 的大小在编译时确定，一旦定义，大小不可改变；内部使用连续的内存存储元素；

2.2 创建方式

std::array<int, 5> myArray;// 默认构造，默认初始化，如int 类型初始化为0
std::array<int, 5> myArray = {1, 2, 3, 4, 5}; // 初始化列表int arr[] = {1, 2, 3, 4, 5};
std::array<int, 5> myArray(std::begin(arr), std::end(arr)); // 范围构造std::array<int, 5> originalArray = {1, 2, 3, 4, 5};
std::array<int, 5> myArray(originalArray);                  // 拷贝构造std::array<int, 5> originalArray = {1, 2, 3, 4, 5};
std::array<int, 5> myArray(std::move(originalArray));       // 移动构造

2.3 成员函数

// 1. 容量相关函数
size();              // 返回元素个数
max_size()           //返回数组可以容纳的最大元素数量（与 size() 相同）
empty()              // 检查数组是否为空// 2. 元素访问
operator[]           // 通过下标访问元素
at()                 // 下标访问元素，会进行边界检查，如果越界会抛出 std::out_of_range 异常
front()              // 返回数组的第一个元素
back()               // 返回数组的最后一个元素
data()               // 返回指向数组首元素的指针，可以用于与 C 风格的 API 交互// 3. 迭代器相关函数
begin()              // 返回指向数组第一个元素的迭代器
end()                // 返回指向数组最后一个元素之后的迭代器
rbegin()             // 返回指向数组最后一个元素的反向迭代器
rend()               // 返回指向数组第一个元素之前的反向迭代器
cbegin()             // 返回指向数组第一个元素的常量迭代器
cend()
crbegin()
crend()// 4.  其他函数
fill()               // 将所有元素设置为指定值 如：myArray.fill(10)
swap()               // 交换两个数组的内容     如：myArray.swap(anotherArray);

3. deque(顺序容器)

3.1 概念

deque C++ STL 中的一种序列容器，为双端队列，它允许在两端高效地插入和删除元素。

内部使用多个固定大小的内存块（称为“内存池”）来存储元素，这使得它在两端插入和删除时比 std::vector 更高效；元素存储在不连续的内存块中，因此不支持指针或引用的连续性；

3.2 创建方式

std::deque<int> myDeque; //默认构造，创建空的deque
std::deque<int> myDeque = {1, 2, 3, 4, 5}; // 使用初始化列表std::vector<int> vec = {1, 2, 3, 4, 5};
std::deque<int> myDeque(vec.begin(), vec.end()); // 使用范围构造std::deque<int> originalDeque = {1, 2, 3, 4, 5};
std::deque<int> myDeque(originalDeque);          //  使用拷贝构造std::deque<int> originalDeque = {1, 2, 3, 4, 5};
std::deque<int> myDeque(std::move(originalDeque)); // 使用移动构造

3.3 成员函数

size()
max_size()
empty()
resize()            调整容器的大小
shrink_to_fit()     请求减少内存分配，但不保证成功  如：myDeque.shrink_to_fit();operator[]
at()
front()
back()push_front()
push_back()         在容器的后端插入一个元素
pop_front()         删除容器前端的元素
pop_back()
insert()            在指定位置插入一个元素
erase()             删除指定位置的元素             如：myDeque.erase(myDeque.begin() + 2);begin()、end()、rbegin()、rend()、cbegin()、cend()、crbegin()、crend()clear()
swap()

插入操作的时间复杂度为 O(n)，其中 n 是插入位置到容器末尾的元素数量。这是因为插入操作可能需要移动插入点之后的所有元素。在两端插入的时间复杂度为 O(1)，因为这些操作不需要移动其他元素。

插入操作可能会触发内存分配，尤其是在容器空间不足时。std::deque 内部使用多个固定大小的内存块来存储元素，当一个内存块满时，会分配新的内存块，这可能会导致一些额外的内存管理开销。

删除操作的时间复杂度为 O(n)，其中 n 是删除位置到容器末尾的元素数量。这是因为删除操作可能需要移动删除点之后的所有元素。在两端删除的时间复杂度为 O(1)，因为这些操作不需要移动其他元素。

删除操作可能会触发内存回收，尤其是在删除大量元素后。std::deque 的内存管理机制会尝试回收不再使用的内存块，但这可能会导致一些额外的内存管理开销。

删除操作会使指向删除点及其之后的迭代器失效。

 // 遍历并删除值为 3 的元素for (auto it = dq.begin(); it != dq.end(); ) {if (*it == 3) {it = dq.erase(it); // 删除元素并返回下一个有效迭代器} else {++it; // 移动到下一个元素}}

3.4 使用场景

std::deque 提供了高效的两端操作，适用于需要频繁在两端插入和删除元素的场景。

std::deque 提供了类似数组的随机访问能力，访问任意元素的时间复杂度为 O(1)。

std::deque 的内存分配方式使得它在动态扩展时比 std::vector 更高效

3.5 注意

std::deque 的元素存储在不连续的内存块中，因此不支持指针或引用的连续性

虽然 std::deque 提供了随机访问能力，但访问速度可能略低于 std::vector，因为需要额外的内存块管理

std::deque 的动态扩展性能优于 std::vector，尤其是在两端插入和删除时

3. list与forward_list (顺序容器)

3.1 概念

二者都是 c++ 的序列容器，list 底层结构为带头的双向循环链表。

forward_list 是一个单向链表，每个节点只包含一个指向下一个节点的指针。

二者区别不大，由于是单向链表，std::forward_list 的内存占用比 std::list 更小。下面主要介绍list的使用。

【C++】list 容器最全详解（什么是list? list容器的常用接口有那些？）-CSDN博客

3.2 创建方式

std::list<int> list1; // 默认构造，空链表
std::list<int> list2(5, 10); // 构造一个包含 5 个值为 10 的元素的链表
std::list<int> list3 = {1, 2, 3, 4, 5}; // 使用初始化列表构造
std::list<int> list4(list3.begin(), list3.end()); // 从另一个容器的范围构造

3.3 方法

list1.assign(5, 10); // 用 5 个值为 10 的元素替换链表内容list1.push_front(10);  在头部插入元素
list1.push_back(20);   在尾部插入元素在指定位置插入元素
auto it = list1.begin();
std::advance(it, 2); // 移动到第三个位置
list1.insert(it, 99); // 在第三个位置插入 99插入多个元素
list1.insert(it, 3, 99); // 在指定位置插入 3 个值为 99 的元素
list1.insert(it, list2.begin(), list2.end()); // 插入另一个链表的范围list1.pop_front();     删除头部元素
list1.pop_back()       删除尾部元素删除指定位置的元素，并返回下一个元素的迭代器
auto it = list1.begin();
std::advance(it, 2); // 移动到第三个位置
list1.erase(it); // 删除第三个元素
list1.erase(it, list1.end()); // 删除从 it 到尾部的所有元素它需要遍历整个链表来查找所有值等于指定值的元素，时间复杂度为 O(n)
list1.remove(2);  // 删除所有值为 2 的元素
list1.remove_if([](int x) { return x % 2 == 0; }); // 删除所有偶数size_t size = list1.size(); // 获取大小
list1.clear();
list1.reverse(); //反转链表
list1.resize(5, 0); // 扩展链表大小到 5，新元素值为 0
list1.swap(list2); // 交换两个链表的内容
list1.merge(list2); // 合并两个已排序的链表list1.unique(); // 删除连续的重复元素(需要先排序 list1.sort();)list1.sort(); // 默认升序
list1.sort([](int a, int b) { return a > b; }); // 自定义排序规则