目录
0.前言
1.list介绍
1.1优势
1.2劣势
1.3容器属性
2.list使用
2.1构造函数
2.1.1默认构造函数
2.1.2填充构造函数
2.1.3范围构造函数
2.1.4拷贝构造函数
2.1.5初始化列表构造函数
2.2迭代器
2.2.1 begin()
2.2.2 end()
2.2.3 cbegin()
2.2.4 cend()
2.2.5 rbegin()
2.2.6 rend()
2.2.7 crbegin()
2.2.8 crend()
2.3容量获取及元素访问函数
2.3.1 empty()
2.3.2 size()
2.3.3 front()
2.3.4 back()
2.4修改函数
2.4.1 assign
2.4.2 push_front 和 pop_front
2.4.3 push_back 和 pop_back
2.4.4 insert
2.4.5 erase
2.4.6 swap
2.4.7 clear
2.5其他功能函数
2.5.1 splice
2.5.2 unique
3.list的模拟实现
3.1基本实现代码
3.2 list正/反向迭代器实现
3.2.1正向迭代器 (ListIterator)
3.2.2反向迭代器 (ListReverseIterator)
4.list与vector的比较
4.1 内部实现
4.2 存储方式
4.3 访问和遍历
4.4 插入和删除操作
4.5 内存管理
4.6 使用场景
5.结语
（图像由AI生成）
0.前言
在前面的文章中，我们已经详细介绍了 C++ 标准模板库中的 string 和 vector 类的用法及实现。接下来，我们将深入探讨 list 类，这是一种双向链表结构，适合于频繁插入和删除操作的场景。通过这篇文章，我们将全面了解 list 的构造函数、迭代器、容量获取与元素访问函数、修改函数、以及其他功能函数，并比较 list 与 vector 的异同，帮助你在实际编程中做出更合适的数据结构选择。
1.list介绍
list 是 C++ 标准模板库中的一种序列容器，允许在序列中的任何位置进行常数时间的插入和删除操作，并且支持双向迭代。它的实现基于双向链表，这种结构允许元素存储在不同且不相关的内存位置，内部通过每个元素与前一个和后一个元素的链接来保持顺序。
双向链表与单向链表（如 forward_list）非常相似，主要区别在于单向链表只能向前迭代，而双向链表可以在两个方向上迭代。尽管单向链表在内存占用和效率上略优，但双向链表提供了更灵活的迭代和操作方式。
1.1优势
与其他基本标准序列容器（如 array、vector 和 deque）相比，list 在以下方面通常表现更好：
- 插入和删除操作：在任意位置插入、提取和移动元素的性能更优，特别是在已获得迭代器的位置。
- 排序算法：在需要频繁插入和删除操作的排序算法中表现更佳。
1.2劣势
list 和 forward_list 与其他序列容器相比存在一些缺点：
- 缺乏直接访问：无法通过位置直接访问元素。例如，要访问
list中的第六个元素，需要从已知位置（如开头或结尾）迭代到该位置，这需要线性时间。 - 额外的内存开销：为了维护元素之间的链接信息，
list需要额外的内存，这在处理大量小元素时可能是一个重要因素。
1.3容器属性
- 序列：序列容器中的元素按严格的线性顺序排列。可以通过其在序列中的位置访问单个元素。
- 双向链表：每个元素都包含信息以定位下一个和前一个元素，从而允许在特定元素之前或之后（甚至是整个范围）进行常数时间的插入和删除操作，但不支持直接随机访问。
- 分配器感知：容器使用分配器对象来动态管理其存储需求。
2.list使用
2.1构造函数
| default (1) | explicit list (const allocator_type& alloc = allocator_type()); |
|---|---|
| fill (2) | explicit list (size_type n);
list (size_type n, const value_type& val,
const allocator_type& alloc = allocator_type());
|
| range (3) | template <class InputIterator>
list (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());
|
| copy (4) | list (const list& x); list (const list& x, const allocator_type& alloc); |
| initializer list (5) | list (initializer_list<value_type> il,
const allocator_type& alloc = allocator_type());
|
C++ 中的 list 提供了多种构造函数，用于不同的初始化需求。下面我们详细介绍每种构造函数，并提供示例代码来说明它们的使用。
2.1.1默认构造函数
explicit list (const allocator_type& alloc = allocator_type());
创建一个空链表，可以指定一个分配器。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist;
std::cout << "Size of mylist: " << mylist.size() << std::endl;
return 0;
}
//输出：Size of mylist: 02.1.2填充构造函数
explicit list (size_type n);
list (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());
创建一个包含 n 个默认值元素的链表，或创建一个包含 n 个指定值 val 的链表。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist1(5); // 创建一个包含5个默认值元素的链表
std::list<int> mylist2(5, 100); // 创建一个包含5个值为100的元素的链表
std::cout << "mylist1 contains:";
for (int& x : mylist1) std::cout << ' ' << x;
std::cout << '\n';
std::cout << "mylist2 contains:";
for (int& x : mylist2) std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
//输出：
//mylist1 contains: 0 0 0 0 0
//mylist2 contains: 100 100 100 100 1002.1.3范围构造函数
template <class InputIterator>
list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
使用迭代器范围 [first, last) 构造链表。
#include <iostream>
#include <list>
int main() {
std::list<int> original = {1, 2, 3, 4, 5};
std::list<int> copy(original); // 使用拷贝构造函数
std::cout << "copy contains:";
for (int& x : copy) std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
示例代码：
#include <iostream>
#include <list>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> mylist(vec.begin(), vec.end()); // 使用vector的迭代器范围构造链表
std::cout << "mylist contains:";
for (int& x : mylist) std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
//输出：mylist contains: 1 2 3 4 5
2.1.4拷贝构造函数
list (const list& x);
list (const list& x, const allocator_type& alloc);
创建一个与现有链表 x 相同的新链表。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> original = {1, 2, 3, 4, 5};
std::list<int> copy(original); // 使用拷贝构造函数
std::cout << "copy contains:";
for (int& x : copy) std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
//输出：copy contains: 1 2 3 4 5
2.1.5初始化列表构造函数
list (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());
使用初始化列表 il 构造链表。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30, 40, 50}; // 使用初始化列表构造链表
std::cout << "mylist contains:";
for (int& x : mylist) std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
//输出：mylist contains: 10 20 30 40 50
2.2迭代器
2.2.1 begin()
begin() 返回指向容器中第一个元素的迭代器。
2.2.2 end()
end() 返回指向容器末尾后一个位置的迭代器，这个位置不包含任何元素。
2.2.3 cbegin()
cbegin() 返回指向容器中第一个元素的常量迭代器，不能用于修改元素。
2.2.4 cend()
cend() 返回指向容器末尾后一个位置的常量迭代器，这个位置不包含任何元素，不能用于修改元素。
2.2.5 rbegin()
rbegin() 返回指向容器中最后一个元素的反向迭代器。
2.2.6 rend()
rend() 返回指向容器第一个元素前一个位置的反向迭代器，这个位置不包含任何元素。
2.2.7 crbegin()
crbegin() 返回指向容器中最后一个元素的常量反向迭代器，不能用于修改元素。
2.2.8 crend()
crend() 返回指向容器第一个元素前一个位置的常量反向迭代器，这个位置不包含任何元素，不能用于修改元素。
下面是一个示例代码，展示了这些迭代器的使用：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30, 40, 50};
// 使用 begin() 和 end() 迭代器
std::cout << "Elements using begin() and end(): ";
for (auto it = mylist.begin(); it != mylist.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用 cbegin() 和 cend() 迭代器
std::cout << "Elements using cbegin() and cend(): ";
for (auto it = mylist.cbegin(); it != mylist.cend(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用 rbegin() 和 rend() 迭代器
std::cout << "Elements using rbegin() and rend(): ";
for (auto it = mylist.rbegin(); it != mylist.rend(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用 crbegin() 和 crend() 迭代器
std::cout << "Elements using crbegin() and crend(): ";
for (auto it = mylist.crbegin(); it != mylist.crend(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
代码解析
- begin() 和 end()：用于从前向后遍历并访问列表中的元素。
- cbegin() 和 cend()：常量迭代器，用于从前向后遍历但不允许修改元素。
- rbegin() 和 rend()：反向迭代器，用于从后向前遍历并访问列表中的元素。
- crbegin() 和 crend()：常量反向迭代器，用于从后向前遍历但不允许修改元素。
2.3容量获取及元素访问函数
在使用 C++ 的 list 类时，容量获取和元素访问函数是非常重要的，它们可以帮助我们了解和操作容器中的元素。主要包括以下几个函数。
2.3.1 empty()
empty() 函数用于检查容器是否为空。如果容器中没有元素，则返回 true，否则返回 false。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist;
if (mylist.empty()) {
std::cout << "The list is empty." << std::endl;
} else {
std::cout << "The list is not empty." << std::endl;
}
mylist.push_back(10);
if (mylist.empty()) {
std::cout << "The list is empty." << std::endl;
} else {
std::cout << "The list is not empty." << std::endl;
}
return 0;
}
//输出：
//The list is empty.
//The list is not empty.
2.3.2 size()
size() 函数返回容器中元素的数量。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30, 40, 50};
std::cout << "The size of the list is: " << mylist.size() << std::endl;
mylist.push_back(60);
std::cout << "After adding an element, the size of the list is: " << mylist.size() << std::endl;
return 0;
}
//输出：
//The size of the list is: 5
//After adding an element, the size of the list is: 6
2.3.3 front()
front() 函数返回容器中第一个元素的引用。注意，front() 不能用于空容器，否则行为是未定义的。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30};
std::cout << "The first element is: " << mylist.front() << std::endl;
mylist.front() = 100; // 修改第一个元素的值
std::cout << "After modification, the first element is: " << mylist.front() << std::endl;
return 0;
}
//输出：
//The first element is: 10
//After modification, the first element is: 100
2.3.4 back()
back() 函数返回容器中最后一个元素的引用。注意，back() 不能用于空容器，否则行为是未定义的。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30};
std::cout << "The last element is: " << mylist.back() << std::endl;
mylist.back() = 300; // 修改最后一个元素的值
std::cout << "After modification, the last element is: " << mylist.back() << std::endl;
return 0;
}
//输出：
//The last element is: 30
//After modification, the last element is: 300
2.4修改函数
C++ list 类提供了多种修改容器内容的函数。这些函数允许我们在列表中插入、删除和替换元素。下面我们将详细介绍以下修改函数，并提供示例代码展示它们的使用：
2.4.1 assign
assign 函数用于替换当前容器内容，接受多个重载版本，可以使用指定的元素、范围或初始化列表。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist;
mylist.assign(5, 100); // 使用5个100替换当前内容
std::cout << "List after assign(5, 100): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
std::list<int> another_list = {1, 2, 3};
mylist.assign(another_list.begin(), another_list.end()); // 使用另一个list的范围替换当前内容
std::cout << "List after assign from another list: ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
mylist.assign({10, 20, 30}); // 使用初始化列表替换当前内容
std::cout << "List after assign({10, 20, 30}): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List after assign(5, 100): 100 100 100 100 100
// List after assign from another list: 1 2 3
// List after assign({10, 20, 30}): 10 20 30
2.4.2 push_front 和 pop_front
push_front函数在容器开头插入一个元素。pop_front函数移除容器开头的元素。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {20, 30};
mylist.push_front(10); // 在开头插入元素10
std::cout << "List after push_front(10): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
mylist.pop_front(); // 移除开头的元素
std::cout << "List after pop_front(): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List after push_front(10): 10 20 30
// List after pop_front(): 20 30
2.4.3 push_back 和 pop_back
push_back函数在容器末尾插入一个元素。pop_back函数移除容器末尾的元素。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20};
mylist.push_back(30); // 在末尾插入元素30
std::cout << "List after push_back(30): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
mylist.pop_back(); // 移除末尾的元素
std::cout << "List after pop_back(): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List after push_back(30): 10 20 30
// List after pop_back(): 10 20
2.4.4 insert
insert 函数用于在指定位置插入一个或多个元素，可以通过单个元素、初始化列表或迭代器范围进行插入。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30};
auto it = mylist.begin();
++it; // 指向第二个元素
mylist.insert(it, 15); // 在第二个元素前插入15
std::cout << "List after insert(15): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
mylist.insert(it, 2, 25); // 在第二个元素前插入两个25
std::cout << "List after insert(2, 25): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
std::list<int> another_list = {1, 2, 3};
mylist.insert(it, another_list.begin(), another_list.end()); // 在第二个元素前插入另一个list的范围
std::cout << "List after insert from another list: ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List after insert(15): 10 15 20 30
// List after insert(2, 25): 10 25 25 15 20 30
// List after insert from another list: 10 1 2 3 25 25 15 20 30
2.4.5 erase
erase 函数用于移除一个或多个元素，可以通过单个迭代器或迭代器范围进行删除。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30, 40, 50};
auto it = mylist.begin();
++it; // 指向第二个元素
mylist.erase(it); // 移除第二个元素
std::cout << "List after erase second element: ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
auto it1 = mylist.begin();
auto it2 = mylist.end();
--it2; // 指向最后一个元素
mylist.erase(it1, it2); // 移除范围 [it1, it2)
std::cout << "List after erase range [begin, end-1): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List after erase second element: 10 30 40 50
// List after erase range [begin, end-1): 50
2.4.6 swap
swap 函数用于交换两个容器的内容。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {10, 20, 30};
list1.swap(list2); // 交换list1和list2的内容
std::cout << "List1 after swap: ";
for (const int& x : list1) {
std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "List2 after swap: ";
for (const int& x : list2) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List1 after swap: 10 20 30
// List2 after swap: 1 2 3
2.4.7 clear
clear 函数用于移除容器中的所有元素，使其变为空容器。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 30};
mylist.clear(); // 清空list中的所有元素
std::cout << "List after clear: ";
if (mylist.empty()) {
std::cout << "The list is empty." << std::endl;
} else {
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
}
return 0;
}
// 输出：
// List after clear: The list is empty.
2.5其他功能函数
除了基本的修改函数，C++ 的 list 类还提供了一些其他功能函数，这些函数可以更高效地操作链表中的元素。
2.5.1 splice
splice 函数用于将另一个 list 中的元素移到当前 list 的指定位置。splice 函数有三个重载版本：
splice(iterator position, list& x)：将x的所有元素移动到当前list中position之前的位置。splice(iterator position, list& x, iterator i)：将x中的元素i移动到当前list中position之前的位置。splice(iterator position, list& x, iterator first, iterator last)：将x中[first, last)范围内的元素移动到当前list中position之前的位置。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> list1 = {1, 2, 3, 4, 5};
std::list<int> list2 = {10, 20, 30};
auto it = list1.begin();
++it; // 指向第二个元素
// 将list2的所有元素移动到list1中第二个元素之前
list1.splice(it, list2);
std::cout << "List1 after splice all elements from List2: ";
for (const int& x : list1) {
std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "List2 after splice all elements to List1: ";
for (const int& x : list2) {
std::cout << x << " ";
}
std::cout << std::endl;
// 初始化list2
list2 = {10, 20, 30};
it = list1.begin();
++it; // 指向第二个元素
auto it2 = list2.begin();
++it2; // 指向list2中的第二个元素
// 将list2中的第二个元素移动到list1中第二个元素之前
list1.splice(it, list2, it2);
std::cout << "List1 after splice one element from List2: ";
for (const int& x : list1) {
std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "List2 after splice one element to List1: ";
for (const int& x : list2) {
std::cout << x << " ";
}
std::cout << std::endl;
// 初始化list2
list2 = {10, 20, 30};
it = list1.begin();
++it; // 指向第二个元素
// 将list2中的第一个和第二个元素移动到list1中第二个元素之前
list1.splice(it, list2, list2.begin(), ++(++list2.begin()));
std::cout << "List1 after splice range from List2: ";
for (const int& x : list1) {
std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "List2 after splice range to List1: ";
for (const int& x : list2) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List1 after splice all elements from List2: 1 10 20 30 2 3 4 5
// List2 after splice all elements to List1:
// List1 after splice one element from List2: 1 20 10 20 30 2 3 4 5
// List2 after splice one element to List1: 10 30
// List1 after splice range from List2: 1 10 20 20 10 20 30 2 3 4 5
// List2 after splice range to List1: 30
2.5.2 unique
unique 函数用于移除容器中相邻的重复元素，只保留一个。它有两个重载版本：
unique()：移除相邻重复的元素。unique(BinaryPredicate pred)：使用自定义的二元谓词函数来判断元素是否相邻重复。
示例代码：
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {10, 20, 20, 30, 30, 30, 40, 40, 50};
mylist.unique(); // 移除相邻重复的元素
std::cout << "List after unique(): ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
mylist = {10, 20, 21, 30, 31, 32, 40, 41, 50};
// 自定义二元谓词函数，移除相邻差值小于等于1的元素
mylist.unique([](int a, int b) { return std::abs(a - b) <= 1; });
std::cout << "List after unique with custom predicate: ";
for (const int& x : mylist) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
// 输出：
// List after unique(): 10 20 30 40 50
// List after unique with custom predicate: 10 20 30 32 40 50
3.list的模拟实现
3.1基本实现代码
#pragma once
#include <cstddef> // for size_t
template<class T>
struct ListNode
{
T data;
ListNode<T>* _next;
ListNode<T>* _prev;
ListNode(const T& d = T())
: data(d), _next(nullptr), _prev(nullptr)
{}
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node;
ListIterator(Node* node)
: _node(node)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return &_node->data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& it) const
{
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
};
template<class T, class Ref, class Ptr>
struct ListReverseIterator
{
typedef ListNode<T> Node;
typedef ListReverseIterator<T, Ref, Ptr> Self;
Node* _node;
ListReverseIterator(Node* node)
: _node(node)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return &_node->data;
}
Self& operator++()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
Self& operator--()
{
_node = _node->_next;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
bool operator!=(const Self& it) const
{
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
};
template<class T>
class list
{
public:
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
typedef ListReverseIterator<T, T&, T*> reverse_iterator;
typedef ListReverseIterator<T, const T&, const T*> const_reverse_iterator;
typedef T& reference;
typedef const T& const_reference;
private:
Node* _head;
public:
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
list(const list<T>& l)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
for (const auto& e : l)
{
push_back(e);
}
}
list(size_t n, const T& data = T())
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
while (n--)
{
push_back(data);
}
}
list<T>& operator=(const list<T>& l)
{
if (this != &l)
{
list<T> tmp(l);
swap(tmp);
}
return *this;
}
bool empty() const
{
return _head->_next == _head;
}
size_t size() const
{
size_t count = 0;
Node* cur = _head->_next;
while (cur != _head)
{
++count;
cur = cur->_next;
}
return count;
}
reference front()
{
return _head->_next->data;
}
const_reference front() const
{
return _head->_next->data;
}
reference back()
{
return _head->_prev->data;
}
const_reference back() const
{
return _head->_prev->data;
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
reverse_iterator rbegin()
{
return reverse_iterator(_head->_prev);
}
reverse_iterator rend()
{
return reverse_iterator(_head);
}
const_reverse_iterator crbegin() const
{
return const_reverse_iterator(_head->_prev);
}
const_reverse_iterator crend() const
{
return const_reverse_iterator(_head);
}
iterator insert(iterator pos, const T& data)
{
Node* newNode = new Node(data);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
return iterator(newNode);
}
void push_back(const T& data)
{
insert(end(), data);
}
void push_front(const T& data)
{
insert(begin(), data);
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
iterator erase(iterator first, iterator last)
{
while (first != last)
{
first = erase(first);
}
return last;
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
void swap(list<T>& l)
{
std::swap(_head, l._head);
}
void clear()
{
Node* cur = _head->_next;
while (cur != _head)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_head->_next = _head;
_head->_prev = _head;
}
};
3.2 list正/反向迭代器实现
在 list 容器的模拟实现中，迭代器是一个非常重要的部分。迭代器允许我们遍历、访问和修改链表中的元素。为了支持标准库中 list 的功能，我们需要实现正向迭代器和反向迭代器。下面是对正向迭代器和反向迭代器实现的详细介绍。
3.2.1正向迭代器 (ListIterator)
ListIterator 是一个模板结构体，用于表示 list 容器的正向迭代器。它支持常见的迭代器操作，如解引用、前进、后退和比较。
定义和成员
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node; // 指向当前节点的指针
// 构造函数
ListIterator(Node* node)
: _node(node)
{}
// 解引用运算符，返回当前节点的数据
Ref operator*()
{
return _node->data;
}
// 指针访问运算符，返回指向当前节点数据的指针
Ptr operator->()
{
return &_node->data;
}
// 前置递增运算符，移动到下一个节点
Self& operator++()
{
_node = _node->_next;
return *this;
}
// 后置递增运算符，移动到下一个节点，返回旧值
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
// 前置递减运算符，移动到前一个节点
Self& operator--()
{
_node = _node->_prev;
return *this;
}
// 后置递减运算符，移动到前一个节点，返回旧值
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 不等比较运算符
bool operator!=(const Self& it) const
{
return _node != it._node;
}
// 相等比较运算符
bool operator==(const Self& it) const
{
return _node == it._node;
}
};
3.2.2反向迭代器 (ListReverseIterator)
ListReverseIterator 是一个模板结构体，用于表示 list 容器的反向迭代器。反向迭代器允许我们从后向前遍历容器。
定义和成员
template<class T, class Ref, class Ptr>
struct ListReverseIterator
{
typedef ListNode<T> Node;
typedef ListReverseIterator<T, Ref, Ptr> Self;
Node* _node; // 指向当前节点的指针
// 构造函数
ListReverseIterator(Node* node)
: _node(node)
{}
// 解引用运算符，返回当前节点的数据
Ref operator*()
{
return _node->data;
}
// 指针访问运算符，返回指向当前节点数据的指针
Ptr operator->()
{
return &_node->data;
}
// 前置递增运算符，移动到前一个节点
Self& operator++()
{
_node = _node->_prev;
return *this;
}
// 后置递增运算符，移动到前一个节点，返回旧值
Self operator++(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 前置递减运算符，移动到下一个节点
Self& operator--()
{
_node = _node->_next;
return *this;
}
// 后置递减运算符，移动到下一个节点，返回旧值
Self operator--(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
// 不等比较运算符
bool operator!=(const Self& it) const
{
return _node != it._node;
}
// 相等比较运算符
bool operator==(const Self& it) const
{
return _node == it._node;
}
};
4.list与vector的比较
list 和 vector 是 C++ 标准模板库（STL）中两个常用的序列容器，它们在内部实现、使用场景和性能方面都有显著差异。下面将详细介绍 list 和 vector 的比较，从以下几个方面进行探讨：
4.1 内部实现
- list：
list是一种双向链表，每个节点包含一个数据元素以及指向前一个和后一个节点的指针。它的实现基于动态分配的节点，节点通过指针相互连接。 - vector：
vector是一种动态数组，底层实现为一个连续的内存块。它通过动态调整大小来适应插入和删除操作。
4.2 存储方式
- list：存储的元素不连续，每个元素通过指针连接到前一个和后一个元素。由于链表节点是分散存储的，因此元素的物理位置在内存中不是连续的。
- vector：存储的元素是连续的，这意味着
vector的元素在内存中是紧挨着的。这样有利于缓存的利用，访问速度较快。
4.3 访问和遍历
- list：访问任意位置的元素需要线性时间复杂度 (
O(n))，因为必须从链表的头部或尾部开始遍历到目标位置。list支持双向迭代。 - vector：可以在常数时间内 (
O(1)) 通过索引直接访问任意位置的元素。vector支持随机访问和双向迭代。
4.4 插入和删除操作
- list：在任意位置插入或删除元素的时间复杂度为常数时间 (
O(1))，只需调整指针。然而，找到插入或删除位置可能需要线性时间。 - vector：在末尾插入或删除元素的时间复杂度为常数时间 (
O(1))，但是在中间位置插入或删除元素的时间复杂度为线性时间 (O(n))，因为需要移动其他元素以保持连续性。
4.5 内存管理
- list：每个元素都需要额外的内存来存储前后指针，因此内存开销较大。链表节点是分散分配的，适合频繁的插入和删除操作。
- vector：当需要增加容量时，
vector会重新分配一块更大的内存，并将现有元素复制到新位置，这可能涉及大量的元素移动。为了减少内存重新分配的频率，vector通常会预留比实际需要更多的内存。
4.6 使用场景
-
list：
- 适用于频繁在中间插入或删除元素的场景。
- 不需要随机访问，只需顺序访问的场景。
- 内存管理分散，不需要连续内存的场景。
-
vector：
- 适用于需要频繁随机访问元素的场景。
- 在末尾进行插入或删除操作较多的场景。
- 数据量较小，不需要频繁调整大小的场景。
示例代码比较
下面的代码展示了 list 和 vector 在插入、删除和访问操作上的不同：
#include <iostream>
#include <list>
#include <vector>
int main() {
// list 示例
std::list<int> myList = {10, 20, 30, 40, 50};
auto it = myList.begin();
++it;
myList.insert(it, 15); // 在第二个位置插入15
myList.erase(it); // 删除第二个位置元素
std::cout << "List elements: ";
for (auto elem : myList) {
std::cout << elem << " ";
}
std::cout << std::endl;
// vector 示例
std::vector<int> myVector = {10, 20, 30, 40, 50};
myVector.insert(myVector.begin() + 1, 15); // 在第二个位置插入15
myVector.erase(myVector.begin() + 1); // 删除第二个位置元素
std::cout << "Vector elements: ";
for (auto elem : myVector) {
std::cout << elem << " ";
}
std::cout << std::endl;
// 访问元素
std::cout << "List element at position 2: " << *std::next(myList.begin(), 2) << std::endl;
std::cout << "Vector element at position 2: " << myVector[2] << std::endl;
return 0;
}
// 输出：
// List elements: 10 15 30 40 50
// Vector elements: 10 20 30 40 50
// List element at position 2: 30
// Vector element at position 2: 305.结语
通过这篇文章，我们深入探讨了 C++ 标准模板库中的 list 类，包括其构造函数、迭代器、容量获取与元素访问函数、修改函数及其他功能函数。我们还实现了一个简单的 list 模拟，并详细比较了 list 与 vector 的异同。希望通过这些内容，读者能够更全面地理解 list 的使用场景和实现原理，从而在实际编程中做出更加合理的数据结构选择，提高代码的效率和性能。
