「C/C++」C++ STL容器库 之 std::list 双向链表容器

✨博客主页
何曾参静谧的博客
📌文章专栏
「C/C++」C/C++程序设计
📚全部专栏
「VS」Visual Studio	「C/C++」C/C++程序设计	「UG/NX」BlockUI集合
「Win」Windows程序设计	「DSA」数据结构与算法	「UG/NX」NX二次开发
「QT」QT5程序设计	「File」数据文件格式	「PK」Parasolid函数说明

std::list容器详解

上图截取自C++黑马课程

1. 容器说明

std::list是C++标准模板库（STL）中的一种双向链表容器，属于顺序容器的一种。与std::vector和std::deque等容器不同，std::list在插入和删除操作上具有显著优势，特别是在容器的中间部分。std::list的每个元素包含指向前一个元素和后一个元素的指针，这使得在链表的任意位置进行插入和删除操作的时间复杂度为O(1)。然而，std::list不支持随机访问，访问某个位置的元素需要O(n)时间。

2. 引用头文件

在使用std::list之前，必须包含对应的头文件：

#include <list>

3. 函数构造与对象初始化

std::list提供了多种构造函数来初始化对象，包括默认构造函数、拷贝构造函数、赋值构造函数、初始化列表构造函数、迭代器范围构造函数、大小和值构造函数以及移动构造函数等。

• 默认构造函数：创建一个空的list容器。
• 拷贝构造函数：用另一个list容器来初始化一个新的list容器。
• 赋值构造函数：通过赋值运算符从一个list容器创建另一个list容器。
• 初始化列表构造函数：使用初始化列表来初始化list容器。
• 迭代器范围构造函数：使用两个迭代器（指向容器或其他序列的起始和结束位置）来初始化list容器。
• 大小和值构造函数：使用指定的大小和值来初始化list容器。
• 移动构造函数（C++11开始支持）：从另一个list容器移动元素来初始化新的list容器。

示例代码：

#include <list>
#include <iostream>int main() {// 默认构造函数std::list<int> lst1;// 初始化列表构造函数std::list<int> lst2 = {1, 2, 3, 4, 5};// 大小和值构造函数std::list<int> lst3(5, 10);// 拷贝构造函数std::list<int> lst4(lst2);// 输出list元素for (int elem : lst4) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

4. 元素访问

std::list不支持通过下标随机访问元素，只能通过迭代器进行访问。访问某个位置的元素需要从头或尾开始遍历链表。

#include <list>
#include <iostream>int main() {std::list<int> lst = {1, 2, 3, 4, 5};std::cout << lst.front() << std::endl; // 输出：1std::cout << lst.back() << std::endl;  // 输出：5return 0;
}

5. 迭代器

std::list的迭代器可以双向移动，支持向前和向后遍历链表。迭代器的稳定性使得在插入和删除操作时，除了被删除的迭代器外，其余迭代器仍然有效。

#include <list>
#include <iostream>int main() {std::list<int> lst = {1, 2, 3, 4, 5};// 使用迭代器访问元素for (auto it = lst.begin(); it != lst.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

6. 容器修改器

std::list提供了多种成员函数来修改容器，包括添加元素（push_back、push_front）、删除元素（pop_back、pop_front）、插入元素（insert）、删除指定位置的元素（erase）、合并和拼接（merge、splice）、移除元素（remove、remove_if）、排序（sort）等。

示例代码：

#include <list>
#include <iostream>int main() {std::list<int> lst = {1, 2, 3, 4, 5};// 在末尾添加元素lst.push_back(6);// 在前面添加元素lst.push_front(0);// 删除末尾元素lst.pop_back();// 删除前面元素lst.pop_front();// 插入元素auto it = lst.begin();++it; // 移动到第二个位置lst.insert(it, 10); // 在第二个位置插入10// 删除指定位置的元素it = lst.begin();++it; // 移动到第二个位置lst.erase(it); // 删除第二个位置的元素// 输出修改后的list元素for (const auto& elem : lst) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

7. 元素比较

std::list的元素比较通常通过迭代器来实现，可以使用标准库中的算法函数（如std::equal）来比较两个list容器是否相等或具有相同的元素顺序。

8.反转\排序\交换

#include <list>
#include <iostream>
using namespace std;void printList(const list<int>& L) {for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {cout << *it << " ";}cout << endl;
}
int main()
{list<int> l = {90,20,30,40,50};//反转容器的元素l.reverse();printList(l); // 50 40 30 20 90 //排序l.sort(); //默认的排序规则 从小到大printList(l); // 20 30 40 50 90 list<int> l2 = {10,30,50,70,90};l.swap(l2);printList(l); // 10 30 50 70 90 
}

总结与场景应用

std::list容器具有动态大小、高效插入删除、内存分配灵活和双向遍历等优点，但访问元素速度较慢且内存开销较大。因此，std::list适用于需要在两端频繁插入和删除元素的场景，如排序算法中维护活跃连接列表、实现某种内存池或对象池等。同时，std::list也适用于处理大小动态变化的集合和需要双向遍历的场景。

通过合理的使用std::list容器，可以显著提高程序的灵活性和效率，特别是在需要频繁修改容器内容的场景中。

---