【C++】list详解及模拟实现

1. list是一个带头双向循环链表。

2. list的声明，一个模板参数还有一个空间配置器。

3. Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

4. 大框架：默认成员函数，迭代器，容量相关，元素访问，修改相关，排序，合并等。

2. list使用

2.1 修改相关

1. 支持头插，头删，尾插，尾删，pos插，pos删。
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
}
2. assign是赋值，可以用迭代器区间赋值或n个val赋值。

2.2 遍历

1. list不再支持方括号[ ]。

2. 主要还是用迭代器进行遍历，迭代器是内嵌类型，一般用typedef或内部类实现。

3. 支持了迭代器就支持范围for，因为范围for的底层就是迭代器。
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);

list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;

for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

2.3 构造

1. 无参构造，n个val构造，迭代器区间构造，拷贝构造。

2.4 迭代器

1. 有正向迭代器和反向迭代器，并且各自有const版本。

2. 虽然说新加了cbegin这些const系列，但其实begin本身也有const版本。

2.5 容量相关

1. 判空，返回数据个数，max_size没什么意义。

2.6 元素访问

1. 访问头和尾。

2.7 操作相关

1. reverse，逆置

void test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;

lt.reverse();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

2. sort，排序，默认是升序，降序需要用到仿函数。

void test3()
{
list<int> lt;
lt.push_back(5);
lt.push_back(3);
lt.push_back(1);

lt.sort();
//lt.sort(greater<int>());

for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

3. merge，两个链表归并到一起。

4. unique，去重，要求有序。

void test4()
{
list<int> lt(5, 1);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;

lt.unique();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}

5. remove，直接删除val值。

6. splice，转移节点。

3. 模拟实现

3.1 节点类

3.1.1 初始结构

1. 管理节点的类模板，包含节点的数据，节点的前驱指针和后继指针。
template<typename T>
struct list_node
{
T _data; //节点数据
list_node<T>* _prev; //前驱指针
list_node<T>* _next; //后继指针
};

3.1.2 节点的构造函数

1. 参数是节点数据，缺省值是该类型的无参匿名对象。

2. 初始化列表进行成员初始化，节点数据用传入的参数，指针初始为空。
list_node(cosnt T& data = T())
:_data(data)
,_prev(nullptr)
,_next(nullptr)
{}

3.2 迭代器类

3.2.1 初始结构

1. 这里用struct而不是class，因为所有都可以公开，不受访问限定符限制。

2. 成员是一个节点类型的指针。

3. 构造函数，传入一个节点类型的指针，在初始化列表初始化。
template<typename T>
struct list_iterator
{
typedef list_node<T> node;

node* _cur; //迭代器成员

//构造
list_iterator(const node*& cur)
:_cur(cur)
{}
};

3.2.2 迭代器++

1. 前置++，指针指向自己的后一个节点，返回自己的引用。
list_iterator& operator++()
{
_cur = _cur->_next;
return *this;
}
2. 后置++，先把自己拷贝给tmp然后++，返回tmp。后置的参数需要一个int作为标识。
list_iterator operator++(int)
{
list_iterator tmp(*this);
_cur = _cur->_next;
return tmp;
}

3.2.3 迭代器--

1. 前置--，指针指向自己的前一个节点，返回自己的引用。
list_iterator& operator--()
{
_cur = _cur->_prev;
return *this;
}
2. 后置--，先把自己拷贝给tmp然后--，返回tmp。
list_iterator operator--(int)
{
list_iterator tmp(*this);
_cur = _cur->_prev;
return tmp;
}

3.2.4 解引用重载

1. *，解引用重载，返回节点数据的引用。

2. ->，箭头解引用，返回节点数据的地址。这里有两个箭头但被编译器省略了一个，第一个箭头是获取节点中数据成员的地址，第二个箭头是通过这个地址获取数据成员内的成员，因为数据成员可能是自定义类型。
T& operator*()
{
return _cur->_data;
}
T* operator->()
{
return &_cur->_data;
}

3.2.5 比较重载

1. !=重载，和其他迭代器比较，传入迭代器的引用，比较它们的成员。

2. ==重载，传入一个迭代器，进行成员比较。
bool operator==(const list_iterator& it)
{
return _cut == it._cut;
}
bool operator!=(const list_iterator& it)
{
return !(*this == it);
}

3.3 链表类

3.3.1 初始结构

1. 管理链表的类模板，成员只有头结点，这个链表是带头双向循环链表。
namespace lyh
{
//带头循环双向链表
template<typename T>
class list
{
public:
typedef list_node<T> node;

private:
node* _head; //链表头结点
};
}

3.3.2 初始化链表

1. 创建第一个节点也就是头结点。

2. 前驱指针指向自己，后继指针指向自己。
void ListInit()
{
_head = new node;
_head->_prev = _head;
_head->_next = _head;
}

3.3.3 默认成员函数

3.3.3.1 无参构造

1. 直接调用初始化。
list()
{
ListInit();
}

3.3.3.2 析构

1. 复用clear，再释放头结点然后置空，因为clear不清头结点。
~list()
{
clear();
delete _head;
_head = nullptr;
}

3.3.3.3 拷贝构造

1. 先调用初始化函数生成头结点。

2. 用范围for遍历传入的链表，不断给自己尾插。
list(cosnt list& lt)
{
ListInit();
for (auto e : lt)
{
push_back(e);
}
}

3.3.3.4 赋值重载

1. 传入一个链表，拷贝构造给形参。

2. 将自己和形参交换，交换成员。

3. 返回自己的引用。
void swap(const list& lt)
{
std::swap(_head, lt._head);
}
list& operator=(list lt)
{
swap(lt);
return *this;
}

3.3.4 Iterators(迭代器)

1. list类外写了迭代器对象，list类内提供begin和end。

2. begin，返回开始位置的迭代器，返回头结点的下一个节点，会隐式类型转换。

3. end，返回最后一个位置的下一个位置的迭代器，就是头节点，返回地址会隐式类型转换成迭代器。
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}

3.3.4.1 const迭代器

1. 在写一个const迭代器类，相比原本的迭代器就是不能修改指向的内容。

2. 修改内容是通过解引用修改的，所以需要把和解引用的函数修改一下，把解引用的返回值加一个const。

3. 同时在list类提供const版本的begin和end，参数加一个const，返回值是const迭代器。

1. 上面这种方法会造成代码冗余，接下来的方法可以复用代码。

2. 就算类模板相同，只要模板参数不同就是不同的类型。

3. 增加两个模板参数，一个代表引用，一个代表指针，这两个模板参数写在解引用返回值的位置，根据你传什么模板参数，我的返回值就是什么样的，因为迭代器与const迭代器只有解引用的返回值有差别，所以把这两个返回值变成模板参数自己传，其他代码都可以复用。

4. 在list类里面定义迭代器类型和cosnt迭代器类型，这里可以把模板参数写好，然后提供const版本的begin和end。

3.3.5 Modifiers(修改相关)

3.3.5.1 insert(pos插)

1. 传入一个迭代器和节点数据，返回的迭代器指向新插入的节点。

2. 先把迭代器指向的位置赋值给cur，再获取迭代器指向位置的前一个节点prev，建新节点new，new插入在prev和cur之间。

3. 这里迭代器不失效。
iterator insert(iterator pos, const T& val)
{
node* cur = pos._cur;
node* prev = cur->_prev;
node* newnode = new node(val);

prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;

return newnode;
}

3.3.5.2 erase(pos删)

1. 传入迭代器，返回下一个位置的迭代器。

2. 把迭代器指向的位置赋值给cur，获取迭代器的前一个位置prev和后一个位置next。

3. 将prev和next连接，释放cur。

4. 删除后迭代器失效。
iterator erase(iterator pos)
{
node* cur = pos._cur;
node* prev = cur->_prev;
node* next = cur->_next;

prev->_next = next;
next->_prev = prev;
delete cur;

return next;
}

3.3.5.3 push_back(尾插)与push_front(头插)

1. 传入新节点的节点数据，无返回值。

2. 复用insert，尾插在end迭代器前面插入，头插在begin迭代器前面插入。
//尾插
void push_back(const T& val)
{
insert(end(), val);
}
//头插
void push_front(const T& val)
{
insert(begin(), val);
}

3.3.5.4 pop_front(头删)与pop_back(尾删)

1. 无参无返。

2. 复用erase，头删删除begin迭代器指向的位置，尾删删除end前一个位置。
//头删
void pop_front()
{
erase(begin());
}
//尾删
void pop_back()
{
erase(--end());
}

3.3.5.5 clear(清除节点)

1. 用迭代器遍历，然后不断erase。
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}

3.3.6 size(返回数据个数)

1. 这里需要加一个size成员用来记录数据个数。

2. 初始化函数把size置0，insert函数++size，erase函数--size，交换成员也要多一个。
size_t size()
{
return _size;
}

private:
node* _head; //链表头结点
size_t _size; //数据个数

完整代码：List/List · 林宇恒/code-cpp - 码云 - 开源中国 (gitee.com)

4. 打印

1. 这里的list<T>只是类模板还没实例化，不能去取const_iterator。

2. 因为静态成员变量也可以通过类域访问，然后list<T>是未实例化的类模板，编译器不能去里面找，所以这里编译器分不清是静态成员变量还是内嵌类型。

3. 在前面加一个typename就是告诉编译器这是一个内嵌类型，等实例化之后再去里面取。

4.1 不同容器的打印

5. list和vector的区别

1. 随机访问肯定用vector。大量头部，中部的修改肯定用list。vector适合尾插。

2. 迭代器erase都会失效，list insert不会，vector会。

原文地址：https://blog.csdn.net/m0_71164215/article/details/142316497

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：十八，Spring Boot 整合 MyBatis-Plus 的详细配置
下一篇：win11 wsl2安装ubuntu22最快捷方法

低版本JMX Console未授权
低版本JMX Console未授权
阅读更多2024-09-22
图书管理系统
这样所有书籍的所有信息和借阅记录都会保存在文件里，使用查看图书功能可以直接查看。如果不想要这些信息可以直接删除，但只能一条一条的删除（以后会添加一键全部删除的功能）。下面是一个用Python写的图书管
阅读更多2024-09-22
外包干了4年，技术退步太明显了。。。。。
先说一下自己的情况，本科生生，20年通过校招进入武汉某软件公司，干了差不多4年的功能测试，今年国庆，感觉自己不能够在这样下去了，长时间呆在一个舒适的环境会让一个人堕落!没办法，我找到了我在腾讯的老哥，
阅读更多2024-09-22
【学习笔记】STM32F407探索者HAL库开发（五）F407时钟系统配置
在单片机系统中，设计时以时序电路控制替代纯粹的组合电路，在每一级输出结果前对各个信号进行采样，从而使得电路中某些信号即使出现延时也可以保证各个信号的同步，可以避免电路中发生的“毛刺现象”，达到精确控制
阅读更多2024-09-22
C++ 知识要点：其它
八. 其它调试程序的方法？gdb遇到 coredump 要怎么调试？模板的用法与适用场景用过 C++11？新特性？auto,decltype、explicit、lambda、final函数调用的压栈过
阅读更多2024-09-22
【机器学习】11——矩阵求导
矩阵求导
阅读更多2024-09-22
在excel中使用python？
是的！excel中可以使用python了！在去年8月22日，微软通过官方博客发布将与anaconda展开合作，简而言之就是excel将支持python，可以在表格中直接利用python就行数据分析，可
阅读更多2024-09-22
第160天：安全开发-Python-蓝队项目&流量攻击分析&文件动态监控&Webshell检测
本来后续上传的文件，可以调用api接口上传到威胁分析平台进行分析是否有害，根据分析返回的结果，来判断是否进行删除，但是百度免费的网站已经停掉了，virustotal免费的api坏掉了，别的免费的不好用
阅读更多2024-09-22
【Flink实战】flink消费http数据并将数组展开多行
【Flink实战】flink消费http数据并将数组展开多行
阅读更多2024-09-22
【Android】浅析MVC与MVP
架构（Architecture）在软件开发中指的是软件系统的整体设计和结构，它描述了系统的高层组织方式，包括系统中各个组件之间的关系、依赖、交互方式，以及这些组件如何协同工作来完成系统的功能。组件的划
阅读更多2024-09-22