C++初阶之list的模拟实现过程详解 C++初阶之list的模拟实现过程详

list的介绍

list的优点：

list头部、中间插入不再需要挪动数据，O(1)效率高
list插入数据是新增节点，不需要增容

【C++初阶之list的模拟实现过程详解】list的缺点：

不支持随机访问,访问某个元素效率O(N)
底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低。

今天来模拟实现list
我们先来看看官方文档中对于list的描述

文章图片

我们先大致了解一下list的遍历
迭代器

对于迭代器我们可以用while循环+begin（）end（）。同时还可以用迭代器区间。
当然迭代器区间的方式只适用于内存连续的结构比如数组stringvector等
它们的原生指针就可以当作迭代器来用。

文章图片

范围for

其实范围for和迭代器的底层是完全一样的，我们只有写好迭代器，才能用范围for，而且这里的迭代器必须和库里的命名一样才可以用范围for
我们再来了解一下有关算法函数中，我们最常用的函数

swap
find
sort

我们主要看看sort函数
sort函数在官方库中是用快排写的，其中快排的精髓就是三数取中的优化操作。
sort默认是排升序如果想排降序需要使用functional文件中的greater()这个模板函数，我们以vector来举例。

文章图片

对于list，我们极度不推荐使用algorithm文件中的sort函数，上文提到了sort函数是使用的快速排序的手段进行排序的，而其关键在于三数取中这样的操作，那么三数取中这样的操作只有在内存连续的数据结构中才能操作，如果给你一个head，给你一个tail，你如果能找到中间的结点？很明显是很复杂的。
我们这里list迭代器是不支持随机访问，他不是随即迭代器。
而vector string这样的迭代器是支持随机访问的，所以他们用快排很有优势。

文章图片

我们可以看到这三个函数的迭代器是不同的，它们是继承关系，随机的支持双向，双向支持单向，反过来就不行。
当然除了这几种迭代器，还有输入输出迭代器，也叫可读可写迭代器，他们是最弱的迭代器，一个单向迭代器都可以支持可读可写的功能。也就是说，可读可写迭代器在继承的最上端。所有人都包含了他俩。
但是虽然他们功能很弱，但他们在一些重要的特性上有至关重要的作用，那就是迭代器的萃取。这个和复杂，暂时不去管它们。
总结上面两段话：

文章图片

当我们使用迭代器遍历的时候，我们需要知道的是，begin（）代表了第一个结点，end（）代表了头结点。

这里再穿插一个小知识，我们再官方文档中总能看到max_size这样的变量，
它的意义是整形的最大值除以一个节点的大小，也就是得出的节点个数
无符号整形最大是2^32-1，也就是42亿多，对于int类型的vector，就是42亿除以4得到的值，对于list，就是42亿除以三个指针的大小得到的值。

我们还知道再vector中，我们在insert的扩容插入，还有erase的删除时，会导致迭代器失效的问题。那么对于list我们还要去关注迭代器失效的问题吗？
我们再insert的时候，插入数据并不会影响到其他的数据的地址，只是影响链接的关系，所以不会引起迭代器失效
但是对于erase，当我们删除对应的结点之后，他会变成野指针。所以我们erase的时候通常去接收它的返回值，也就是下一个结点的迭代器。
当然库中还有一些我们不常用的函数
splice 接合函数，把一个list的数据转移到另一个list

文章图片

这里不是拷贝，是转移。
还有remove，找到就删，没找到就没什么反应。
unique 去重，这里又一个小小的bug，只有连续的重复数据才会删除。

文章图片

聪明的同学会反应过来，这里sort+unique可以解决这样的问题。当然没反应过来的同学也很聪明。
这里显然还是那个问题，我们不建议堆链表进行排序，效率是很低的。
list的成员函数是用的归并排序。为什么不用algorithm中的sort快排呢？原因我们上文已经解释过了。
说了这么多，来看看代码吧。
先来看看头文件吧！

#pragma once#include #include #include using namespace std; namespace LL{ 我们先写结点类，这里用类模板，并且是用struct实现，默认内容是公开的,其他的类都可以调用 template 其中结点类中要有三个变量，一个存值，两个指针 struct _list_node {T _val; _list_node*_next; _list_node*_prev; 结点类中除了要有三个变量，还需要有一个构造函数。当我们定义一个新结点的时候，进行构造函数初始化我们这里的参数是一个缺省的val值，其中缺省参数给的是匿名构造函数。最好以const接收。_list_node(const T& val = T()):_val(val), _next(nullptr), _prev(nullptr){} }; 这里实现迭代器类。首先我们依旧是使用类模板，我们这里给三个模板参数，同时类还是用struct来实现在迭代器类中，我们主要实现 1、构造 2、解引用操作3、！= 和== 操作3、前置++后置++ --操作 template 这里三个模板参数是什么意思呢?当我们需要const迭代器和非const迭代器的时候我们可以根据第二个参数的不同来实例化出不同的迭代器，就不需要写两个迭代器了 typedef _list_iterator iterator; typedef _list_iterator const_iterator; 我们可以根据模板参数实例化出不同的迭代器。 struct _list_iterator {typedef _list_nodenode; typedef _list_iteratorself; node* _pnode; 构造函数，把node传进来，然后把值赋给我们内部创建的_pnode,总不能乱修改外部指针吧。_list_iterator(node * node):_pnode(node){}这里我们不需要实现拷贝构造、operator=、析构，直接用编译器生成的，对于内置类型直接进行浅拷贝我们发现浅拷贝指针对于list来说完全没问题。解引用，解引用我们返回值写为Ref ，这样可以根据const和非const，并且就是引用返回可读可修改，如果ref为const，那就不可修改只可读。这里不需要传入参数，我们直接进行调用，返回值当然为对应的val引用.Ref operator * (){return _pnode->_val; }同理的我们写一下这个指针解引用，这里返回值依旧用模板参数，很方便啊。我们应该返回一个地址。Ptr operator ->(){return &(_pnode->_val); }！= 和 == ，当我们使用迭代器的时候，需要比较两个迭代器是否相等来进行循环条件判定，所以这是必要的。我们这里返回值当然是bool，参数传入我们的迭代器，比较迭代器内的节点是否相等。再加上const最好。bool operator != (const self& s) const{return _pnode != s._pnode; }bool operator == (const self& s) const{return _pnode == s._pnode; }接着我们实现前置后置++--前置 ++ it我们返回值是原迭代器self& operator++(){_pnode = _pnode->_next; return *this; }后置 ++ it ，我们需要进行传参，第一个参数就是默认的this，第二个参数为0it ++ --> it.operator ++(&it,0); 我们可以缺省掉第二个参数，因为默认是从参数列表末尾开始匹配的。当然返回值就不能返回引用了，因为这里我们要用临时变量进行返回,我们先用传入的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; } }; 接下来我们开始写list类,当然也要用类模板来写，里面要实现1、迭代器 2、构造 3、push_back 。我们这里的list是带头双向循环列表 template class list {我们先来实现一下迭代器,我们首先需要typedef 我们的迭代器，所以先实现迭代器。然后需要定义const和非const的beginend ,这里需要记住end和begin要有非const和cosnt，因为无法同时满足可修改和可读。比如const迭代器调用只能掉const的end，非const的迭代器虽然可以调用const的end，但是导致权限缩小，无法修改内容。typedef _list_node node; public:typedef _list_iterator iterator; typedef _list_iterator const_iterator; iterator begin()//begin指头结点后第一个结点，end指头结点。{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); }构造函数，这里直接进行头结点的创建（自己链自己）list(){_head = new node(T()); 当然可以有这种写法，我们用匿名构造一个头结点，可以是各种类型。这里和上文中，结点的构造函数是一样的，我们写一个就好了。_head = new node; _head->_next = _head; _head->_prev = _head; }push_back 我们传入一个要插入的值，创建新节点进行链接的更新。void push_back(const T& val){node* newnode = new node(val); //这里因为我们在结点的构造函数中写了模板参数类型匿名构造，可以传任意类型。node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; }拷贝构造1、创造新的头结点，把传入的list循环赋值给新的头结点。list(const list& l){_head = new node; _head->_next = _head; _head->_prev = _head; const_iterator it = l.begin(); while (it != l.end()){push_back(*it); ++it; }}insert，在指定位置插入元素，我们不用返回值，参数是pos迭代器和val先给一个cur 存pos位置的结点，然后定义一个我们的prev，为了之后和新节点链接。2、创建新节点，更新链接就好了。void insert(iterator pos, const T& val)//这里不需要用const 因为，const迭代器对应了constlist ，const list怎么会来插入数据呢？{node* cur = pos._pnode; node* prev = cur->_prev; node* newnode = new node(val); newnode->_next = cur; newnode->_prev = prev; prev->_next = newnode; cur->_prev = newnode; }erase ,返回下一个位置的迭代器，传入一个pos1、保存指向结点，并找到前后的两节点 2、更新链接删除掉当前节点。3、返回迭代器。这里需要强转，从指针转成迭代器类型。iterator erase(iterator pos){node* cur = pos._pnode; node* prev = cur->_prev; node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return (iterator)next; }那我们在赋值运算符重载的时候需要先清理掉自身的结点，所以我们实现一下clearclear 清空list中除了头结点以外的所有结点。很好实现，我们循环erase就好了，erase返回下一个的迭代器，所以接收其返回值就好了。void clear(){iterator it = begin(); while (it != end()){it = erase(it); }}赋值运算符重载，返回值是类型的引用，参数传入list1、首先判断是否给自己赋值，否则我们删除后会发生野指针的问题 2、条件成立我们先清除现在的一切，然后循环赋值。最后返回*this；list& operator = (list& l){if (this != &l){clear (); iterator it = l.begin(); while (it != l.end()){push_back(*it); it++; }}return *this; }析构：析构要做的就是析构一切，先clear，在delete 头，并给头赋空~list(){clear(); delete _head; _head = nullptr; cout << "析构执行成功" << endl; }获得第一个元素，返回一定是类型的引用,这里应该有两个版本，否则当const对象调用的时候，会无法调用。这里返回也要返回const，否则你给人家偷偷扩大了权限。T& front(){return _head->_next->_val; }const T& front() const{return _head->_next->_val; }获得最后一个元素T& back(){return _head->_prev->_val; }const T& back() const{return _head->_prev->_val; }交换两个list,传入list。我们只需要交换一下头结点就可以了void swap(list& l){::swap(_head, l._head); }void push_back_insert(const T& val){insert(end(), val); }void push_front_insert(const T& val){insert(begin(), val); }void pop_front_erase(){erase(begin()); }void pop_back_erase(){erase(--end()); }求结点个数循环计数size_t size(){size_t count = 0; auto it = begin(); while (it != end()){++it; ++count; }return count; }bool empty(){return begin() == end(); }resize ,开辟n个空间并赋初始值，用匿名构造赋值。1、计算旧结点个数，如果就空间比新的空间大，我们就删除多余的空间2、否则就从新空间开始给其赋初值。void resize(size_t newsize, T& val = T()){size_t oldsize = size(); if (oldsize > newsize){for (int i = newsize; i < oldsize; i++){pop_back_erase(); }}else{for (int i = oldsize; i < newsize; i++){push_back_insert(val); }}} private:node* _head; }; }

我们来测试一下我们的函数

#include "List.h"//printlist 打印不需要返回什么，参数是一个模板参数类型的列表templatevoid PrintContainer(const Con& c){ Con::const_iterator it = c.begin(); while (it != c.end()) {cout << *it << " "; ++it; } cout << endl; }void test_list1(){ cout << "list1使用pushback插入数据的打印" << endl; LL::list lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(5); lt1.push_back(6); PrintContainer(lt1); //for (auto e : lt) //{ // cout << e << " "; //} //cout << endl; //LL::list::iterator it = lt.begin(); //while (it != lt.end()) //{ // (*it)++; // cout << *it << " "; // ++it; //} //cout << endl; cout << "拷贝构造list2的打印" << endl; LL::list lt2(lt1); PrintContainer(lt2); //cout << "在list2的2位置前insert一个0并打印" << endl; //LL::list::iterator pos = find(lt2.begin(), lt2.end(),2); //lt2.insert(pos,0); //PrintContainer(lt2); //cout << "在list2的2位置前insert一个0并打印" << endl; //lt2.erase(pos); //PrintContainer(lt2); cout << "用list2给list3赋值,并打印" << endl; LL::list lt3; lt3 = lt2; PrintContainer(lt3); cout << "获得list3的第一个元素和最后一个元素" << endl; cout << lt3.front() <<""; cout << lt3.back() << endl; cout << "整一个全是0的list4，并打印" << endl; LL::list lt4; lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); PrintContainer(lt4); cout << "交换链表list1和list4、并打印" << endl; lt1.swap(lt4); PrintContainer(lt4); cout << "头删list4" << endl; lt4.pop_front_erase(); PrintContainer(lt4); cout << "头插list4" << endl; lt4.push_front_insert(0); PrintContainer(lt4); cout << "尾删list4" << endl; lt4.pop_back_erase(); PrintContainer(lt4); cout << "尾插list4" << endl; lt4.push_back_insert(0); PrintContainer(lt4); cout << "list4的节点个数" << endl; cout << lt4.size() << endl; cout << "判断是list1是否为空链表" << endl; cout << lt1.empty() << endl; cout << "" << endl; cout << "" << endl; cout << "" << endl; cout << "" << endl; cout << "" << endl; cout << "" << endl; }int main(){ test_list1(); return 0; }