感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步

数据结构习题_LaNzikinh篮子的博客-CSDN博客

初阶数据结构_LaNzikinh篮子的博客-CSDN博客

收入专栏：C++_LaNzikinh篮子的博客-CSDN博客

其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客

个人主页：LaNzikinh-CSDN博客

文章目录

前言一.迭代器二.list的底层实现三.list使用和细节总结

前言

经过前面两个容器的讲解，其实已经对很多接口的使用都了解的差不多了，容器之间接口的使用真的都是大体相同的，但是底层的实现是不同的，今天我们来看看列表是如何实现这个功能的，在讲解列表的实现之前，我们先要再次来讲解这个迭代器

一.迭代器

迭代器的功能分为四种迭代器，反向迭代器，常数迭代器，反向常数迭代器，他的性质有三种，单向迭代器，双向迭代器和随机迭代器，性质的意思就是底层结构，底层结构可以决定可以用哪些算法

举个例子来说，比如说我们之前学过的排序算法，他在库里面就一个专门这样子的函数sort，他支持的就是随机的代替其他不支持，所以说在list创建的类就不能用这个库里面的算法，只能自己实现一个，又比如说逆置算法reverse（需要++/--）他支持双向迭代器，所以说随机的也可以，但是单向的就不行

我们的list就是双向迭代器，我们之前学过的vector和string就是随机迭代器，那我们后面的栈和队列是什么呢？

答案是根本不支持迭代,栈的特性是先进后出，队列的特性是先进先出，如果都满足了迭代器的遍历，那这些特性就不存在了，你支持了迭代器，那你的特性的意义在什么地方呢

二.list的底层实现

我们之前讲过了库函数的使用，直接看文档即可，在这里就不做多的了解了，和之前的使用string，vector是大致相同的，主要还是来看list的底层，他是一个带头双向循环列表，不是我们以前C语言学过的单链表

接下来了，我们先要来定义两个结构体，一个就是节点本身，还有一个就是指向节点的指针，即便它是一个带头双向循环列表，这两个也是必不可少的

2.1定义两个结构体

结点

const T& data = T()；利用缺省参数来进行初始化

<code>template<class T>

struct list_node

{

T _data;

list_node<T>* _next;

list_node<T>* _prev;

list_node(const T& data = T())

:_data(data)

, _next(nullptr)

, _prev(nullptr)

{}

};

指向节点的指针

注意：这里获取的迭代器，就是一个节点的指针

因为他是一个指针，所以说我们要用函数重载来定义它的加加减减和判断等于，还有解引用

template<class T>

struct list_iterator

{

typedef list_node<T> Node;

typedef list_iterator<T> Self;

Node* _node;

list_iterator(Node* node)

:_node(node)

{}

T& operator*()

{

return _node->_data;

}

Self& operator++()

{

_node = _node->_next;

return *this;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

bool operator!=(const Self& s) const

{

return _node != s._node;

}

bool operator==(const Self& s) const

{

return _node == s._node;

}

};

2.2insert（）和 erase（）

迭代器失效问题

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

insert（）

void insert(iterator pos, const T& x)

{

Node* cur = pos._node;

Node* prev = cur->_prev;

Node* newnode = new Node(x);

// prev newnode cur

newnode->_next = cur;

cur->_prev = newnode;

newnode->_prev = prev;

prev->_next = newnode;

++_size;

}

erase（）

只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

void erase(iterator pos)

{

assert(pos != end());

Node* prev = pos._node->_prev;

Node* next = pos._node->_next;

prev->_next = next;

next->_prev = prev;

delete pos._node;

--_size;

}

所以要用返回值来改正，防止迭代器失效

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };

list<int> l(array, array+sizeof(array)/sizeof(array[0]));

auto it = l.begin();

while (it != l.end())

{

l.erase(it++); // it = l.erase(it);

}

2.3头插尾插一个数据

直接复用就可以了

void push_back(const T& x)

{

insert(end(), x);

}

void push_front(const T& x)

{

insert(begin(), x);

}

2.4析构函数和迭代器函数

iterator begin()

{

return _head->_next;

}

iterator end()

{

return _head;

}

list()

{

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

_size = 0;

}

2.4成员对象

private:

Node* _head;

size_t _size;

三.list使用和细节

还是补充几个list一些独特的函数使用方式和一些使用它的细节

emplace：构造和插入元素

他是支持直接传构造函数对象的参数的

list<A> lt;

A a1(1,1);

lt.push_back(3,3);//不合理，不存在

lt.emplace_back(3,3);//可以

unique：删除重复值

注意：前提要有序不然删不完全

merge：合并排序列表

注意：合并排序列表，v1会被滞空

it.merge(v1);

补：

如果要在pos的位置插入一个30大小的元素

auto it = lt.begin();

int k = 3;

while (k--)

{

++*it;

}

it.insert(it, 30);

因为他的迭代器只支持++

总结

链表容器结构到这里就结束了，下一章，我们将引入一个适配器的概念去完成栈与队列的知识