list
本章思维导图
注：本章思维导图对应的 .png和 .xmind文件都以同步至 资源，可免费查阅
list也是C++标准模板库中的一大容器，事实上，他就是我们在数据结构中学的带头循环双向链表
接下来，让我们来学习它的基本使用以及模拟实现：
1. 基本使用
1.1 list对象的定义
template < class T, class Alloc = allocator<T> > class list;
- 作为标准模板库中的容器，
list同样也是一个类模板 - 如果要定义一个
list对象，就需要指定其存储的数据类型T。例如：list<int>
1.2 增（插入数据）
list作为带头循环双向链表，其支持头插（push_front）、尾插(push_back)、在pos位置之前插入（insert）等添加数据的操作
void push_back (const value_type& val); void push_front (const value_type& val); iterator insert (iterator position, const value_type& val);
接下来做简单的演示：
#include <iostream> #include <list> using namespace std; int main() { list<int> lt; //尾插 for (int i = 0; i < 3; i++) lt.push_back(i); for (auto& e : lt) cout << e << " "; cout << endl; //头插 for (int i = 3; i < 6; i++) lt.push_front(i); for (auto& e : lt) cout << e << " "; cout << endl; //在`pos`前插入 lt.insert(lt.end(), 99); for (auto& e : lt) cout << e << " "; cout << endl; return 0; }
output:
0 1 2 5 4 3 0 1 2 5 4 3 0 1 2 99
1.3 删（删除数据）
和添加数据一样，list删除数据同样也支持**头删（pop_front）、尾删（pop_back）、删除pos位置的节点（erase）**等删除操作
void pop_front(); void pop_back(); iterator erase (iterator position);
接下来做简单的演示：
#include <iostream> #include <list> using namespace std; int main() { list<int> lt; for (int i = 0; i < 5; i++) lt.push_back(i + 1); //尾删 lt.pop_back(); for (auto& e : lt) cout << e << " "; cout << endl; //头删 lt.pop_front(); for (auto& e : lt) cout << e << " "; cout << endl; //删除`pos`处的节点 lt.erase(lt.begin()); for (auto& e : lt) cout << e << " "; cout << endl; return 0; }
output:
1 2 3 4 2 3 4 3 4
1.4 遍历访问
不同于string和vector，list并不支持[]访问。list只有两种访问方式：
- 迭代器访问
- 范围for
- 实际上，范围for使用的同样也是迭代器
- 关于
list的迭代器后面会做详细说明，这里仅做使用展示
接下来做简单的演示：
#include <iostream> #include <list> using namespace std; int main() { list<int> lt; for (int i = 0; i < 5; i++) lt.push_back(i + 1); //迭代器访问 list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; //范围for for (auto& e : lt) cout << e << " "; cout << endl; return 0; }
2. 模拟实现
不同于string、vector这种连续的结构，对于存储空间不连续的list而言，其模拟实现就要复杂了许多
接下来进行逐步分析：
2.1 节点类ListNode
list是带头循环双向链表，其每个节点都存储着：前一个节点和后一个节点的指针以及存储的数据。- 因此，我们需要创建一个
ListNode类来存储对应的信息
template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; //构造函数 ListNode(const T& value = T()) : _next(nullptr) , _prev(nullptr) , _data(value) {} };
注：
- 不要忘记在C++中**
struct不是结构体而是一个类**，只是其默认的访问限定符为public。因此它也需要构造函数ListNOde是一个类模板，所以ListNode不是类名，而是模板名；ListNode<T>才是类名
2.2 封装ListNode类，实现list基本功能
实现好了ListNOde类后，我们就可以将其封装进list类中，利用list对其进行管理：
template<class T> class list { typedef ListNode<T> Node; public: //构造 list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } //尾插 void push_back(const T& value = T()) { Node* newNode = new Node(value); Node* tail = _head->_prev; tail->_next = newNode; newNode->_prev = tail; newNode->_next = _head; _head->_prev = newNode; } //尾删 void pop_back() { assert(begin() != end()); Node* tail = _head->_prev; Node* newTail = tail->_prev; _head->_prev = newTail; newTail->_next = _head; delete tail; } //头插 void push_front(const T& value = T()) { Node* cur = _head->_next; Node* newNode = new Node(value); _head->_next = newNode; newNode->_prev = _head; newNode->_next = cur; cur->_prev = newNode; } //头删 void pop_front() { assert(begin() != end()); Node* cur = _head->_next; cur->_next->_prev = _head; _head->_next = cur->_next; delete cur; } //交换两个list void swap(list<T>& it) { std::swap(_head, it._head); } private: Node* _head; };
注：部分需要用到迭代器的功能放到后面实现
2.3 实现迭代器iterator
让我们再来回顾一下C++迭代器的概念：
迭代器是一个设计模式，它允许你遍历一个容器（如数组、列表、向量等）的所有元素，而无需知道容器的底层表示方式
也就是说，迭代器为我们提供了一个统一的方式来遍历容器。例如我们
++一个迭代器就可以指向其后一个元素，--一个迭代器就可以指向前一个元素，而不要管这个容器具体是什么。
- 迭代器的底层实际上都是指针
- 对于
string、vector这种连续的物理空间，他们的迭代器很好实现，就是原生指针 - 但是对于
list这种物理空间并不连续的存储结构，一个节点的指针++后并不能指向它后面的指针，因此就不能使用原生指针来实现其迭代器了。
因此，为了让屏蔽节点的指针++后不能指向它后面的指针 这一缺陷，我们就需要对ListNode类进行封装，使其++和- - 等操作符合迭代器的规范。而对其封装的类，就是我们的迭代器__List_iterator
template<class T> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T> self; Node* _node; __list_iterator(Node* node) : _node(node) {} //++it self& operator++ () { _node = _node->_next; return *this; } //it++ self operator++ (int) { self temp(_node); _node = _node->_next; return temp; } //--it self& operator-- () { _node = _node->_prev; return *this; } //it-- self operator-- (int) { self temp(_node); _node = _node->_prev; return temp; } T& operator* () { return _node->_data; } T* operator-> () { return &_node->_data; } bool operator!= (const self& value) { return _node != value._node; } bool operator == (const self& value) { return _node == value._node; } };
2.3.1 实现const迭代器const_iterator
要实现一个const迭代器，最容易想到的方法，当然就是复制一份普通的迭代器__list_iterator对象，再对operator*()和operator->()的返回值做简单的修改就行了：
template<class T> struct __list_const_iterator { typedef ListNode<T> Node; typedef __list_const_iterator<T> self; Node* _node; __list_const_iterator(Node* node) : _node(node) {} //++it self& operator++ () { _node = _node->_next; return *this; } //it++ self operator++ (int) { self temp(_node); _node = _node->_next; return temp; } //--it self& operator-- () { _node = _node->_prev; return *this; } //it-- self operator-- (int) { self temp(_node); _node = _node->_prev; return temp; } const T& operator* () { return _node->_data; } const T* operator-> () { return &_node->_data; } bool operator!= (const self& value) { return _node != value._node; } bool operator == (const self& value) { return _node == value._node; } };
但是，这样的做法无疑会添加大量冗余的代码，显然不是最恰当的。因此最初编写标准模板库的大佬们就想出了这样的办法——添加类模板参数。也就是说，我们可以将__list_iterator类模板写成这样：
template<class T, class Referance, class Ptr> struct __list_iterator {}
T就是list存储的数据类型Referance就是operator*()的返回值，如果是非const对象，就传入T&；如果是const对象，就传入const T&Ptr就是operator->()的返回值，如果是非const对象，就传入T*；如果是const对象，就传入const T*
这样，我们就可以将普通迭代器和const迭代器整合为一个迭代器__list_iterator：
template<class T, class Referance, class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T, Referance, Ptr> self; Node* _node; __list_iterator(Node* node) : _node(node) {} //++it self& operator++ () { _node = _node->_next; return *this; } //it++ self operator++ (int) { self temp(_node); _node = _node->_next; return temp; } //--it self& operator-- () { _node = _node->_prev; return *this; } //it-- self operator-- (int) { self temp(_node); _node = _node->_prev; return temp; } Referance operator* () { return _node->_data; } Ptr operator-> () { return &_node->_data; } bool operator!= (const self& value) { return _node != value._node; } bool operator == (const self& value) { return _node == value._node; } };
2.3.2 实现反向迭代器reverse_iterator
需要注意：
为了实现对称性，C++规定：
- 反向迭代器的开头
rbegin()实际上是正向迭代器的结束end()；反向迭代器的结束rend()即为正向迭代器的开始begin()- 当对一个反向迭代器进行
*操作时，并不会对当前的位置进行*操作，而是会对当前位置的之前一个位置进行*操作
和const迭代器，一样写出反向迭代器最简单的方式同样是复制一下普通迭代器类，再修改一下代码逻辑即可。这里不再做展示。
但很显然，这种方法同样也不是最好的。
最初编写标准模板库的大佬们在写反向迭代器的代码时会思考这样的问题：
是否可以写这样一份代码，可以将所有的正向迭代器都转化为对应的反向迭代器呢？
事实上，他们确实是这样做的：
- 可以新建一个头文件
reverse_iterator，其包含一个反向迭代器类Reverse_iterator，其实现了关于反向迭代器的各种操作。 - 为了做到可以 将所有的正向迭代器转化为其对应的反向迭代器 ，其各种操作并不需要我们手动实现，而是需要复用正向迭代器的方法
我们可以先来看看其具体的实现：
template<class Iterator, class Ref, class Ptr> struct Reverse_iterator { Reverse_iterator(const Iterator& it) : _it(it) {} typedef Reverse_iterator<Iterator, Ref, Ptr> Self; Self& operator++ () { --_it; return *this; } Self& operator-- () { ++_it; return *this; } Self operator++ (int) { Self tmp = _it; --_it; return tmp; } Self operator-- (int) { Self tmp = _it; ++_it; return tmp; } //注意，*运算不是对当前位置 //而是对当前位置的前一个位置进行运算 Ref operator* () { Iterator tmp = --_it; ++_it; return *tmp; } Ptr operator-> () { return &(operator*()); } bool operator!= (const Self& it) { return _it != it._it; } bool operator== (const Self& it) { return _it == it._it; } Iterator _it; };
Iterator即为对应正向迭代器- 这里通过对
Iterator的封装，利用Iterator的方法来间接实现其反向迭代器的操作，从而就可以实现用同一份代码就可以将所有的正向迭代器都转换为其对应的反向迭代器
3. list容器模拟实现代码
reverse_list.h
template<class Iterator, class Ref, class Ptr> struct Reverse_iterator { Reverse_iterator(const Iterator& it) : _it(it) {} typedef Reverse_iterator<Iterator, Ref, Ptr> Self; Self& operator++ () { --_it; return *this; } Self& operator-- () { ++_it; return *this; } Self operator++ (int) { Self tmp = _it; --_it; return tmp; } Self operator-- (int) { Self tmp = _it; ++_it; return tmp; } Ref operator* () { Iterator tmp = --_it; ++_it; return *tmp; } Ptr operator-> () { return &(operator*()); } bool operator!= (const Self& it) { return _it != it._it; } bool operator== (const Self& it) { return _it == it._it; } Iterator _it; };
list.h
#pragma once #include <iostream> #include <list> #include <assert.h> #include "reverse_iterator.h" using namespace std; namespace TEST { template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; ListNode(const T& value = T()) : _next(nullptr) , _prev(nullptr) , _data(value) {} }; //正向迭代器 template<class T, class Referance, class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T, Referance, Ptr> self; Node* _node; __list_iterator(Node* node) : _node(node) {} //++it self& operator++ () { _node = _node->_next; return *this; } //it++ self operator++ (int) { self temp(_node); _node = _node->_next; return temp; } //--it self& operator-- () { _node = _node->_prev; return *this; } //it-- self operator-- (int) { self temp(_node); _node = _node->_prev; return temp; } Referance operator* () { return _node->_data; } Ptr operator-> () { return &_node->_data; } bool operator!= (const self& value) { return _node != value._node; } bool operator == (const self& value) { return _node == value._node; } }; template<class T> class list { typedef ListNode<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef Reverse_iterator<iterator, T&, T*> reverse_iterator; typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list(list<T>& it) { _head = new Node; _head->_next = _head; _head->_prev = _head; for (const auto e : it) { push_back(e); } } list<T>& operator= (list<T> it) { swap(it); return *this; } void push_back(const T& value = T()) { insert(end(), value); } void pop_back() { erase(--end()); } void push_front(const T& value = T()) { insert(begin(), value); } void pop_front() { erase(begin()); } iterator erase(iterator pos) { assert(begin() != end()); Node* curNode = pos._node; Node* prevNode = curNode->_prev; Node* nextNode = curNode->_next; nextNode->_prev = prevNode; prevNode->_next = nextNode; delete curNode; return nextNode; } iterator insert(iterator pos, const T& value = T()) { Node* newNode = new Node(value); Node* prevNode = pos._node->_prev; Node* curNode = pos._node; //prevNode newNode curNode; prevNode->_next = newNode; newNode->_prev = prevNode; newNode->_next = curNode; curNode->_prev = newNode; return newNode; } void swap(list<T>& it) { std::swap(_head, it._head); } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } iterator begin() { return _head->_next; } const_iterator begin() const { return _head->_next; } iterator end() { return _head; } const_iterator end() const { return _head; } reverse_iterator rbegin() { return end(); } const_reverse_iterator rbegin() const { return end(); } reverse_iterator rend() { return begin(); } const_reverse_iterator rend() const { return begin(); } ~list() { clear(); delete _head; _head = nullptr; } private: Node* _head; }; }
本篇完
如果错误敬请指正
