C++——list模拟实现

目录

前言

一、list的结构

二、默认成员函数

构造函数

析构函数

clear

拷贝构造

赋值重载

swap

三、容量相关

empty

size

四、数据访问

front/back

五、普通迭代器

begin/end

六、const迭代器

begin/end

七、插入数据

insert

push_back

push_front

八、删除数据

erase

pop_back

pop_front

九、代码

总结

---

前言

我们之前讲解了string和vector的模拟实现，它们都是类似于顺序表的结构，string的底层是一个指针，一个元素的数量，一个空间总容量，而vector的底层是三个指针，这是它们结构上不一样的地方，但是实现的方法和原理还是大差不差的，那本篇我们来谈谈list，list的迭代器和之前的容器是不一样的，而且是一个双向带头循环链表，任意位置的插入删除效率都是O(1)，那我们开始正题

---

一、list的结构

list的结构是一个一个的节点，所以我们在定义的时候就要去定义一个节点

template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _val;
};

_prev指向前一个节点

_next指向下一个节点

_val表示节点中存储的值

list_node这个类可以写成class，然后放成公有，也可以直接定义成struct的，因为这个类中的成员在list这个类中会用到，所以像这种节点类就直接放成公有就好

---

template<class T>
class list
{typedef list_node<T> Node;
private:Node* _head;size_t _size;
};

对于list这个类，我们需要先把list_node这个类给typedef，否则一直用他太长了，而且要带上模版参数，要注意的是，typedef也会受到访问限定符的限制，所以在外面是看不到Node的，然后我们用这个Node来定义一个头结点，也就是指向头节点的指针_head，然后还有一个成员函数是_size，_size是用来返回链表内的数据个数的，如果没有_size的话就只能遍历求一遍，这样增加一个成员变量代价反而小了

---

二、默认成员函数

构造函数

构造函数要来初始化成员变量，所以就需要先去给_head去new一个节点，然后它的前驱和后继都指向自己，_size初始化成0就好了，因为头节点不存储有效数据，所以也就不算做元素个数了

list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}

对于Node这个类在new的时候会去调用它的构造函数，所以我们要给Node类补上一个构造，用匿名对象做这里的缺省参数

template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}
};

---

析构函数

析构函数需要把所有的节点都释放了，因为所有节点都是new出来的，那就先来实现一个clear函数

clear

clear是要清空除头节点外链表中所有的节点，就要从头节点的下一个节点开始，去删除每一个节点，但是删除了当前节点就会找不到下一个节点，所以要先保存一下下一个节点

void clear()
{Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}
}

cur表示的是当前节点，next记录下一个节点的位置，循环判断的条件就是不等于头结点就继续删，删到最后一个节点，那它的next就是头结点了，也就证明删完了，循环结束

---

那在析构函数中就先去调用clear先把后面链接的节点全部删掉，然后再把头节点删掉并置空就好了

~list()
{clear();delete _head;_head = nullptr;
}

---

拷贝构造

这里就不能再去用memcpy或者赋值来写了，因为list在物理上并不是连续的空间，不可以用下标来访问，所以采用的方法是遍历有数据的这个容器，然后依次尾插进被拷贝的容器中

//l2(l1)
list(const list<T>& l)
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto e : l){push_back(e);}
}

然后这里的l2在插入数据前一定要去初始化，要把头节点new出来再把前后都指向自己，否则在访问时会出问题，这里用的是范围for，那就需要支持迭代器才可以，并且push_back也还没有实现，所以暂时这个拷贝构造是不能跑的，大家可以等下面的实现完再回来看

---

赋值重载

赋值就写一个现代写法去调用拷贝构造就可以，这个我们很详细的说过了，在这里就不再多赘述了

swap

void swap(list<T>& l)
{std::swap(_head, l._head);std::swap(_size, l._size);
}

---

//l2 = l1
list<T>& operator=(list<T> l)
{swap(l);return *this;
}

---

三、容量相关

empty

判空的逻辑是判断头节点的前驱和后继是不是指向自己，且元素个数是否为0

bool empty() const
{return _head->_next == _head&& _head->_prev == _head&& _size == 0;
}

---

size

size函数只需要返回_size的值就可以

size_t size() const
{return _size;
}

---

四、数据访问

front/back

front就是返回第一个节点里存储的值，back返回最后一个节点里的值，一定要注意是第一个存储有效数据的节点，所以是头结点的下一个节点，而不是头节点中存储的值

front和back各自分别有两个版本，一个普通版本，一个const版本，跟我们之前讲的一样，普通对象优先调用普通版本，如果没有普通版本再去调用const版本，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的迭代器有哪些不一样，可以说list最重要的部分就是迭代器，大家先来看可不可以这么写我们的迭代器呢？

typedef Node* iterator

答案显而易见，肯定是不可以的，因为迭代器我们解引用是要拿到数据，但是现在解引用拿到的是一个节点，而且++要向下一个位置走，--要向前一个位置走，现在这个迭代器++走到哪去谁能知道呢？所以我们要用运算符重载来控制这里的逻辑，也就要再封装一个迭代器的类来控制

template<class T>
struct __list_iterator
{typedef list_node<T> Node;Node* _node;
};

在外面需要去访问这个类中的成员函数，所以我们把这个迭代器类定义成struct的，里面有一个节点的指针_node，我们先来实现下*和->，*就是返回数据的引用，->是返回数据的地址

T& operator*()
{return _node->_val;
}T* operator->()
{return &(_node->_val);
}

---

然后是++和--，++就是向下一个节点走，--就是向前一个节点走，而++和--呢又分为前置和后置，我们先实现前置，前置的话就是_node走完返回迭代器的本身，那这个迭代器类的名字太长了，我们也同样来typedef一下

typedef __list_iterator<T> Self;

这个typedef就和Node的typedef放在一起就行 

Self& operator++()
{_node = _node->_next;return *this;
}    Self& operator--()
{_node = _node->_prev;return *this;
}

前置++返回的是迭代器走完的结果，所以就可以用引用返回

---

后置是返回++或者--之前的值，那就需要先保存一份才可以，然后返回保存的这一份，区分前置和后置，就是给后置加上一个int类型的参数

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)
{return _node != s._node;
}bool operator==(const Self& s)
{return _node == s._node;
}

---

begin/end

begin就是返回头节点的下一个位置，因为迭代器是左闭右开，所以end应该返回的是最后一个有效数据的下一个位置，也就是头节点_head

iterator begin()
{return _head->_next;
}iterator end()
{return _head;
}

那在list这个类中需要用到iterator，我们就把这个类给嵌到list这个类里，这个要放成公有的，外面要用迭代器

public:typedef __list_iterator<T> iterator;

而且还要给迭代器类实现一个构造函数，用节点指针去构造迭代器，现在的begin和end是隐式类型转换，构造加拷贝构造，拷贝构造我们不需要实现，迭代器去浅拷贝就可以了，也可以返回匿名对象或者是先构造出来对象再返回这个对象，这三种都可以，我们这种是最简单的，直接隐式类型的转换

__list_iterator(Node* node):_node(node)
{}

---

我们再结合迭代器的使用来看

int main()
{hx::list<int> l;hx::list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

需要什么我们就写什么就可以了，迭代器也就是需要这几个函数，不需要实现其他功能了，那我们的普通迭代器就实现好了

---

六、const迭代器

下面我们来看一下const迭代器，有了刚才的封装，那const迭代器可不可以直接套上一个const呢？

typedef __list_iterator<T> iterator;
typedef const __list_iterator<T> const_iterator;

这样写也是不行的，因为这样写就是修饰迭代器本身不能修改了，那迭代器本身都不能修改了还怎么++/--呢？所以const迭代器也是需要我们自己去封装一个自定义类型来控制，那我们就照葫芦画瓢来实现一个

template<class T>
struct __list_const_iterator
{typedef __list_const_iterator<T> Self;typedef list_node<T> Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_val;}const T* 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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

那大家有没有发现，普通迭代器和const迭代器不一样的地方就在于*和->的返回值，其他的地方全都一样，那这样设计就太冗余了，我们有没有办法可以就用一个类来控制一下*和->的返回值呢？其实很好办，只需要增加模版参数就可以

template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr> Self;typedef list_node<T> Node;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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

Ref是引用，也就是operator*的返回值，Ptr是指针，也就是operator->的返回值，然后不要忘记在typedef Self的时候把这两个模版参数给加上，然后在list类中我们把后面的两个模版参数写死就可以了

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

begin/end

const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}

begin和end还是一样的实现逻辑，返回值变一样，再设计成const成员函数就可以

那迭代器部分我们就说到这里，因为这里可能会比较复杂，三个类互相缠绕，所以在文章的最后会把所有的代码给贴出来，如果大家对这里还有不太懂的地方可以去参考

---

七、插入数据

insert

insert是在某个迭代器插入一个val，那就是把这个迭代器里存的节点指针定义出来，然后找到前一个，再新创建一个节点，把他们之间互相链接起来就行了，最后返回新插入的这个节点的迭代器

iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;
}

---

push_back

push_back是尾插，直接去复用insert，给一个迭代器位置

void push_back(const T& val)
{insert(end(), val);
}

 end就是头结点，那在头节点的前面插入也就是尾插

---

push_front

push_back是头插，直接去复用insert，给一个迭代器位置

void push_front(const T& val)
{insert(begin(), val);
}

begin就是头结点的下一个位置，在begin之前插入，也就是在头结点和第一个节点之间插入，就是头插

---

八、删除数据

erase

erase是要删除某个迭代器位置，那也是把迭代器里存的节点指针定义出来，然后找到前后节点，把前后节点互相连起来就好了，最后再删除，然后要返回删除的这个位置的下一个节点的迭代器

iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;
}

---

pop_back

pop_back是尾删，直接去复用erase，给一个迭代器位置

void pop_back()
{erase(--end());
}

end是头节点的位置，那--end就是头结点的前一个，也就是最后一个节点

---

pop_front

pop_front是头删，直接去复用erase，给一个迭代器位置

	void pop_front(){erase(begin());}

begin是头结点的下一个位置，也就是第一个存放有效数据的节点

---

九、代码

namespace hx
{template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef __list_iterator<T, Ref, Ptr> Self;typedef list_node<T> Node;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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){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;}//l2(l1)list(const list<T>& l){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto e : l){push_back(e);}}//l2 = l1list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}bool empty() const{return _head->_next == _head&& _head->_prev == _head&& _size == 0;}size_t size() const{return _size;}void clear(){Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}}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;}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}void push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}private:Node* _head;size_t _size;};
}

---

总结

本篇文章我们讲了list，以及关于迭代器部分，list的迭代器类型是一个自定义类型，跟以前不太一样，但是这种方式在以前也还是很常见的，比如map/set，unordered map/unordered set，还是要这么用，迭代器部分都要去这样封装，大家还是要习惯这种方式，那本篇文章就到这里啦，如果觉得下篇写的不错的小伙伴，可以给小编一个一键三连表示支持，感谢大家！！！