目录

🚀前言🚀一，节点类🚀二，迭代器类1，普通迭代器类的实现2，->;运算符的使用场景3，const迭代器类的实现4，通过模板参数，把两个类型的迭代器类结合5，迭代器类的一些问题的思考

🚀三，list 类1，list类的结构2，迭代器的实现3，插入数据insert4，删除数据erase5，头插，头删，尾插，尾删6，常见构造函数的实现7，析构函数

🚀前言

点击跳转到文章：【list的基本使用】

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，list的底层是带头双向循环链表，通过上一篇文章的学习，这些内容已基本掌握，现在我们来模拟实现list容器的主要接口。

与前面的vector类似，由于使用了模板，也只分成.cpp和.h两个文件。

.cpp文件里放节点类，迭代器类，list类及其成员函数，测试函数的实现，在.h文件里进行测试。

本文的重点是：对三个类的区分与理解，迭代器类的实现。

🚀一，节点类

1.为什么定义节点结构体时使用struct而不是class?

答：(1)其实用class也可以，但是class与struct默认的访问限定不同，当没有声明公有，私有时，struct内容默认是公有，class内容默认的私有，所以用class要加上public。

(2)当我们用class没有加上public，也没有实例化对象时，编译不会报错(报私有成员的错误)，因为模版是不会被细节编译的。只有当我们实例化出对象，模版才会被编译，并且类的实例化并不是对所有成员函数都实例化，而是调用哪个成员函数就实例化哪个。这叫做按需实例化。

2.可用匿名对象初始化。如果T是自定义类型，则调用其默认构造，并且T是内置类型也升级成了有默认构造的概念了。

<code>template <class T>

struct ListNode

{

ListNode<T>* _next;

ListNode<T>* _prev;

T _data;

ListNode(const T& data = T())

:_next(nullptr)

,_prev(nullptr)

,_data(data)

{ }

};

🚀二，迭代器类

前面学习的string类和vector的迭代器用的是原生指针类型，即T*。但是在list容器中是不能这样的，因为前面两者的底层物理空间是连续的，符合迭代器++与- -的行为。但是list是由一个一个节点构成的，物理空间不连续，Node*的++和- -不符合迭代器的行为，无法变遍历。

所以用一个类把Node* 封装，就可以重载运算符，使得用起来像内置类型，但会转换成函数调用，继而控制Node*的行为。

1，普通迭代器类的实现

遍历需要的核心运算符重载是 *，!=，++ 和 ->;。所以只需要利用带头双向循环链表的特性，对Node * 进行封装，从而控制Node * 的行为。

class ListIterator

{

typedef ListNode<T> Node;

typedef ListIterator<T> Self;//名字变得简短

public:

Node* _node;//定义一个节点指针

ListIterator(Node* node)

:_node(node)

{ }

//前置:返回之后的值

//++it;//返回与自己一样的类型

Self& operator++()

{

_node = _node->_next;

return *this;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//后置:返回之前的值

Self operator++(int)

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self operator--(int)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

T& operator*()

{

return _node->_data;

}

//返回的是数据的地址

T* operator->()

{

return &_node->_data;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

bool operator==(const Self& it)

{

return _node == it._node;

}

};

2，->运算符的使用场景

假设某个场景下存在一个坐标类：

struct Pos

{

int _row;

int _col;

Pos(int row = 0,int col = 0)

:_row(row)

,_col(col)

{ }

};

如果我们插入坐标，并且想要打印出坐标，该如何遍历？

错误示范：

void test_list2()

{

list<Pos> lt1;

lt1.push_back(Pos(100, 100));//使用匿名对象

lt1.push_back(Pos(200, 200));

lt1.push_back(Pos(300, 300));

//这里的it是Pos*,是结构体指针

list<Pos>::iterator it = lt1.begin();

while (it != lt1.end())

{

cout << *it << " ";//err

++it;

}

cout << endl;

}

原因：因为这里的*it返回的是Pos自定义类型，而访问自定义类型需要需要在类中自己重载流插入(<<)，这里并没有重载，所以报错。

正确操遍历的两种方式：

方式1：通过.操作符直接访问结构体的成员变量(一般不这样访问数据)。

cout << (*it)._row << ":" << (*it)._col << endl;//ok

方式2：通过重载->运算符，对结构体指针进行解引用。

cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;//ok

注意：其实这里严格来说是有两个箭头,第一个运算符重载的调用 it.operator->() 返回的是 Pos*，第二个箭头才是原生指针，Pos*再用箭头访问。为了可读性，省略了一个->。

void test_list2()

{

list<Pos> lt1;

lt1.push_back(Pos(100, 100));//使用匿名对象

lt1.push_back(Pos(200, 200));

lt1.push_back(Pos(300, 300));

//这里的it是Pos*,是结构体指针

list<Pos>::iterator it = lt1.begin();

while (it != lt1.end())

{

//方式1：

//cout << (*it)._row << ":" << (*it)._col << endl;//ok

//*it就是Pos结构体，再用.操作符访问成员

//方式2：

cout << it->_row << ":" << it->_col << endl;//ok

//cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;//ok

++it;

}

cout << endl;

}

3，const迭代器类的实现

在我们遍历数据时，有时会写一个打印函数，引用传参，一般建议加const，这就出现了一个const链表：

void Func(const list<int>& lt1)

{

list<int>::const_iterator it = lt1.begin();

while (it != lt1.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

const迭代器不是在普通迭代器前面加const,即不是const iterator。

//err 这样使it本身也不能++了

const list< int >::iterator it = it.begin();

const 迭代器目的:本身可以修改，指向的内容不能修改，类似const T* p。

所以我们要再定义一个类，控制*和->的返回值就可以了。

template <class T>

class ListConstIterator

{

typedef ListNode<T> Node;

typedef ListConstIterator<T> Self;//名字变得简短

public:

Node* _node;//定义一个节点指针

ListConstIterator(Node* node)

:_node(node)

{ }

//前置:返回之后的值

//++it;//返回与自己一样的类型

Self& operator++()

{

_node = _node->_next;

return *this;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//后置:返回之前的值

Self operator++(int)

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self operator--(int)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

// 所以我们要再定义一个类，使用const控制*和->的返回值就可以

const T& operator*()

{

return _node->_data;

}

const T* operator->()

{

return &_node->_data;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

bool operator==(const Self& it)

{

return _node == it._node;

}

};

4，通过模板参数，把两个类型的迭代器类结合

可以发现，其实普通迭代器和const迭代器的本质区别是 * 和 ->，这两个运算符的返回类型的变化。两个类冗余，所以可以通过模板，给不同的模板参数，让编译器自己实例化两个类。

template <class T,class Ref,class Ptr>

struct ListIterator

{

typedef ListNode<T> Node;

typedef ListIterator<T, Ref, Ptr> Self;//名字变得简短

Node* _node;//定义一个节点指针

ListIterator(Node* node)

:_node(node)

{ }

//前置:返回之后的值

//++it;//返回与自己一样的类型

Self& operator++()

{

_node = _node->_next;

return *this;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//后置:返回之前的值

Self operator++(int)

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self operator--(int)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

bool operator==(const Self& it)

{

return _node == it._node;

}

};

5，迭代器类的一些问题的思考

(1) 类中是否需要写析构函数？

这个迭代器类不要写析构函数，因为这里的节点不是迭代器的，是链表的，不用把它释放。我们使用begin，end返回节点给迭代器，是借助迭代器修改，访问数据，所以我们不需要释放。

(2) 类中是否需要写拷贝构造进行深拷贝和写赋值拷贝？

这里也不需要写拷贝构造进行深拷贝，因为这里要的就是浅拷贝。begin返回了第一个节点的迭代器给it，这里就是用默认生成的拷贝构造，浅拷贝给it，那这两个迭代器就指向同一个节点，所以这里用默认的拷贝构造和赋值拷贝就可以了。

🚀三，list 类

1，list类的结构

template <class T>

class list

{

typedef ListNode<T> Node;

public:

//物理空间不是连续的，不符合迭代器的行为，无法遍历

//typedef Node* iterator;

//规范命名

//typedef ListIterator<T> iterator;

//typedef ListConstIterator<T> const_iterator;

typedef ListIterator<T, T&, T*> iterator;

typedef ListIterator<T, const T&, const T*> const_iterator;

//………………

private:

Node* _head;

};

2，迭代器的实现

包含普通迭代器和const迭代器。

iterator begin()

{

//iterator it(_head->_next);

//return it;

return iterator(_head->_next);//使用匿名对象

}

iterator end()

{

return iterator(_head);

}

const_iterator begin()const

{

return const_iterator(_head->_next);

}

const_iterator end()const

{

return const_iterator(_head);

}

3，插入数据insert

iterator insert(iterator pos, const T& x)

{

Node* cur = pos._node;//找到当前节点

Node* newnode = new Node(x);//申请节点

Node* prev = cur->_prev;//找到前一个节点

//prev newnode cur 进行链接

newnode->_next = cur;

cur->_prev = newnode;

prev->_next = newnode;

newnode->_prev = prev;

return iterator(newnode);

}

注意：链表的insert没有迭代器失效问题，因为没有扩容的概念，pos位置的节点不会改变。但是STL库里insert也给了返回值，返回的是新插入位置的迭代器。

4，删除数据erase

iterator erase(iterator pos)

{

assert(pos != end());//防止删除头节点

Node* cur = pos._node;//找到当前节点

Node* prev = cur->_prev;//找到前一个节点

Node* next = cur->_next;//找到后一个节点

prev->_next = next;

next->_prev = prev;

delete cur;

return iterator(next);

}

注意：链表的erase后有迭代器失效问题，pos失效了，因为pos指向的节点被释放了。所以也要返回值，返回的是删除节点的下一个节点的迭代器。

5，头插，头删，尾插，尾删

可以复用前面的 insert和 erase 。

//尾插:end()的下一个位置

void push_back(const T& x)

{

//Node* newnode = new Node(x);//申请节点并且初始化

//Node* tail = _head->_prev;

链接节点

//tail->_next = newnode;

//newnode->_prev = tail;

//_head->_prev = newnode;

//newnode->_next = _head;

insert(end(), x);

}

//尾删

void pop_back()

{

erase(--end());//注意：前置--

}

//头插:在begin前面插入

void push_front(const T& x)

{

insert(begin(), x);

}

//头删

void pop_front()

{

erase(begin());

}

6，常见构造函数的实现

主要包含：构造函数，拷贝构造，initializer_list构造(列表构造)。

注意：由于这些都是在有哨兵位节点的前提下实现的，所以可以把申请哨兵位头节点这一步骤提取出来。

//空初始化，申请哨兵位头节点

void empty_init()

{

_head = new Node();

_head->_next = _head;

_head->_prev = _head;

}

list()

{

empty_init();

}

//拷贝构造:直接复用尾插，前提要有哨兵位头节点

//lt2(lt1)

list(const list<T>& lt)

{

empty_init();

//注意：使用范围for时加上const和&

for (const auto& e : lt)

{

push_back(e);

}

}

//initializer_list构造，前提要有哨兵位头节点

list(initializer_list<T> il)

{

empty_init();

for (const auto& e : il)

{

push_back(e);

}

}

7，析构函数

析构函数的作用是：删除整个链表结构，包括哨兵位节点。

//清空当前数据 留头节点，其余节点释放

void clear()

{

auto it = begin();

while (it != end())

{

//返回删除节点的下一个节点的迭代器

it = erase(it);

}

}

//析构：销毁整个链表

~list()

{

clear();

delete _head;

_head = nullptr;

}