📍前言
本篇将学习 list 的模拟实现，它的主要难点在与迭代器的模拟。
🕺作者： 迷茫的启明星
专栏：《C++初阶》
😘欢迎关注：👍点赞🙌收藏✍️留言
🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！
持续更新中~
🌈STL之list的模拟实现
🎈list_node节点的定义
这里需要使用结构体
在这里需要使用模板，因为数据类型是不确定的
双向链表的结构包括：两个指针和数据
我们在定义节点时还需要初始化
template<class T> struct list_node { T _data; list_node<T>* _next; list_node<T>* _prev; //初始化 list_node(const T& val = T()) //为什么传引用？ //传引用减少拷贝 //初始化的值是T的默认构造函数，不能传0 //T可能是string类型或其他类型 :_data(val) ,_next(nullptr) ,_prev(nullptr) {} };
🎈iterator迭代器
迭代器可以理解成指针，但是它比指针复杂多了，指针无外乎地址，而迭代器则是不是指针，却要让它实现指针的功能：++、–、*等操作
🕯️构造函数
我们构造好了一个_node，但是没有给他赋值，就等着外面传过来一个node，把node给给里面的_node即可。
__list_iterator(Node* node)
:_node(node)
{}
🕯️*it
我们把迭代器比作指针，方便理解，这个函数就是对“指针”解引用，拿到它的值。注意结果返回引用，减少拷贝
Ref operator*() { return _node->_data; }
🕯️->
拿到节点的值的地址，因为返回的是一个地址，所以要用指针接收。结果返回一个指针。
Ptr operator->() { return &(operator*()); }
🕯️it++/++it
为了实现类似指针的效果，迭代器前置++和后置++分别就要返回没改变的值和改变了的值。
++it
迭代器向后走一步，返回加过的值(还是一个迭代器)
it++
迭代器向后走一步，返回没加过的值(还是一个迭代器)
//++it iterator& operator++() { _node = _node->_next; return *this; } // it++ iterator operator++(int) { iterator tmp(*this);//保存原来的值 _node = _node->_next; return tmp; }
🕯️it–/–it
原因与上同
// --it iterator& operator--() { _node = _node->_prev; return *this; } // it-- iterator operator--(int) { iterator tmp(*this); _node = _node->_prev; return tmp; }
🕯️!= / ==
仅需判断里面的this是否一样即可
bool operator!=(const iterator& it) const { return _node != it._node; } bool operator==(const iterator& it) const { return _node == it._node; }
🎈list类
🕯️begin()/end()
iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); }
🕯️const_begin()/const_end()
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; }
🕯️insert函数
双向链表的插入，是不是非常简单呢？只需要将新的节点的指针与插入位置前后指针相连即可。
iterator insert(iterator pos, const T& x) { 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; return iterator(newnode);
🕯️erase函数
与Insert函数一样，把需要删除的节点的前后节点绑在一起就完成了。
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); }
🕯️push_back函数
它有两种方式，既可以自己来实现每一步，也可以直接复用insert函数在末尾插入
void push_back(const T& x) { //Node* tail = _head->_prev; //Node* newnode = new Node(x); _head tail newnode //tail->_next = newnode; //newnode->_prev = tail; //newnode->_next = _head; //_head->_prev = newnode; insert(end(), x); }
🕯️push_front函数
它和上面push_back函数讲的一样，不过这是在开头插入
void push_front(const T& x) { insert(begin(), x); }
🕯️pop_back函数
复用erase函数 void pop_back() { erase(--end()); }
🕯️pop_front函数
复用erase函数
void pop_front() { erase(begin()); }
🎈源码
namespace hxq { template<class T> struct list_node { T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& x = T()) :_data(x) , _next(nullptr) , _prev(nullptr) {} }; template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> iterator; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef ptrdiff_t difference_type; Node* _node; __list_iterator(Node* node) :_node(node) {} bool operator!=(const iterator& it) const { return _node != it._node; } bool operator==(const iterator& it) const { return _node == it._node; } Ref operator*() { return _node->_data; } //T* operator->() Ptr operator->() { return &(operator*()); } // ++it iterator& operator++() { _node = _node->_next; return *this; } // it++ iterator operator++(int) { iterator tmp(*this); _node = _node->_next; return tmp; } // --it iterator& operator--() { _node = _node->_prev; return *this; } // it-- iterator operator--(int) { iterator tmp(*this); _node = _node->_prev; return tmp; } }; template<class T> class list { typedef list_node<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } void push_back(const T& x) { //Node* tail = _head->_prev; //Node* newnode = new Node(x); _head tail newnode //tail->_next = newnode; //newnode->_prev = tail; //newnode->_next = _head; //_head->_prev = newnode; insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator insert(iterator pos, const T& x) { 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; return iterator(newnode); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } 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* _head; }; }
📍后记
本文主要介绍了STL中双向链表list的模拟实现。
✨通过结构体定义list_node节点，通过模板实现数据类型的不确定性，并对节点进行初始化。
✨利用迭代器iterator实现指针的功能，包括构造函数、解引用、*it、->、前后置++/–、!=和==等操作。
✨在list类中，通过双向链表实现了begin()/end()、const_begin()/const_end()、insert、erase、push_back、push_front、pop_back和pop_front等函数。
✨其中，push_back和push_front函数可以复用insert函数，在末尾和开头插入元素。
✨pop_back和pop_front函数可以复用erase函数，删除末尾和开头的元素。
感谢大家支持！！！
respect！
下篇见！
