8.list的insert、erase等接口
当我们实现了迭代器以后，剩余的接口其实就很简单了，与C语言中list的实现是一模一样的。
void push_back(const T& val) { //insert(end(), val); Node* newnode = new Node(val); Node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; } void push_front(const T& val) { insert(begin(), val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T& val) { Node* newnode = new Node(val); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return newnode; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; cur = nullptr; prev->_next = next; next->_prev = prev; return next; }
9.size
对于这个size，我们有两种方法，第一种如下所示，我们直接遍历统计。这样时间复杂度是O(N)
size_t size() { size_t sz = 0; iterator it = begin(); while (it != end()) { it++; sz++; } return sz; }
还有一种方法是增加一个私有成员变量_size，当插入数据的时候加一，当删除数据的时候减一即可。还有构造函数我们也需要初始化一下这个_size。
这样一来，我们只需要将前面的代码都给修改一下即可。
10.list的clear
对于clear，我们直接复用前面的接口即可。
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
11.list的析构函数
析构函数也是很简单的，析构和clear的区别就是析构会删除头节点，而clear不会删除头节点。
~list() { clear(); delete _head; _head = nullptr; }
12.list拷贝构造函数
我们这里已经涉及到资源的申请与释放了，所以我们必须得构造一个深拷贝构造函数
list(const list<T>& lt) { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; for (auto& e : lt) { push_back(e); } }
当然在这里我们可能会觉得拷贝构造和默认构造有点重复了。我们可以对前面重复的部分在封装一个函数，从而简化代码
void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() { //_head = new Node; //_head->_next = _head; //_head->_prev = _head; //_size = 0; empty_init(); } list(const list<T>& lt) { //_head = new Node; //_head->_next = _head; //_head->_prev = _head; //_size = 0; empty_init(); for (auto& e : lt) { push_back(e); } }
13.赋值运算符重载
如下所示，这个也是比较简单，我们直接使用现代写法即可
void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(list<T> lt) { swap(lt); return *this; }
这里我们还有一个东西需要注意的是
我们也许会发现，库里面的函数返回值和形参写的是类名，而不是类型
这个的话，是因为在类模板里面写成员函数的时候，是允许用类名代替类型的。
即我们的代码下面这些部分可以直接换为类名，但是呢，这里不建议使用，因为会降低可读性。
14. 测试代码
我们现在用如下的代码可以测试出以上的全部函数的使用
void test3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; lt.push_front(6); lt.push_front(7); lt.push_front(8); lt.push_front(9); lt.push_front(10); for (auto e : lt) { cout << e << " "; } cout << endl; Print(lt); cout << lt.size() << endl; lt.clear(); cout << lt.size() << endl; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); it = lt.begin(); it++; for (auto e : lt) { cout << e << " "; } cout << endl; it = lt.insert(it, 100); for (auto e : lt) { cout << e << " "; } cout << endl; it--; it = lt.insert(it, 200); for (auto e : lt) { cout << e << " "; } cout << endl; ++it; it = lt.insert(it, 300); for (auto e : lt) { cout << e << " "; } cout << endl; --it; it = lt.erase(it); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; list<int> lt2; lt2.push_back(1); lt2 = lt; for (auto e : lt2) { cout << e << " "; } cout << endl; }
经测试，运行结果正常
三、模拟list类的全部代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<list> #include<assert.h> using namespace std; namespace Sim { template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _val; list_node(const T& val = T()) :_next(nullptr) ,_prev(nullptr) ,_val(val) {} }; template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; __list_iterator(Node* node) :_node(node) {} Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } self& operator++() { _node = _node->_next; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self & it) const { return _node != it._node; } bool operator==(const self & it) const { return _node == it._node; } }; //template<class T> //struct __list_const_iterator //{ // typedef list_node<T> Node; // Node* _node; // __list_const_iterator(Node* node) // :_node(node) // {} // const T& operator*() // { // return _node->_val; // } // __list_const_iterator<T>& operator++() // { // _node = _node->_next; // return *this; // } // __list_const_iterator<T> operator++(int) // { // __list_const_iterator<T> tmp(*this); // _node = _node->_next; // return tmp; // } // bool operator!=(const __list_const_iterator<T>& it) // { // return _node != it._node; // } // bool operator==(const __list_const_iterator<T>& it) // { // return _node == it._node; // } //}; template<class T> class list { typedef list_node<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; //typedef __list_const_iterator<T> const_iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; iterator begin() { //return _head->_next //单参数的构造函数支持隐式类型转换 return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { //return _head->_next //单参数的构造函数支持隐式类型转换 return const_iterator(_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() { //_head = new Node; //_head->_next = _head; //_head->_prev = _head; //_size = 0; empty_init(); } list(const list<T>& lt) { //_head = new Node; //_head->_next = _head; //_head->_prev = _head; //_size = 0; empty_init(); for (auto& e : lt) { push_back(e); } } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(list<T> lt) { swap(lt); return *this; } void push_back(const T& val) { insert(end(), val); //Node* newnode = new Node(val); //Node* tail = _head->_prev; //tail->_next = newnode; //newnode->_prev = tail; //newnode->_next = _head; //_head->_prev = newnode; } void push_front(const T& val) { insert(begin(), val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T& val) { Node* newnode = new Node(val); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return newnode; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; cur = nullptr; prev->_next = next; next->_prev = prev; --_size; return next; } size_t size() { //size_t sz = 0; //iterator it = begin(); //while (it != end()) //{ // it++; // sz++; //} //return sz; return _size; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } private: Node* _head; size_t _size; }; void Print(const list<int> lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << (*it) << " "; ++it; } cout << endl; } void test1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; Print(lt); } struct A { A(int a = 0, int b = 0) :_a(a) ,_b(b) {} int _a; int _b; }; void Print(const list<A>& lt) { list<A>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << it->_a << " "; it++; } cout << endl; } void test2() { list<A> lt; lt.push_back(A(1, 1)); lt.push_back(A(2, 2)); lt.push_back(A(3, 3)); lt.push_back(A(4, 4)); lt.push_back(A(5, 5)); cout << lt.size() << endl; lt.clear(); cout << lt.size() << endl; list<A>::iterator it = lt.begin(); while (it != lt.end()) { cout << it->_a << " "; it++; } cout << endl; Print(lt); } void test3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; lt.push_front(6); lt.push_front(7); lt.push_front(8); lt.push_front(9); lt.push_front(10); for (auto e : lt) { cout << e << " "; } cout << endl; Print(lt); cout << lt.size() << endl; lt.clear(); cout << lt.size() << endl; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); it = lt.begin(); it++; for (auto e : lt) { cout << e << " "; } cout << endl; it = lt.insert(it, 100); for (auto e : lt) { cout << e << " "; } cout << endl; it--; it = lt.insert(it, 200); for (auto e : lt) { cout << e << " "; } cout << endl; ++it; it = lt.insert(it, 300); for (auto e : lt) { cout << e << " "; } cout << endl; --it; it = lt.erase(it); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; list<int> lt2; lt2.push_back(1); lt2 = lt; for (auto e : lt2) { cout << e << " "; } cout << endl; } }
好了，本节内容就到这里了
本节内容难度稍大，希望读者可以好好阅读。有不懂的可以及时私聊博主解答疑惑
如果对你有帮助的话，不要忘记点赞加收藏哦！！！
