一、 list的介绍
std::list 是 C++ 标准模板库（STL）中的一种双向链表容器。每个元素包含指向前后节点的指针，支持高效插入和删除操作，但随机访问性能较差。
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素
二、list的使用
#include <iostream>
#include <list>
#include <algorithm> // 用于 find 示例
using namespace std;
void printList(const string& hint, const list<int>& lst)
{
cout << hint << ": ";
for (const auto& val : lst) cout << val << " ";
cout << "\n\n";
}
int main()
{
// ================== 初始化 ==================
list<int> lst1; // 空列表
list<int> lst2(3, 100); // 3个100
list<int> lst3 = { 7, 2, 5, 1 }; // 初始化列表
list<int> lst4(lst3); // 拷贝构造
printList("lst2 (填充构造)", lst2);
printList("lst3 (初始化列表)", lst3);
printList("lst4 (拷贝构造)", lst4);
// ================== 增删操作 ==================
lst3.push_front(9); // 头部插入
lst3.push_back(3); // 尾部插入
printList("push_front(9) + push_back(3)", lst3); // 9 7 2 5 1 3
lst3.pop_front(); // 删除头部
lst3.pop_back(); // 删除尾部
printList("pop_front() + pop_back()", lst3); // 7 2 5 1
auto it = lst3.begin();
advance(it, 2); // 移动到第3个元素(5)
lst3.insert(it, 99); // 在5前面插入99
printList("insert(99) at pos3", lst3); // 7 2 99 5 1
it = lst3.begin();
advance(it, 3);
lst3.erase(it); // 删除第4个元素(5)
printList("erase(pos4)", lst3); // 7 2 99 1
lst3.remove(99); // 删除所有99
printList("remove(99)", lst3); // 7 2 1
// ================== 容量操作 ==================
cout << "size: " << lst3.size() << endl; // 3
cout << "empty: " << boolalpha << lst3.empty() << endl; // false
lst3.clear();
printList("after clear()", lst3); // 空列表
cout << "empty after clear: " << lst3.empty() << endl << endl; // true
// ================== 元素访问 ==================
lst3 = { 10, 20, 30 };
cout << "front: " << lst3.front() << endl; // 10
cout << "back: " << lst3.back() << endl; // 30
cout << endl;
// ================== 特殊操作 ==================
list<int> lstA = { 5, 3, 1, 4, 2 };
lstA.sort();
printList("sorted lstA", lstA); // 1 2 3 4 5
lstA.unique(); // 无连续重复元素时无效
printList("unique (无变化)", lstA);
lstA.reverse();
printList("reversed lstA", lstA); // 5 4 3 2 1
// splice示例
list<int> lstB = { 100, 200, 300 };
auto splice_pos = lstA.begin();
advance(splice_pos, 2); // 插入到第3个位置前
lstA.splice(splice_pos, lstB);
printList("splice lstB into lstA", lstA); // 5 4 100 200 300 3 2 1
printList("lstB after splice", lstB); // 空列表
// merge示例（需要两个列表已排序）
list<int> lstC = { 2, 5, 8 };
list<int> lstD = { 1, 3, 6 };
lstC.merge(lstD);
printList("merged lstC", lstC); // 1 2 3 5 6 8
printList("lstD after merge", lstD); // 空列表
// ================== 遍历方式 ==================
cout << "迭代器遍历: ";
for (auto it = lstC.begin(); it != lstC.end(); ++it)
{
cout << *it << " ";
}
cout << "\n范围遍历: ";
for (const auto& val : lstC)
{
cout << val << " ";
}
cout << "\n\n";
// ================== 算法库结合示例 ==================
list<int> nums = { 5, 3, 9, 1, 7 };
auto find_it = find(nums.begin(), nums.end(), 9);
if (find_it != nums.end())
{
cout << "Found 9 at position: " << distance(nums.begin(), find_it) << endl;
}
return 0;
}
三、list的模拟实现
#include <iostream>
#include <cassert>
#include <stdexcept>
// 双向链表节点的模板定义
template<typename T>
struct ListNode
{
T data; // 节点存储的数据
ListNode* prev; // 指向前一个节点的指针
ListNode* next; // 指向后一个节点的指针
ListNode(const T& val) : data(val), prev(nullptr), next(nullptr) {} // 构造函数初始化节点值
};
// 双向链表的模板类
template<typename T>
class List
{
private:
ListNode<T>* head; // 指向链表头节点的指针
ListNode<T>* tail; // 指向链表尾节点的指针
size_t size; // 链表中元素的数量
public:
// 默认构造函数：初始化一个空链表
List() : head(nullptr), tail(nullptr), size(0) {}
// 析构函数：清空链表释放内存
~List() { clear(); }
// 拷贝构造函数：创建一个新链表，内容与另一个链表相同
List(const List& other) : head(nullptr), tail(nullptr), size(0)
{
ListNode<T>* current = other.head;
while (current != nullptr)
{
push_back(current->data); // 逐个复制元素
current = current->next;
}
}
// 移动构造函数：从另一个链表转移资源，避免深拷贝
List(List&& other) noexcept : head(other.head), tail(other.tail), size(other.size)
{
other.head = nullptr; // 原链表置空
other.tail = nullptr;
other.size = 0;
}
// 拷贝赋值运算符：先清空当前链表，再复制另一个链表的内容
List& operator=(const List& other)
{
if (this != &other)
{
clear(); // 清空当前链表
ListNode<T>* current = other.head;
while (current != nullptr)
{
push_back(current->data); // 逐个复制元素
current = current->next;
}
}
return *this;
}
// 移动赋值运算符：先清空当前链表，再转移另一个链表的资源
List& operator=(List&& other) noexcept
{
if (this != &other)
{
clear(); // 清空当前链表
head = other.head;
tail = other.tail;
size = other.size;
other.head = nullptr; // 原链表置空
other.tail = nullptr;
other.size = 0;
}
return *this;
}
// 迭代器类：用于遍历链表
class iterator
{
ListNode<T>* current; // 当前指向的节点
public:
iterator(ListNode<T>* node = nullptr) : current(node) {} // 构造函数
T& operator*() const { return current->data; } // 解引用操作符
// 前置自增运算符：指向下一个节点
iterator& operator++()
{
current = current->next;
return *this;
}
// 后置自增运算符：返回当前迭代器，然后指向下一个节点
iterator operator++(int)
{
iterator tmp = *this;
current = current->next;
return tmp;
}
// 相等比较运算符
bool operator==(const iterator& other) const { return current == other.current; }
// 不等比较运算符
bool operator!=(const iterator& other) const { return current != other.current; }
// 获取当前节点指针（供内部使用）
ListNode<T>* getCurrent() const { return current; }
};
iterator begin() const { return iterator(head); } // 返回指向第一个元素的迭代器
iterator end() const { return iterator(nullptr); } // 返回指向尾后的迭代器
// 判断链表是否为空
bool empty() const { return size == 0; }
// 返回链表中元素的数量
size_t get_size() const { return size; }
// 返回第一个元素的引用
T& front()
{
if (empty()) throw std::out_of_range("List is empty");
return head->data;
}
// 返回最后一个元素的引用
T& back()
{
if (empty()) throw std::out_of_range("List is empty");
return tail->data;
}
// 在链表尾部添加元素
void push_back(const T& value)
{
ListNode<T>* newNode = new ListNode<T>(value);
if (!tail) // 链表为空的情况
{
head = tail = newNode;
}
else // 链表不为空的情况
{
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
size++;
}
// 在链表头部添加元素
void push_front(const T& value)
{
ListNode<T>* newNode = new ListNode<T>(value);
if (!head) // 链表为空的情况
{
head = tail = newNode;
}
else // 链表不为空的情况
{
newNode->next = head;
head->prev = newNode;
head = newNode;
}
size++;
}
// 删除链表尾部的元素
void pop_back()
{
if (empty()) return;
ListNode<T>* temp = tail;
if (head == tail) // 链表只有一个元素的情况
{
head = tail = nullptr;
}
else // 链表有多个元素的情况
{
tail = tail->prev;
tail->next = nullptr;
}
delete temp; // 释放内存
size--;
}
// 删除链表头部的元素
void pop_front()
{
if (empty()) return;
ListNode<T>* temp = head;
if (head == tail) // 链表只有一个元素的情况
{
head = tail = nullptr;
}
else // 链表有多个元素的情况
{
head = head->next;
head->prev = nullptr;
}
delete temp; // 释放内存
size--;
}
// 清空链表：删除所有元素
void clear()
{
while (!empty())
{
pop_front(); // 逐个删除元素
}
}
// 在指定位置前插入元素，返回指向新插入元素的迭代器
iterator insert(iterator pos, const T& value)
{
if (pos == begin()) // 在头部插入
{
push_front(value);
return begin();
}
else if (pos == end()) // 在尾部插入
{
push_back(value);
return iterator(tail);
}
else // 在中间插入
{
ListNode<T>* newNode = new ListNode<T>(value);
ListNode<T>* curr = pos.getCurrent();
newNode->prev = curr->prev;
newNode->next = curr;
curr->prev->next = newNode;
curr->prev = newNode;
size++;
return iterator(newNode);
}
}
// 删除指定位置的元素，返回指向下一个元素的迭代器
iterator erase(iterator pos)
{
if (pos == end()) return end();
ListNode<T>* curr = pos.getCurrent();
if (curr == head) // 删除头部元素
{
pop_front();
return begin();
}
else if (curr == tail) // 删除尾部元素
{
pop_back();
return end();
}
else // 删除中间元素
{
ListNode<T>* prev = curr->prev;
ListNode<T>* next = curr->next;
prev->next = next;
next->prev = prev;
delete curr; // 释放内存
size--;
return iterator(next);
}
}
};
// 测试用例：验证链表实现的正确性
int main()
{
// 测试默认构造函数
List<int> list1;
assert(list1.empty());
assert(list1.get_size() == 0);
// 测试push_back和front/back方法
list1.push_back(1);
assert(list1.get_size() == 1);
assert(list1.front() == 1);
assert(list1.back() == 1);
list1.push_back(2);
assert(list1.get_size() == 2);
assert(list1.front() == 1);
assert(list1.back() == 2);
// 测试push_front方法
List<int> list2;
list2.push_front(2);
assert(list2.get_size() == 1);
assert(list2.front() == 2);
list2.push_front(1);
assert(list2.get_size() == 2);
assert(list2.front() == 1);
assert(list2.back() == 2);
// 测试pop_back方法
list2.pop_back();
assert(list2.get_size() == 1);
assert(list2.back() == 1);
list2.pop_back();
assert(list2.empty());
// 测试pop_front方法
List<int> list3;
list3.push_back(1);
list3.push_back(2);
list3.pop_front();
assert(list3.get_size() == 1);
assert(list3.front() == 2);
list3.pop_front();
assert(list3.empty());
// 测试clear方法
List<int> list4;
list4.push_back(1);
list4.push_back(2);
list4.clear();
assert(list4.empty());
assert(list4.get_size() == 0);
try
{
list4.front(); // 尝试访问空链表的元素，应该抛出异常
assert(false); // 如果没有抛出异常，断言失败
}
catch (const std::out_of_range&) {} // 捕获预期的异常
// 测试拷贝构造函数
List<int> list5;
list5.push_back(1);
list5.push_back(2);
List<int> list6(list5); // 拷贝构造
assert(list6.get_size() == 2);
assert(list6.front() == 1);
assert(list6.back() == 2);
list5.pop_front(); // 修改原链表
assert(list5.get_size() == 1);
assert(list6.get_size() == 2); // 验证拷贝的链表不受影响
// 测试移动构造函数
List<int> list7(std::move(list5)); // 移动构造
assert(list7.get_size() == 1);
assert(list5.empty()); // 原链表应该被置空
// 测试拷贝赋值运算符
List<int> list8;
list8 = list6; // 拷贝赋值
assert(list8.get_size() == 2);
list6.pop_back(); // 修改被拷贝的链表
assert(list8.get_size() == 2); // 验证拷贝的链表不受影响
// 测试移动赋值运算符
List<int> list9;
list9 = std::move(list8); // 移动赋值
assert(list9.get_size() == 2);
assert(list8.empty()); // 原链表应该被置空
// 测试插入和迭代器
List<int> list10;
list10.push_back(1);
list10.push_back(3);
auto it = list10.begin();
++it; // 指向元素3
list10.insert(it, 2); // 在3之前插入2
assert(list10.get_size() == 3);
auto iter = list10.begin();
assert(*iter == 1);
++iter;
assert(*iter == 2);
++iter;
assert(*iter == 3);
++iter;
assert(iter == list10.end()); // 验证迭代器到达尾部
// 测试删除
it = list10.begin();
++it; // 指向元素2
it = list10.erase(it); // 删除元素2，it应该指向元素3
assert(*it == 3);
assert(list10.get_size() == 2);
assert(list10.front() == 1);
assert(list10.back() == 3);
std::cout << "All tests passed!" << std::endl;
return 0;
}四、list的迭代器失效及反向迭代器
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
改正：
反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭
代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。
五、list和vector的区别
