阅读量:0
目录
⭐list介绍
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。
⭐list模拟实现
- list的底层是双向链表结构，包含有一个哨兵节点。
- 模拟实现list，要实现下列三个类：
- ①list节点类
- ②迭代器的类
- ③list主要功能的类(size()，empty()...)
模拟实现list的类的基本功能（增删等操作）要建立在迭代器类和节点类均已实现好的情况下才得以完成。
✨list 节点类
- 定义list中的节点ListNode，包含前驱指针，后驱指针和数据变量；
- 使用struct而不使用class定义类，是为了方便访问每个一个节点 ，struct默认是pbulic，而class中成员变量要定义为private，不方便访问。
template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} };✨list 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
- 指针可以解引用，迭代器的类中必须重载operator*()
- 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
- 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
- 至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--
- 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
📖定义
template<class T,class Ref,class Ptr> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T,Ref,Ptr> Self; //内置类型 指针 Node* _node; }- 可以发现这里list的模板含有三个类型参数，这样做是为了方便让编译器能依照模板自动生成一个const迭代器，而不需要我们手动写。
- 两个参数名Ref（reference:引用）和Ptr（pointer:指针），见名知义。
📖构造函数
ListIterator(Node* node) :_node(node) {}迭代器指向所传节点
📖解引用
//*it 解引用 //T& operator*() Ref operator*() { return _node->_data; } //it-> //T* operator->() Ptr operator->() { return &_node->_data; }- 重载 * ，解引用就可以直接访问到节点里面的数据data
- 如果访问的数据是Date类型的，那么重载 -> 就可以访问到Date类里面的_year、_day等（如果是Date类，那data就说Date类里面的数据）
📖operator前置++和--与后置++和--
//前置++ Self& operator++() { _node = _node->_next; return *this; } //后置++ Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; // tmp 是一个局部变量，它在函数返回后将不再存在，所以不能返回引用 } //前置-- Self& operator--() { _node = _node->_prev; return *this; } //后置-- Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp;// tmp 是一个局部变量，它在函数返回后将不再存在，所以不能返回引用 }注：
- 这里值得注意的是，为了区分前置和后置，我们会在后置的重载函数中传缺省值int，从而与前置构成重载
- 局部变量不能返回引用
📖operator==与operator!=
bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } - 这个比较的就是两个迭代器中指向的节点的地址是否相等，从而可以判断迭代器是否指向了end() 。
✨list 类
template<class T> class list { typedef ListNode<T> Node; public : typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T,const T&,const T*> const_iterator; private: Node* _head; size_t _size; }- 迭代器写成三个参数类型的模板，可以让编译器生成两个类，一个普通的iterator和一个const_iterator
const_iterator只能读取它所指向的元素，不能修改。
📖构造函数
//带头双向循环链表的构造函数 list() { _head = new Node; _head->_next = _head; _head->_prev = _head; }- 初始化时，new一个头节点，然后使这个头节点的前后指针都指向自己
📖begin()和end()
iterator begin() { return _head->_next;//也可以直接这么写，进行隐式类型转换（单参数的构造函数支持隐式类型转换） } iterator end() { return iterator(_head);//匿名对象，局部变量 不能返回引用 } //const迭代器需要的是迭代器指向的内容不能修改 //const iterator 是迭代器本身不能修改 const_iterator begin() const { return _head->_next; } const_iterator end()const { return const_iterator(_head); }- 返回时使用了匿名对象，不用实例化一个新的对象
- 不能引用返回的匿名对象
- const迭代器指向的内容不能修改
📖拷贝构造
//lt2(lt) list(const list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } }- list的每个节点不连续，需要一个个拷贝
- 需要析构的时候，一般就需要自己写深拷贝
📖erase()
iterator erase(iterator pos) { //prev cur next Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; _size--; prev->_next = next; next->_prev = prev; delete cur; return iterator(next);//匿名对象，局部变量 不能返回引用 }delete删除节点,每一个节点都是动态开辟出来的
- 返回被删除元素后面一个元素的迭代器位置
📖clear()
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } //不清除头节点 }- erase之后，it更新到下一个节点的位置继续erase
- clear()不删除头节点
📖析构函数
~list() { clear(); delete _head; _head = nullptr; }- clear()删除除去头节点以外的所有节点
- delete删除头节点
📖insert
void insert(iterator pos, const T& val) { Node* cur = pos._node; Node* newnode = new Node(val); Node* prev = cur->_prev; _size++; //prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; }- 插入到pos位置之前
📖push_back 和 push_front
void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); }- 复用insert ()
📖pop_back 和 pop_front
void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }- 复用erase()
✨完整代码
template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} }; template<class T,class Ref,class Ptr> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T,Ref,Ptr> Self; //内置类型 指针 Node* _node; ListIterator(Node* node) :_node(node) {} //*it 解引用 //T& operator*() Ref operator*() { return _node->_data; } //it-> //T* operator->() Ptr operator->() { return &_node->_data; } //前置++ Self& operator++() { _node = _node->_next; return *this; } //后置++ Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; // tmp 是一个局部变量，它在函数返回后将不再存在，所以不能返回引用 } //前置-- Self& operator--() { _node = _node->_prev; return *this; } //后置-- Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp;// tmp 是一个局部变量，它在函数返回后将不再存在，所以不能返回引用 } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } }; template<class T> class list { typedef ListNode<T> Node; public : //typedef ListIterator<T> iterator; //typedef ListConstIterator<T> const_iterator;//重新写一个ListConstIterator类(这个方法比较冗余) typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T,const T&,const T*> const_iterator;//写成模板,让编译器生成两个类，而不是我们自己写 /*iterator begin() { return iterator(_head->_next); }*/ iterator begin() { return _head->_next;//也可以直接这么写，进行隐式类型转换（单参数的构造函数支持隐式类型转换） } iterator end() { return iterator(_head);//匿名对象，局部变量 不能返回引用 } //const迭代器需要的是迭代器指向的内容不能修改 //const iterator 是迭代器本身不能修改 const_iterator begin() const { return _head->_next; } const_iterator end()const { return const_iterator(_head); } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() { //this->empty_init(); empty_init(); } //lt2(lt) list(const list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } //需要析构，一般就需要自己写深拷贝 void swap(list<T>& lt) { //lt是局部变量 std::swap(_head, lt._head); std::swap(_size, lt._size); } //lt1 = lt3 list<T>& operator=(list<T> lt) { swap(lt); return *this; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } //不清除头节点 } ~list() { clear(); delete _head; _head = nullptr; } /*void push_back(const T& x) { Node* newnode = new Node(x); Node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; }*/ void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } void insert(iterator pos, const T& val) { Node* cur = pos._node; Node* newnode = new Node(val); Node* prev = cur->_prev; _size++; //prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; _size--; prev->_next = next; next->_prev = prev; delete cur; return iterator(next);//匿名对象，局部变量 不能返回引用 } size_t size()const { return _size; } bool empty() { return _size == 0; } private: Node* _head; size_t _size; };____________________
⭐感谢你的阅读，希望本文能够对你有所帮助。如果你喜欢我的内容，记得点赞关注收藏我的博客，我会继续分享更多的内容。⭐
