C++--list 蔚落 2024-03-30 14:38 39阅读 0赞 ### 前言 ### 这篇文章对于理解封装是非常有帮助的,list的底层是双向链表结构,我们在学习数据结构是就已经学过了双向链表,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。因为list独特的结构,在模拟实现的时候就会发现为了list接口更好为用户使用更多是通过封装。 这篇文章会开始从list的使用开始,看完list的使用之后你会发现跟string和vector的接口使用几乎是一样的,虽然他们的使用是一样的,他的接口都是一样的,但是后面我们通过对接口的模拟实现,你就会发现是不一样,到底哪里不一样就需要你的深入观看--卖个关子。总的来说这篇文章就是来展示迭代器的魅力和模板的魅力。 -------------------- **目录** 前言 一、list的介绍及使用 1.1list的介绍 1.2.list的使用 二、list的模拟实现--非const 2.1list的节点 2.2list的迭代器 2.2迭代器的价值 2.3list的接口 三、list的模拟实现--const 3.1理解const修饰iterator 3.2实现const修饰iterator 四、list的模拟实现--大佬的iterator 4.1第三个参数 4.2大佬的iterator 五、反向迭代器 -------------------- ### 一、list的介绍及使用 ### -------------------- #### 1.1list的介绍 #### list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。因为list的底层是双向链表结构。 list与forward\_list非常相似:最主要的不同在于forward\_list是单链表,只能朝前迭代,已让其更简单高效。与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。 与其他序列式容器相比,list和forward\_list最大的缺陷是**不支持任意位置的随机访问,**比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。 **带头循环双向链表** ![dc391b9d63674bf98fb421a61ae5c8a1.png][] #### 1.2.list的使用 #### 对于list的使用来说,list中的接口比较多,实则是与vector差不多的,接下来我们就来简单的演示,掌握list正确的使用,然后再去深入研究背后的原理,已达到可扩展的能力。 **1.2.1 list的构造** <table style="width:700px;"> <tbody> <tr> <td style="width:377px;">构造函数( (constructor))</td> <td style="width:321px;">接口说明</td> </tr> <tr> <td style="width:377px;">list (size_type n, const value_type& val = value_type())</td> <td style="width:321px;">构造的list中包含n个值为val的元素</td> </tr> <tr> <td style="width:377px;">list()</td> <td style="width:321px;">构造空的list</td> </tr> <tr> <td style="width:377px;">list (const list& x)</td> <td style="width:321px;">拷贝构造函数</td> </tr> <tr> <td style="width:377px;">list (InputIterator first, InputIterator last)</td> <td style="width:321px;">用[first, last)区间中的元素构造list</td> </tr> </tbody> </table> **例:** void TestList1() { list<int> l1; // 构造空的l1 list<int> l2(4, 100); // l2中放4个值为100的元素 list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end())左闭右开的区间构造l3 list<int> l4(l3); // 用l3拷贝构造l4 // 以数组为迭代器区间构造l5 int array[] = { 16, 2, 77, 29 }; list<int> l5(array, array + sizeof(array) / sizeof(int)); // 列表格式初始化C++11 list<int> l6{ 1, 2, 3, 4, 5 }; // 用迭代器方式打印l5中的元素 list<int>::iterator it = l5.begin(); while (it != l5.end()) { cout << *it << " "; ++it; } cout << endl; // C++11范围for的方式遍历 for (auto& e : l5) cout << e << " "; cout << endl; } **1.2.2 list iterator的使用** 在list使用中,我们通过迭代器的方式打印链表元素,在vector中我们用的是\[\],因为vector是顺序表结构,我们可以通过下标进行随机访问。而list却不能,只能用迭代器的方式进行,它的行为像指针一样。这个后面会通过源码剖析的角度来看待,这里就简单的认为迭代就类似于指针。 list是链表结构,在链表中因为内存地址不是连续开辟的,比如:通过下标2去找地址,顺序表中,地址是连续对应的,而链表的地址是随机开辟的,通过下标是不能找到相应的地址的。 ![e914fdd03aea46b98f8a6d2956a704b5.png][] 以上就是证明为什么list不能用\[\]访问,而选择用迭代器。 <table style="width:700px;"> <tbody> <tr> <td style="width:239px;">函数声明</td> <td style="width:459px;">接口说明</td> </tr> <tr> <td style="width:239px;">begin+end</td> <td style="width:459px;">返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器</td> </tr> </tbody> </table> **例:** // list迭代器的使用 // 注意:遍历链表只能用迭代器和范围for void PrintList(const list<int>& l) { // 注意这里调用的是list的 begin() const,返回list的const_iterator对象 for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) { cout << *it << " "; // *it = 10; 编译不通过 } cout << endl; } int main() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); PrintList(l); return 0; } 这里需要说明一下就是begin和end既能使用iterator又能使用const\_iterator。 > begin > iterator begin();const_iterator begin() const; > end > iterator end();const_iterator end() const; 使用const\_iterator it =l.begin();这里是通过拷贝构造,即使我们没有写拷贝构造,但是系统会默认生成拷贝构造将指针进行拷贝。 > const\_iterator it = l.begin(); **1.2.3list capacity** 在链表中就不需要提前把空间开好,这里是按需申请,就不需要reserve和resize了。 <table style="width:700px;"> <tbody> <tr> <td style="width:239px;">函数声明</td> <td style="width:459px;">接口说明</td> </tr> <tr> <td style="width:239px;">empty</td> <td style="width:459px;">检测list是否为空,是返回true,否则返回false</td> </tr> <tr> <td style="width:239px;">size</td> <td style="width:459px;">返回list中有效节点的个数</td> </tr> </tbody> </table> **例:** int main() { list<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); cout << l.size() << endl; if (!l.empty()) { cout << "no empty!" << endl; } return 0; } **1.2.4 list element access** <table style="width:700px;"> <tbody> <tr> <td style="width:239px;">函数声明</td> <td style="width:459px;">接口说明</td> </tr> <tr> <td style="width:239px;">front</td> <td style="width:459px;">返回list的第一个节点中值的引用</td> </tr> <tr> <td style="width:239px;">back</td> <td style="width:459px;">返回list的最后一个节点中值的引用</td> </tr> </tbody> </table> **例:** void tets_element(list<int>& l) { cout << l.front() << endl; cout << l.back() << endl; } **1.2.5 list modifiers** <table style="width:700px;"> <tbody> <tr> <td style="width:239px;">函数声明</td> <td style="width:459px;">接口说明</td> </tr> <tr> <td style="width:239px;">push_front</td> <td style="width:459px;">在list首元素前插入值为val的元素</td> </tr> <tr> <td style="width:239px;">pop_front</td> <td style="width:459px;">删除list中第一个元素</td> </tr> <tr> <td style="width:239px;">push_back</td> <td style="width:459px;">在list尾部插入值为val的元素</td> </tr> <tr> <td style="width:239px;">insert</td> <td style="width:459px;">在list position 位置中插入值为val的元素</td> </tr> <tr> <td style="width:239px;">erase</td> <td style="width:459px;">删除list position位置的元素</td> </tr> <tr> <td style="width:239px;">swap</td> <td style="width:459px;">交换两个list中的元素</td> </tr> <tr> <td style="width:239px;">clear</td> <td style="width:459px;">清空list中的有效元素</td> </tr> </tbody> </table> **例:** // list插入和删除 void test_modifiers() { list <int> l; //尾插 l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); //尾删 l.pop_back(); PrintList(l); cout << endl; //头插 l.push_front(6); l.push_front(7); l.push_front(8); //头删 l.pop_front(); PrintList(l); cout << endl; //第一个位置插入10 auto pos = l.begin(); l.insert(pos, 10); PrintList(l); cout << endl; // 删除pos位置上的元素 l.erase(++pos); PrintList(l); } // resize/swap/clear void TestList5() { // 用数组来构造list int array1[] = { 1, 2, 3 }; list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0])); PrintList(l1); // 交换l1和l2中的元素 list<int> l2; l1.swap(l2); PrintList(l1); PrintList(l2); // 将l2中的元素清空 l2.clear(); cout << l2.size() << endl; } **1.2.6 list的迭代器失效** 之前在vector中insert是失效的,但是在list中insert是不失效的。因为insert插入并没有改变pos的地址。erase却会失效,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。 ![7c245ac87f2846db84e6e3ab09fda81c.png][] **例:** void TestListIterator1() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array + sizeof(array) / sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { // erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值 l.erase(it); ++it; } } ![1c7e3a0d61fd481f991497ff4bce0b5e.png][] void TestListIterator() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { l.erase(it++); // it = l.erase(it); } } **1.2.7 sort** 在list中单独有sort,在之前是以模板的形式写入算法库<algorithm>。这里就说明因为它是已链表的结构,排序需要重新实现,那么就意味着list中sort的时间复杂度是不一样的。 > list::sort > void sort(); > > std::sort > template <class RandomAccessIterator> > void sort (RandomAccessIterator first, RandomAccessIterator last); 我们通过一段测试代码来比较,同样的长度但是花费时间是巨大的。 void test_op() { srand(time(0)); const int N = 100000; vector<int> v; v.reserve(N); list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); //v.push_back(e); lt1.push_back(e); lt2.push_back(e); } // 拷贝到vector排序,排完以后再拷贝回来 int begin1 = clock(); for (auto e : lt1) { v.push_back(e); } sort(v.begin(), v.end()); size_t i = 0; for (auto& e : lt1) { e = v[i++]; } int end1 = clock(); int begin2 = clock(); // sort(lt.begin(), lt.end()); lt2.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); } > 在运行结果: > > 1.Debug > > vector sort:437 > list sort:6937 > > 2.Release > > vector sort:7 > list sort:16 在N个数据需要排序,vector+ 算法sort list+ sort通过测试发现list中sort是非常耗时的,vector中sort想对来说更加省时直接用list排序还不如将list的数据拷贝到vector中快。 ### 二、list的模拟实现--非const ### 我们会通过几个阶段来进行模拟实现,如果一下将全部模拟实现是加大了学习的成本,是对学习很不友好的。 -------------------- #### 2.1list的节点 #### 因为我们知道list是一个双向链表,所以节点里面有一个前指针,一个后指针,有一个数据data。同时我们也模拟一个构造函数list (const list& x),用于list节点的初始化。 template < class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _data; //构造函数 list_node(const T& x) :_next(nullptr) , _prev(nullptr) , _data(x) {} }; #### 2.2list的迭代器 #### stl3.0当中的迭代器实现: template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } reference operator*() const { return (*node).data; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self& operator++() { node = (link_type)((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { node = (link_type)((*node).prev); return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; } 对于stl3.0当中的迭代器实现,我们首先不去关系为什么是3个模板参数,也不用去深研其他的typedef,我们可以理解在iterator中不单单是一个指针了,当然在iterator也有指针,如下 > typedef \_\_list\_node<T>\* link\_type; > > link\_type node; 在之前我们理解中,我们直接对指针进行操作,进行++,--,\*(解引用)等等操作,但是对于迭代器iterator,我们通过观察发现iterator中,因为list是链式结构,我们对其++,--,接引用是不能直接实现,所以就不能简单的通过指针就能完成这些操作,那么它是通过对iterator封装来实现++,--等操作的。使用++,--等操作是通过函数调用 大家感兴趣可以先看看上面的,我们先用一个简述版的来带大家简要实现一下 template < class T> struct _list_iterator { typedef list_node<T> node; node* _pnode; //构造函数 _list_iterator(node* p) :_pnode(p) {} //接引用就是返回节点的值 T& operator*() { return _pnode->_data; } //++操作就是就将当前指向下一个节点 _list_iterator<T>& operator++() { _pnode = _pnode->_next; return *this; } //--操作就是将当前指向前一个节点 _list_iterator<T>& operator--() { _pnode = _pnode->_prev; return *this; } //不等于传参节点的指针不等于this节点的指针 bool operator!=(const _list_iterator<T>& it) { return _pnode != it._pnode; } }; #### 2.2迭代器的价值 #### 这里虽然我们使用vector和list的使用方法是基本类似的,但是我们发现他们的底层已经出现很大的差别。这里\*(接引用),在gcc下的vector中我们是直接对原生指针进行操作,但是在list下我们是通过函数调用来实现的。 最后关于迭代器需要强调一点,关于vector中的 iterator其实他可能也不是用原生指针,这个需要看代码的实现,因为我们在gcc和vs中我们发现迭代器失效,他们失效并不一样,意味着他们底层代码实现时不一样的,在gcc它可以是通过原生指针的方式实现,在vs也可以通过封装来实现。 ![20fed60b87ce4003928d361140b35a98.png][] ![989f4f889bf645fa853eb3bd22c8c354.png][] > **结论:** > > 1.封装底层实现,不暴露底层的实现细节 > > 2.提供统一访问方式,降低使用成本 物理层面比较 对于list类封装中的iteratior与vector中的iteratior的字节大小是一样的,他们都是4字节。 为什么list也是4字节,因为只看成员变量,不看函数。所以说指针在类中封装后并没有变大,在内存中还是实实在在的4byte。 他们不同的是list中存的时候节点位置的指针,而vector中的是数据位置的指针。 所以在物理层面上他们是没有区别的,他们字节的大小是一样的,但是他们的类型不一样,底层实现就是天差地别了--类型的力量。 #### 2.3list的接口 #### template < class T> class list { typedef list_node<T> node; public: typedef _list_iterator<T> iterator; iterator begin() { //使用了匿名对象--调用拷贝构造 return iterator(_head->_next); } iterator end() { return iterator(_head); } //当为null时,next与prev都指向head void empty_initalize() { _head = new node(T()); _head->_next = _head; _head->_prev = _head; } //为null调用empty_initalize list() { empty_initalize(); } //拷贝构造 list(const list<T> & lt) { empty_initalize(); //这里需要特别注意&(引用) //如果是内置类型就不影响,e接受数据后,push_back传入后销毁,下一个传又是从lt引用 //如果lt是其他类型,比如是vector类型或者是泛型,数据是一串, //当push_back完后,没有用引用那么push_back会销毁,传一个数据他销毁了再传一个数据它又没了 for (const auto &e : lt) { push_back(e);//this.push_back } return *this;//返回链接值 head->1->2->3 } //析构函数 ~list() { clear();//第一步清楚数据 //第二步将头结点置空 delete _head; _head = nullptr; } //将数据一一清理 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } list<T>& operator=(const list<T>& lt) { if (this != <)//判断链表数据不一样后进行操作 { clear();//先清空 for (const auto&e : lt)//传值 { push_back(e); } } } //头插 void push_front(const T& x) { insert(begin(), x);//调用insert } //头删 void pop_front() { erase(begin());//调用erase } //尾删 void pop_back() { erase(--end()); } //尾插 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; //insert(end(),x) } iterator insert(iterator pos, const T& x) { node* newnode = new node();//新建节点 node* cur = pos._pnode;//插入节点是在数据后插,保存改数据后的节点 node* prev = cur._prve;//保存数据前的节点 //4步链接头尾 prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode);//返回节点 } iterator erase(iterator pos) { assert(pos != end());//不能删除头节点 node* prev = pos._pnode->_prev;//保存pos前的节点 node* next = pos._pnode->_next;//保存pos后的节点 prev->_next = next;//将后节点链接前节点 next->_prev = prev;//将前节点链接后节点 delete pos._pnode;//删除pos节点--会失效 return iterator(next);//返回pos节点后的节点 } private: node* _head; }; list接口的模拟实现主要insert和erase有些难度,但是对于写过数据结构的代码,我相信大家稍花功夫就能够轻松解决。 insert图解如下 ![3256fe2ec3f249dca2abdca3af9b8470.png][] erase图解如下![0cc7b76f3b1344d596d07524d0a7c117.png][] ### 三、list的模拟实现--const ### 下面内容主要是迭代器被const修饰,普通人的写法和大佬的写法,他们尽显锋芒。 -------------------- #### 3.1理解const修饰iterator #### 错误写法 void list_test(const list<int>& lt) { const list<int>::iterator lt1 = lt.begin(); } 首先需要理解const T\* p1与T\* const p2,**const迭代器类似p1的行为**,保护指向对象不被修改,但是迭代器本身是可以被修改的。 这里的const是修饰的lt1,不符合const迭代器的行为,因为他保护迭代器本身不能修改,那么我们也就不能++迭代器。 因为iterator是被封装使用的,我们发现在struct \_list\_iterator中,我们改变其返回值用const修饰,那么我们还是可以对迭代器进行++,--等操作,只是返回值不能被改变。 T& operator*() { return _pnode->_data; } 既然是需要const修饰返回值,那么我们能不能直接通过函数重载来支持呢? T& operator*() { return _pnode->_data; } const T& operator*() const { return _pnode->_data; } 答案是不能的。如果clt(被const修饰的参数)++,就调用operator++(),返回值是不被修改,这里的this也被const修改,那么this指向的节点都被修改,该节点就不能实现++操作,这样实现的话只能接引用,但不能++。 const T& operator*() const { return _pnode->_data; } _list_iterator<T>& operator++() { _pnode = _pnode->_next; return *this; } 如果我们是实现 > const \_list\_iterator<T>& operator++() const 答案也是不行的,因为这个过程就是对this值进行操作,这里其实就this已经都被const修饰了。**有点绕但是我们主要需要知道整个this值,不然很容易就昏了。** #### 3.2实现const修饰iterator #### 既然上述解释了在一个类中通过函数重载,const修饰的this会影响,因为我们需要函数重载的话,const不仅仅需要修返回值,也要修改this,上面写法就是错误的 > const T& operator\*() const 那么我们重新建立类,其他不变,只将返回参数改成被const修饰即可。 > const T& operator\*() template<class T> struct _list_const_iterator { typedef list_node<T> node; node* _pnode; _list_const_iterator(node* p) :_pnode(p) {} const T& operator*() { return _pnode->_data; } _list_const_iterator<T>& operator++() { _pnode = _pnode->_next; return *this; } _list_const_iterator<T>& operator--() { _pnode = _pnode->_prev; return *this; } bool operator!=(const _list_const_iterator<T>& it) { return _pnode != it._pnode; } }; 我们建立了两个类,所以我们在list直接进行用就可以了。添加上begin+end被const修饰的接口就可以了。 template <class T> class list { typedef list_node<T> node; public: typedef _list_iterator<T> iterator; typedef _list_const_iterator<T> const_iterator; const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } } ### 四、list的模拟实现--大佬的iterator ### 上面写的iterator,我们发现大多数代码都是一样的,仅仅是返回值不一样,就建立了两个类,这样的话代码就比较冗余。那么大佬是不可能写出这样的代码,大佬就通过增加模板参数就很好的解决这一问题了。 -------------------- #### 4.1第三个参数 #### 原来模板参数只有一个类型,现在将模板参数增加为两个,以前我们是通过自己构建两个类,来实现他们不同功能,但是我们直接在模板里多增加一个类型,编译器就默认实例化两个类型。 > template<class T, class Ref> 同一个类模板实例化出的2个类型 > typedef \_\_list\_iterator<T, T&,> iterator; > typedef \_\_list\_iterator<T, const T&, const T\*> const\_iterator; 这里T就是普通参数,Ref就是被const修饰的参数。那么在看源码的时候有三个参数,这里就不得不提到返回数据的指针了。 struct pos { int _row; int _col; pos(int row=0, int col=0) :_row(row) , _col(col) { } }; int main() { list<pos> lt; pos p1(1,1); lt.push_back(p1); lt.push_back(p1); lt.push_back(p1); lt.push_back(pos(2,2)); lt.push_back(pos(3,3)); list<pos>::iterator it = lt.begin(); while (it != lt.end()) { cout << (*it)._row << ":" << (*it)._col << endl; ++it; } return 0; } 我们在结构体中,是通过接引用(迭代器的位置)的值,该值再通过**.**去访问结构体中的行的值。这样用起来是非常别扭,以前访问结构体就是直接地址->指向实参,it->\_row。 回忆C语言中->的用法 struct Data { int a, b, c; }; int main() { struct Data * p; struct Data A = { 1, 2, 3 }; int x; p = &A; x = p->a; cout << x << endl; return 0; } 这里it是迭代器,所以我们需要封装->,然后在进行应用。 > Ptr operator->() > \{ > return &\_pnode->\_data; > \} Ptr返回的是节点数据的地址,拥有->后,我们再看看使用。 > while (it != lt.end()) > \{ > cout << it->\_row << ":" << it->\_col << endl; > \++it; > > \} it->\_row是什么意思?it->是调用it.operator->(),返回节点数据的地址,紧接着是返回节点数据的地址->\_row,正确的写法应该是it->->\_row。但是这是既不好看又不好用,编译器为了可读性,省略了一个->。 > while (it != lt.end()) > \{ > cout << it.operator->()->\_row << ":" << it->\_col << endl; > \++it; > > \} 当然这样用也是不错的。 综上所述知道我们所添加的第三个参数就是T\*,用于接受返回的地址。 > template<class T, class Ref, class Ptr> > > typedef \_\_list\_iterator<T, T&, T\*> iterator; #### 4.2大佬的iterator #### #pragma once #include<assert.h> namespace qhx { template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _data; list_node(const T& x) :_next(nullptr) , _prev(nullptr) , _data(x) {} }; // 同一个类模板实例化出的2个类型 // typedef __list_iterator<T, T&, T*> iterator; // typedef __list_iterator<T, const T&, const T*> const_iterator; template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref, Ptr> Self; node* _pnode; __list_iterator(node* p) :_pnode(p) {} //因为很多时候我们需要返回到数据的指针 //返回数据的指针 Ptr operator->() { return &_pnode->_data; } Ref operator*() { return _pnode->_data; } Self& operator++() { _pnode = _pnode->_next; return *this; } // it++ Self operator++(int) { Self tmp(*this); _pnode = _pnode->_next; return tmp; } Self& operator--() { _pnode = _pnode->_prev; return *this; } Self operator--(int) { Self tmp(*this); _pnode = _pnode->_prev; return tmp; } bool operator!=(const Self& it) const { return _pnode != it._pnode; } bool operator==(const Self& it) const { return _pnode == it._pnode; } }; //vector<int> //vector<string> //vector<vector<int>> // 类名 类型 // 普通类 类名 等价于 类型 // 类模板 类名 不等价于 类型 // 如:list模板 类名list 类型list<T> // 类模板里面可以用类名代表类型,但是建议不要那么用 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; 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() { //iterator it(_head); //return it; return iterator(_head); } void empty_initialize() { _head = new node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_initialize(); } //迭代器区间构造 template <class InputIterator> list(InputIterator first, InputIterator last) { empty_initialize(); while (first != last) { push_back(*first); ++first; } } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } // 现代写法--复用 // lt2(lt1) list(const list<T>& lt)//在类内部:类名 等等价于 类型 //list(const list& lt) // 这里list<T>&与list&是一样的,但是不建议用 { empty_initialize(); list<T> tmp(lt.begin(), lt.end());//复用迭代器区间构造 swap(tmp);//交换head和size } // lt3 = lt1 list<T>& operator=(list<T> lt)//不能加&,因为就是需要交换的是lt的拷贝 //list& operator=(list lt) // 不建议 { swap(lt); return *this; } size_t size() const { return _size; } bool empty() const { return _size == 0; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } void pop_back() { erase(--end()); } iterator insert(iterator pos, const T& x) { node* newnode = new node(x); node* cur = pos._pnode; node* prev = cur->_prev; // prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return iterator(newnode); } iterator erase(iterator pos) { assert(pos != end()); node* prev = pos._pnode->_prev; node* next = pos._pnode->_next; prev->_next = next; next->_prev = prev; delete pos._pnode; --_size; return iterator(next); } private: void CreateHead() { _head = new Node; _head->_prev = _head; _head->_next = _head; } private: node* _head; size_t _size;//为了减少后续频繁调用循环查找size }; } ### **五、反向迭代器** ### 在stl源码中,他是通过适配器得到将正向迭代器的接口传过来,然后直接在正向迭起的基础上进行改进。 ![637318ce654a4dd7a03026af7be43579.png][] ![737f98688a98455fba1841e5b0162388.png][] self& operator++() { --current; return *this; } self operator++(int) { self tmp = *this; --current; return tmp; } self& operator--() { ++current; return *this; } self operator--(int) { self tmp = *this; ++current; return tmp; } -------------------- **完结!** ![9097293c451e459db439a56227a95d08.gif][] [dc391b9d63674bf98fb421a61ae5c8a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f8e73828dc58491496ec8c4ccd692c92.png [e914fdd03aea46b98f8a6d2956a704b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6998b8de355841908e5750712ca4d5bf.png [7c245ac87f2846db84e6e3ab09fda81c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dd504f83e00040499aef18e7ddb67430.png [1c7e3a0d61fd481f991497ff4bce0b5e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/afb637a96d764c2c92272e37865ecda3.png [20fed60b87ce4003928d361140b35a98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3ef4676ecb16479abf9042eb25be9f73.png [989f4f889bf645fa853eb3bd22c8c354.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/004e6a882f974370bf6c03dc44da3fc3.png [3256fe2ec3f249dca2abdca3af9b8470.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fcaa507716ad4a4c892bb1d6afc8c691.png [0cc7b76f3b1344d596d07524d0a7c117.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e4570d57a885484b84370f85e1ae5e60.png [637318ce654a4dd7a03026af7be43579.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dd6b16089ee34554afca3ceb1a603adc.png [737f98688a98455fba1841e5b0162388.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bb6079492ee6490998c3e3377f15b695.png [9097293c451e459db439a56227a95d08.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e0a1c40976ee479ea30dc8cfc991f495.gif
相关 CList的使用 1. CListCtrl 风格 LVS_ICON: 为每个item显示大图标 LVS_SMALLICON: 为每个item显示小图标 Bertha 。/ 2022年10月25日 11:28/ 0 赞/ 108 阅读
相关 C#自定义双向链表,功能类似C++中的CList 参照博客: [http://www.cnblogs.com/linzheng/news/2011/07/14/2106530.html][http_www.cnblogs.c 太过爱你忘了你带给我的痛/ 2022年08月11日 06:58/ 0 赞/ 128 阅读
相关 CList类(双向链表)介绍及使用 参照博客: [http://blog.163.com/bluesky\_hebo/blog/static/8136530201021232119907/][http_blog 我不是女神ヾ/ 2022年08月11日 06:58/ 0 赞/ 111 阅读
还没有评论,来说两句吧...