🔥个人主页：Quitecoder
🔥专栏：c++笔记仓
朋友们大家好，本篇文章来到list有关部分，这一部分函数与前面的类似，我们简单讲解，重难点在模拟实现时的迭代器有关实现
目录
- `1.List介绍`
- `2.接口函数`
- `operations`
- `3.模拟实现`
- `3.1基本框架`
- `3.2 list的基本函数`
- `3.3迭代器的封装和实现`
- `++等重载函数的实现`
- `与list的关联`
- `3.4list函数完善`
- `3.5迭代器进一步完善`
- `const迭代器`
- `合并两种迭代器`
1.List介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素）
所以list本质就是我们的双向循环链表，我们接下来看它的接口函数
2.接口函数
构造函数
这里的构造函数与vector类似
- Default constructor (构造一个空的 std::list):
std::list myList1; // 创建一个空的整型链表
- Fill constructor (构造一个有特定数量元素且每个元素都有相同初始值的 std::list):
std::list myList2(5, 10); // 创建一个有5个元素的链表，每个元素都初始化为10
- Range constructor (从另一个迭代器定义范围的容器中构建 std::list):
std::vector myVector{1, 2, 3, 4, 5}; std::list myList3(myVector.begin(), myVector.end()); // 使用vector的范围来初始化链表- Copy constructor (使用另一个 std::list 来构造一个新的 std::list, 是副本):
std::list myOriginalList{1, 2, 3, 4, 5}; std::list myList4(myOriginalList); // 使用另一个list来初始化这个新的list每个构造函数都有它们独特的用途，可以根据具体需要选择合适的构造函数进行对象的创建和初始化。
- 默认构造函数创建一个没有任何元素的空链表。
- 填充构造函数允许创建一个包含特定数量相同值的元素的链表。
- 范围构造函数可以从任何提供迭代器接口的其他容器复制元素。
- 拷贝构造函数创建了一个当前list的副本。
填充构造函数前面的explicit关键字表明这个构造函数不能用于隐式转换或复制初始化，它需要直接调用来构造对象。其他构造函数则根据是否带有explicit关键字来决定是否能用于隐式转换或复制初始化
迭代器
迭代器用来遍历链表，下面是迭代器的简单使用
list lt = { 10,20,30,40,50 }; list::iterator i1 = lt.begin(); while (i1 != lt.end()) { cout cout int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list l.erase(it); ++it; } } int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list l.erase(it++); // it = l.erase(it); } } 1, 2, 3}; std::list4, 5, 6}; list1.splice(list1.end(), list2); // 把list2的所有元素移动到list1的末尾 1, 2, 3, 3, 4, 3, 5}; myList.remove(3); // 移除所有值为3的元素 1, 2, 3, 4, 5}; myList.remove_if([](int n){ return n % 2 == 0; }); // 移除myList中所有偶数元素 1, 1, 2, 2, 2, 3, 4, 4, 5, 5}; myList.unique(); // 移除相邻重复的元素，列表变为1, 2, 3, 4, 5 1, 3, 5}; std::list2, 4, 6}; list1.merge(list2); // 合并两个列表为1, 2, 3, 4, 5, 6 4, 3, 5, 2, 1}; myList.sort(); // 排序列表为1, 2, 3, 4, 5 1, 2, 3, 4, 5}; myList.reverse(); // 反转后列表为5, 4, 3, 2, 1 template ListNode} }; template typedef ListNode ListNode} }; typedef ListNode _head = new Node; _head-_next = _head; _head-_prev = _head; _size = 0; } Node* newnode = new Node(x); Node* tail = _head-_prev; tail-_next = newnode; newnode-_prev = tail; newnode-_next = _head; _head->_prev = newnode; _size++; }
- 获取尾节点，即head的上一个位置
- 更新四个指针即可
那我们完成了尾插工作，接下来如何实现下面的遍历呢？
void test1() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_front(6); list::iterator it = lt.begin(); while (it != lt.end()) { cout typedef ListNode} }; public: // 这是一个嵌套类型的别名定义。 typedef ListIterator public: typedef ListIterator} _node = _node-_next; return *this; } Self tmp(*this); _node = _node-_next; return tmp; } _node = _node-_prev; return *this; } Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }🔥operator*()
这里解引用得到节点的值，需要我们自己手动重载实现：
T& operator*() { return _node->_data; }🔥operator!=()
我们在循环中还有判断两个迭代器不相等，本质就是两个节点指针不相等
bool operator!=(const Self& it) { return _node != it._node; }基本完成类的封装后，我们需要把它和list连起来
与list的关联
这里begin和end只能由list提供
template class list { typedef ListNode Node; public: typedef ListIterator iterator; iterator begin() { return iterator(_head->_next);//匿名对象 } iterator end() { return iterator(_head);//最后一个位置的下一个位置 } '''''''''''''''''''''''''''''''''''' //其他函数 private: Node* _head; size_t _size; };begin返回第一个数据的迭代器，end返回最后一个数据的下一个位置
测试代码：
void test1() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list::iterator it = lt.begin(); while (it != lt.end()) { cout Node* cur = pos._node;//拿到这个位置的节点 Node* newnode = new Node(val); Node* prev = cur-_prev; prev-_next = newnode; newnode-_prev = prev; newnode->_next = cur; cur->_prev = newnode; _size++; }🔥erase()
iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return iterator(next); }erase删除返回的是下一个位置的迭代器
🔥头尾删插
有了insert和erase，我们这几个函数就可以直接进行复用
void push_front(const T& x) { insert(begin(), x); } void push_back(const T& x) { insert(end(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }与size相关函数：
size_t size()const { return _size; } bool empty() { return _size == 0; }🔥链表销毁
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); delete _head; _head = nullptr; }3.5迭代器进一步完善
对于下面的这种类
struct A { int _a1; int _a2; A(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} };如果list存的是上面的自定义类型呢？
插入有以下几种方法：
void test_list2() { list lt; A aa1(1, 1); A aa2 = { 1, 1 }; lt.push_back(aa1); lt.push_back(aa2); lt.push_back(A(2, 2)); lt.push_back({ 3, 3 }); lt.push_back({ 4, 4 }); }上面代码使用不同方式来创建和插入 A 类型的对象到自定义的 list 容器中。下面是每种方式的详细说明以及它们所涉及的概念：
-
有名对象的直接插入:
A aa1(1, 1); lt.push_back(aa1);
这里，首先创建了一个命名对象 aa1，使用了 A 的构造函数 A(int a1, int a2) 并为其提供了两个参数。然后，你将 aa1 作为参数传递给 lt.push_back() 函数。在这种情况下，aa1 是有名对象（也就是说，它有一个名称），并且 push_back 函数接受到的是 aa1 的一个副本
-
多参数隐式类型转换:
A aa2 = { 1, 1 }; lt.push_back(aa2);aa2 通过列表初始化的方式被创建。这里的列表初始化允许直接用花括号 {} 来初始化对象。C++11 引入的列表初始化特性可以用来初始化任何对象，包括具有构造函数的对象。创建了 aa2 有名对象并将其插入到列表中
-
通过构造函数创建匿名对象并插入:
lt.push_back(A(2, 2));
在这里，没有给新创建的 A 对象一个名字，因此它是一个匿名对象（也称作临时对象）。这个匿名的 A 对象是通过调用它的构造函数来直接初始化的，并立即被传递到 push_back 函数中。
-
通过隐式类型转换创建匿名对象并插入:
lt.push_back({ 3, 3 });与第三种方式类似，创隐式类型转换建了一个匿名的 A 对象，但这次是通过。初始化时没有使用相应类型的构造函数，而是依赖编译器生成的代码来创建一个具有给定初始化列表的对象，并将其传递给 push_back 函数。
在所有这些情况中，实际插入到 list 容器中的都是 A
现在我们来进行遍历：
list::iterator it = lt.begin(); while (it != lt.end()) { cout return &_node-_data; }
p这里返回的是_data的地址/p p我们就可以这样访问：/p pre class="brush:python;toolbar:false"cout -
- 如果这个类型有一个 operator-> 的重载，编译器就调用 it.operator->()
- it.operator->() 应该返回一个指向对象的指针，这个对象有一个我们尝试访问的 member 成员
- 编译器取得这个指针，并继续访问 member
这个流程只需要一个 -> 即可。编译器在背后处理了所有操作，直到访问到一个实际对象，然后这个对象的成员可以直接通过 -> 运算符访问
因此，我们不需要手动写成 it->->member；只需写 it->member 即可。编译器会自动将其 “转换” 为 it.operator->()->member
在 ListIterator 示例里，it->_a1 意味着：
- 调用 it.operator->() 拿到 ListNode 中 _data 成员的地址（这是一个 A 类型的对象）。
- 使用返回的指针来访问 A 对象的 _a1 成员。
整个过程对于编程者来说是透明的，不需要编写多个 ->。这种处理方式使得重载 -> 可以更自然地使用，就像处理普通的指针一样。
const迭代器
我们上面写的迭代器对于const对象是无法编译成功的，const不能调用非const成员函数
对于const类迭代器，我们需要在list类里面重新增加重载：
typedef ConstListIterator const_iterator; const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; }使普通版本调用普通版本，const调用const版本
这里的const迭代器不能是下面这种形式，而需单独创建版本：
const iterator end() const { return _head; }因为const迭代器的本质是迭代器指向的内容不能修改，而不是迭代器本身不能修改
const iterator这样定义是迭代器不能修改，内容还是可以修改的
那我们如何实现const迭代器呢？
方法一：单独实现一个类，修改正常版本的迭代器
template struct ConstListIterator { typedef ListNode Node; typedef ConstListIterator Self; Node* _node; ListIterator(Node* node) :_node(node) {} const T* operator->() { return &_node->_data; } const T& 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) { return _node != it._node; } };我们目的是不修改指向的值，只需要在这两个函数前面加上const即可：
const T* operator->() { return &_node->_data; } const T& operator*() { return _node->_data; }
我们这两个类只有这两个函数不同，那么能不能将他们两个合并呢？
合并两种迭代器
这里仅是两种返回类型不同，这里我们利用模版来对这里内容进行合并
template struct ListIterator { typedef ListNode Node; typedef ListIterator Self; Node* _node; ListIterator(Node* node) :_node(node) {} // *it //T& operator*() Ref operator*() { return _node->_data; } // it-> //T* operator->() Ptr operator->() { return &_node->_data; } };我们只提取不同的部分，其他部分与原来相同
Ref代表引用，Ptr代表指针
让我们来看一下这个合并后的迭代器的模板参数：
- T：列表节点存储的数据类型
- Ref：通过迭代器访问数据时的返回类型，可以是T&或者const T&。
- Ptr：通过迭代器访问数据的指针类型，可以是T*或者const T*。
这样，我们可以创建一个常量迭代器，为Ref和Ptr参数指定常量类型，例如：
ListIterator const_iterator;
对于非常量迭代器，就简单地传递非常量类型的引用和指针：
ListIterator iterator;
在list类中，我们需要相应地声明两种类型的迭代器：
template class list { // ... 省略其他代码 ... public: typedef ListIterator iterator; typedef ListIterator const_iterator; // ... 省略其他代码 ... };list类中的其他成员函数像begin、end需要按照是否接收常量类型来适配这两种迭代器。
