电脑软件下载网站,国际军事最新消息今天,苏州旅游必去十大景点,备案号文章目录 C list 容器详解#xff1a;从入门到精通前言第一章#xff1a;C list 容器简介1.1 C STL 容器概述1.2 list 的特点 第二章#xff1a;list 的构造方法2.1 常见构造函数2.1.1 示例#xff1a;不同构造方法2.1.2 相关文档 第三章#xff1a;list 迭代器的使用3.1 … 文章目录 C list 容器详解从入门到精通前言第一章C list 容器简介1.1 C STL 容器概述1.2 list 的特点 第二章list 的构造方法2.1 常见构造函数2.1.1 示例不同构造方法2.1.2 相关文档 第三章list 迭代器的使用3.1 常见迭代器3.1.1 示例使用正向和反向迭代器遍历 list3.1.2 相关文档 第四章list 的容量与大小操作4.1 容量管理接口4.1.1 示例容量操作4.1.2 相关文档 第五章list 的元素访问5.1 元素访问方法5.1.1 示例访问第一个与最后一个元素5.1.2 相关文档 第六章list 的插入、删除与修改6.1 插入操作6.1.1 示例使用 push_back() 和 push_front() 插入元素6.1.2 示例使用 insert() 在指定位置插入元素6.1.3 插入元素的常见问题6.1.4 相关文档 6.2 删除操作6.2.1 示例删除 list 中的首尾元素6.2.2 示例删除指定位置的元素6.2.3 示例清空 list6.2.4 删除操作的常见问题6.2.5 相关文档 6.3 修改操作6.3.1 示例修改 list 中的首尾元素6.3.2 示例通过迭代器修改 list 中的元素6.3.3 修改操作的常见问题 第七章list 的迭代器失效问题7.1 删除操作导致的迭代器失效7.1.1 示例删除元素时正确的迭代器处理7.1.2 错误示例删除后不更新迭代器7.1.3 相关文档 第八章list 常见的其他修改操作8.1 splice() 操作8.1.1 示例使用 splice() 操作8.1.2 相关文档 8.2 merge() 操作8.2.1 示例使用 merge() 操作8.2.2 相关文档 第九章list 的排序与去重9.1 sort() 操作9.1.1 示例对 list 进行排序9.1.2 使用自定义比较函数排序 9.2 unique() 操作9.2.1 示例使用 unique() 去重9.2.2 使用自定义规则去重 第十章list 的其他操作10.1 reverse() 操作10.1.1 示例反转 list 中的元素10.1.2 相关文档 10.2 swap() 操作10.2.1 示例交换两个 list 的内容11.2.2 相关文档 10.3 remove() 操作10.3.1 示例移除指定值的元素10.3.2 相关文档 10.4 remove_if() 操作10.4.1 示例使用 remove_if() 删除符合条件的元素10.4.2 相关文档 10.5 emplace() 和 emplace_back() 操作10.5.1 示例使用 emplace() 和 emplace_back()10.5.2 相关文档 第十一章list 的内存管理11.1 shrink_to_fit() 操作 写在最后 C list 容器详解从入门到精通 欢迎讨论学习过程中有问题吗随时在评论区与我交流。你们的互动是我创作的动力 支持我如果你觉得这篇文章对你有帮助请点赞、收藏并分享给更多朋友吧 一起成长欢迎分享给更多对 C 感兴趣的小伙伴让我们共同进步 前言
C 标准模板库STL中的 list 容器是一个双向链表结构它提供了高效的插入和删除操 作。与 vector 不同list 中的元素不是连续存储的因此可以在任何位置高效插入和删除元素而无需移动其他元素。虽然它在随机访问方面不如 vector 高效但在大量的插入和删除操作场景中具有不可替代的优势。
本文将通过详细的示例代码从基础到进阶逐步讲解如何使用 C 中的 list 容器并探讨其特性与常用操作。 第一章C list 容器简介
1.1 C STL 容器概述
C 提供了丰富的标准模板库 (STL)其中包括顺序容器如 vector、deque和关联容器如 map、set。list 是一种链表结构的顺序容器它的底层实现是双向链表。这使得 list 在插入和删除操作上比 vector 更加高效但由于不支持随机访问因此访问特定位置的元素时效率较低。
1.2 list 的特点
双向链表list 底层是一个双向链表能够高效地进行插入和删除操作。不支持随机访问由于链表的结构特点list 只能顺序访问随机访问效率低下。动态增长list 不需要预留空间它会根据需要动态分配内存。
#include list
#include iostream
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};for (int val : lst) {cout val ;}return 0;
}第二章list 的构造方法
2.1 常见构造函数 C list 提供了多种构造函数允许用户根据不同需求初始化链表。 构造函数功能list()构造一个空的 listlist(size_type n, const T val)构造一个包含 n 个值为 val 的元素的 listlist(const list x)拷贝构造函数构造与 x 相同的 listlist(InputIterator first, InputIterator last)使用 [first, last) 区间内的元素构造 list
2.1.1 示例不同构造方法
#include iostream
#include list
using namespace std;int main() {listint lst1; // 空 listlistint lst2(5, 100); // 5个值为100的元素listint lst3(lst2); // 拷贝构造listint lst4 {1, 2, 3, 4, 5}; // 初始化列表for (int val : lst4) {cout val ; // 输出: 1 2 3 4 5}return 0;
}2.1.2 相关文档
C Reference: list constructor 第三章list 迭代器的使用 list 支持多种迭代器类型允许我们遍历、访问和修改链表中的元素。迭代器可以看作指向 list 中节点的指针遍历时可以用迭代器依次访问链表中的每一个节点。 3.1 常见迭代器
迭代器类型功能begin()返回指向链表第一个元素的迭代器end()返回指向链表末尾的迭代器rbegin()返回指向链表最后一个元素的反向迭代器rend()返回指向链表第一个元素之前的反向迭代器cbegin()返回常量迭代器不能修改元素cend()返回常量迭代器指向链表末尾
3.1.1 示例使用正向和反向迭代器遍历 list
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 使用正向迭代器遍历for (auto it lst.begin(); it ! lst.end(); it) {cout *it ; // 输出: 1 2 3 4 5}cout endl;// 使用反向迭代器遍历for (auto rit lst.rbegin(); rit ! lst.rend(); rit) {cout *rit ; // 输出: 5 4 3 2 1}cout endl;return 0;
}3.1.2 相关文档
C Reference: list iterator 第四章list 的容量与大小操作
4.1 容量管理接口
list 提供了常用的容量管理接口方便用户操作链表的大小和判断链表状态。
方法名功能描述empty()检测 list 是否为空size()返回 list 中元素的数量max_size()返回 list 可容纳的最大元素数resize(n)调整 list 的大小为 n
4.1.1 示例容量操作
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};cout Size: lst.size() endl; // 输出当前元素个数cout Is empty: (lst.empty() ? Yes : No) endl; // 判断是否为空lst.resize(3); // 调整大小为3保留前3个元素for (int val : lst) {cout val ; // 输出: 1 2 3}return 0;
}4.1.2 相关文档
C Reference: list size 第五章list 的元素访问
5.1 元素访问方法
list 提供了几种常用的方法用于访问链表中的元素。
方法名功能front()返回 list 的第一个元素back()返回 list 的最后一个元素
5.1.1 示例访问第一个与最后一个元素
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};cout First element: lst.front() endl; // 访问第一个元素cout Last element: lst.back() endl; // 访问最后一个元素return 0;
}5.1.2 相关文档
C Reference: list element access 第六章list 的插入、删除与修改
6.1 插入操作
list 容器提供了多种插入操作包括在前部、尾部插入元素或在指定位置插入。与 vector 不同的是list 插入时不需要移动其他元素只修改指针因此插入效率非常高。
方法名功能描述push_front()在 list 的前部插入元素push_back()在 list 的末尾插入元素insert(position, val)在指定位置插入元素
6.1.1 示例使用 push_back() 和 push_front() 插入元素
push_front() 和 push_back() 是将元素插入到链表前部和尾部的常用方法。由于 list 是双向链表头部和尾部操作的效率都非常高为 O(1)。
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3};// 在前部插入元素lst.push_front(0);// 在末尾插入元素lst.push_back(4);for (int val : lst) {cout val ; // 输出: 0 1 2 3 4}return 0;
}6.1.2 示例使用 insert() 在指定位置插入元素
insert() 用于在链表中指定位置插入元素。该方法需要提供一个迭代器指向要插入的位置。
#include iostream
#include list
using namespace std;int main() {listint lst {1, 3, 4};// 在第二个位置插入2auto it lst.begin();it;lst.insert(it, 2);for (int val : lst) {cout val ; // 输出: 1 2 3 4 }return 0;
}6.1.3 插入元素的常见问题
迭代器失效在 list 中进行插入操作时插入不会使已有迭代器失效因为 list 是双向链表插入时只修改指针。尾部插入效率在链表尾部插入元素的效率始终为 O(1)无需移动其他元素这点不同于 vector。插入到特定位置的效率虽然 insert() 操作本身是 O(1)但查找特定插入位置的时间复杂度是 O(n)这取决于你如何获取迭代器。
6.1.4 相关文档
C Reference: list insertions 6.2 删除操作
list 提供了多种删除元素的方式包括从前部和尾部删除删除指定位置的元素以及一次性清空整个链表。
方法名功能描述pop_front()删除 list 的第一个元素pop_back()删除 list 的最后一个元素erase()删除指定位置的元素clear()清空 list
6.2.1 示例删除 list 中的首尾元素
pop_front() 和 pop_back() 用于删除 list 中的第一个或最后一个元素。与插入操作类似这两种操作的时间复杂度都是 O(1)不会影响其他元素的指针。
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 删除第一个元素lst.pop_front();// 删除最后一个元素lst.pop_back();for (int val : lst) {cout val ; // 输出: 2 3 4}return 0;
}6.2.2 示例删除指定位置的元素
erase() 用于删除指定位置的元素。它需要提供一个指向该位置的迭代器。
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 查找要删除的元素auto it lst.begin();advance(it, 2); // 移动到第三个元素// 删除第三个元素lst.erase(it);for (int val : lst) {cout val ; // 输出: 1 2 4 5}return 0;
}6.2.3 示例清空 list
clear() 是一种非常彻底的清除操作它会删除 list 中的所有元素。值得注意的是clear() 仅会删除有效节点不会删除链表的头节点即 list 对象本身。
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 清空 listlst.clear();cout Size after clear: lst.size() endl; // 输出: 0cout Is list empty? (lst.empty() ? Yes : No) endl; // 输出: Yesreturn 0;
}6.2.4 删除操作的常见问题
迭代器失效在 list 中删除操作只会导致指向被删除元素的迭代器失效其他迭代器不受影响。删除后如果需要继续使用迭代器应该使用 erase() 的返回值指向下一个有效元素。clear() 是否删除头节点clear() 不会删除 list 的头节点。调用 clear() 后list 对象依然存在只是里面的所有元素被删除list 的结构保持完好。
6.2.5 相关文档
C Reference: list clearC Reference: list eraseC Reference: list pop_back 6.3 修改操作 通过迭代器或者 list 提供的访问接口用户可以直接修改链表中的元素。由于 list 不支持随机访问所以修改操作通常需要遍历元素。 方法名功能描述front()返回 list 中第一个元素back()返回 list 中最后一个元素迭代器通过迭代器访问修改元素
6.3.1 示例修改 list 中的首尾元素
通过 front() 和 back()可以分别访问并修改 list 中的第一个和最后一个元素。修改操作的时间复杂度为 O(1)。
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 修改第一个元素lst.front() 10;// 修改最后一个元素lst.back() 20;for (int val : lst) {cout val ; // 输出: 10 2 3 4 20}return 0;
}6.3.2 示例通过迭代器修改 list 中的元素
由于 list 不支持随机访问修改中间位置的元素需要通过迭代器遍历找到目标位置。
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 使用迭代器修改第三个元素auto it lst.begin();advance(it, 2); // 移动到第三个元素*it 30;for (int val : lst) {cout val ; // 输出: 1 2 30 4 5}return 0;
}6.3.3 修改操作的常见问题
效率问题由于 list 是链表结构访问中间元素时无法像 vector 一样通过下标随机访问而是必须通过迭代器进行遍历时间复杂度为 O(n)。advance() 函数用于将迭代器向前或向后移动指定的距离这是 list 中最常用的访问与修改元素方式之一。由于 list 不能通过下标随机访问迭代器的使用显得尤为重要。避免无效访问通过迭代器进行修改时确保在修改过程中没有删除操作否则迭代器可能失效导致未定义行为。 第七章list 的迭代器失效问题 list 的底层实现为双向链表因此与 vector 不同list 的插入和删除操作不会导致整体迭代器失效。具体来说 插入操作不会导致现有迭代器失效。删除操作仅导致被删除元素的迭代器失效其他迭代器不会受影响。
7.1 删除操作导致的迭代器失效
删除操作会使指向被删除元素的迭代器失效如果在删除元素后继续使用失效的迭代器将会导致程序的未定义行为。因此在执行删除操作后我们必须重新更新迭代器。
7.1.1 示例删除元素时正确的迭代器处理
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 查找并删除元素3auto it lst.begin();while (it ! lst.end()) {if (*it 3) {it lst.erase(it); // 删除元素并获取下一个有效迭代器} else {it; // 继续遍历}}for (int val : lst) {cout val ; // 输出: 1 2 4 5}return 0;
}在上面的代码中erase() 函数会返回一个指向被删除元素之后的迭代器因此我们使用该返回值继续遍历。这是一种常见的迭代器删除操作的最佳实践可以避免迭代器失效问题。 7.1.2 错误示例删除后不更新迭代器
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};auto it lst.begin();while (it ! lst.end()) {if (*it 3) {lst.erase(it); // 删除元素但未更新迭代器it; // 错误it 已经失效导致未定义行为} else {it;}}return 0;
}在这个错误的示例中删除操作使 it 失效但我们在下一个循环中继续使用了失效的 it这会导致未定义行为可能会引发程序崩溃。
7.1.3 相关文档
C Reference: list erase 第八章list 常见的其他修改操作
8.1 splice() 操作 splice() 是 list 特有的操作它允许我们将一个 list 中的元素直接拼接到另一个 list 中而不会重新分配内存或复制元素。该操作非常高效因为它仅修改链表的指针。 方法名功能描述splice(position, x)将 list x 的所有元素插入到当前 list 中splice(position, x, it)将 list x 中的 it 指定的元素插入到当前 list 中splice(position, x, first, last)将 x 中 [first, last) 区间的元素插入当前 list
8.1.1 示例使用 splice() 操作
#include iostream
#include list
using namespace std;int main() {listint lst1 {1, 2, 3};listint lst2 {4, 5, 6};// 将 lst2 的元素拼接到 lst1 的末尾lst1.splice(lst1.end(), lst2);for (int val : lst1) {cout val ; // 输出: 1 2 3 4 5 6}cout \nList 2 size: lst2.size() endl; // 输出: 0 (lst2 已被清空)return 0;
}splice() 可以高效地将一个链表中的元素移动到另一个链表中它不会复制元素也不会破坏链表的连续性。
8.1.2 相关文档
C Reference: list splice 8.2 merge() 操作 merge() 函数用于将两个已经排序好的 list 合并为一个有序的 list。它会自动按照升序或自定义的比较规则合并两个链表。 方法名功能描述merge(list x)将已排序的 x 合并到当前链表中merge(list x, Compare comp)使用自定义比较函数 comp 合并 x
8.2.1 示例使用 merge() 操作
#include iostream
#include list
using namespace std;int main() {listint lst1 {1, 3, 5};listint lst2 {2, 4, 6};// 合并两个已排序的链表lst1.merge(lst2);for (int val : lst1) {cout val ; // 输出: 1 2 3 4 5 6}return 0;
}merge() 会将两个有序链表合并成一个新的有序链表并且不会对原链表进行元素的复制只是对链表节点进行了重新连接。
8.2.2 相关文档
C Reference: list merge 第九章list 的排序与去重
9.1 sort() 操作 list 提供了 sort() 函数来对链表进行排序。由于 list 不支持随机访问因此它使用的排序算法是稳定的归并排序性能为 O(N log N)。 方法名功能描述sort()默认按照升序排序sort(Compare comp)使用自定义比较函数 comp 进行排序
9.1.1 示例对 list 进行排序
#include iostream
#include list
using namespace std;int main() {listint lst {5, 2, 9, 1, 5, 6};// 对链表进行排序lst.sort();for (int val : lst) {cout val ; // 输出: 1 2 5 5 6 9}return 0;
}9.1.2 使用自定义比较函数排序
#include iostream
#include list
using namespace std;bool customCompare(int a, int b) {return a b; // 降序比较
}int main() {listint lst {5, 2, 9, 1, 5, 6};// 使用自定义比较函数进行降序排序lst.sort(customCompare);for (int val : lst) {cout val ; // 输出: 9 6 5 5 2 1}return 0;
}9.2 unique() 操作 unique() 函数用于去除链表中相邻的重复元素。它会比较相邻的两个元素如果它们相等则删除后一个元素。 方法名功能描述unique()移除相邻的重复元素unique(BinaryPredicate p)使用自定义的比较规则 p 移除相邻的元素
9.2.1 示例使用 unique() 去重
#include iostream
#include list
using namespace std;int main() {listint lst {1, 1, 2, 3, 3, 4, 5, 5};// 去除相邻的重复元素lst.unique();for (int val : lst) {cout val ; // 输出: 1 2 3 4 5}return 0;
}9.2.2 使用自定义规则去重
#include iostream
#include list
using namespace std;bool customEqual(int a, int b) {return a % 2 b % 2; // 自定义规则移除相邻的偶数/奇数
}int main() {listint lst {1, 3, 2, 4, 5, 6};// 使用自定义规则去重lst.unique(customEqual);for (int val : lst) {cout val ; // 输出: 1 2 5}return 0;
}第十章list 的其他操作
10.1 reverse() 操作 reverse() 函数用于将 list 的顺序进行反转。该操作不会创建新的链表而是直接修改现有链表的链接顺序。 方法名功能描述reverse()将 list 中的元素顺序反转
10.1.1 示例反转 list 中的元素
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 5};// 反转 list 中的元素lst.reverse();for (int val : lst) {cout val ; // 输出: 5 4 3 2 1}return 0;
}通过 reverse() 函数原本顺序存储的元素将被反转链表中的第一个元素变为最后一个最后一个变为第一个。
10.1.2 相关文档
C Reference: list reverse 10.2 swap() 操作 swap() 函数用于交换两个 list 容器的内容。这个操作非常高效因为 list 只交换内部的指针和相关数据而不会实际移动或复制元素。 方法名功能描述swap(list x)交换当前 list 与 x 中的元素
10.2.1 示例交换两个 list 的内容
#include iostream
#include list
using namespace std;int main() {listint lst1 {1, 2, 3};listint lst2 {4, 5, 6};// 交换两个 listlst1.swap(lst2);cout List 1: ;for (int val : lst1) {cout val ; // 输出: 4 5 6}cout \nList 2: ;for (int val : lst2) {cout val ; // 输出: 1 2 3}return 0;
}swap() 是一种非常高效的操作尤其是在需要大量数据交换时可以避免拷贝开销。
11.2.2 相关文档
C Reference: list swap 10.3 remove() 操作 remove() 函数用于从 list 中移除所有与指定值相等的元素。它会遍历整个链表删除所有匹配的元素。 方法名功能描述remove(const T val)删除所有与 val 相等的元素
10.3.1 示例移除指定值的元素
#include iostream
#include list
using namespace std;int main() {listint lst {1, 2, 3, 4, 2, 5};// 移除值为2的所有元素lst.remove(2);for (int val : lst) {cout val ; // 输出: 1 3 4 5}return 0;
}remove() 函数会移除链表中所有等于指定值的元素。由于链表是双向的这种操作不会导致大量的数据移动只是修改指针指向。
10.3.2 相关文档
C Reference: list remove 10.4 remove_if() 操作 remove_if() 函数根据给定的条件谓词移除链表中符合条件的所有元素。与 remove() 不同它可以使用自定义的判断规则来删除元素。 方法名功能描述remove_if(UnaryPredicate p)移除所有满足谓词 p 条件的元素
10.4.1 示例使用 remove_if() 删除符合条件的元素
#include iostream
#include list
using namespace std;// 判断条件删除所有偶数
bool isEven(int n) {return n % 2 0;
}int main() {listint lst {1, 2, 3, 4, 5, 6};// 删除所有偶数元素lst.remove_if(isEven);for (int val : lst) {cout val ; // 输出: 1 3 5}return 0;
}在这个例子中remove_if() 根据自定义的谓词函数 isEven() 删除了链表中所有的偶数元素。
10.4.2 相关文档
C Reference: list remove_if 10.5 emplace() 和 emplace_back() 操作 emplace() 和 emplace_back() 是 list 提供的构造元素的方法它们允许我们直接在链表中构造元素避免不必要的复制操作。相比 push_back()emplace_back() 更加高效尤其是在插入复杂对象时。 方法名功能描述emplace(position, args...)在指定位置直接构造元素emplace_back(args...)在链表末尾直接构造元素避免复制构造开销
10.5.1 示例使用 emplace() 和 emplace_back()
#include iostream
#include list
using namespace std;struct Point {int x, y;Point(int a, int b) : x(a), y(b) {}
};int main() {listPoint points;// 在 list 中直接构造元素points.emplace_back(1, 2); // 在末尾构造元素 (1, 2)points.emplace(points.begin(), 3, 4); // 在起始位置构造元素 (3, 4)for (const auto pt : points) {cout ( pt.x , pt.y ) ; // 输出: (3, 4) (1, 2)}return 0;
}emplace() 和 emplace_back() 提供了更灵活和高效的插入方式尤其在处理复杂对象时可以减少额外的构造和复制操作。
10.5.2 相关文档
C Reference: list emplace 第十一章list 的内存管理
11.1 shrink_to_fit() 操作 list 不像 vector 那样需要经常处理容量管理和扩容问题因为它的底层实现是链表元素的插入和删除并不会影响容器的容量分配。但 STL 容器通常提供 shrink_to_fit() 函数来缩减不必要的内存开销而 list 没有此函数因为链表结构本身并不涉及到多余的容量分配问题。 写在最后
本文详尽介绍了 C STL 中 list 容器的各类操作。我们从基本的构造、元素访问、容量管理到迭代器、修改操作、排序与去重等高级功能深入讲解了如何使用 list 实现高效的插入、删除和操作。同时我们也讨论了 list 特有的操作如 splice()、merge()、remove() 等。
在 C 中list 作为双向链表非常适合频繁插入和删除元素的场景但它不支持随机访问这与 vector 的应用场景有所不同。在实际开发中可以根据需要选择合适的容器来优化性能和提高程序的可读性。 欢迎讨论如果你有任何问题或建议请在评论区留言。 支持一下如果你觉得这篇文章对你有帮助请点赞、收藏并分享你们的支持是我持续创作的动力 以上就是关于【C篇】深度剖析C STL玩转 list 容器解锁高效编程的秘密武器的内容啦各位大佬有什么问题欢迎在评论区指正或者私信我也是可以的啦您的支持是我创作的最大动力❤️
