赞
踩
目录
专栏:C++学习笔记
C++ 中的 list
是一个强大的容器,特别适用于需要频繁插入和删除元素的场景。本文将详细介绍 list
容器,包括其介绍、使用方法、实现原理以及与 vector
容器的对比。
list
的介绍及使用list
的介绍list
是一种序列式容器,底层实现为双向链表。双向链表中的每个元素存储在独立的节点中,节点通过指针互相连接,可以在常数时间内在任意位置进行插入和删除操作。与 forward_list
的单链表不同,list
支持双向迭代。与其他序列式容器(如 array
、vector
、deque
)相比,list
在插入和删除操作方面表现更优,但不支持随机访问。
list
就像一条双向街道上的车队,每辆车(节点)都有前后两个链接,指向前后两辆车。你可以轻松地在任何地方插入或删除一辆车,而不需要移动其他车。但是,如果你想找到某辆车,就需要从头或尾开始,一辆辆查找,比较费时。
list
的使用list
的构造list
提供多种构造方法,包括创建空的 list
,创建包含多个相同元素的 list
,使用区间构造 list
以及拷贝构造等。
构造 list
就像创建不同类型的车队,你可以创建一个空车队,或者一个全是同样车的车队,还可以用现有的车队来创建新的车队。
- #include <list>
- #include <iostream>
-
- int main() {
- // 创建一个空的 list
- std::list<int> empty_list;
-
- // 创建一个包含 5 个值为 10 的元素的 list
- std::list<int> filled_list(5, 10);
-
- // 使用区间构造 list
- int arr[] = {1, 2, 3, 4, 5};
- std::list<int> range_list(arr, arr + 5);
-
- // 打印 filled_list 的元素
- for(int n : filled_list) {
- std::cout << n << " ";
- }
- std::cout << std::endl;
-
- return 0;
- }
这个程序首先创建一个空的
list
,然后创建一个包含 5 个值为 10 的list
,接着用数组中的元素构造一个list
。最后打印filled_list
的元素,显示 5 个 10。
list
迭代器的使用list
的迭代器类似于指针,指向 list
中的节点。你可以使用迭代器遍历 list
,访问或修改元素。
迭代器就像你走在车队中的一个人,你可以走到每辆车旁边查看里面的东西,或者往回走查看后面的车。
- #include <list>
- #include <iostream>
-
- int main() {
- std::list<int> my_list = {1, 2, 3, 4, 5};
-
- // 正向迭代
- for (auto it = my_list.begin(); it != my_list.end(); ++it) {
- std::cout << *it << " ";
- }
- std::cout << std::endl;
-
- // 反向迭代
- for (auto rit = my_list.rbegin(); rit != my_list.rend(); ++rit) {
- std::cout << *rit << " ";
- }
- std::cout << std::endl;
-
- return 0;
- }
这个程序创建一个包含 5 个整数的
list
。正向迭代器遍历list
,从头到尾打印元素,反向迭代器遍历list
,从尾到头打印元素。
list
的容量你可以使用 empty()
函数检查 list
是否为空,使用 size()
函数获取 list
中的元素个数。
这就像你检查车队中是否有车,以及数一数车队中有多少辆车。
- #include <list>
- #include <iostream>
-
- int main() {
- std::list<int> my_list = {1, 2, 3, 4, 5};
-
- // 检查是否为空
- if (my_list.empty()) {
- std::cout << "List is empty" << std::endl;
- } else {
- std::cout << "List is not empty" << std::endl;
- }
-
- // 获取大小
- std::cout << "List size: " << my_list.size() << std::endl;
-
- return 0;
- }
程序首先检查
list
是否为空,显然my_list
不为空,然后打印list
的大小,显示有 5 个元素。
list
的元素访问你可以使用 front()
函数访问 list
的第一个元素,使用 back()
函数访问 list
的最后一个元素。
这就像你想看看车队的第一辆车和最后一辆车里装了什么东西。
- #include <list>
- #include <iostream>
-
- int main() {
- std::list<int> my_list = {1, 2, 3, 4, 5};
-
- // 访问第一个和最后一个元素
- std::cout << "First element: " << my_list.front() << std::endl;
- std::cout << "Last element: " << my_list.back() << std::endl;
-
- return 0;
- }
程序分别打印
list
的第一个和最后一个元素,显示 1 和 5。
list
的修改操作list
提供丰富的修改操作,包括在头部和尾部插入和删除元素,插入和删除特定位置的元素,交换两个 list
的内容以及清空 list
。
这就像你可以在车队的任何位置加车或减车,甚至可以交换两队车里的车,或者把整个车队清空。
- #include <list>
- #include <iostream>
-
- int main() {
- std::list<int> my_list = {1, 2, 3, 4, 5};
-
- // 插入和删除操作
- my_list.push_front(0); // 在前面插入 0
- my_list.push_back(6); // 在后面插入 6
-
- my_list.pop_front(); // 删除第一个元素
- my_list.pop_back(); // 删除最后一个元素
-
- // 插入和删除特定位置的元素
- auto it = my_list.begin();
- ++it; // 指向第二个元素
- my_list.insert(it, 100); // 在第二个位置插入 100
-
- it = my_list.begin();
- ++it;
- my_list.erase(it); // 删除第二个位置的元素
-
- // 交换和清空 list
- std::list<int> another_list = {10, 20, 30};
- my_list.swap(another_list);
- my_list.clear();
-
- return 0;
- }
以下是程序在各步之后的状态:
my_list
初始为{1, 2, 3, 4, 5}
- 插入 0 和 6 后为
{0, 1, 2, 3, 4, 5, 6}
- 删除第一个和最后一个元素后为
{1, 2, 3, 4, 5}
- 在第二个位置插入 100 后为
{1, 100, 2, 3, 4, 5}
- 删除第二个位置的元素后为
{1, 2, 3, 4, 5}
- 与
another_list
交换后my_list
为{10, 20, 30}
- 清空后
my_list
为空
list
迭代器失效在 list
中,插入操作不会导致迭代器失效,删除操作会使指向被删除节点的迭代器失效。
就像你从车队中移走一辆车时,那个位置的指示牌(迭代器)也被移走了,但其他位置的指示牌不受影响。
- #include <list>
- #include <iostream>
-
- int main() {
- std::list<int> my_list = {1, 2, 3, 4, 5};
-
- auto it = my_list.begin();
- while (it != my_list.end()) {
- it = my_list.erase(it); // 删除元素后,更新迭代器
- }
-
- return 0;
- }
这个程序将删除
list
中的所有元素,最后my_list
为空。每次删除一个元素后,迭代器指向下一个元素,直到
list
清空。
list
的模拟实现实现一个简化版本的 list
,需要理解其底层结构和接口的含义。以下是一个简化的 list
实现示例:
模拟实现 list
就像你自己动手造一辆汽车,你需要理解汽车的每个部件和它们如何协同工作。
- #include <iostream>
-
- template<typename T>
- class Node {
- public:
- T data;
- Node* prev;
- Node* next;
-
- Node(T val) : data(val), prev(nullptr), next(nullptr) {}
- };
-
- template<typename T>
- class List {
- private:
- Node<T>* head;
- Node<T>* tail;
-
- public:
- List() : head(nullptr), tail(nullptr) {}
-
- void push_back(T val) {
- Node<T>* newNode = new Node<T>(val);
- if (!tail) {
- head = tail = newNode;
- } else {
- tail->next = newNode;
- newNode->prev = tail;
- tail = newNode;
- }
- }
-
- void print() {
- Node<T>* temp = head;
- while (temp) {
- std::cout << temp->data << " ";
- temp = temp->next;
- }
- std::cout << std::endl;
- }
-
- ~List() {
- Node<T>* temp;
- while (head) {
- temp = head;
- head = head->next;
- delete temp;
- }
- }
- };
-
- int main() {
- List<int> my_list;
- my_list.push_back(1);
- my_list.push_back(2);
- my_list.push_back(3);
- my_list.print();
-
- return 0;
- }
这个程序手动实现了一个简单的
list
,并添加了 3 个元素。最终打印出list
中的所有元素。
list
与 vector
的对比
底层结构:
vector
:动态顺序表,连续内存空间。list
:双向链表,不连续。随机访问:
vector
:支持,效率为 O(1)。list
:不支持,效率为 O(N)。插入和删除:
vector
:效率低,时间复杂度为 O(N)。list
:效率高,时间复杂度为 O(1)。空间利用率:
vector
:高,连续空间,缓存利用率高。list
:低,节点动态分配,容易造成内存碎片。迭代器:
vector
:原生指针。list
:封装的节点指针。迭代器失效:
vector
:插入时可能失效,删除时当前迭代器失效。list
:插入不会失效,删除时当前迭代器失效。使用场景:
vector
:高效存储,随机访问。list
:频繁插入和删除操作。
vector
就像一块连续的停车场,每辆车(元素)都紧挨着,如果你要在中间插入或删除一辆车,就需要挪动很多车。而 list
就像一列火车,每节车厢(元素)独立,可以随意插入或移除车厢,但要找到某个特定车厢就得一节一节地找。
C++ 中的
list
容器是一个基于双向链表的序列式容器,适用于需要频繁插入和删除操作的场景,但不支持随机访问。list
提供了多种构造方法和丰富的操作接口,包括插入、删除、访问等。与vector
相比,list
在插入和删除操作上更高效,但在随机访问和空间利用率上较差。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。