【C++】STL——list底层实现
目录
💕1.list的三个类介绍
💕2.list——节点类 （ListNode）
💕3.list——链表类 （List）
💕4.list——迭代器类（重点思考）(ListIterator)
💕5. list遍历(迭代器，const迭代器)
💕6.整体代码
💕7.测试用例
💕8.完结
一个人的坚持到底有多难
声明:此文内容基于此文章->:【C++】STL——list的使用
💕1.list的三个类介绍
在list中存在着三个类，而我们使用的list就是这三个类相辅相成形成的功能
它们分别是节点类,链表类，迭代器类
节点类用来代表每一个节点的内容
迭代器类用来实现链表的遍历，成员为单个节点的地址
而链表类就是用来实现各种链表功能，成员为头结点
💕2.list——节点类 （ListNode）
节点类是每一个节点的内容，因此需要有前一个节点的地址，后一个节点的地址，以及数据
但因为它的内容需要频繁运用，因此最好用struct，struct中所有都为public，因此很方便，当然class也没有问题，只不过需要显示public
因此需要这样写->:
template<class T> struct ListNode { ListNode* prev; ListNode* next; T data; //1.T& x可以让形参不开辟新的空间，时间和空间上都有节省 //2.const保护引用不被修改 //3.T()是因为节点内容不一定是什么类型，而T()可以更好地初始化 //例:int(),自动初始化为0，double()，string() ListNode(const T& x = T()) :data(x) ,prev(nullptr) ,next(nullptr) { } };
💕3.list——链表类 （List）
链表类的实现主要是具体功能，而我们知道链表是有一个头结点的，因此可以在链表类中实现
template<class T> class List { typedef ListNode<T> Node;//将节点类重命名为Node //创建头节点，让其指向自己 List() { phead = new Node(); phead->next = phead; phead->prev = phead; } private: Node* phead; };
💕4.list——迭代器类（重点思考）(ListIterator)
迭代器类需要实现的是链表的遍历，想要实现遍历，必不可少的就是begin()函数，正常来说，begin()函数的返回类型应该是节点的地址，但是仔细思考一下，如果返回的是节点的地址，那这个节点的地址++后，不一定是下一个节点的地址，因此，begiin()函数不应该使用节点的地址作为返回值
新的思路：我们可以利用对象进行遍历，什么意思？
我们在进行遍历时，每一次begin()返回的是一个对象，通过访问这个对象中的节点地址，加上运算符重载，来进行遍历，因为利用这个对象中的节点地址，就进而可以通过这个节点地址访问到节点的数值
因此可以这样写->:
template<class T> struct ListIterator { typedef ListNode<T> Node; Node* node;//单个节点的地址 };为什么是结构体?先不要在意，请看后面
💕5. list遍历(迭代器，const迭代器)
我们的思路是，通过对象进行遍历，因此我们需要实现对象的++,--运算符重载，来一个一个的遍历每一个节点对象
template<class T> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T> Self; ListIterator(Node* x) { node = x; } //前置++,作用是遍历，不可以返回节点地址，因为无法进行下一次++，不一定会指向下一个节点 //利用对象进行遍历，因此返回的应该是一个对象，迭代器类的对象，因为要用迭代器类中的单个节点的地址来遍历 Self& operator++() { node = node->next; return *this; } Self& operator--() { node = node->prev; return *this; } //后置-- //后置--需要利用一个临时变量来表示原来的值，首先传参传给来的是对象的地址，即this Self operator--(int) { //Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别 Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的 node = node->prev; return tep; //后置的返回值不可以用引用，因为临时变量tep出了函数就销毁了，用引用会导致空引用 } Self operator++(int) { //Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别 Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的 node = node->next; return tep; } T& operator*() { return this->node->data; } bool operator!=(const Self& it) { return this->node != it.node; } bool operator==(const Self& it) { return this->node == it.node; } Node* node;//单个节点的地址 };
接下来是begin函数与end函数，写在List类中iterator begin() { //phead->next的类型是Node*类型，而返回类型需要是iterator类型，也就是对象 //利用匿名对象，将phead->next传给ListIterator的构造函数，使它变为一个匿名对象，再return回去 return iterator(phead->next); } iterator end() { return iterator(phead); }如何实现const迭代器?
我们可以新建一个const的迭代器类，通过const修饰constIterator类中的成员变量，进而实现const迭代器的效果
具体实现如下->:
// 新增 const 迭代器 template<class T> struct ListConstIterator { typedef const ListNode<T> Node; typedef ListConstIterator<T> Self; ListConstIterator(Node* x) :node(x) {} // 前置++ Self& operator++() { node = node->next; return *this; } Self& operator--() { node = node->prev; return *this; } // 后置++ Self operator++(int) { Self tep(*this); node = node->next; return tep; } Self operator--(int) { Self tep(*this); node = node->prev; return tep; } const T& operator*() const { return node->data; } bool operator!=(const Self& it) const { return node != it.node; } bool operator==(const Self& it) const { return node == it.node; } //把节点定义为const类，因为const迭代器要实现的是const T* ,限制的是解引用 const Node* node; };template<class T> class List { public: typedef ListNode<T> Node;//将节点类重命名为Node typedef ListIterator<T> iterator;//将迭代器类重命名为iterator typedef ListConstIterator<T> const_iterator; // 新增 const_iterator //创建头节点，让其指向自己 const_iterator begin() const { return const_iterator(phead->next); } const_iterator end() const { return const_iterator(phead); } };至此难点就全部完成了，剩下的就只剩拷贝构造等，看看整体代码即可
💕6.整体代码
#pragma #include<assert.h> namespace yzq { template<class T> struct ListNode { ListNode* prev; ListNode* next; T data; //1.T& x可以让形参不开辟新的空间，时间和空间上都有节省 //2.const保护引用不被修改 //3.T()是因为节点内容不一定是什么类型，而T()可以更好地初始化 //例:int(),自动初始化为0，double()，string() ListNode(const T& x = T()) :data(x) ,prev(nullptr) ,next(nullptr) { } }; template<class T> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T> Self; ListIterator(Node* x) { node = x; } //前置++,作用是遍历，不可以返回节点地址，因为无法进行下一次++，不一定会指向下一个节点 //利用对象进行遍历，因此返回的应该是一个对象，迭代器类的对象，因为要用迭代器类中的单个节点的地址来遍历 Self& operator++() { node = node->next; return *this; } Self& operator--() { node = node->prev; return *this; } //后置-- //后置--需要利用一个临时变量来表示原来的值，首先传参传给来的是对象的地址，即this Self operator--(int) { //Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别 Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的 node = node->prev; return tep; //后置的返回值不可以用引用，因为临时变量tep出了函数就销毁了，用引用会导致空引用 } Self operator++(int) { //Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别 Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的 node = node->next; return tep; } T& operator*() { return this->node->data; } bool operator!=(const Self& it) { return this->node != it.node; } bool operator==(const Self& it) { return this->node == it.node; } Node* node;//单个节点的地址 }; // 新增 const 迭代器 template<class T> struct ListConstIterator { typedef const ListNode<T> Node; typedef ListConstIterator<T> Self; ListConstIterator(Node* x) :node(x) {} // 前置++ Self& operator++() { node = node->next; return *this; } Self& operator--() { node = node->prev; return *this; } // 后置++ Self operator++(int) { Self tep(*this); node = node->next; return tep; } Self operator--(int) { Self tep(*this); node = node->prev; return tep; } const T& operator*() const { return node->data; } bool operator!=(const Self& it) const { return node != it.node; } bool operator==(const Self& it) const { return node == it.node; } //把节点定义为const类，因为const迭代器要实现的是const T* ,限制的是解引用 const Node* node; }; template<class T> class List { public: typedef ListNode<T> Node;//将节点类重命名为Node typedef ListIterator<T> iterator;//将迭代器类重命名为iterator typedef ListConstIterator<T> const_iterator; // 新增 const_iterator //创建头节点，让其指向自己 const_iterator begin() const { return const_iterator(phead->next); } const_iterator end() const { return const_iterator(phead); } List() { phead = new Node(); phead->next = phead; phead->prev = phead; } //拷贝构造函数，可以开辟新空间然后直接尾插 //因为l2是const类型的，所以auto时需要const类型的迭代器 //遍历 const 对象需要 const 迭代器 List(const List<T>& l2) { phead = new Node(); phead->next = phead; phead->prev = phead; for (const auto& e : l2) { push_back(e); } } //赋值运算符重载 //直接更改头结点，后面的访问就全更改了 List<T>& operator=(List<T> lt) { swap(phead, lt.phead); return *this; } //析构函数 ~List() { clear(); delete phead; phead = nullptr; } //全部遍历一遍s释放 void clear() { auto it = begin(); while (it != end()) { it = erase(it); } } //头删 void pop_back() { erase(--end()); } //头插 void push_front(const T& x) { insert(begin(), x); } //头删 void pop_front() { erase(begin()); } void push_back(const T& x) { Node* newnode = new Node(x); Node* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } iterator begin() { //phead->next的类型是Node*类型，而返回类型需要是iterator类型，也就是对象 //利用匿名对象，将phead->next传给ListIterator的构造函数，使它变为一个匿名对象，再return回去 return iterator(phead->next); } iterator end() { return iterator(phead); } iterator insert(iterator pos, const T& x) { Node* cur = pos.node; Node* newnode = new Node(x); Node* prev = cur->prev; // prev newnode cur prev->next = newnode; newnode->prev = prev; newnode->next = cur; cur->prev = newnode; return iterator(newnode); } // erase 后 pos失效了，pos指向节点被释放了 iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos.node; Node* prev = cur->prev; Node* next = cur->next; prev->next = next; next->prev = prev; delete cur; return iterator(next); } private: Node* phead; }; }
💕7.测试用例
#define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; #include"list.h" int main() { yzq::List<int> l1; l1.push_back(2); l1.push_back(3); l1.insert(l1.begin(), 5); l1.erase(l1.begin()); yzq::List<int> l2(l1); //遍历输出： 2 3 for (auto e : l2) { std::cout << e << " "; } return 0; }
