基本结构
list的底层是 带头双向循环链表, 底层构架如下:
list类: 维护头节点 _head 及 整个双链表结构
Node类: 每个节点的结构 _prev, _next, _data
iterator类: 通过类进行封装, 进而通过重载运算符来实现迭代器行为(++/ --/ */ ->等)
🗨️为什么不能跟 vector/ string类一样, 我们直接以 Node* 充当迭代器呢?
首先, vector/ string类中, T*直接充当迭代器的原因就是:
1.物理空间是连续的, 从而导致 ++/ -- 就可以指向下一个数据了
2.T* 经过解引用就是 T, 是我们需要的数据了
其次, list类中, Node不能直接充当迭代器 的原因:
1.双链表的物理空间是不连续的, 从而导致 ++ 不是下一个节点
2.Node*经过解引用就是Node, 而我们需要的数据是 _data
通过上面的原因, 我们知道了 Node* 不能直接充当迭代器的原因了!
通过封装类实现迭代器行为的原因:
虽然Node* 并不能直接充当迭代器, 但是节点的指针有我们需要的东西:
_next 和 _data.
我们就可以以Node* 为核心来封装一个类, 通过重载++/ */ -- 等运算符来实现迭代器的行为
(1)iterator类的基本结构
template<class T, class Ref, class Ptr> struct list_iterator { public: typedef list_node<T> Node; typedef list_iterator<T, Ref, Ptr> self; // 还是以节点的指针来充当迭代器 list_iterator(Node* node) {} list_iterator(const self& it) {} // 返回的还是一个迭代器 self& operator++() {} self operator++(int) {} self& operator--() {} Ptr operator->() {} self operator--(int) {} // 还是节点指针的比较 bool operator!=(const self& list) const {} bool operator==(const self& list) {} // iterator 和 const_iterator Ref operator*() {} public: // 成员变量 Node* _node; };
成员变量是 Node* _node — — 迭代器的本质还是Node*
🗨️为什么迭代器类有三个参数?
首先, 我们先明确迭代器分为 普通迭代器 和 const迭代器
我们是想通过一个模版, 通过不同参数实例化出不同的类型来实现 普通迭代器和const迭代器
T — — 来控制节点内部数据的类型
Ref — — 来控制 解引用(*) 的返回类型, 即分普通迭代器返回 T&, const迭代器返回 const T&
Ptr — — 来控制 ->的返回类型, 即普通迭代器返回T*, const迭代器返回 const T*
即, 我们在 list类中, 通过不同的参数就可以借助一个模版来实现普通迭代器 和 const迭代器: typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator;
(2)Node类的基本结构
template<class T> struct list_node { list_node(const T& val = T()) { _data = val; } public: // 成员变量 list_node<T>* _prev = nullptr; list_node<T>* _next = nullptr; T _data; };
(3)list类的基本结构
template<class T> class list { public: typedef list_node<T> Node; typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; iterator begin() {} iterator end() {} const_iterator begin()const {} const_iterator end()const {} size_t size() {} list(const list<T>& tem) {} list<T>& operator=(list<T> tem) {} // 各种函数 // ... // ... private: // 成员变量 Node* _head; size_t _size = 0; };
初始化
(1) list类的构造函数
我们都知道, 带头双向循环链表中, 头节点的作用就是: 方便链接 和 哨兵位的作用.
所以, 一个带头双向循环链表的初始化就是要 初始化头结点 和 连接结构.
由于有多种初始化的方式, 而头节点的初始化是最基本的⇒ 那么, 我们就把初始化头节点单独写一个函数出来👇👇👇
// 头结点的初始化 void Init() { // 为头节点开空间 _head = new Node; // 连接结构 _head->_next = _head; _head->_prev = _head; _size = 0; }
- 默认构造函数 — — 初始化头节点
// 头结点的初始化 list() { Init(); }
- n个val来进行初始化
list(int n, const T& val = T()) { // 头结点的初始化 Init(); while (n--) { // 借助尾插 push_back(val); } }
- 迭代器区间初始化
template<class InputIterator> list(InputIterator first, InputIterator last) { Init(); while (first != last) { push_back(*first); ++first; } }
- 拷贝构造函数
list(const list<T>& tem) { // 都是内置类型 _head = tem._head; _size = tem._size; }
(2) Node类的构造函数
list_node(const T& val = T()) :_prev(nullptr) ,_next(nullptr) ,_data(val) {}
(3) iterator类中的构造函数
- 构造函数
因为list类的迭代器的本质还是Node*
那么, iterator类的初始化只需要节点指针, 当然成员变量也是一个节点指针
// 还是以节点的指针来充当迭代器 list_iterator(Node* node) { _node = node; }
- 拷贝构造函数
拷贝构造需要用同类型的变量来充当形参— — 故形参的类型是 iterator<T, Ref, Ptr> , 由于前面有typedef, 简写成self
list_iterator(const self& it) { _node = it._node; }
迭代器行为
(1) 前置++&& 后置++
前置++: 返回++以后的迭代器
后置++: 返回++以前的迭代器
共同点: ++以后节点都要+1, 且返回的都是一个迭代器类型
// 前置++ self& operator++() { _node = _node->_next; return *this; } // 后置++ self operator++(int) { Node* tem = _node; _node = _node->_next; return tem; }
(2) 前置-- && 后置–
前置–: 返回–以后的迭代器
后置–: 返回–以前的迭代器
共同点: --以后节点都要-1, 且返回的都是一个迭代器类型
// 前置-- self& operator--() { _node = _node->_prev; return *this; } // 后置-- self operator--(int) { Node* tem = _node->_prev; _node = _node->_prev; return tem; }
(3)operator* && operator->
// iterator 和 const_iterator Ref operator*() { return _node->_data; } // iterator 和 const_iterator Ptr operator->() { return &(_node->_data); }
先看一下使用场景吧👇👇👇
struct Person { public: // 默认构造 Person(const string name = "", const int age = 0) { _name = name; _age = age; } // 成员变量 string _name; int _age; }; void list_test6() { muyu::list<Person> lt1; lt1.push_back(Person("张三", 20)); lt1.push_back(Person("李四", 21)); lt1.push_back(Person("王五", 22)); // 使用* cout << "*" << endl; muyu::list<Person>::iterator tem = lt1.begin(); while (tem != lt1.end()) { cout << (*tem)._name << " " << (*tem)._age << endl; ++tem; } cout << endl; cout << "->" << endl; // 使用-> muyu::list<Person>::iterator t = lt1.begin(); while (t != lt1.end()) { cout << t->_name << " " << t->_age << endl; ++t; } cout << endl; } int main() { list_test6(); return 0; }
运行结果:
* 张三 20 李四 21 王五 22 -> 张三 20 李四 21 王五 22
(4)operator== && operator!=
迭代器相等的本质是: 对应节点的指针是否相等, 即_node是否相等
// 还是节点指针的比较 bool operator!=(const self& list) const { return _node != list._node; } bool operator==(const self& list)const { return _node == list._node; }
list类中的各种函数
插入
(1) insert
- 找到对应节点, 以及前节点和后节点
- 更新连接关系
iterator insert(iterator pos, const T& val = T()) { // 找节点 Node* cur = pos._node; Node* tem = new Node(val); Node* prev = cur->_prev; // 更新链接关系 prev->_next = tem; tem->_prev = prev; tem->_next = cur; cur->_prev = tem; ++_size; return tem; }
(2)push_back && push_front
复用insert函数
void push_back(const T& val = T()) { //Node* tail = _head->_prev; //Node* cur = new Node(val); //tail->_next = cur; //cur->_prev = tail; //cur->_next = _head; //_head->_prev = cur; insert(end(), val); } void push_front(const T& val = T()) { //Node* cur = new Node(val); //Node* next = _head->_next; 更新链接关系 //_head->_next = cur; //cur->_prev = _head; //cur->_next = next; //next->_prev = cur; insert(begin(), val); }
删除
(1)erase
- 找到对应节点, 以及前节点和后节点
- 更新连接关系
iterator erase(iterator pos) { // 头节点不能删除 assert(pos != end()); // 找节点 Node* tem = pos._node; Node* prev = tem->_prev; Node* next = tem->_next; // 更新连接关系 prev->_next = next; next->_prev = prev; delete tem; --_size; return next; }
(2) pop_back && pop_front
复用erase函数
void pop_back() { //Node* tail = _head->_prev->_prev; //if (tail) //{ // tail->_next = _head; // _head->_next = tail; //} erase(--end()); } void pop_front() { //Node* cur = _head->_next->_next; //if (cur) //{ // _head->_next = cur; // cur->_prev = _head; //} erase(begin()); }
swap && operator=
void swap(list<T>& tem) { std::swap(_head, tem._head); std::swap(_size, tem._size); } // 现代写法, 巧借tem的拷贝构造 list<T>& list(list<T> tem) { swap(tem); return *this; }
begin && end
单参数的构造函数支持 隐式类型装换
返回的类型是 iterator, iterator类中构造函数是单参数的, 支持隐式类型装换
iterator begin() { return _head->_next; // return iterator(_head->_next); } iterator end() { return _head; // return iterator(_head); } const_iterator begin()const { return (_head->_next); // return iterator(_head); } const_iterator end()const { return (_head); // return iterator(_head); }
其他函数
- size
size_t size() { return _size; }
- clear
删除list类中的有效数据
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } _size = 0; }
- 析构
~list() { clear(); delete _head; _head = nullptr; }
