【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
文章目录
- 从零实现 `list` 容器:细粒度剖析与代码实现
- 前言
- 1. `list` 的核心数据结构
- 1.1节点结构分析:
- 2. 迭代器设计与实现
- 2.1 为什么 `list` 需要迭代器?
- 2.2 实现一个简单的迭代器
- 2.2.1 迭代器代码实现:
- 2.2.2 解释:
- 2.3 测试简单迭代器
- 2.3.1 测试代码:
- 2.3.2 输出:
- 2.3.3 解释:
- 2.4 增加后向移动和 `->` 运算符
- 2.4.1关键点:
- 2.4.2 增加后向移动和 `->` 运算符的实现代码:
- 2.5 测试前后移动和 `->` 运算符
- 2.5.1 目的:
- 2.5.2 测试代码:
- 2.5.3 输出:
- 2.5.4 解释:
- 2.6 为什么不能简单使用 `const` 修饰?
- 2.6.1 问题解释:
- 2.6.2 为什么不能简单使用 `const` 修饰?
- 2.6.3 错误示例:直接使用 `const` 修饰
- 2.6.4 错误代码:
- 2.6.5 错误分析:
- 2.7 正确的解决方案:使用模板参数区分 `const` 和 `non-const`
- 2.7.1 使用模板参数的好处:
- 2.7.2 实现代码:
- 2.8 测试模板泛化后的迭代器
- 2.8.1 测试代码:
- 2.8.2 输出结果:
- 2.8.3 解释:
- 3. `list` 容器的基本操作
- 3.1 构造函数
- 3.2 构造函数分析:
- 4. 插入与删除操作
- 4.1 插入操作
- 4.1.1 插入操作分析:
- 4.2 删除操作
- 4.2.1 删除操作分析:
- 5. 反向迭代器的设计
- 5.1 反向迭代器分析:
- 6. 迭代器失效问题
- 6.1 删除操作中的迭代器失效
- 6.2 错误使用示例
- 6.3 解决方案
- 7. 总结与展望
- 完整的 `list` 容器实现代码
从零实现 list
容器:细粒度剖析与代码实现
接上篇【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
💬 欢迎讨论:学习过程中有问题吗?随时在评论区与我交流。你们的互动是我创作的动力!
👍 支持我:如果你觉得这篇文章对你有帮助,请点赞、收藏并分享给更多朋友吧!
🚀 一起成长:欢迎分享给更多对计算机视觉和图像处理感兴趣的小伙伴,让我们共同进步!
本文详细介绍如何从零开始实现一个 C++ list
容器,帮助读者深入理解 list
的底层实现,包括核心数据结构、迭代器的设计、以及常见的插入、删除等操作。从初学者到进阶开发者都能从中受益。
前言
在 C++ 标准模板库 (STL) 中,list
是一种双向链表容器,适合频繁的插入和删除操作。它与 vector
的主要区别在于 list
不支持随机访问,并且在进行插入、删除操作时无需移动其他元素。这使得 list
在某些需要大量动态修改元素的场景下具有独特优势,例如链表的插入删除操作具有 O(1) 的时间复杂度。
为了更好地理解 list
的工作原理,本文将从零开始实现一个简化版的 list
,并详细分析每个步骤背后的实现原理及其易错点。
1. list
的核心数据结构
在
list
的实现中,底层是通过双向链表结构来存储数据。双向链表中的每个节点不仅包含数据,还包含指向前一个节点和后一个节点的两个指针。以下是节点结构的定义:
namespace W {// 定义链表节点template<class T>struct ListNode {T _val; // 节点存储的值ListNode* _prev; // 指向前一个节点ListNode* _next; // 指向后一个节点ListNode(const T& val = T()) : _val(val), _prev(nullptr), _next(nullptr) {}};
}
1.1节点结构分析:
- _val:存储节点的数据。
- _prev 和 _next:分别指向前一个节点和后一个节点,便于实现双向链表的遍历、插入和删除操作。
该结构简单明了,双向链表的节点可以方便地进行前向和后向操作。接下来我们将实现如何使用该结构构建一个完整的 list
容器。
2. 迭代器设计与实现
2.1 为什么 list
需要迭代器?
在 C++ 中,
vector
是一种动态数组,元素在内存中是连续存储的,因此我们可以使用下标快速访问元素,例如vec[0]
可以直接访问vector
的第一个元素。而list
底层是通过链表结构实现的,每个节点在内存中的位置并不连续。因此,链表无法像数组一样通过下标随机访问元素。每个节点都通过指针链接到前一个节点(_prev
)和后一个节点(_next
)。为了遍历链表,我们需要使用迭代器。
迭代器的作用类似于一个指针,它指向链表中的某个节点,允许我们通过类似指针的方式来访问和操作链表节点。与普通指针不同,迭代器提供了更高级的功能,并且能够保持接口的一致性,因此它成为了 STL 容器中访问元素的核心工具。
2.2 实现一个简单的迭代器
为了实现最基本的链表迭代器,首先我们需要定义链表节点的结构。该结构已经在上文定义了。
接下来,我们将实现 ListIterator
,它内部保存一个指向 ListNode
的指针 _node
,并支持以下基本操作:
- 解引用操作:通过
*it
访问链表节点中的值。 - 前向移动操作:通过
++it
访问链表中的下一个节点。 - 比较操作:通过
it != end()
判断两个迭代器是否相等。
2.2.1 迭代器代码实现:
namespace W {template<class T>class ListIterator {typedef ListNode<T> Node; // 使用 Node 表示链表节点类型public:// 构造函数,接受一个指向链表节点的指针ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作,返回节点的值T& operator*() { return _node->_val; }// 前向移动操作,指向下一个节点ListIterator& operator++() {_node = _node->_next; // 将当前节点移动到下一个节点return *this; // 返回自身以支持链式调用}// 比较操作,判断两个迭代器是否相等bool operator!=(const ListIterator& other) const { return _node != other._node; }private:Node* _node; // 迭代器指向的链表节点};
}
2.2.2 解释:
- 构造函数:初始化一个指向链表节点的指针
_node
,用于遍历链表。 operator*
:返回节点存储的值_val
。operator++
:将迭代器移动到链表中的下一个节点。operator!=
:用于判断两个迭代器是否相等。
2.3 测试简单迭代器
为了验证我们刚刚实现的迭代器功能,先创建一些链表节点,并将它们链接成一个链表。然后我们使用迭代器遍历链表并输出每个节点的值。
2.3.1 测试代码:
#include <iostream>int main() {// 创建三个节点,分别存储值 1、2、3W::ListNode<int> node1(1); W::ListNode<int> node2(2); W::ListNode<int> node3(3); // 链接节点形成链表node1._next = &node2; // node1 的下一个节点是 node2node2._prev = &node1; // node2 的前一个节点是 node1node2._next = &node3; // node2 的下一个节点是 node3node3._prev = &node2; // node3 的前一个节点是 node2// 创建迭代器,指向第一个节点W::ListIterator<int> it(&node1);// 使用迭代器遍历链表并输出每个节点的值while (it != nullptr) {std::cout << *it << std::endl; // 输出当前节点的值++it; // 前向移动到下一个节点}return 0;
}
2.3.2 输出:
1
2
3
2.3.3 解释:
- 迭代器
it
初始指向第一个节点node1
。 - 通过
*it
获取节点的值,并通过++it
将迭代器移动到下一个节点,直到链表末尾。
2.4 增加后向移动和 ->
运算符
目前的迭代器只能进行前向移动,而
list
是双向链表,因此我们还需要增加后向移动 (--
) 的功能,使迭代器可以从链表末尾向前遍历。同时,为了让迭代器像指针一样操作,我们还需要重载->
运算符,以便可以通过->
访问链表节点的成员。
2.4.1关键点:
-
当
_val
是基本数据类型(如int
)时,可以直接通过*it
来获取节点的值,而不需要使用*(it->)
。虽然*(it->)
语法上是正确的,但显得繁琐且不必要。为什么
*(it->)
是正确的?
因为it->
是在调用operator->()
,返回_val
的指针,然后*(it->)
解引用该指针。语法上是没有问题的,但通常我们直接使用*it
更简洁。 -
当
_val
是自定义类型时,可以使用it->x
直接访问自定义类型的成员变量x
。编译器会将it->x
优化为it.operator->()->x
,让访问更加方便。
2.4.2 增加后向移动和 ->
运算符的实现代码:
namespace W {template<class T>class ListIterator {typedef ListNode<T> Node;public:ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作,返回节点的值T& operator*() { return _node->_val; }// 指针操作,返回节点的指针T* operator->() { return &(_node->_val); }// 前向移动ListIterator& operator++() {_node = _node->_next;return *this;}// 后向移动ListIterator& operator--() {_node = _node->_prev;return *this;}// 比较操作bool operator!=(const ListIterator& other) const { return _node != other._node; }private:Node* _node;};
}
2.5 测试前后移动和 ->
运算符
2.5.1 目的:
我们通过一个测试程序验证迭代器的前向和后向移动功能,同时通过
->
运算符访问链表节点的值。我们会分别测试基本数据类型int
和自定义类型CustomType
的场景,展示迭代器在不同数据类型下的使用方式。
2.5.2 测试代码:
-
对于
int
类型,我们可以通过*it
来访问节点的值,而不需要使用*(it->)
,虽然*(it->)
也是合法的,但没有必要。 -
对于自定义类型
CustomType
,可以通过it->x
来访问自定义类型CustomType
中的成员变量x
。
#include <iostream>struct CustomType {int x;
};int main() {// 创建三个 int 类型的节点,分别存储值 1、2、3W::ListNode<int> node1(1); W::ListNode<int> node2(2); W::ListNode<int> node3(3); // 链接节点形成链表node1._next = &node2;node2._prev = &node1;node2._next = &node3;node3._prev = &node2;// 创建迭代器,初始指向第二个节点W::ListIterator<int> it(&node2);// 对于 int 类型,使用 *it 访问节点的值std::cout << *it << std::endl; // 输出 2// 后向移动,指向第一个节点--it;std::cout << *it << std::endl; // 输出 1// 前向移动,指向第三个节点++it;++it;std::cout << *it << std::endl; // 输出 3// 创建自定义类型 CustomType 的节点W::ListNode<CustomType> customNode1({1});W::ListNode<CustomType> customNode2({2});customNode1._next = &customNode2;customNode2._prev = &customNode1;// 创建自定义类型 CustomType 的迭代器W::ListIterator<CustomType> customIt(&customNode1);// 使用 it-> 访问 CustomType 的成员变量 xstd::cout << customIt->x << std::endl; // 输出 1return 0;
}
2.5.3 输出:
2
1
3
1
2.5.4 解释:
- 对于
int
类型的节点,我们通过*it
访问节点的值,++it
和--it
分别实现了前向和后向移动。 - 对于自定义类型
CustomType
的节点,通过it->x
可以访问自定义类型成员变量x
。编译器会将it->x
优化为it.operator->()->x
,使得操作简化。
2.6 为什么不能简单使用 const
修饰?
2.6.1 问题解释:
在 vector
中,const_iterator
通过 const
修饰符即可实现不可修改的迭代器,这是因为 vector
的底层存储是连续的内存块,通过 const
限制访问的值即可。而 list
的底层是双向链表,迭代器不仅需要访问链表节点的值,还需要操作链表的前驱和后继节点(即 _prev
和 _next
指针)。直接使用 const
修饰迭代器无法满足这些需求,因为 const
限制了对链表结构的必要修改。
2.6.2 为什么不能简单使用 const
修饰?
const
修饰的迭代器会限制所有成员的修改,包括迭代器内部的_node
指针。如果我们对const
迭代器执行++
或--
操作,这些操作会修改_node
,而const
禁止这种修改。
2.6.3 错误示例:直接使用 const
修饰
下面是一个简单的错误示例,展示了为什么简单地使用 const
修饰符会导致问题:
2.6.4 错误代码:
#include <iostream>template<class T>
struct ListNode {T _val;ListNode* _prev;ListNode* _next;ListNode(T val) : _val(val), _prev(nullptr), _next(nullptr) {}
};template<class T>
class ListIterator {typedef ListNode<T> Node;public:ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作,返回节点的值T& operator*() { return _node->_val; }// 前向移动ListIterator& operator++() {_node = _node->_next;return *this;}// 后向移动ListIterator& operator--() {_node = _node->_prev;return *this;}private:Node* _node;
};int main() {// 创建三个节点,分别存储值 1、2、3ListNode<int> node1(1), node2(2), node3(3);// 链接节点形成链表node1._next = &node2;node2._prev = &node1;node2._next = &node3;node3._prev = &node2;// 尝试创建一个 const 迭代器const ListIterator<int> constIt(&node1);// 错误1:前向移动时,编译器报错,因为 ++ 操作符不能对 const 迭代器操作++constIt; // 编译错误// 错误2:解引用操作也无法进行修改*constIt = 5; // 编译错误
}
2.6.5 错误分析:
-
无法执行前向移动 (
++constIt
):由于const
修饰符限制了修改成员变量_node
,因此++
操作无法执行,因为该操作会修改迭代器的内部指针。 -
无法修改节点的值 (
*constIt = 5
):由于迭代器是const
的,解引用操作也不能用于修改节点的值,因此编译器会报错。
2.7 正确的解决方案:使用模板参数区分 const
和 non-const
为了处理上述问题,我们可以使用模板参数来区分 const
和 non-const
的情况。通过模板参数 Ref
和 Ptr
,我们可以控制迭代器的行为,使得它在常量链表和非常量链表中都能正常工作。
2.7.1 使用模板参数的好处:
- 灵活性:可以根据需要处理
const
和non-const
的迭代器场景。 - 安全性:对于常量链表,保证不能修改节点的值;对于非常量链表,允许修改。
- 代码复用:通过模板参数,既可以编写一套代码,处理
const
和non-const
两种情况。
2.7.2 实现代码:
namespace W {template<class T, class Ref, class Ptr>class ListIterator {typedef ListNode<T> Node; // 使用 Node 表示链表节点类型public:ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作,返回节点的值Ref operator*() const { return _node->_val; }// 指针操作,返回节点的值的指针Ptr operator->() const { return &_node->_val; }// 前向移动ListIterator& operator++() {_node = _node->_next;return *this;}// 后向移动ListIterator& operator--() {_node = _node->_prev;return *this;}// 比较操作,判断两个迭代器是否相等bool operator!=(const ListIterator& other) const { return _node != other._node; }private:Node* _node;};
}
2.8 测试模板泛化后的迭代器
现在我们通过测试来验证模板参数 Ref
和 Ptr
的设计是否能够正确处理常量链表和非常量链表的迭代器情况。以下场景将会被测试:
- 非常量链表:迭代器允许修改节点的值。
- 常量链表:
const
迭代器只能读取节点值,不能修改。
2.8.1 测试代码:
#include <iostream>struct CustomType {int x;
};int main() {// 创建三个 int 类型的节点,分别存储值 1、2、3W::ListNode<int> node1(1); W::ListNode<int> node2(2); W::ListNode<int> node3(3); // 链接节点形成链表node1._next = &node2;node2._prev = &node1;node2._next = &node3;node3._prev = &node2;// 创建一个非常量迭代器W::ListIterator<int, int&, int*> it(&node1);std::cout << *it << std::endl; // 输出 1++it; // 前向移动std::cout << *it << std::endl; // 输出 2// 修改节点的值*it = 20;std::cout << *it << std::endl; // 输出 20// 创建一个常量链表节点const W::ListNode<int> constNode1(1);const W::ListNode<int> constNode2(2);constNode1._next = &constNode2;// 创建一个常量迭代器W::ListIterator<int, const int&, const int*> constIt(&constNode1);std::cout << *constIt << std::endl; // 输出 1// 常量迭代器不允许修改值// *constIt = 10; // 错误:无法修改常量链表节点的值return 0;
}
2.8.2 输出结果:
1
2
20
1
2.8.3 解释:
- 非常量链表:
- 使用
it
迭代器遍历链表,前向移动并修改节点的值。*it = 20
修改了第二个节点的值。
- 使用
- 常量链表:
- 使用
constIt
迭代器只能读取节点的值,无法修改。如果尝试*constIt = 10
,编译器会报错,禁止修改。
- 使用
3. list
容器的基本操作
3.1 构造函数
我们将实现多种构造函数,允许用户创建空链表、指定大小的链表,以及从迭代器区间构造链表。
namespace W {template<class T>class list {typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;// 默认构造函数list() { CreateHead(); }// 指定大小的构造函数list(size_t n, const T& val = T()) {CreateHead();for (size_t i = 0; i < n; ++i)push_back(val);}// 迭代器区间构造函数template<class Iterator>list(Iterator first, Iterator last) {CreateHead();while (first != last) {push_back(*first);++first;}}// 析构函数~list() {clear();delete _head;}// 头节点初始化void CreateHead() {_head = new Node();_head->_next = _head;_head->_prev = _head;}// 清空链表void clear() {Node* cur = _head->_next;while (cur != _head) {Node* next = cur->_next;delete cur;cur = next;}_head->_next = _head;_head->_prev = _head;}private:Node* _head; // 指向头节点的指针};
}
3.2 构造函数分析:
- 默认构造函数:创建一个空链表,并初始化头节点。
- 指定大小构造函数:使用
push_back
向链表中插入n
个值为val
的节点。 - 迭代器区间构造函数:通过一对迭代器
[first, last)
形成的区间构造链表。
4. 插入与删除操作
list
容器的优势在于高效的插入与删除操作。我们将在指定位置插入节点,或删除指定节点,插入和删除的时间复杂度均为 O(1)。
4.1 插入操作
namespace W {template<class T>class list {typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:// 在指定位置前插入新节点iterator insert(iterator pos, const T& val) {Node* newNode = new Node(val);Node* cur = pos._node;newNode->_next = cur;newNode->_prev = cur->_prev;cur->_prev->_next = newNode;cur->_prev = newNode;return iterator(newNode);}// 在链表末尾插入新节点void push_back(const T& val) { insert(end(), val); }// 在链表头部插入新节点void push_front(const T& val) { insert(begin(), val); }};
}
4.1.1 插入操作分析:
- 插入效率:由于链表的结构,插入操作只需调整节点的指针,不涉及大规模的内存移动,时间复杂度为 O(1)。
- 头尾插入:通过
push_back
和push_front
可以方便地在链表的头部和尾部插入新节点。
4.2 删除操作
namespace W {template<class T>class list {typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:// 删除指定位置的节点iterator erase(iterator pos) {Node* cur = pos._node;Node* nextNode = cur->_next;cur->_prev->_next = cur->_next;cur->_next->_prev = cur->_prev;delete cur;return iterator(nextNode);}// 删除链表头部节点void pop_front() { erase(begin()); }// 删除链表尾部节点void pop_back() { erase(--end()); }};
}
4.2.1 删除操作分析:
- 删除效率:删除节点同样是通过调整指针实现,时间复杂度为 O(1)。
- 头尾删除:通过
pop_front
和pop_back
实现头部和尾部节点的删除。
5. 反向迭代器的设计
在双向链表中,反向迭代器可以通过包装普通迭代器实现。反向迭代器的 ++
对应正向迭代器的 --
,反之亦然。
namespace W {template<class Iterator>class ReverseListIterator {Iterator _it;public:ReverseListIterator(Iterator it) : _it(it) {}auto operator*() { Iterator temp = _it; --temp; return *temp; }auto operator->() { return &(operator*()); }ReverseListIterator& operator++() { --_it; return *this; }ReverseListIterator operator++(int) { ReverseListIterator temp = *this; --_it; return temp; }ReverseListIterator& operator--() { ++_it; return *this; }ReverseListIterator operator--(int) { ReverseListIterator temp = *this; ++_it; return temp; }bool operator==(const ReverseListIterator& other) const { return _it == other._it; }bool operator!=(const ReverseListIterator& other) const { return !(*this == other); }};
}
5.1 反向迭代器分析:
- 解引用和指针操作:反向迭代器的
operator*
和operator->
实际上是操作前一个节点。 - 前向和后向移动:反向迭代器的
++
操作是通过调用普通迭代器的--
来实现的。
6. 迭代器失效问题
在操作 list
容器时,特别是在删除节点的过程中,可能会出现迭代器失效问题。迭代器失效是指当某个节点被删除后,指向该节点的迭代器变得无效,继续使用这个迭代器将导致未定义行为。因此,在删除节点后,必须使用返回的迭代器进行下一步操作,以避免迭代器失效问题。
6.1 删除操作中的迭代器失效
假设我们使用 erase
函数删除链表中的节点。如果我们继续使用之前的迭代器而不更新它,程序将会崩溃,因为该迭代器指向的内存已经被释放。
void TestIteratorInvalidation() {W::list<int> lst = {1, 2, 3, 4, 5};auto it = lst.begin();while (it != lst.end()) {it = lst.erase(it); // 正确:使用 erase 返回的新迭代器}
}
6.2 错误使用示例
下面的示例展示了错误的迭代器使用方式,迭代器在删除操作后没有更新,导致其指向了已被释放的内存。
void WrongIteratorUsage() {W::list<int> lst = {1, 2, 3, 4, 5};auto it = lst.begin();while (it != lst.end()) {lst.erase(it); // 错误:删除后 it 失效++it; // 未更新的迭代器继续操作,导致崩溃}
}
6.3 解决方案
为了解决迭代器失效问题,每次删除节点后都要使用 erase
返回的新迭代器,确保迭代器指向的内存有效。
void CorrectIteratorUsage() {W::list<int> lst = {1, 2, 3, 4, 5};auto it = lst.begin();while (it != lst.end()) {it = lst.erase(it); // 正确:每次使用 erase 返回的新迭代器}
}
7. 总结与展望
通过这篇文章,我们从零开始模拟实现了一个 list
容器,并深入剖析了以下几个方面:
- 双向链表的核心数据结构:理解链表节点的
_prev
和_next
指针,以及如何通过它们实现双向遍历。 - 迭代器的设计:实现了
list
的正向和反向迭代器,支持前向移动、后向移动和解引用操作。 - 模板参数解决
const
和non-const
场景:通过模板参数Ref
和Ptr
,灵活应对const
链表和非常量链表的不同需求,保证代码的安全性和灵活性。 - 插入与删除操作:高效的插入和删除操作,时间复杂度均为 O(1),体现了链表结构的优势。
- 反向迭代器的实现:通过包装普通迭代器,设计了一个反向迭代器,方便反向遍历链表。
- 迭代器失效问题:讲解了迭代器失效的原因及其解决方法,避免了未定义行为。
今后,读者您可以尝试进一步扩展这篇文章中的 list
容器,例如:
- 实现更多的容器操作:如
find
、sort
等高级操作。 - 实现与 STL 接口兼容的完整
list
容器:包括迭代器失效的处理、异常安全的插入与删除操作。 - 性能优化与内存管理:如使用自定义的内存池优化链表的节点分配和释放。
通过持续的实践和优化,我们能够更深入地理解 C++ 标准库的实现细节,并在开发过程中提高代码的效率和健壮性。
完整的 list
容器实现代码
最后,附上完整的代码实现,包括链表节点结构、迭代器、插入删除操作等。
namespace W {// 链表节点结构template<class T>struct ListNode {T _val;ListNode* _prev;ListNode* _next;ListNode(const T& val = T()) : _val(val), _prev(nullptr), _next(nullptr) {}};// 正向迭代器template<class T, class Ref, class Ptr>class ListIterator {typedef ListNode<T> Node;public:ListIterator(Node* node = nullptr) : _node(node) {}Ref operator*() const { return _node->_val; }Ptr operator->() const { return &_node->_val; }ListIterator& operator++() {_node = _node->_next;return *this;}ListIterator& operator--() {_node = _node->_prev;return *this;}bool operator!=(const ListIterator& other) const { return _node != other._node; }private:Node* _node;};// 反向迭代器template<class Iterator>class ReverseListIterator {Iterator _it;public:ReverseListIterator(Iterator it) : _it(it) {}auto operator*() { Iterator temp = _it; --temp; return *temp; }auto operator->() { return &(operator*()); }ReverseListIterator& operator++() { --_it; return *this; }ReverseListIterator operator++(int) { ReverseListIterator temp = *this; --_it; return temp; }ReverseListIterator& operator--() { ++_it; return *this; }ReverseListIterator operator--(int) { ReverseListIterator temp = *this; ++_it; return temp; }bool operator==(const ReverseListIterator& other) const { return _it == other._it; }bool operator!=(const ReverseListIterator& other) const { return !(*this == other); }};// list 容器实现template<class T>class list {typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:list() { CreateHead(); }list(size_t n, const T& val = T()) {CreateHead();for (size_t i = 0; i < n; ++i)push_back(val);}~list() {clear();delete _head;}iterator begin() { return iterator(_head->_next); }iterator end() { return iterator(_head); }void push_back(const T& val) { insert(end(), val); }void push_front(const T& val) { insert(begin(), val); }iterator insert(iterator pos, const T& val) {Node* newNode = new Node(val);Node* cur = pos._node;newNode->_next = cur;newNode->_prev = cur->_prev;cur->_prev->_next = newNode;cur->_prev = newNode;return iterator(newNode);}iterator erase(iterator pos) {Node* cur = pos._node;Node* nextNode = cur->_next;cur->_prev->_next = cur->_next;cur->_next->_prev = cur->_prev;delete cur;return iterator(nextNode);}void pop_front() { erase(begin()); }void pop_back() { erase(--end()); }void clear() {Node* cur = _head->_next;while (cur != _head) {Node* next = cur->_next;delete cur;cur = next;}_head->_next = _head;_head->_prev = _head;}private:void CreateHead() {_head = new Node();_head->_next = _head;_head->_prev = _head;}Node* _head;};
}
以上就是关于【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析的内容啦,各位大佬有什么问题欢迎在评论区指正,或者私信我也是可以的啦,您的支持是我创作的最大动力!❤️
相关文章:

【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
文章目录 从零实现 list 容器:细粒度剖析与代码实现前言1. list 的核心数据结构1.1节点结构分析: 2. 迭代器设计与实现2.1 为什么 list 需要迭代器?2.2 实现一个简单的迭代器2.2.1 迭代器代码实现:2.2.2 解释: 2.3 测试…...

【C#生态园】打造现代化跨平台应用:深度解析.NET桌面应用工具
选择最适合你的.NET UI框架:全面解析六种热门选择 前言 在现代软件开发中,选择合适的桌面应用框架和UI库对于开发人员来说至关重要。本文将介绍几种流行的.NET桌面应用框架和UI库,包括Eto.Forms、Avalonia、ReactiveUI、MahApps.Metro、Mat…...

第二十一章 (动态内存管理)
1. 为什么要有动态内存分配 2. malloc和free 3. calloc和realloc 4. 常⻅的动态内存的错误 5. 动态内存经典笔试题分析 6. 总结C/C中程序内存区域划分 1.为什么要有动态内存管理 我们目前已经掌握的内存开辟方式有 int main() {int num 0; //开辟4个字节int arr[10] …...

机器学习框架总结
机器学习框架是用于构建、训练、评估和部署机器学习模型的工具和库的集合。它们简化了模型开发过程,并提供了预构建的功能、优化的计算性能和对深度学习、监督学习、无监督学习等技术的支持。下面是一些主要的机器学习框架的详细介绍: 1. TensorFlow 1…...

docker pull 超时的问题如何解决
docker不能使用,使用之前的阿里云镜像失败。。。 搜了各种解决方法,感谢B站UP主 <iframe src"//player.bilibili.com/player.html?isOutsidetrue&aid113173361331402&bvidBV1KstBeEEQR&cid25942297878&p1" scrolling"…...

【数学分析笔记】第4章第3节 导数四则运算和反函数求导法则(2)
4. 微分 4.3 导数四则运算与反函数求导法则 双曲正弦函数 sh x e x − e − x 2 \sh x\frac{e^x-e^{-x}}{2} shx2ex−e−x 双曲余弦函数 ch x e x e − x 2 \ch x\frac{e^xe^{-x}}{2} chx2exe−x ch 2 x − sh 2 x 1 \ch^2 x-\sh^2 x1 ch2x−sh2x1 ( e…...

【2024】基于mysqldump的数据备份与恢复
基于mysqldump备份与恢复 mysqldump是一个用于备份 MySQL 数据库的实用工具。 它可以将数据库的结构(如数据库、表、视图、存储过程等的定义)和数据(表中的记录)导出为文本文件,这些文本文件可以包含 SQL 语句&#…...

家用无线路由器配置
一.首先进行线路连接。如下图:"光猫LAN口"—网线—"路由器WAN口"。 注意:家用光纤宽带一般选择使用200兆宽带到1000兆,如果网速不达标请查看路由器是否是千兆路由器。千兆路由器通常是双频的,支持两个信号一个…...

模拟算法(4)_外观数列
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 模拟算法(4)_外观数列 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌 目录 1. 题目链…...

vsomeip用到的socket
概述: vsomeip用到的socket的代码全部都在implementation\endpoints目录下面,主要分布在下面六个endpoint类中: local_client_endpoint_impl // 本地客户端socket(UDS Socket或者127.0.0.1的socket)local_server…...

MFC有三个选项:MFC ActiveX控件、MFC应用程序、MFC DLL,如何选择?
深耕AI:互联网行业 算法研发工程师 目录 MFC ActiveX 控件 控件的类型 标准控件 自定义控件 ActiveX控件 MFC ActiveX控件 标准/自定义控件 MFC ActiveX控件分类 3种MFC如何选择? MFC ActiveX控件 MFC 应用程序 MFC DLL 总结 举例说明…...

边缘概率 | 条件概率
关于什么是边缘概率分布和条件概率分布,在理论上,我自己也还没有理解,那么现在就根据我学习到的理解方式来记录一下,有错误指出,请大家指正!!! 例如,一个箱子里有十个乒乓…...

深入浅出:现代JavaScript开发者必知必会的Web性能优化技巧
亲爱的读者们,欢迎来到本期博客。今天,我们将深入探讨JavaScript开发者在日常工作中如何提升Web性能。在快节奏的Web开发世界中,性能优化至关重要。本文将分享一些实用技巧,帮助你构建快速、高效的Web应用。 1. 使用CDN加速资源加…...

【S32K3 RTD LLD篇5】K344 ADC SW+HW trigger
【S32K3 RTD LLD篇5】K344 ADC SWHW trigger 一,文档简介二,ADC SW HW 触发2.1 软硬件平台2.2 SWADC 软件触发2.3 SWBCTUADC 软件BCTU触发2.4 PITTRIGMUXADC 硬件PIT TRIGUMX触发2.5 EMIOSBCTUHWADC硬件EMIOS BCTU触发2.6 EMIOSBCTUHW LISTADC硬件EMIOS …...

TransFormer 视频笔记
TransFormer BasicsAttention单头注意力 single head attentionQ: query 查寻矩阵 128*12288K key matrix 128*12288SoftMax 归一 Value matrix 12288*12288 MLP Bas…...

前端的混合全栈之路Meteor篇(三):发布订阅示例代码及如何将Meteor的响应数据映射到vue3的reactive系统
Meteor 3.0 是一个功能强大的全栈 JavaScript 框架,特别适合实时应用程序的开发。它的核心机制之一就包括发布-订阅(Publish-Subscribe)模型,它允许服务器端发布数据,客户端订阅并实时更新。本文将介绍如何在 Meteor 3…...

自动驾驶系列—颠覆未来驾驶:深入解析自动驾驶线控转向系统技术
🌟🌟 欢迎来到我的技术小筑,一个专为技术探索者打造的交流空间。在这里,我们不仅分享代码的智慧,还探讨技术的深度与广度。无论您是资深开发者还是技术新手,这里都有一片属于您的天空。让我们在知识的海洋中…...

Webstorm 中对 Node.js 后端项目进行断点调试
首先,肯定需要有一个启动服务器的命令脚本。 然后,写一个 debug 的配置: 然后,debug 模式 启动项目和 启动调试服务: 最后,发送请求,即可调试: 这几个关键按钮含义: 重启…...

VUE前后端分离毕业设计题目项目有哪些,VUE程序开发常见毕业论文设计推荐
目录 0 为什么选择Vue.js 1 Vue.js 的主要特点 2 前后端分离毕业设计项目推荐 3 后端推荐 4 总结 0 为什么选择Vue.js 使用Vue.js开发计算机毕业设计是一个很好的选择,因为它不仅具有现代前端框架的所有优点,还能让你专注于构建高性能、高可用性的W…...

一、Spring Boot集成Spring Security之自动装配
Spring Boot集成Spring Security之自动装配介绍 一、实现功能及软件版本说明二、创建Spring Boot项目三、查看自动装配配置类四、自动装配配置类之SecurityAutoConfiguration1、SecurityAutoConfiguration部分源码2、主要作用3、SpringBootWebSecurityConfiguration3.1、Spring…...

计数相关的题 Python 力扣
2284. 最多单词数的发件人 给你一个聊天记录,共包含 n 条信息。给你两个字符串数组 messages 和 senders ,其中 messages[i] 是 senders[i] 发出的一条 信息 。 一条 信息 是若干用单个空格连接的 单词 ,信息开头和结尾不会有多余空格。发件…...

Express内置的中间件(express.json和express.urlencoded)格式的请求体数据
目录 Express内置的中间件 express.json 中间件的使用 express.urlencoded 中间件的使用 express.urlencoded([options]) 解析req.body的兼容写法 Express内置的中间件 自 Express 4.16.0 版本开始,Express 内置了 3 个常用的中间件,极大的提高了 …...

cmakelist加载Qt模块
Qt编程中,cmakelist会自动添加Core,Gui,Widgets模块,有时需要添加新的Qt的模块。在命令find_package中搜索要新增的模块,在命令target_link_libraries中添加要新增的模块。 比如要使用QUiLoader类,要增加对…...

8-2.Android 任务之 CountDownTimer 编码模板(开启计时器、取消计时器)
一、CountDownTimer 1、概述 CountDownTimer 是 Android 中一个用于执行定时操作的类 CountDownTimer 主要应用于在指定时间段内完成某项任务,或者每隔一段时间触发某项任务 2、使用步骤 创建 CountDownTimer:创建 CountDownTimer 就是创建它的匿名…...

Servlet的生命周期及用户提交表单页面的实现(实验报告)
一、实验目的、要求 1. 掌握Servlet的定义,即Servlet是运行在服务器端的Java程序,用于扩展服务器的功能。 2. 学习和掌握在开发环境中搭建Servlet应用所需的工具,如Tomcat服务器、IDEA等。 二、实验内容 根据本章所学知识,实验…...

【Router】路由功能之IP过滤(IP Filter)功能(基于端口)介绍及实现
IP过滤(IP Filter) IP Filter是一种通过对网络数据包中的 IP 地址进行分析和筛选,以实现对网络流量的控制和管理的技术。 IP过滤(IP Filter)作用 安全防护 可以阻止来自特定 IP 地址或 IP 地址范围的恶意攻击、非法访问等,增强网络的安全性。 流量管理 根据不同的 IP …...

数据结构_2.2、顺序表插入删除查找
1、线性表的顺序存储表示定义: 线性表:是具有相同数据类型的n (n≥0)个数据元素的有限序列 顺序表:用顺序存储的方式实现线性表 顺序存储:把逻辑上相邻的元素存储在物理 位置上也相邻的存储单元中&#…...

嵌入式C语言自我修养:编译链接
源文件生成可执行文件的过程? 源文件经过预处理、编译、汇编、链接生成一个可执行的目标文件。 编译器驱动程序,包括预处理器、编译器、汇编器和链接器。Linux用户可以调用GCC驱动程序来完成整个编译流程。 使用GCC驱动程序将示例程序从ASCII码源文件转换…...

Mac制作Linux操作系统启动盘
前期准备 一个 Mac 电脑 一个 U 盘(8GB 以上) 下载好 Linux 系统镜像(iso 文件) 具体步骤 挂载 U 盘 解挂 U 盘 写系统镜像到 U 盘 完成 一、挂载 U 盘 首先插入 U 盘,打开终端输入下面的命令查看 U 盘是否已经 m…...

PHP语言发展历程
PHP是一种开源的服务器端脚本语言,主要用于Web开发,最初由Rasmus Lerdorf在1994年创建。PHP的发展历程如下: PHP的起源:1994年,Rasmus Lerdorf创建了PHP的第一个版本,最初是一套用于跟踪他个人简历访问的C…...