【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…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...