c++ STL容器之list 实现

代码中的注释已经写的比较清楚了，就直接上代码吧

#include <iostream> // 节点定义 template<typename T> struct ListNode { ListNode *prev; ListNode *next; T data; }; template<typename T> class MyList { private: using Node = ListNode<T>; public: /** * iterator类作用 * 如果没有iterator类，则MyList类对外暴露Node*类型，用户可以自定义操作节点 * 现在是用iterator类，封装指针节点的指针，通过运算符重载只给用户提供遍历和访问的能力 * 从而屏蔽容器内部的节点结构，禁止用户直接操作节点。 * */ class iterator { public: iterator(Node* n = nullptr) : _node(n) {} T& operator*() const {return _node->data;} T* operator->() const {return &_node->data;} iterator& operator++() { _node = _node->next; return *this; } iterator operator++(int) { iterator t = *this; ++(*this); return t; } iterator& operator--() { _node = _node->prev; return *this; } bool operator==(const iterator& obj) const { return _node == obj._node; } bool operator!=(const iterator& obj) const { return _node != obj._node; } friend class MyList; private: Node *_node; }; /** * 限制“通过迭代器访问元素的能力”，而不是容器或节点本身是否可修改。 */ class const_iterator { public: const_iterator(Node *n = nullptr): _node(n) {} const_iterator(const iterator& it) : _node(it._node) {} const T& operator*() const {return _node->data;} const T* operator->() const {return &_node->data;} const_iterator& operator++() { _node = _node->next; return *this; } const_iterator operator++(int) { const_iterator t = *this; ++(*this); return t; } const_iterator& operator--() { _node = _node->prev; return *this; } bool operator==(const const_iterator& obj) const { return _node == obj._node; } bool operator!=(const const_iterator& obj) const { return _node != obj._node; } friend class MyList; private: Node *_node; }; public: MyList() : _size(0) { _head = new Node; _head->next = _head; _head->prev = _head; } ~MyList() { clear(); delete _head; } bool empty() const {return _size == 0;} size_t size() const {return _size;} iterator begin() {return iterator(_head->next);} const_iterator begin() const {return const_iterator(_head->next);} iterator end() {return iterator(_head);} // 返回最后一个元素前一个位置 const_iterator end() const {return const_iterator(_head);} // 在 pos 前面插入新节点 O(1) void insert(iterator pos, const T &val) { Node *cur = pos._node; Node* prev = cur->prev; Node *n = new Node; n->data = val; // 分别指向前后节点 n->next = cur; n->prev = prev; // 前一个的下一个节点为当前插入的节点 prev->next = n; // 在当前节点之前插入，则前置指针指向新的节点 cur->prev = n; ++_size; } // 清除当前节点 iterator erase(iterator pos) { Node * cur = pos._node; Node * prev = cur->prev; Node * next = cur->next; // 上一个与下一个节点都取消对当前节点的指向 prev->next = next; next->prev = prev; delete cur; --_size; return iterator(next); // 删除当前节点之后，下一个节点按顺序变为这个位置的节点 } void push_back(const T&val) { insert(end(),val); // 直接调用inset 方法,在末尾直接插入 } void push_front(const T&val) { insert(begin(),val); //front 在表头插入 } void pop_back() { erase(--end()); // 删除表尾 } void pop_front() { erase(begin()); // 删除表头 } void clear() { Node * cur = _head->next; while(cur != _head) { Node* next = cur->next; delete cur; cur = next; } _head->next = _head; _head->prev = _head; _size = 0; } /** * splice 含义： * 不拷贝、不构造、不析构元素， * 仅通过修改指针，把节点从一个 list 挂到另一个 list。 * 本质是：“改链表结构，而不是操作元素” 即直接修改指针 * */ // 把 other 中 [first, last) 区间移动到 pos 前 void splice(iterator pos,MyList &other,iterator first,iterator last) { if (first == last) return; // 如果 pos 落在 [first, last) 区间内 什么也不做 /** * 处理自己与自己的元素移动 self-splice * list:0 1 2 3 _head <-> 0 <-> 1 <-> 2 <-> 3 <-> _head * 例如传递参数(begin(),list,begin(),begin() + 1) 即把[0,1)区间的元素移动到0之前 * 当没有下面的判断则会: * firstNode = &0 lastNode = &1 lastPrev = &0 * firstNode->prev->next = lastNode * lastNode->prev = firstNode->prev; * 相当于 _head <-> 1 <-> 2 <-> 3 <-> _head, _head<- 0 ->1 通过链表已经找不到0元素了 * * posNode = &0 posPrev = _head; * posPrev->next = firstNode; * 相当于 _head -> 0 -> 1 <-> 2 <-> 3 <-> _head , 但是_head <- 1; 1前驱变为_head * * firstNode->prev = posPrev; * 相当于 _head <-> 0 -> 1 <-> 2 <-> 3 <-> _head , _head <- 1; * * 错误点： * lastPrev->next = posNode; * posNode->prev = lastPrev; * 0 与 0 产生自环 0 <-> 0 * 0 的前驱也指向自己，与_head断开,即链表元素变为 1 <-> 2 <-> 3, 1 <- _head,3 -> _head */ if(this == &other) { for(auto it = first; it != last; it++) { if (it == pos) return; } } Node *firstNode = first._node; Node *lastNode = last._node; Node *lastPrev = lastNode->prev; // [first, last) 之中的节点从整个链表中脱离 firstNode->prev->next = lastNode; lastNode->prev = firstNode->prev; // 将[first, last)指针指向ops之前 Node *posNode = pos._node; Node *posPrev = posNode->prev; // 修改first指向与lastpre指向 posPrev->next = firstNode; firstNode->prev = posPrev; lastPrev->next = posNode; posNode->prev = lastPrev; // 修改size size_t cnt = 0; for(auto it = first; it != last; it++) cnt += 1; _size += cnt; other._size -= cnt; } // 把 other 整个移动到pos前 void splice(iterator pos, MyList& other) { if (other.empty()) return; splice(pos, other, other.begin(), other.end()); } //把 other 中 it 指向的一个节点移动到 pos 前 void splice(iterator pos, MyList& other, iterator it) { iterator next = it; ++next; // [it,next) 区间直接移动 splice(pos, other, it, next); } private: Node *_head; // 头节点 size_t _size; };