模拟编写一个简易的list

目录1.编写简易list1.定义节点2.构造函数3.push_back4.size(),empty()5.迭代器6.insert7.erase8.pop_back,pop_front9.operator-1. operator* 的调用2. operator- 的调用10.print_container问题为什么一直写的是const_iterator而不是const iterator?问题那么如何保证const迭代器指向内容不能修改呢11.简化代码12.迭代器失效问题13.list的析构函数14.拷贝构造15.赋值16.补充 initializer_list17.完整代码上一篇文章我们对list的接口进行了了解接下来我们进行模拟编写一个简易的list1.编写简易list1.定义节点使用类模板定义一个list_node和list把两者分离其实就是跟链表一样。通过一个个节点链接起来namespace bit { templateclass T struct list_node { T _data; list_nodeT* _next; list_nodeT* _prev; }; templateclass T class list { typedef list_nodeT Node; private: Node* _head; size_t _size; }; }2.构造函数我们在这里进行构造函数初始化操作list() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; }3.push_backvoid 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; _size; }4.size(),empty()size_t size() const { return _size; } bool empty() const { return _size 0; }5.迭代器list无法到下一个节点不像前面那些一样。用一个类去封装节点的指针最终代码#pragma once #includeiostream using namespace std; namespace bit { templateclass T struct list_node { T _data; list_nodeT* _next; list_nodeT* _prev; list_node(const T dataT())//构造 :_data(data) ,_next(nullptr) ,_prev(nullptr) { } }; templateclass T struct list_iterator { typedef list_nodeT Node; typedef list_iteratorT Self; Node* _node; list_iterator(Node* node)//构造函数 :_node(node) { } T operator*() { return _node-_data; } 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 s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } }; templateclass T class list { typedef list_nodeT Node; public: typedef list_iteratorT iterator; iterator begin() { ////有名对象 //iterator it(_head-_next); //return it; //匿名对象 //return iterator(_head-_next); return _head-_next; } iterator end() { return _head;//隐式类型转换 } list() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; } 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; _size; } size_t size() const { return _size; } bool empty() const { return _size 0; } private: Node* _head; size_t _size; }; void test_list1() { listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); listint::iterator it lt.begin(); while (it ! lt.end()) { cout *it ; it; } cout endl; } }测试6.insertvoid insert(iterator pos, const T x) { Node* cur pos._node; Node* prev cur-_prev; Node* newnode new Node(x); //prev newnode cur newnode-_next cur; cur-_prev newnode; newnode-_prev prev; prev-_next newnode; _size; }我们可以发现实现了insert之前的push_back就可以不用自己实现了直接调用insert同理push_front也是一样。void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); }7.erasevoid erase(iterator pos) { assert(pos ! end()); Node* prev pos._node-_prev; Node* next pos._node-_next; prev-_next next; next-_prev prev; delete pos._node; --_size; }8.pop_back,pop_front同理跟之前push_backpush_front类似直接调用即可void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }9.operator-在 C 中-和.的使用取决于左侧表达式的类型左侧是指针或重载了-的类对象如迭代器、智能指针使用-例如it-_a1其中it是迭代器其operator-返回元素的指针左侧是对象或引用使用.例如obj._a1obj是普通对象或引用定义一个AA类struct AA { int _a11; int _a21; };如果是这样会报错AA目前不支持流插入listAA lta; lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); listAA::iterator ita lta.begin(); while (ita ! lta.end()) { cout *ita ; ita; } cout endl;可以写一个流插入也可以改成如下*ita返回的是AA引用通过(*ita)._a1可以取到结构体成员listAA lta; lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); listAA::iterator ita lta.begin(); while (ita ! lta.end()) { cout (*ita)._a1 :(*ita)._a2endl; ita; } cout endl;或者重载一个operator-T* operator-() { return _node-_data; }listAA lta; lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); listAA::iterator ita lta.begin(); while (ita ! lta.end()) { //cout (*ita)._a1 :(*ita)._a2endl; cout ita-_a1 : ita-_a2 endl; ita; } cout endl;特殊处理本来应该是两个-才合理为了可读性省略了一个-cout ita.operator-()-_a1 : ita.operator-()-_a2 endl;1.operator*的调用当写*ita时编译器会调用ita.operator*()它返回_node-_data的引用AA。因此*ita就是节点中存储的AA对象本身可以用.访问其成员例如(*ita)._a1。2.operator-的调用当写ita-_a1时编译器将其转换为ita.operator-()-_a1先调用ita.operator-()它返回_node-_data即AA*。再对这个指针使用内置的-访问_a1成员。所以ita-_a1等价于ita.operator-()-_a1第二个就是显式写出了这个两步过程。10.print_containertemplateclass Container void print_container(const Container con) { for (auto e : con) { cout e ; } cout endl; }直接调用前面vector写的进行调用print_container(lt);结果发现报错如果不调就没事。其实是还没实现const迭代器导致的。print_container函数接受const Container con这意味着con是一个const 引用。在函数内部范围for循环会展开为auto it con.begin(); // 需要调用 const 版本的 begin() auto end con.end(); // 需要调用 const 版本的 end()但我们的list类只提供了非const的begin()和end()iterator begin() { return _head-_next; } iterator end() { return _head; }这些成员函数没有const限定因此不能被const对象调用。编译器会报错提示“无法将this指针从const转换为非const”。问题为什么一直写的是const_iterator而不是const iterator?const迭代器是指向的内容不能修改而不是自身就像指针T* const ptr修饰本身const T* ptr指向修饰的内容const iterator --- 迭代器本身不能修改const_iterator --- 指向内容不能修改问题那么如何保证const迭代器指向内容不能修改呢这些内容修改时通过operator*跟operator-所以写一个const迭代器const里面的*跟-templateclass T struct list_const_iterator { typedef list_nodeT Node; typedef list_const_iteratorT Self; Node* _node; list_const_iterator(Node* node)//构造函数 :_node(node) { } const T operator*() { return _node-_data; } const T* operator-() { return _node-_data; } 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 s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } };在list类中typedef一下同时多写两个begin跟endtypedef list_const_iteratorT const_iterator; const_iterator begin() const { return _head-_next; } const_iterator end() const { return _head;//隐式类型转换 }//按需实例化 templateclass Container void print_container(const Container con) { listint::const_iterator it con.begin(); while (it ! con.end()) { *it 10;//返回const T cout *it ; it; } cout endl; for (auto e : con) { cout e ; } cout endl; }我们会发现如果在里面修改也就是*it 10; 编译器并没有报错这就是按需实例化。这种细节上的东西没有进行实际上的调用编译器检查不出来。如果把print_container那个调用取消注释会发现报错将*it 10;取消掉就通过了。11.简化代码但是搞两个差不多的类模板(list_iterator跟list_const_iterator)大部分的代码都相同是不是有点冗余有没有什么方法可以简化吗?库里面的实现用同一个类模板增加两个模板参数进行控制这样就不用写两个类实现了类模板给编译器给了不同的模板参数编译器实例化出了两个不同的类templateclass T, class Ref, class Ptr struct list_iterator { typedef list_nodeT Node; typedef list_iteratorT, Ref, Ptr Self; Node* _node; list_iterator(Node* node) :_node(node) { } Ref operator*() { return _node-_data; } Ptr operator-() { return _node-_data; } Self operator() { _node _node-_next; return *this; } Self operator--() { _node _node-_prev; return *this; } Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; } Self operator--(int) { Self tmp(*this); _node _node-_prev; return tmp; } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } };typedef list_iteratorT,T,T* iterator; typedef list_iteratorT,const T,const T* const_iterator;12.迭代器失效问题测试void test_list2() { listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); // insert以后迭代器不失效 listint::iterator it lt.begin(); lt.insert(it, 10); *it 100; print_container(lt); }可以发现insert没有迭代器失效的问题但是我们后面会发现erase有迭代器失效的问题。// erase以后迭代器失效 // 删除所有的偶数 it lt.begin(); while (it ! lt.end()) { if (*it % 2 0) { lt.erase(it); } it; }1.insert为什么不失效链表节点是独立分配的通过new Node插入操作只修改相邻节点的_next和_prev指针并不移动已有节点。因此指向任何已有节点的迭代器如it所指向的内存地址不会改变依然有效。2.erase为什么失效erase会删除指定的节点delete pos._node该节点的内存被释放。因此指向该节点的迭代器变成野指针再次使用会导致未定义行为通常崩溃。所以说解决方案还是去接收这个返回值void test_list2() { listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); // insert以后迭代器不失效 listint::iterator it lt.begin(); lt.insert(it, 10); *it 100; print_container(lt); // erase以后迭代器失效 // 删除所有的偶数 it lt.begin(); while (it ! lt.end()) { if (*it % 2 0) { it lt.erase(it); } else { it; } } print_container(lt); }两个也都给一下返回值iterator insert(iterator pos, const T x) { Node* cur pos._node; Node* prev cur-_prev; Node* newnode new Node(x); //prev newnode cur newnode-_next cur; cur-_prev newnode; newnode-_prev prev; prev-_next newnode; _size; return newnode; } iterator erase(iterator pos) { assert(pos ! end()); Node* prev pos._node-_prev; Node* next pos._node-_next; prev-_next next; next-_prev prev; delete pos._node; --_size; return next; }同时如果我们调用库里面会发现我们之前print_container有点写死了typename Container::const_iterator it con.begin();或者auto it con.begin();//按需实例化 templateclass Container void print_container(const Container con) { //listint::const_iterator it con.begin(); typename Container::const_iterator it con.begin(); //auto it con.begin(); while (it ! con.end()) { //*it 10;//返回const T cout *it ; it; } cout endl; for (auto e : con) { cout e ; } cout endl; }13.list的析构函数~list() { clear(); delete _head; _head nullptr; } void clear() { auto it begin(); while (it ! end()) { it erase(it);//避免迭代器失效。会返回下一个位置的迭代器 } }14.拷贝构造void test_list3() { listint lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); listint lt2(lt1); print_container(lt1); print_container(lt2); }会崩溃原因是浅拷贝要实现一个深拷贝// lt2(lt1) list(const listT lt) { for (auto e : lt) { push_back(e); } }结果发现编译编不过是因为lt2没有哨兵位的头节点所以说如果是个空链表要走一个空初始化void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; } list() { empty_init(); }// lt2(lt1) list(const listT lt) { empty_init(); for (auto e : lt) { push_back(e); } }15.赋值listint lt3; lt3.push_back(10); lt3.push_back(20); lt3.push_back(30); lt3.push_back(40); lt1 lt3; print_container(lt1); print_container(lt3);同样赋值不写也是浅拷贝写个深拷贝// lt1 lt3 //现代写法 listT operator(listT lt) { swap(lt); return *this; } void swap(listT lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); }16.补充 initializer_list标准库里面有这样初始化的void test_list4() { std::listint lt1 {1,2,3,4,5,6}; print_container(lt1); }我们这样就不太行这涉及到C11中的initializer_list支持begin和end迭代器但支持读不支持写x86下x64下需要其支持如下构造list(initializer_listT il) { empty_init(); for (auto e : il) { push_back(e); } }void func(const listint lt) { print_container(lt); }void test_list4() { // 直接构造 listint lt0({ 1,2,3,4,5,6 }); // 隐式类型转换 listint lt1 { 1,2,3,4,5,6,7,8 }; const listint lt3 { 1,2,3,4,5,6,7,8 }; func(lt0);//fun可以直接传链表 func({ 1,2,3,4,5,6 });//也可以直接传这个 print_container(lt1); //auto il { 10, 20, 30 }; /* initializer_listint il { 10, 20, 30 }; cout typeid(il).name() endl; cout sizeof(il) endl;*/ }17.完整代码List.h#pragma once #includeiostream #includeassert.h using namespace std; namespace bit { templateclass T struct list_node { T _data; list_nodeT* _next; list_nodeT* _prev; list_node(const T dataT())//构造 :_data(data) ,_next(nullptr) ,_prev(nullptr) { } }; templateclass T, class Ref, class Ptr struct list_iterator { typedef list_nodeT Node; typedef list_iteratorT, Ref, Ptr Self; Node* _node; list_iterator(Node* node) :_node(node) { } Ref operator*() { return _node-_data; } Ptr operator-() { return _node-_data; } Self operator() { _node _node-_next; return *this; } Self operator--() { _node _node-_prev; return *this; } Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; } Self operator--(int) { Self tmp(*this); _node _node-_prev; return tmp; } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } }; //templateclass T //struct list_iterator //{ // typedef list_nodeT Node; // typedef list_iteratorT Self; // Node* _node; // list_iterator(Node* node)//构造函数 // :_node(node) // { } // T operator*() // { // return _node-_data; // } // T* operator-() // { // return _node-_data; // } // 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 s) const // { // return _node ! s._node; // } // bool operator(const Self s) const // { // return _node s._node; // } //}; //templateclass T //struct list_const_iterator //{ // typedef list_nodeT Node; // typedef list_const_iteratorT Self; // Node* _node; // list_const_iterator(Node* node)//构造函数 // :_node(node) // { } // const T operator*() // { // return _node-_data; // } // const T* operator-() // { // return _node-_data; // } // 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 s) const // { // return _node ! s._node; // } // bool operator(const Self s) const // { // return _node s._node; // } //}; templateclass T class list { typedef list_nodeT Node; public: //typedef list_iteratorT iterator; //typedef list_const_iteratorT const_iterator; typedef list_iteratorT,T,T* iterator; typedef list_iteratorT,const T,const T* const_iterator; iterator begin() { ////有名对象 //iterator it(_head-_next); //return it; //匿名对象 //return iterator(_head-_next); return _head-_next; } iterator end() { return _head;//隐式类型转换 } const_iterator begin() const { return _head-_next; } const_iterator end() const { return _head;//隐式类型转换 } //list() //{ // _head new Node; // _head-_next _head; // _head-_prev _head; // _size 0; //} void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; } list() { empty_init(); } list(initializer_listT il) { empty_init(); for (auto e : il) { push_back(e); } } // lt2(lt1) list(const listT lt) { empty_init(); for (auto e : lt) { push_back(e); } } // lt1 lt3 listT operator(listT lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head nullptr; } void clear() { auto it begin(); while (it ! end()) { it erase(it);//避免迭代器失效。会返回下一个位置的迭代器 } } void swap(listT lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } 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; //_size; 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 newnode cur newnode-_next cur; cur-_prev newnode; newnode-_prev prev; prev-_next newnode; _size; return newnode; } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator erase(iterator pos) { assert(pos ! end()); Node* prev pos._node-_prev; Node* next pos._node-_next; prev-_next next; next-_prev prev; delete pos._node; --_size; return next; } size_t size() const { return _size; } bool empty() const { return _size 0; } private: Node* _head; size_t _size; }; struct AA { int _a11; int _a21; }; //按需实例化 templateclass Container void print_container(const Container con) { //listint::const_iterator it con.begin(); typename Container::const_iterator it con.begin(); //auto it con.begin(); while (it ! con.end()) { //*it 10;//返回const T cout *it ; it; } cout endl; for (auto e : con) { cout e ; } cout endl; } void test_list1() { listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); listint::iterator it lt.begin(); while (it ! lt.end()) { *it 10; cout *it ; it; } cout endl; for (auto e : lt) { cout e ; } cout endl; print_container(lt); listAA lta; lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); listAA::iterator ita lta.begin(); while (ita ! lta.end()) { //cout (*ita)._a1 :(*ita)._a2endl; //特殊处理本来应该是两个-才合理为了可读性省略了一个- cout ita-_a1 : ita-_a2 endl; cout ita.operator-()-_a1 : ita.operator-()-_a2 endl; ita; } cout endl; } void test_list2() { listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); // insert以后迭代器不失效 listint::iterator it lt.begin(); lt.insert(it, 10); *it 100; print_container(lt); // erase以后迭代器失效 // 删除所有的偶数 it lt.begin(); while (it ! lt.end()) { if (*it % 2 0) { it lt.erase(it); } else { it; } } print_container(lt); } void test_list3() { listint lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); listint lt2(lt1); print_container(lt1); print_container(lt2); listint lt3; lt3.push_back(10); lt3.push_back(20); lt3.push_back(30); lt3.push_back(40); lt1 lt3; print_container(lt1); print_container(lt3); } void func(const listint lt) { print_container(lt); } void test_list4() { // 直接构造 listint lt0({ 1,2,3,4,5,6 }); // 隐式类型转换 listint lt1 { 1,2,3,4,5,6,7,8 }; const listint lt3 { 1,2,3,4,5,6,7,8 }; func(lt0); func({ 1,2,3,4,5,6 }); print_container(lt1); //auto il { 10, 20, 30 }; } }Test.cpp#includeList.h int main() { //bit::test_list1(); //bit::test_list2(); //bit::test_list3(); bit::test_list4(); }今天的模拟一个简易的list就到此结束期待我们下一次见面