二、list的深度剖析及模拟实现
💨大概瞅下源码的大概框架
template <class T> struct __list_node { typedef void* void_pointer; //其实感觉没必要搞成void*,后面还得强转 void_pointer next; void_pointer prev; T data; }; class list { protected: typedef __list_node<T> list_node; typedef list_node* link_type; protected: link_type node; protected: link_type get_node() { return list_node_allocator::allocate(); } protected: void empty_initialize() { //体现了带头双向循环链表的特性 node = get_node(); node->next = node; node->prev = node; } public: list() { empty_initialize(); } }
💦 模拟实现list
💨 list.h
#pragma once namespace bit { template<class T> struct __list_node//一般前面使用__,表示给内部使用,为什么不使用内部类,因为不仅仅list要用它,迭代器也要用它(C++里还是比较少用内部类的) { __list_node<T>* _next; __list_node<T>* _prev; T _data; //这里支持无参的new Node,或者有参的new Node(x) __list_node(const T& x = T()) : _next(nullptr) , _prev(nullptr) , _data(x) {} }; //迭代器,用一个类去封装节点的指针,所以目前为止我们已知的迭代器的实现方式有两种: //a)原生指针(天然迭代器),它所指向的空间物理结构是连续的,也就是说只有string、vector才可以做天然迭代器(*就是当前位置的数据/++就是下一个位置/--就是下一个位置) //b)类(用一个类去封装原生指针,重载相关运算符,让这个类对象用起来像指针),它所指向的空间物理结构是不连续的(没有封装指针之前,*是结构体/++--的位置不明确) //这里使用类模板是因为里面需要使用__list_node节点,而它又是一个类模板 //不适用const //template<class T> //struct __list_iterator //{ // typedef __list_iterator<T> self; // typedef __list_node<T> Node; // Node* _node; // //这个类里包含一个节点的指针,然后就可以用一个节点的指针调用它的构造函数就可以构造一个迭代器,这里我们的迭代器begin()/end()是list里的成员函数,它们分别返回第一个有效节点和最后一个节点的下一个无效头节点 // __list_iterator(Node* node) // : _node(node) // {} // //*it // T& operator*() // { // return _node->_data; // } // //++it // self& operator++() // { // _node = _node->_next; // return *this; // } // //it++,tmp出了作用域销毁,传值返回,不能用引用 // self operator++(int) // { // //备份 // self tmp(*this); // _node = _node->_next; // return tmp; // } // //--it // self& operator--() // { // _node = _node->_prev; // return *this; // } // //it-- // self operator--(int) // { // self tmp(*this); // _node = _node->_prev; // return tmp; // } // //it+,它可以operator+(),但是效率很低,所以也就没有支持 // //lt.begin() != lt.end() // bool operator!=(const self& it) const // { // return _node != it._node; // } // //lt.begin() == lt.end() // bool operator==(const self& it) const // { // return _node == it._node; // } // //__list_iterator时有一个节点的指针,要不要去做深拷贝和析构函数呢? // /*并不是说一个类里有节点的指针,就要做深拷贝和析构,要看这个空间是不是你的,你拿了一个指针构造了一个迭代器,这个节点是你迭代器的吗,节点是list的,不需要迭代器去析构, // 同时iterator it = begin();，这里需要的就是浅拷贝,begin()构造了一个迭代器对象(_head->_next),你把这个对象赋值给it,难道是要再深拷贝一个节点出来吗,所以说默认生成的浅拷贝也是有价值的 // 所以我们不需要去写拷贝构造和赋值,因为默认生成的对于内置类型就会完成浅拷贝;不需要去写析构函数,因为节点是list的对象 */ //}; //常规的写法就是实现一个专属的__list_const_iterator类,这两个除了类名称、operator*()不一样,其它完全一样 //template<class T> //struct __list_const_iterator //{ // typedef __list_const_iterator<T> self; // typedef __list_node<T> Node; // Node* _node; // __list_const_iterator(Node* node) // : _node(node) // {} // //*it // const T& operator*() // { // return _node->_data; // } // //++it // self& operator++() // { // _node = _node->_next; // return *this; // } // //it++,tmp出了作用域销毁,传值返回,不能用引用 // self operator++(int) // { // //备份 // self tmp(*this); // _node = _node->_next; // return tmp; // } // //--it // self& operator--() // { // _node = _node->_prev; // return *this; // } // //it-- // self operator--(int) // { // self tmp(*this); // _node = _node->_prev; // return tmp; // } // //it+,它可以operator+(),但是效率很低,所以也就没有支持 // //lt.begin() != lt.end() // bool operator!=(const self& it) const // { // return _node != it._node; // } // //lt.begin() == lt.end() // bool operator==(const self& it) const // { // return _node == it._node; // } //}; //仰望大佬 //iterator:<T, T&, T*> //const_iterator<T, const T&, const T*> template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, Ref, Ptr> self; typedef __list_node<T> Node; Node* _node; __list_iterator(Node* node) : _node(node) {} //*it Ref operator*() { return _node->_data; } // Ptr operator->() { return &_node->_data; } //++it self& operator++() { _node = _node->_next; return *this; } //it++,tmp出了作用域销毁,传值返回,不能用引用 self operator++(int) { //备份 self tmp(*this); _node = _node->_next; return tmp; } //--it self& operator--() { _node = _node->_prev; return *this; } //it-- self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } //it+,它可以operator+(),但是效率很低,所以也就没有支持 //lt.begin() != lt.end() bool operator!=(const self& it) const { return _node != it._node; } //lt.begin() == lt.end() bool operator==(const self& it) const { return _node == it._node; } }; template<class T> class list { //这个不想让外面的人用,所以默认是私有的 typedef __list_node<T> Node; public: //__list_iterator是什么名字并不重要,最终都会typedef为iterator,因为我们要用统一的方式去访问容器。比如vector<int>::iterator;你那个真正的迭代器是什么名称不重要 //typedef __list_iterator<T> iterator; //typedef __list_const_iterator<T> const_iterator; typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head);//最后一个节点的下一个位置,哨兵位 } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } list() { //带头双向循环链表 _head = new Node; _head->_next = _head; _head->_prev = _head; } //lt2(lt1) //传统写法 /*list(const list<T>& lt) { _head = new Node; _head->_next = _head; _head->_prev = _head; for(const auto& e : lt) { push_back(e); } }*/ //现代写法,可以看到这里现代写法相比传统写法并没有讲到便宜,所以说现代写法也不一定是最优,需要灵活运用 //它要先支持一个迭代器区间的才能写现代写法,同时这里支持其它容器的拷贝构造 template<class InputIterator> list(InputIterator first, InputIterator last) { _head = new Node; _head->_next = _head; _head->_prev = _head; while (first != last) { push_back(*first); ++first; } } list(const list<T>& lt) { _head = new Node; _head->_next = _head; _head->_prev = _head; list<T> tmp(lt.begin(), lt.end()); std::swap(_head, tmp._head); } //lt1 = lt2 //传统写法 /*list<T>& operator=(const list<T>& lt) { if(this != <) { clear(); for(const auto& e : lt) { push_back(e); } } return *this; }*/ //现代写法,对于赋值有一个原则,深拷贝现代写法一定非常简单(只要写了拷贝构造,赋值就一定能用现代写法,并且很简洁) list<T>& operator=(list<T> lt) { swap(_head, lt._head); return *this; } //对于~list,先实现clear ~list() { clear(); //清除头节点 delete _head; _head = nullptr; } void clear() { iterator it = begin(); while(it != end()) { //不清除头节点,直接复用 it = erase(it); } } void push_back(const T& x) { //同insert(_head, x);,end()是最后节点的下一个位置_head insert(end(), x); } void push_front(const T& x) { //insert(_head->_next, x);,begin()是头节点的下一个位置 insert(begin(), x); } void pop_back() { //同erase(_head->_prev); erase(--end()); } void pop_front() { //同erase(_head->_next); erase(begin()); } iterator insert(iterator pos, const T& x) { //备份;这里就体现了为啥我们在设计__list_node和__list_iterator时为什么是struct,如果用class,这里就得用友源,但没必要 Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); //关联 prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; //双向链表的insert是不会失效的,返回新插入的节点,这里同 __list_iterator<T> (newnode),且这里是一个匿名对象。 return iterator(newnode); //同上,newnode是Node*(__list_node<T>)类型,而insert的返回类型是iterator(__list_iterator<T>)也可以,这是因为单参数的构造函数支持隐式类型转换,如 A aa = 1; 或 string s = "hello";。但因为不太明确,所以不太推荐 //return newnode; } //虽然在外面调用list实例化了lt,但是list里面的函数编译器会按需实例化(外面调用了哪个成员函数,就实例化哪个) //erase不是模板?这里要注意类模板里的成员函数都是函数模板,erase的参数iterator就是typedef出来的模板 iterator erase(iterator pos) { //空链表(只剩头节点)不能erase assert(pos != end()); //备份 Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; //释放 delete cur; //关联 prev->_next = next; next->_prev = prev; //返回删除元素之后的位置,注意这里的pos已经是野指针了 return iterator(next); } size_t size() { size_t n = 0; iterator it = begin(); while (it != end()) { ++it; ++n; } return n; } bool empty() { return begin() == end(); } private: Node* _head; }; //const迭代器一般出现的场景是在传参的时候 void print_list(const list<int>& l) { list<int>::const_iterator it = l.begin(); while (it != l.end()) { //*it += 2;//err,表达式必须是可修改的左值 cout << *it << " "; ++it; } cout << endl; } void test_list1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); print_list(lt); list<int>::iterator it = lt.begin(); while (it != lt.end()) { *it *= 2; cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; } struct TreeNode { struct TreeNode* _left; struct TreeNode* _right; int _val; TreeNode(int val = -1) : _left(nullptr) , _right(nullptr) , _val(val) {} }; //ostream operator<<(ostream& TreeNode, TreeNode n){} void test_list2() { list<TreeNode> lt; lt.push_back(TreeNode(1)); lt.push_back(TreeNode(2)); lt.push_back(TreeNode(3)); lt.push_back(TreeNode(4)); list<TreeNode>::iterator it = lt.begin(); while (it != lt.end()) { //*it调operator*,返回_node->_data;,_data是T类型,而这的T是TreeNode,是一个结构体类型的树节点,而*it后是TreeNode,我们说了内置类型可以直接cout输出,但是自定义类型不行,所以我们可以operator<<,或者不用重载(使用结构体的特性) //cout << *it << " "; //有些场景不适合用cout //cout << (*it)._val << " "; //这是结构体的访问方式(结构体和指针的访问方式,细节如下说明 3. List item) printf("val:%d,left:%p,right:%p\n", (*it)._val, (*it)._left, (*it)._right); //像指针一样就要去重载->,[int* p *p] [TreeNode* p p->_val] printf("val:%d,left:%p,right:%p\n", it->_val, it->_left, it->_right); ++it; } cout << endl; } void test_list3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); print_list(lt); lt.clear(); lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); print_list(lt); } void test_list4() { list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); list<int> lt2(lt1); print_list(lt2); list<int> lt3(lt1.begin(), lt1.end()); string s("hello"); list<int> lt4(s.begin(), s.end()); for (auto e : lt3) { cout << e << " "; } cout << endl; for (auto e : lt4) { cout << e << " "; } cout << endl; lt1 = lt4; for (auto e : lt1) { cout << e << " "; } cout << endl; } }
💨 test.cpp
#include<iostream> #include<stdbool.h> #include<assert.h> using namespace std; #include"list.h" int main() { bit::test_list1(); bit::test_list2(); bit::test_list3(); bit::test_list4(); return 0; }
📝说明
- List item
list 迭代器 ❓
在 string、vector 里我们实现的都是简单迭代器，用的是原生指针。而对于 list，现在要遍历它，你用原生指针是不能实现的(++操作不会指向下一个节点)，因为每个节点的地址是不连续的，并且毫无关联。
我们瞅下源码，看下是它的迭代器是怎么设计的：可以看到它的迭代器不再是一个 Node*，而用了一个 __list_iterator 的类去封装节点的指针，它有三个模板参数(先不管)。对于 string 是 char*，对于 vector 是 T*，对于 list 是自定义类型，所以我们说迭代器是像指针一样的东西。
这个类的核心成员是 Link_type node，Link_type 是 Node*
本身类(对象)不能 ++，但是我们可以去重载它的 ++，也就是说 __list_iterator 不是指针，但是我们可以让它像指针一样
- List item
const 迭代器的实现，对于 const 迭代器的实现，我们一般人是再写一个专属的 __list_const_iterator 类，这两个除了类名称、operator*() 不一样，其它完全一样，非常的冗余。但是好像也没有更好的办法了呀，怎么让 operator*() 一个返回 T&，一个返回 const T& 呢 ？这里我们瞅下高手写的源码是怎么实现的：
可以看到如下源码的实现，它只实现了一个类，如是是普通迭代器 operator* 的返回值是 T&，如果是 const 迭代器，operator* 的返回值是 const T&
- List item
list 的迭代器要像指针一样，除了需要重载 “*”，还需要重载 “->”。
- List item
严格来说迭代器是分类型的，在我们的 STL 3.0 中找到 stl_iterator.h 文件，它里面把迭代器类型分为五种，并且它们构成继承关系：
这里涉及 “类型萃取” 的概念，有兴趣可以去了解下，这里就不细谈了。
💦 对模拟的bite::list进行测试
参考 test.cpp 文件
三、list与vector的对比
在 32 位的机器下 vector 和 list 的迭代器所占多少字节 ❓
相比 vector 的迭代器，就逻辑上来说 list 的迭代器就要复杂一点，因为 vector 的迭代器是一个天然的迭代器，它是原生指针，但要注意原生指针要做天然迭代器的要求是指针指向的物理空间是连续的。而 list 不能做天然的迭代器，所以我们要将指针封装成一个类，让它完成指针的操作。而就物理层面上来说 vector 和 list 的迭代器没有更复杂，也就是它们所占用的空间是一样的。至此，我们就可以看到 C++ 运算符重载的能力。
所以在 32 位的机器下 vector 的迭代器占 4 个字节；list 的迭代器也占 4 个字节。
vector 与 list 都是 STL 中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景也不同，其主要不同如下：
| vector | list | |
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率 O(1) | 不支持随机访问，访问某个元素效率 O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为 O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失数，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
