【C++】list讲解及模拟

news/2024/11/15 6:04:29/

目录

list的基本介绍

list模拟实现

一.创建节点

二.迭代器

1.模版参数

2.迭代器的实现：

a. !=

b. ==

c. ++ --

d. *指针

e.&引用

整体iterator (与const复用)：

三.功能实现

1.模版参数

2.具体功能实现：

2.1 构造函数

2.2 begin() && end()

2.3插入

insert任意位置插入

push_back 尾插&& push_front前插

2.4 删除

erase任意位置删除

pop_back 头删 && pop_front尾删

2.5 拷贝构造 && 赋值操作符

2.6 clear() && 析构函数

代码示例

Test.cpp

list.h

list的基本介绍

list本质上是一个带头双向循环链表，列表是一种用于存储一组元素的数据结构，元素按照插入的顺序排列。它允许动态地添加和删除元素，可以重复存储相同的值。列表提供了对元素的插入、删除、访问和遍历等常用操作。

列表是序列容器，允许在序列内的任何位置插入和擦除操作，并在两个方向上进行迭代。

列表容器被实现为双链接列表；双链接列表可以将它们所包含的每个元素存储在不同的和不相关的存储位置中。顺序通过与前面元素的链接和后面元素的链接的关联在内部保持。

与其他序列容器相比，列表和前向列表的主要缺点是它们无法通过位置直接访问元素； 例如，要访问列表中的第六个元素，必须从已知位置（如开始或结束）迭代到该位置，该位置之间的距离需要线性时间。它们还会消耗一些额外的内存来保持与每个元素相关联的链接信息（这可能是大量小元素列表的一个重要因素）。

若要查看双向循环链表相关知识→：数据结构：线性表之-循环双向链表(万字详解)_数据结构循环双链表概念-CSDN博客

list模拟实现

一.创建节点

template <class T>//模版
struct list_node
{list_node<T> *_prev;//前一节点list_node<T> *_next;//后一节点T _data;
​// 构造函数，创建链表list_node(const T &x = T()) // 用匿名对象做缺省值(调用默认构造)，以存储其他类型的元素: _next(nullptr), _prev(nullptr), _data(x){}
};

二.迭代器

1.模版参数

template <class T, class Ref, class Ptr>

  1. class T:表示元素类型,为了应对要接收不同类型的数据

  2. class Ref:引用类型参数模版，Ref用于提供对迭代器所指向元素的引用

  3. class Ptr：指针类型参数模版，Ptr用于提供对迭代器所指向元素的指针。

后面会提到Ref，Ptr作用，请仔细阅读哦

2.迭代器的实现：

基本模版：

template <class T, class Ref, class Ptr>
struct __list_iterator
{//重新命名typedef list_node<T> node; typedef __list_iterator<T, Ref, Ptr> self;node *_node;//指向列表节点的指针，用于追踪迭代器的当前位置。
​//构造函数，接受一个指向列表节点的指针，并将其作为初始位置给 _node。__list_iterator(node *n): _node(n){}
};

这个结构体的作用是提供列表的迭代功能，它可以被用于遍历列表中的元素，并对元素进行访问和操作。

"const T&"表示迭代器所指向元素的引用类型，而"const T*"表示迭代器所指向元素的指针类型。 这样定义迭代器的目的是为了在const成员函数中使用该迭代器，并保证在遍历列表时不会修改列表中的元素"

参考：

list<int>::iterator it = lt.begin();
//__list_itreator后续被重命名为iterator
a. !=
bool operator!=(const self &s)
{return _node != s._node;
}
b. ==
bool operator==(const self &s)
{return _node == s._node;
}
c. ++ --
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;
}
d. *指针

重载了解引用运算符(*)，返回 _node->_data 的引用，即迭代器所指向的元素

Ref &operator*()//加const不能修改数据
{return _node->_data;
}
e.&引用

重载了箭头运算符(->)，返回 _node->_data 的指针，即迭代器所指向元素的指针。

Ptr operator->()
{return &(_node->_data); // 取地址
}

Ref与Ptr的定义在class list中进行定义

整体iterator (与const复用)：
template <class T, class Ref, class Ptr>
struct __list_iterator
{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node *_node;__list_iterator(node *n): _node(n){}Ref &operator*(){return _node->_data;}Ptr 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){return _node != s._node;}bool operator==(const self &s){return _node == s._node;}
};

三.功能实现

1.模版参数

    
template <class T>
class list
{typedef list_node<T> node;public://iterator和const_iterator都是公用接口typedef __list_iterator<T, T &, T *> iterator;typedef __list_iterator<T, const T &, const T *> const_iterator;private://头节点node *_head; // ListNode<T>是类型 ， ListNode是类名
};

2.具体功能实现：

2.1 构造函数

为了后续操作的方便，将初始化链表代码写在另一个函数里

void empty_init()
{_head = new node;_head->_next = _head;_head->_prev = _head;
}
list()
{empty_init();
}
2.2 begin() && end()
iterator begin()
{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);
}

test:通过迭代器依次打印出元素

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

我们将迭代器遍历封装到一个函数内：

void print_list(const list<T> &lt)
{cout << "---list---" << endl;// list<int>::const_iterator it = lt.begin();list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl<< "---list---" << endl;
}
2.3插入
insert任意位置插入
void insert(iterator pos, const T &x)
{node *cur = pos._node;   // .访问pos内的成员变量_nodenode *prev = cur->_prev; // ->访问指针所指向的节点的成员
​node *new_node = new node(x);
​prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;
}
push_back 尾插&& push_front前插
void push_back(const T &x)
{insert(end(), x);
}
void push_front(const T &x)
{insert(begin(), x);
}

test:

void test_list3()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);
​list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
​it = lt.begin();list<int>::iterator pos = lt.begin();++pos;lt.insert(pos, 20);
​lt.print_list(lt);
​cout << endl;
}
2.4 删除
erase任意位置删除
iterator 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;
​return iterator(next);
}
pop_back 头删 && pop_front尾删
void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}

test:

void test_list4()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout << endl;lt.push_back(100);lt.push_front(99);lt.print_list(lt);cout << endl;
​lt.pop_back();lt.pop_front();lt.print_list(lt);cout << endl;
}

2.5 拷贝构造 && 赋值操作符

swap交换函数：

void swap(list<T> &temp)
{std::swap(_head, temp._head);
}

当调用swap函数时[例子：lt2拷贝lt1调用swap时]，调用拷贝构造将lt1进行拷贝再交换到lt2

list：

list(const list<T> &lt)
{empty_init();//创建头节点list<T> temp(lt.begin(), lt.end());swap(temp);
}

赋值操作数：

// lt3=lt2
// 不能使用&，而是传值调用拷贝构造,拷贝lt2，赋值给lt3
list<T> &operator=(const list<T> lt)//const list<T>& lt
{swap(lt);return *this;
}

test:

void test_list6()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout << endl;
​// list<int> lt2(lt);// lt2.print_list(lt2);// cout << endl;list<int> lt2 = lt;lt2.print_list(lt2);lt.print_list(lt);
}

2.6 clear() && 析构函数

clear：清除头节点以外的数据

void clear()
{iterator it = begin();while (it != end())it = erase(it); // erase(it++);//后置++返回的是前一个的拷贝，不会失效
}

test:

void test_list5()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout << endl;
​lt.clear();lt.push_back(20);
​lt.print_list(lt);
}

析构：

~list()
{clear();delete _head;_head = nullptr;
}

代码示例

Test.cpp

#include "list.h"int main()
{wzf::test_list6();return 0;
}

list.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;namespace wzf
{// 节点template <class T>struct list_node{list_node<T> *_prev;list_node<T> *_next;T _data;// 构造函数，创建链表list_node(const T &x = T()) // 用匿名对象做缺省值(调用默认构造)，以存储收其他类型的元素: _next(nullptr), _prev(nullptr), _data(x){}};// 迭代器// // 1.iterator// template <class T>// struct __list_iterator// {//     typedef list_node<T> node;//     typedef __list_iterator<T> self;//     node *_node;//     __list_iterator(node *n)//         : _node(n)//     {//     }//     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)//     {//         return _node != s._node;//     }//     bool operator==(const self &s)//     {//         return _node == s._node;//     }// };// // 2.const_iterator// template <class T>// struct __list_const_iterator// {//     typedef list_node<T> node;//     typedef __list_const_iterator<T> self;//     node *_node;//     __list_const_iterator(node *n)//         : _node(n)//     {//     }//     const T &operator*() // 与1区别的地方，加const不能修改数据//     {//         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)//     {//         return _node != s._node;//     }//     bool operator==(const self &s)//     {//         return _node == s._node;//     }// };// template <class T,class Ref>// struct __list_iterator// {//     typedef list_node<T> node;//     typedef __list_iterator<T,Ref> self;//     node *_node;//     __list_iterator(node *n)//         : _node(n)//     {//     }//     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)//     {//         return _node != s._node;//     }//     bool operator==(const self &s)//     {//         return _node == s._node;//     }// };// 迭代器template <class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node *_node;__list_iterator(node *n): _node(n){}Ref &operator*(){return _node->_data;}Ptr 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){return _node != s._node;}bool operator==(const self &s){return _node == s._node;}/*"const T&"表示迭代器所指向元素的引用类型，而"const T*"表示迭代器所指向元素的指针类型。这样定义迭代器的目的是为了在const成员函数中使用该迭代器，并保证在遍历列表时不会修改列表中的元素*/};template <class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T &, T *> iterator;typedef __list_iterator<T, const T &, const T *> const_iterator;// typedef __list_const_iterator<T> const_iterator;iterator begin(){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);}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}// 构造函数， 迭代器区间template <class Iterator>list(const Iterator first, const Iterator last){empty_init(); // 创建头节点for (Iterator it = first; it != last; ++it)push_back(*it);}void swap(list<T> &temp){std::swap(_head, temp._head);}// 拷贝构造// lt2(lt1)// list(const list<T> &lt)// {//     empty_init();//     const_iterator it = lt.begin();//     while (it != lt.end())//     {//         push_back(*it);//         ++it;//     }// }list(const list<T> &lt){empty_init();list<T> temp(lt.begin(), lt.end());swap(temp);}// 赋值操作符// lt3=lt2// 不能使用&，而是传值调用拷贝构造,拷贝lt2，赋值给lt3list<T> &operator=(const list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}// 清除头节点以外的数据void clear(){iterator it = begin();while (it != end())it = erase(it); // erase(it++);//后置++返回的是前一个的拷贝，不会失效}// void push_back(const T &x)// {//     node *tail = _head->_prev;//     node *new_node = new node(x);//     tail->_next = new_node;//     new_node->_prev = tail;//     new_node->_next = _head;//     _head->_prev = new_node;// }void push_back(const T &x){insert(end(), x);}void push_front(const T &x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void print_list(const list<T> &lt){cout << "---list---" << endl;// list<int>::const_iterator it = lt.begin();list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl<< "---list---" << endl;}void insert(iterator pos, const T &x){node *cur = pos._node;   // .访问pos内的成员变量_nodenode *prev = cur->_prev; // ->访问指针所指向的节点的成员node *new_node = new node(x);prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;}iterator 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;return iterator(next);}/*在该函数的最后一行，返回了一个迭代器对象 `iterator(next)`。这是因为在 C++ STL 中，通常情况下，删除一个元素后，我们希望返回删除元素的下一个位置作为新的迭代器。直接返回 `next` 的话，可能会暴露内部实现细节，使得用户可以直接操作指针 `next`，可能导致潜在的问题。为了隐藏底层指针的细节，通常会将其封装在迭代器对象中返回。因此，返回 `iterator(next)` 的方式可以提供更好的封装性和安全性，使用户能够使用迭代器对象来操作返回的下一个位置，而不需要直接访问底层的指针。这也符合 C++ STL 设计的一般原则，即通过迭代器提供统一的接口，隐藏底层的具体实现细节。*/private:node *_head; // ListNode<T>是类型 ， ListNode是类名};void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;lt.print_list(lt);}struct AA{int _a1;int _a2;AA(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}};void test_list2(){list<AA> lt;lt.push_back(AA(1, 2));lt.push_back(AA(3, 4));lt.push_back(AA(5, 6));list<AA>::iterator it = lt.begin();while (it != lt.end()){cout << it->_a1 << " " << it._node->_data._a2 << endl;cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;cout << it.operator->() << endl<< endl; // 地址值++it;}}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;it = lt.begin();list<int>::iterator pos = lt.begin();++pos;lt.insert(pos, 20);lt.print_list(lt);cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout << endl;lt.push_back(100);lt.push_front(99);lt.print_list(lt);cout << endl;lt.pop_back();lt.pop_front();lt.print_list(lt);cout << endl;}void test_list5(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout << endl;lt.clear();lt.push_back(20);lt.print_list(lt);}void test_list6(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout << endl;// list<int> lt2(lt);// lt2.print_list(lt2);// cout << endl;list<int> lt2 = lt;lt2.print_list(lt2);lt.print_list(lt);}
}


http://www.ppmy.cn/news/1333586.html

相关文章

mac/macos上编译electron源码

mac/macos上编译electron源码

官方教程&#xff1a;Build Instructions | Electron 准备工作这里不写了&#xff0c;参考官方文档&#xff0c;还有上一篇windows编译electron electron源码下载及编译-CSDN博客 差不多步骤&#xff0c;直接来 网络记得使用魔法 下载编译步骤 0. 选择目录很重要&#xff0…
阅读更多...
EIGRP实验

EIGRP实验

实验大纲 一、基本配置 1.构建网络拓扑结构图 2.路由器基本配置 3.配置PC 4.测试连通性 5.保存配置文件 二、配置EIGRP 1.查看路由表 2.配置EIGRP动态路由 3.查看路由器路由表 4.测试网络连通性 5.查看所有路由器的路由协议 6.保存配置文件 三、配置OSPF 1.配置…
阅读更多...
数据库设计的一些原则

数据库设计的一些原则

文章目录 数据库设计原则表之间的关系一对一关系&#xff08;了解&#xff09;一对多&#xff08;多对一&#xff09;多对多联合主键和复合主键 数据库设计准则-范式1、函数依赖2、完全函数依赖3、部分函数依赖4、传递函数依赖5、码 第一范式第二范式第三范式第三范式 数据库设…
阅读更多...
NodeJS Express实现所有页面Http访问重定向跳转为Https

NodeJS Express实现所有页面Http访问重定向跳转为Https

要在Node.js Express中实现所有页面从HTTP访问跳转到HTTPS&#xff0c;你可以使用重定向中间件。以下是一个简单的示例&#xff1a; 1. 首先&#xff0c;确保你已经安装了Express和express-redirect中间件。如果没有&#xff0c;你可以通过npm进行安装&#xff1a; npm insta…
阅读更多...
构建支持 gpu 的 jupyterlab docker 镜像

构建支持 gpu 的 jupyterlab docker 镜像

构建支持 gpu 的 jupyterlab docker 镜像 1. 创建 Dockerfile2. 构建镜像3. 启动 gpu-jupyter4. 访问 gpu-jupyter 1. 创建 Dockerfile 创建一个 Dockerfile 文件&#xff0c;内容如下 FROM docker.io/nvidia/cuda:12.2.2-cudnn8-runtime-ubuntu22.04ENV DEBIAN_FRONTENDnoni…
阅读更多...
单片机学习笔记---独立按键控制LED亮灭

单片机学习笔记---独立按键控制LED亮灭

直接进入正题&#xff01; 今天开始我们要学习一个新的模块&#xff1a;独立按键&#xff01; 先说独立按键的内部结构&#xff1a; 它相当于一种电子开关&#xff0c;按下时开关接通&#xff0c;松开时开关断开&#xff0c;实现原理是通过轻触按键内部的金属弹片受力弹动来实…
阅读更多...
pip 安装出现报错 SSLError(SSLError(“bad handshake

pip 安装出现报错 SSLError(SSLError(“bad handshake

即使设置了清华源&#xff1a; pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simplepip 安装包不能配置清华源&#xff0c;出现报错: Retrying (Retry(total2, connectNone, readNone, redirectNone, statusNone)) after connection broken by ‘SSLE…
阅读更多...
SimpleDateFormat学习使用

SimpleDateFormat学习使用

提起SimpleDateFormat类&#xff0c;想必做过Java开发的童鞋都不会感到陌生。没错&#xff0c;它就是Java中提供的日期时间的转化类。这里&#xff0c; 为什么说SimpleDateFormat类有线程安全问题呢&#xff1f;有些小伙伴可能会提出疑问&#xff1a;我们生产环境上一直在使用S…
阅读更多...
最新文章

Copyright @ 2022~2023