C++容器——list的模拟实现

目录

一.list的基本结构

二. 接下来就是对list类构造函数的设计了：

三.链表数据的增加：

四.接下来就是迭代器的创建了：

四.简单函数的实现：

五.构造与析构 

六.拷贝构造和赋值重载

传统写法:

现代写法：

七.迭代器模板类型

---

     一.list的基本结构

         想要模拟实现list类，就需要先了解它的底层架构，上篇博客讲到：list容器的底层是双向链表，那么就需要自定义一个节点类，通过节点类可以创建节点，设置节点的前后指针和数据值。之后便可以通过该类类型创建list类的成员变量。

template<class T>
struct list_node {	//该类为内部类，是list的内部类list_node(const T& val):_next(nullptr), _prev(nullptr), _data(val) {}//成员变量list_node* _next;    //后指针list_node* _prev;    //前指针T _data;            //值
};template<class T>
class list {public:typedef list_node<T>  node;    //将节点类作为类类型private:node* _head;	//指向堆区空间链表的指针size_t _size;    //计数
};

node* 类型就好比是对节点类的封装。 

二. 接下来就是对list类构造函数的设计了：

template<class T>
class list {public:typedef list_node<T>  node;    //将节点类作为类类型//初始化操作void empty_Init() {_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list()    //构造函数:_head(nullptr),_size(0){empty_Init();}private:node* _head;	//指向堆区空间链表的指针size_t _size;    //计数
};

        对构造函数的初始化设计就是：创建哨兵位头结点，让链表指针指向哨兵位头结点，由哨兵头节点去控制节点的增删查改，避免了由链表指针去控制，操作和形式上都方便了很多。

         注：哨兵位头结点的创建是在empty_Init()函数中进行的！

三.链表数据的增加：

template<class T>
class list{public:typedef Node<T> node;//尾插  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;++_size;}//尾删void pop_back() {assert(!empty());node* tail = _head->_prev;node* last = tail->_prev;last->_next = _head;_head->_prev = last;delete tail;--_size;}//头插void push_front(const T& val) {node* newnode = new node(val);node* first = _head->_next;_head->_next = newnode;newnode->_prev = _head->_next;newnode->_next = first;first->_prev = newnode;++_size;}//头删void pop_front() {assert(!empty());node* first = _head->_next;node* second = first->_next;_head->_next = second;second->_prev = _head->_next;delete first;--_size;}//任意位置的插入iterator insert(iterator pos, const T& val=T()) {if (pos == this->begin()) {push_front(val);    //复用代码}else if (pos == this->end()) {push_back(val);    //复用代码}else {node* newnode = new node(val);node* cur = pos.phead;node* last = cur->_prev;last->_next = newnode;newnode->_prev = last;newnode->_next = cur;cur->_prev = newnode;++_size;}return pos;}//任意位置的删除iterator erase(iterator pos) {assert(!empty());if (pos == this->begin()) {pop_front();}else if (pos == this->end()) {pop_back();}else {node* cur = pos.phead;node* tail = cur->_next;node* last = cur->_prev;last->_next = tail;tail->_prev = last;delete cur;--_size;}return pos;}private:node* _head;	//指向堆区空间链表的指针size_t _size;    //计数};

        对于数据的增加和删除，头插头删、尾插尾删简单就不说了，重点是insert和erase函数的实现，如上代码，在insert和erase中，各有三种情况，其中头尾的操作直接复用函数即可，对于中间位置的插入删除情况，我想说的是，指定的pos参数是iterator类型——自定义迭代器类，它是指针！！！ 它只是指向该节点元素的位置，所以想要获取该位置的节点，就需要pos.phead才能获取到该节点，只有获取到该节点，才能使用该节点附近的前后指针！ 

 

四.接下来就是迭代器的创建了：

        在对vector、String容器的模拟实现中，我并没有单独创建迭代器，这是因为这两个容器的底层都是数组，是一段连续的地址空间，对于迭代器中的成员begin、end都是可以直接让指针进行类型的字节++/--进行的，很方便的，是使用原生指针来确定位置

        而对于list容器来说，它的底层是链表，各个节点的位置是不连续的，随机的。使用原生指针并不能遍历到每一个对象的元素！所以针对list容器，需要创建一个自定义类型的迭代器进行链表的遍历。 

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;}bool operator!=(const list_iterator<T>& it){   //!=运算符重载return _pnode != it._pnode;}};template<class T>class list{public:typedef list_node<T> node;typedef list_iterator<T> iterator;iterator begin(){return iterator(_head->_next);}iterator end(){//iterator it(_head);//return it;return iterator(_head);}};

        在自定义的迭代器类中，我根据平常练习vector、String的迭代器代码中，写了几个一定会用到的运算符重载函数：解引用、指针++，遍历所用到的!=等函数。

        写好自定义迭代器类后，需要在list类中重命名该类。

        写好迭代器后，我们就可以试验一下了：

 

 

 注：上面的迭代器只是普通迭代器的实现，还会有const迭代器、反向迭代器需要实现，意味着还得再写两个迭代器类。

四.简单函数的实现：

template<class T>
class list{public:size_t size()const {return _size;//方法2：利用指针遍历，每遍历一次记一次数}bool empty() const {//方法1：return _size == 0;//方法2：return _head->next==_head;}void clear() {node* cur = _head->_next;while (cur != _head) {node* del = cur;cur = cur->_next;delete del;}cur->_next = _head;cur->_prev = _head;_size = 0;}T& front() {return  this->begin().phead->_data;}T& back() {return  this->end().phead->_prev->_data;}private:node* _head;size_t _size;};

五.构造与析构 

        有了迭代器，我们就可以对list构造函数进行迭代器区间构造实现了：

template<class T>
class list{
public://迭代器区间构造函数template<class Inputiterator>list(Inputiterator first, Inputiterator last) {		empty_Init();while (first != last) {push_back(*first);++first;}}void empty_Init() {_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list()    //无参构造{empty_Init();}//析构函数~list() {this->clear();delete _head;_head = nullptr;_size = 0;}
private:node* _head;size_t _size;
};

析构函数就是遍历链表中每个节点都进行遍历释放，置空指针，置零变量。

六.拷贝构造和赋值重载

 

传统写法:

//拷贝构造——传统写法list(const list<T>& lt) {empty_Init();for (auto& e : lt) {this->push_back(e);}}//赋值重载函数——传统写法list<T>& operator=(const list<T>& lt) {if (this != &lt) {this->clear();}for (const auto& e : lt) {this->push_back(e);}return *this;}

        拷贝构造和赋值重载本质上都相同，都是复制已有的list对象，然后深拷贝数据给自己。深拷贝就是创建一个属于自己的头结点，剩下的数据就是浅拷贝(无脑将数据以遍历的方式让自己的头指针进行指针链接)。 

现代写法：

    //调用std库中swap函数进行成员交换void Swap(list<T>& lt) {std::swap(this->_head, lt._head);std::swap(this->_size, lt._size);}	//拷贝构造——现代写法list(const list<T>& lt) {empty_Init();list<T> tmp(lt.begin(), lt.end());		//调用迭代器区间构造函数this->Swap(tmp);}//赋值重载——现代写法list<T>& operator=(list<T> lt) {this->Swap(lt);    //值传递，形参的改变不影响实参return *this;}

 

七.迭代器模板类型

        上面讲迭代器的最后说了，迭代器有普通版、const版、反向版、反向const版，意味着我们需要创建四个迭代器类型，但迭代器能用到的运算符重载函数都一样，都是解引用、指针++、!=运算符。

//自定义普通迭代器类
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;}bool operator!=(const list_iterator<T>& it){return _pnode != it._pnode;}};//const迭代器类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;}};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);}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}

        如上，普通迭代器类和const迭代器类唯一的区别：是在遍历上，const迭代器类的解引用运算符重载函数中不能用*it修改数据，那么这俩迭代器类中其他函数的实现完全一样，这极大的造成了代码的冗余，降低了可读性！！！

        于是为了在一种迭代器类中体现不同类型的迭代器，可以这样做:

template<class T, class Ref, class Ptr>	
struct _list_iterator {typedef list_node<T> node;typedef _list_iterator<T, Ref,Ptr> Self;	//Self是T与ref,ptr 模板类型的另一种别称//迭代器构造函数_list_iterator(node* p):_pnode(p) {}//解引用Ref operator*() {return _pnode->_data;}//箭头只有是结构体才可以用Ptr operator->() {return &_pnode->_data;		//返回的是该结点的地址}Self& operator++() {_pnode = _pnode->_next;return *this;}//后置++，使用占位符int，与前置++以示区分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& lt) const {return _pnode != lt._pnode;}bool operator==(const Self& lt)  const{return _pnode == lt._pnode;}node* _pnode;
};

        在迭代器类中，采用了三个模板参数。这三个模板参数：T代表泛型值，Ref代表泛型引用，Ptr代表泛型指针，这三种参数主要应用于运算符重载函数的函数返回值，函数形参，相当方便，一举多得，通过不同实参的传递就可以调用不同类型的函数。

 

template<class T>
class list {
public:typedef list_node<T>  node;typedef _list_iterator<T, T&, T*> iterator;//typedef list_const_iterator<T> const_iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;

完整模拟实现代码 .h文件：

#include<iostream>
#include<assert.h>using std::cout;
using std::endl;template<class T>
struct list_node {	//该类为内部类，是list的内部类list_node(const T& val):_next(nullptr), _prev(nullptr), _data(val) {}//成员变量list_node* _next;list_node* _prev;T _data;
};//typedef list_iterator<T, T&> iterator;
//typedef list_iterator<T, const T&> const_iterator;//这种写法来源：vector<int>,vector<string>,vector<vector<int>> 
template<class T, class Ref, class Ptr>	//新增一个模板参数	，T是一种类型，ref是一种类型
struct list_iterator {typedef list_node<T> node;typedef list_iterator<T, Ref, Ptr> Self;	//Self是T与ref,ptr 模板类型的另一种别称//迭代器构造函数list_iterator(node* p):_pnode(p) {}//在下面的运算符重载中，const版与非const版只有解引用运算符重载函数的类型不同，其他运算符重载都一样//所以operator* 的类型需要使用ref,ref可以理解为constT&, 而非const对象也可以调用const函数，权限够//const对象不可调用非const函数，权限不够，所以使用ref//解引用Ref operator*() {return _pnode->_data;}//箭头只有是结构体才可以用Ptr operator->() {return &_pnode->_data;		//返回的是该结点的地址}//前置++，//为啥要用引用？ 原因：return *this ,this（迭代器对象）出了该函数体，还存在（this的生命周期在该类中是全局的）Self& operator++() {_pnode = _pnode->_next;return *this;//既然this还在，那么直接用引用返回，栈帧中不开临时空间，减少拷贝次数，提高效率//记住：使用引用返回的前提是，要返回的值出了函数体仍在才可以使用，否则会报错}//后置++，使用占位符int，与前置++以示区分Self operator++(int) {Self tmp(*this);_pnode = _pnode->_next;return tmp;//返回tmp后，tmp为临时对象，出了函数就消失了，tmp对象不在，需要拷贝，那就得用传值返回，在栈帧中//创建一个临时空间去接收返回的tmp对象数据。设置一个默认参数和前置++做区分，构成函数重载。//若使用引用返回，那么该函数结束后，返回的tmp已经不存在了，引用返回返回野指针（随机值）就会报错！！！}Self& operator--() {_pnode = _pnode->_prev;return *this;}//后置--Self operator--(int) {Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& lt) const {return _pnode != lt._pnode;}bool operator==(const Self& lt)  const{return _pnode == lt._pnode;}node* _pnode;
};//--------------------------------------------------------------------------------template<class T>
class list {
public:typedef list_node<T>  node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;void empty_Init() {_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_Init();}//析构~list() {this->clear();delete _head;_head = nullptr;_size = 0;}template<class Inputiterator>list(Inputiterator first, Inputiterator last) {		//拷贝构造的天选打工人//先初始化，给头节点，否则没法继续empty_Init();while (first != last) {push_back(*first);++first;}}void swap(list<T>& lt) {std::swap(this->_head, lt._head);std::swap(this->_size, lt._size);}void clear() {iterator it = this->begin();while (it != this->end()) {it = this->erase(it);}}//拷贝构造——传统写法/*list(const list<T>& lt) {empty_Init();for (auto& e : lt) {this->push_back(e);}}*///拷贝构造——现代写法list(const list<T>& lt) {empty_Init();list<T> tmp(lt.begin(), lt.end());		//调用迭代器区间构造函数this->swap(tmp);}//赋值重载——传统写法/*list<T>& operator=(const list<T>& lt) {if (this != &lt) {this->clear();}for (const auto& e : lt) {this->push_back(e);}return *this;}*///赋值重载——现代写法list<T>& operator=(list<T> lt) {this->swap(lt);return *this;}//迭代器iterator begin() {return iterator(_head->_next);}iterator end() {return iterator(_head);}//const迭代器const_iterator begin() const {return const_iterator(_head->_next);}const_iterator end() const {return const_iterator(_head);}//尾插void push_back(const T& val) {node* newnode = new node(T(val));node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}//insertiterator insert(iterator pos, const T& val) {node* newnode = new node(T(val));node* cur = pos._pnode;node* first = cur->_prev;first->_next = newnode;newnode->_prev = first;newnode->_next = cur;cur->_prev = newnode;_size++;//insert后返回新节点的位置，那么下一次pos就会指向最近一次创建新节点的位置了return iterator(newnode);}iterator erase(iterator pos) {//pos不能指向哨兵位头节点，因为pos一旦指向哨兵位头，那么该链表一定为空，空链表是不能再删数据的assert(pos != end());node* first = pos._pnode->_prev;node* last = pos._pnode->_next;first->_next = last;last->_prev = first;delete pos._pnode;pos._pnode = nullptr;--_size;return iterator(last);}void push_front(const T& val) {insert(begin(), val);}void pop_back() {erase(--end());}void pop_front() {erase(begin());}size_t size() const{/*size_t s = 0;iterator it = this->begin();while (it != this->end()) {++it;++s;}return s;*///复用insert和erase//因为在链表中，一切的新增和减少都是复用的insert和erase,所以在insert和erase中size++,size--即可return _size;}bool empty() const {//return _head->_next == _head;//也可以复用size()return _size == 0;}private:node* _head;	//头节点size_t _size;
};