【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最快捷方法

AutoDL上进行tensorboard可视化
3.在实例中执行：tensorboard --port 6006 --logdir work_dirs。2.在实例中执行：export https_proxy=http://127.0.0.1:108
阅读更多2024-11-16
莱特币转型MEME币：背后隐含的加密市场现象
MEME币的兴起标志着加密市场的一种转型，传统的技术创新已经不再是吸引投资者的唯一因素，社区文化和社交媒体的炒作正在成为市场推动力之一。这种趋势的背后，反映了加密市场的一种深层次变化：许多项目原本依靠
阅读更多2024-11-16
STM32仿真proteus位带操作和keil增加头文件C文件
在学习 51 单片机的时候就使用过位操作，通过关键字 sbit 对单片机 IO 口进行位定义。但是 STM32 没有这样的关键字，而是通过访问位带别名区来实现。即将每个比特位膨胀成一个 32 位字，当
阅读更多2024-11-16
【机器学习】机器学习中用到的高等数学知识-5. 函数空间和泛函分析 (Functional Analysis)
函数的连续性和可微性是分析和优化模型的重要数学性质，在机器学习中，这些概念帮助我们评估模型的学习能力和泛化能力。希尔伯特空间和巴拿赫空间是泛函分析中的两个重要概念，它们描述了不同的向量空
阅读更多2024-11-16
苍穹外卖学习-day11
Apache ECharts 是一款基于 Javascript 的数据可视化图表库，提供直观，生动，可交互，可个性化定制的数据可视化图表。常见的统计图形有：柱状图，条形图，折线图不管是哪种形式的图形，
阅读更多2024-11-16
DHTMLX-gantt组件显示不同的颜色
important;important;important;
阅读更多2024-11-16
计算机毕业设计Python+大模型中医养生问答系统知识图谱医疗大数据中医可视化机器学习深度学习人工智能大数据毕业设计
计算机毕业设计Python+大模型中医养生问答系统知识图谱医疗大数据中医可视化机器学习深度学习人工智能大数据毕业设计
阅读更多2024-11-16
使用Markmap从链接生成脑图并下载为交互式HTML文件
在这篇博客中，我们将探讨如何从指定链接中提取内容，生成Markdown格式的脑图，然后使用Markmap将其可视化，并最终下载为交互式HTML文件。通过以上步骤，我们可以轻松从链接中提取内容，生成Ma
阅读更多2024-11-16
SAP+Internet主题HTML样式选择
SAP生成HTML前端界面
阅读更多2024-11-16
关于php Datetime 时区转换因为timezone_version(时区版本)问题造成的时区转换问题
php时区转换 timezone_version(时区版本)问题造成的时区转换问题
阅读更多2024-11-16