【 C++】list及其模拟实现

一、list介绍

在这里插入图片描述

list是我们之前学过的带头双向链表的类模板，具有链表的一系列性质，也有多种多样的接口便于使用，使用方法与vector大体相似：

函数	接口说明
list()	构造空的list，只有头结点，头结点的前后指针指向自己
begin	返回第一个元素（即头结点的下一个）的迭代器
end	返回最后一个元素下一个位置（即头结点）的迭代器
empty	判断list是否为空，是返回true，否则返回false
front	返回第一个节点中值的引用
back	返回最后一个节点中值的引用
push_front	头插
push_back	尾插
pop_front	头删
pop_back	尾删
insert	插入
erase	删除

除此之外，list还有几个特殊的接口：

• unique，删除重复值

在这里插入图片描述

这个接口能删除list中的重复值，但前提是这个list中数据必须是有序的，如果不是有序的则结果会出错。所以一般都要在调用算法库中的sort排序后再用unique。

在这里插入图片描述

• remove，移除指定元素

在这里插入图片描述

很好理解

在这里插入图片描述

• splice，接合

在这里插入图片描述

splice既可以用于不同list间的数据转移，也可以用于一个list中的数据调整位置：

在这里插入图片描述

在这里插入图片描述

二、list模拟实现

list是一个类模板，那么我们要模拟实现它，显然要先实现出list结点的结构，再实现list类。 除此之外，list的迭代器更加特殊，不像string、vector，由于它们的底层是数组，在内存空间中是连续的，所以它们的迭代器可以用指针直接实现，它们的迭代器可以使用指针的一系列运算符如++、+、*、<等。而list的底层在内存中是不连续的，而且每一个元素都存在各自独立的结点中，如果直接用指针做迭代器，指针的那些操作符就是不合法的。所以我们不能直接用指针做迭代器，但是又想让迭代器有指针的效果便于使用，解决方法就是，用类来封装实现迭代器。

1. 节点

在使用list时，用户一般都不会直接接触到它的节点，所以节点的结构没有必要用访问限定符修饰了，直接用struct实现就行。当然，它还是一个模板，因为存储数据类型会多种多样。

代码语言：javascript

AI代码解释

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

2. 迭代器

用类封装迭代器的目的是，能重载相关的运算符，便于使用

代码语言：javascript

AI代码解释

template<class T> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T> Self; //将迭代器暂且命名为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; } };

这是普通的iterator，但list的迭代器有普通的iterator和const_iterator，前者可以修改引用的内容，后者不可以修改引用的内容。在具体实现上它们区别之一是重载*时，iterator中是T& operator*()，const_iterator中是const T& operator*()，这样解引用const_iterator出的结果就无法修改：

代码语言：javascript

AI代码解释

template<class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> Self; //将迭代器暂且命名为Self便于类内使用 Node* _node; //这个迭代器指向的节点 list_const_iterator(Node* node) :_node(node) { } 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; } };

虽说可以这样写，但是不觉得代码太冗余了吗？有人已经能察觉到了，这里关于iterator和const_iterator，完全可以利用模板写在一起：我们在模板类型中增加一个Ref，代表这个迭代器是普通或是const版本，然后在重载*处写成Ref operator*()，其余出不用修改。这样，迭代器如果是const版本的，给Ref传const T&类型，是普通版本的则传T&类型，巧妙完成了这个问题：

代码语言：javascript

AI代码解释

template<class T, class Ref> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T, Ref> Self; //将迭代器暂且命名为Self便于类内使用 Node* _node; //这个迭代器指向的节点 list_iterator(Node* node) :_node(node) { } Ref 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存的数据是自定义类型，此时我们也会想利用->操作符用迭代器访问到自定义结构中的成员：

代码语言：javascript

AI代码解释

struct A { int a1; char a2; }; list<A> lt; lt.push_back({1, 'a'}); list<A>::iterator it = lt.begin(); cout << it->a1 << it->a2 << endl;

所以，迭代器中也要重载->运算符。但同样的，const版本迭代器不能对指向内容进行修改，还是和上面一样，区分const版本和普通版本迭代器最好用模板来解决，给iterator的模板类型中增加第三个类型Ptr，这样，迭代器如果是const版本的，给Ptr传const T*类型，是普通版本的则传T*类型：

tip：一定不能给const版本迭代器传成T& const或T* const类型，因为迭代器本身一定能改变引用或指向的目标，是能修改的。const T&和const T*才是不能修改引用或指向内容的。

www.dongchedi.com/article/7597158211648979481
www.dongchedi.com/article/7597159849193439769
www.dongchedi.com/article/7597158216006861336
www.dongchedi.com/article/7597158526565302808
www.dongchedi.com/article/7597157528921031193
www.dongchedi.com/article/7597157528921129497
www.dongchedi.com/article/7597158828748390937
www.dongchedi.com/article/7597157605437768216
www.dongchedi.com/article/7597157947516748350
www.dongchedi.com/article/7597157059532309016
www.dongchedi.com/article/7597157528921195033
www.dongchedi.com/article/7597157918697554456
www.dongchedi.com/article/7597158225347412542
www.dongchedi.com/article/7597154994248679961
www.dongchedi.com/article/7597156908373656088
www.dongchedi.com/article/7597155389817848344
www.dongchedi.com/article/7597156872139178558
www.dongchedi.com/article/7597156044007031320
www.dongchedi.com/article/7597154815566905881
www.dongchedi.com/article/7597156083979321918
www.dongchedi.com/article/7597154815567233561
www.dongchedi.com/article/7597155548034925081
www.dongchedi.com/article/7597153356364497433
www.dongchedi.com/article/7597155446209643033
www.dongchedi.com/article/7597153704529101336
www.dongchedi.com/article/7597155329252049470
www.dongchedi.com/article/7597153135701885465
www.dongchedi.com/article/7597153238500491838
www.dongchedi.com/article/7597153219835724350
www.dongchedi.com/article/7597152705005535806
www.dongchedi.com/article/7597152321495679513
www.dongchedi.com/article/7597153608114995774
www.dongchedi.com/article/7597153135702147609
www.dongchedi.com/article/7597153201120559640
www.dongchedi.com/article/7597152939333354008
www.dongchedi.com/article/7597153929230828094
www.dongchedi.com/article/7597151125615264281
www.dongchedi.com/article/7597151505988207166
www.dongchedi.com/article/7597153085034889752
www.dongchedi.com/article/7597151163980497432
www.dongchedi.com/article/7597144704257835545
www.dongchedi.com/article/7597144998823641624
www.dongchedi.com/article/7597145929174991384
www.dongchedi.com/article/7597145158681231896
www.dongchedi.com/article/7597144871509443096
www.dongchedi.com/article/7597144629225505342
www.dongchedi.com/article/7597142612923040281
www.dongchedi.com/article/7597142227030196761
www.dongchedi.com/article/7597142612923335193
www.dongchedi.com/article/7597143374680359486
www.dongchedi.com/article/7597143842856485400
www.dongchedi.com/article/7597143131083342361
www.dongchedi.com/article/7597143126788555289
www.dongchedi.com/article/7597138911823086105
www.dongchedi.com/article/7597139690651009561
www.dongchedi.com/article/7597137695479087678
www.dongchedi.com/article/7597137790945575448
www.dongchedi.com/article/7597139271543407129
www.dongchedi.com/article/7597137533486989848
www.dongchedi.com/article/7597138669631390232
www.dongchedi.com/article/7597100744432910873
www.dongchedi.com/article/7597101277981491736
www.dongchedi.com/article/7597101132292637209
www.dongchedi.com/article/7597091310348403262