list容器

1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向

其前一个元素和后一个元素。

3. list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高

效。

4. 与其他的序列式容器相比 (array ， vector ， deque) ， list 通常在任意位置进行插入、移除元素的执行效率

更好。

5. 与其他序列式容器相比， list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list

的第 6 个元素，必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置，在这段位置上迭代需要线性的时间

开销； list 还需要一些额外的空间，以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这

可能是一个重要的因素 )

2.使用

2.1构造函数

//第一种常用
//第一个参数给数量，第二个参数给初始化的值，比如2个3
list<int>i(2,3);
//3 3
//第二种常用
//给一个迭代器区间（可以是指针）
list<int>i1(i.begin(), i.end());
//3 3
//第三种常用
//拷贝构造
list<int>l3(i1);
//3 3

当然还有就是无参构造
list()

另外，还有一个就是=的运算符重载

也就是说，可以这样写

list<int>i1(3,6);
list<int>l3 = i1;//注意，这其实还是拷贝构造，赋值是两个都已存在的实体类之间
list<int>j;
j = l3;//这才是赋值

2.2迭代器

begin(),end(),rbegin(),rend(),cbegin(),cend(),crbegin(),crend()

我们要知道，list是个双向循环的链表，也就是说，每个节点，都存在着前驱和后驱。

begin()和rend()，指向的就是第一个节点（有效节点）,rbegin()和end()指向的就是头结点（不存有效数据）

begin(),end()如果++，是向后移动，rbegin(),rend()是向前移动

至于加个c，纯粹就是const修饰的迭代器罢了

遍历方式

list没有[]的重载，因为list的每个元素，物理空间不一定连续，那么就不能用指针+-的方式来随机访问，因此这里只能用迭代器遍历的方式
list<int>i = { 2,3,4,5,6,6,7,8 };
list<int>::iterator it = i.begin();
while (it != i.end())
{
cout << (*it) << " ";
it++;
}
或者范围for（但范围for本质还是迭代器）

2.3 容量

empty()

很经典的判断容器里面是否还未空，是返回true，否返回false

size()

返回有效数据个数

max_size()

返回最大能存的数据个数（取决于编译环境）

2.4元素遍历

front()

返回容器第一个元素，分两种重载，即非const和const（避免权限放大）

back()

返回容器最后一个元素，同样两种重载，非const和const（原因同理）

2.5修改

assign()

list<int>i = { 2,3,4,5,6,6,7,8 };
//void assign (size_type n, const value_type& val);
list<int>c;
c.assign(4, 5);
//c : 5555
//注意是替换，不是追加
//template <class InputIterator>
//void assign(InputIterator first, InputIterator last);
c.assign(i.begin(), i.end());
//c:2,3,4,5,6,6,7,8
//注意，是替换，不是追加

push_front()

就是在第一个元素前插入一个数据

pop_front()

删除第一个元素

push_back()

在最后插入一个数据

pop_back()

删除最后一个数据

insert()

list<int>i = { 2,3,4,5,6,6,7,8 };
//第一种
//iterator insert (iterator position, const value_type& val);
//在迭代器指定位置插入一个数据
list<int>::iterator it = i.begin();
while (it != i.end())
{
if ((*it) == 4)break;
it++;
}

it=i.insert(it, 4);
cout << (*it);
cout << endl;
//这个重载还会返回迭代器，比如插入了一个4，那返回的就是指向这个4的迭代器
//i: 2,3,4,4,5,6,6,7,8

//第二种
//void insert (iterator position, size_type n, const value_type& val);
//注意，这个重载是插入多个相同值的元素
i.insert(it, 4,6);
//i:2 3 4 6 6 6 6 4 5 6 6 7 8
it = i.begin();
list<int>c;
//第三种,迭代器区间
//template <class InputIterator>
//void insert(iterator position, InputIterator first, InputIterator last);
c.insert(c.begin(),i.begin(), i.end());
//c::2 3 6 6 6 6 4 4 5 6 6 7 8

erase()

list<int>i = { 2,3,4,5,6,6,7,8 };
list<int>::iterator it = i.begin();
while ((*it) != 4)it++;
//第一种
//iterator erase (iterator position);
//删除迭代器指向数据，返回删除之后，新的原相对位置的数据的迭代器
it=i.erase(it);
//i:2 3 5 6 6 7 8

//第二种，删除迭代器区间的元素
//iterator erase (iterator first, iterator last);
while ((*it) != 6)it++;
i.erase(it, i.end());
//i:2 3 5

swap()

简单的交换

resize()

扩容

void resize (size_type n, value_type val = value_type());
给n个空间大小，初始化值val
这里是调用无参构造

clear()

清空容器

2.6操作

reverse()

经典的逆置函数
list<int>i = { 2,3,4,5,6,6,7,8 };
i.reverse();
//i:8 7 6 6 5 4 3 2
sort()

排序，默认从小到大排，你可以自己写个规则,用法跟algorithm的sort()一样

之所以单独提供，是因为链表的物理空间不连续，而算法库的sort是针对连续物理空间的

而且算法库用的是快排，而链表这里用的是归并

平时用的话，速度还不如直接拷贝到vector，用算法库的sort之后，再拷贝回链表快

merge()

合并两个有序的链表，注意一定要有序，然后根据规则（默认从小到大），跟algorithm的sort()一样.

unique()

去重，注意，相同的必须紧邻，所以你可以先sort()，如果为了适配自定义类型，可以自己写个规则，跟algorithm的sort()一样

remove()

跟erase的最大区别就是，不用给迭代器，只用给值，相当于容器自己找

remove_if()

满足条件才删除

splice()
list<int>i = { 2,3,4,5,6,6,7,8 };
list<int>b = { 6,7,8,9,0,34,12,1 };
//第一种
//void splice (iterator position, list& x);
//直接把x的所有节点都转移过去，x变空
i.splice(i.begin(), b);
//i:6 7 8 9 0 34 12 1 2 3 4 5 6 6 7 8

//void splice (iterator position, list& x, iterator i);
list<int>c= { 6,7,8,9,0,34,12,1 };
i.splice(i.begin(), c, c.begin());
//i:6 6 7 8 9 0 34 12 1 2 3 4 5 6 6 7 8
//是将第二个参数指向的链表中的最后一个参数的位置的值转移过去
//c的第一个6会没掉

//void splice (iterator position, list& x, iterator first, iterator last);
//这个就不示范了，就是把一个区间的节点转移过去
注意，可以自己转移自己，就是在一个链表里面转移

3.模拟

反向迭代器，我在这里先不实现，等后面另一篇文章的时候再补充上去

#pragma once
#include<assert.h>
namespace manba {
//注意，这个是节点的类，我们实现的是双向带头链表，所以要有前驱和后驱
template<class T>
struct ListNode {
ListNode<T>* _next;//前驱
ListNode<T>* _prev;//后驱
//注意<>在类里面，是可以忽略的，但我们严谨一些
T _data;//存数据
ListNode(const T& x=T())//默认构造函数，方便后面调用,因为不确定参数类型，所以默认值
//直接用T类型的默认构造即可，不管是内置还是自定义都可以符合
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};

//这里通过Ref，第二个模板参数，简约的实现了const迭代器和正常迭代器的转换
//ptr控制的是配合重载->，区分const迭代器和普通迭代器
template<class T,class Ref,class Ptr>
struct _list_iterator {
typedef ListNode<T> Node;
//注意，类名<T>才是一个链表节点类型，这里重命名一下，方便后面少写点
typedef _list_iterator<T,Ref,Ptr> self;
//跟上面一个同理,这里是一个链表迭代器类型
Node* _node;
//迭代器本质还是指针，只是因为原始指针针对物理空间不连续的容器，无法实现++
//而我们无法重载指针，所以我们采用封装的方式，将指针封装起来，将封装起来的迭代器
//重载前后置++，前后置--，解引用*等运算符，理由前驱后驱指针，实现向前向后走


_list_iterator(Node* node)//这里是默认构造，方便各种调用
:_node(node)
{}


//前置++
self& operator++()
{
_node = _node->_next;
return *this;
}

//后置++
//注意，这里我们返回的时候不用&，因为tmp是局部变量，函数结束后会销毁，所以直接返回迭代器类型
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;
}

//解引用,利用ref，实现const迭代器和普通迭代器
Ref operator*()
{
return _node->_data;
}
//不等于
bool operator !=(const self& s)
{
return _node != s._node;
}
//等于
bool operator==(const self& s)
{
return _node == s._node;
}
Ptr operator->()
{
return &_node->_data;
}
/*struct AA {
int b;
AA(int a = 1)
:b(a)
{

}
};*/
/*manba::List<manba::AA> l1;
l1.push_back(3);
l1.push_back(7);
l1.push_back(9);
l1.push_back(12);
manba::List<manba::AA>::iterator it = l1.begin();
while (it != l1.end())
{

cout << it.operator->()->b << endl;
cout<<it->b<<endl;
it++;
}
cout << endl;*/
};

//const迭代器
//template<class T>
//struct _list_const_iterator {
//typedef ListNode<T> Node;
////注意，类名<T>才是一个链表节点类型，这里重命名一下，方便后面少写点
//typedef _list_const_iterator<T> self;
////跟上面一个同理,这里是一个链表迭代器类型
//Node* _node;
////迭代器本质还是指针，只是因为原始指针针对物理空间不连续的容器，无法实现++
////而我们无法重载指针，所以我们采用封装的方式，将指针封装起来，将封装起来的迭代器
////重载前后置++，前后置--，解引用*等运算符，理由前驱后驱指针，实现向前向后走


//_list_const_iterator(Node* node)//这里是默认构造，方便各种调用
//:_node(node)
//{}



////前置++
//self& operator++()
//{
//_node = _node->_next;
//return *this;
//}

////后置++
////注意，这里我们返回的时候不用&，因为tmp是局部变量，函数结束后会销毁，所以直接返回迭代器类型
//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;
//}

////解引用
//const T& operator*()
//{
//return _node->_data;
//}
////不等于
//bool operator !=(const self& s)
//{
//return _node != s._node;
//}
////等于
//bool operator==(const self& s)
//{
//return _node == s._node;
//}
//};
template<class T>
class List {
typedef ListNode<T> Node;
public:

typedef _list_iterator<T,T&,T*> iterator;
//typedef _list_const_iterator<T> const_iterator;

//这里迭代器直接传const类型的模板参数
typedef _list_iterator<T, const T&,const T*> const_iterator;
//跟上面一样
//空链表初始化
void empty_init() {
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
//默认构造函数
List() {
empty_init();
}
//拷贝构造函数
//List(const List<T> &cp)
List(List<T>& cp)
{
empty_init();
for (const auto& e : cp)
{
push_back(e);
}
}

//交换函数,交换物理地址
void swap(List<T>&t)
{
std::swap(_head, t._head);
}
//赋值
//第一种
//List<T>& operator=(const List<T>& t2)
/*List<T>& operator=( List<T>& t2)
{

if (this != &t2)
{
clear();
for (const auto& e : t2)
{
push_back(e);
}
}
return *this;
}*/
//第二种
//这个方法的妙处在于，因为外面要赋值的链表是直接通过拷贝构造直接给了t2链表
// ，也就是传值。
//而拷贝构造我们用的是深拷贝，这样t2的空间和外面的类是不一样的，如此，直接
//让this链表和t2交换，函数结束之后，t2作为局部变量，t2会自动调用析构函数。
List<T>& operator=(List<T> t2)
{
swap(t2);
return *this;
}

//返回第一个有效节点的迭代器
iterator begin()
{
return _head->_next;
}

iterator end()
{
return _head;
}
//返回第一个有效节点的const迭代器
const_iterator begin() const
{
return _head->_next;
}

const_iterator end() const
{
return _head;
}
//尾插
void push_back(const T& x)
{
insert(iterator(_head), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}

//在指定位置前面插入
//vector 迭代器在insert会失效，list不会
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
//删除指定位置
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 next;
}  
//注意，vector在insert和erase处都会有迭代器失效的风险，所以要注意返回值。
//而list在insert处不会，不用担心，但是erase处就要考虑这个问题了，要注意接收返回值。
//更详细的，可以参考我在vector文章里，vector的模拟中对insert和erase的模拟。
//另外补充一下，vector处的erase会出现迭代器失效，主要是针对vs的强制检查和如果删除了最后一个
//元素，会导致迭代器超出了数组有效范围。
//而对于list的erase，因为链表底层物理不一定是连续的，这样原迭代器封装的指针指向的空间是非法空间，
//所以要注意返回值。

//清空链表
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}

//析构函数
~List()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
//头结点，注意，整个list是左闭右开，head是也是end()返回的

};

}

原文地址：https://blog.csdn.net/MXZSL/article/details/138398480

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

上一篇：Ruby 循环
下一篇：分享一个 .NET EF 6 扩展 Where 的方法

论文《基于现实迷宫地形的电脑鼠设计》深度分析（二）——超声波环境感知算法
《基于现实迷宫地形的电脑鼠设计》是由吴润强、庹忠曜、刘文杰、项璟晨、孙科学等人于2023年发表的一篇优秀期刊论文。其针对现阶段电脑鼠计算量庞大且不适用于现实迷宫地形的问题，特基于超声波测距与传统迷宫算
阅读更多2024-11-18
笔记整理—linux驱动开发部分（13）块设备
整理一下学习的内容，个人观点可能存在错误。本章介绍了什么是块设备，对比了块设备与字符设备的区别，并说明块设备更适合驱动内存类设备的原因。
阅读更多2024-11-18
【Linux】进程状态，优先级，环境变量
进程状态，优先级，环境变量
阅读更多2024-11-18
【Spring】循环引用解决流程，只用一二级缓存？
循环依赖：循环依赖其实就是循环引用，也就是bean互相持有对方，最终形成闭环。比如A依赖于B，B依赖于A循环依赖在spring中是允许存在，spring框架依据三级缓存已经解决了大部分的循环依赖三级缓
阅读更多2024-11-18
Windows、Linux多系统共享蓝牙设备
不需要配对的其实非常不可靠，单独使用可能感受不到，当在很近的距离内使用多套无线鼠标或者无线话筒，就会发现相互干扰的现象，因为它们都是基于一个简单的标签或者信道来区分，而这种划分很容易重复。在网上查资料
阅读更多2024-11-18
自然语言处理技术之细粒度实体识别
细粒度实体识别是自然语言处理（NLP）领域中的一个重要研究方向，其目标是从文本中识别出更加具体和详细的实体类型。相比于传统的实体识别（NER），细粒度实体识别不仅关注常见的实体类别（如。
阅读更多2024-11-18
Linux 域通信
【代码】Linux 域通信。
阅读更多2024-11-18
正则表达式从入门到精通
正则表达式从入门到入土
阅读更多2024-11-18
linux alsa-lib snd_pcm_open函数源码分析（四)
alsa源码分析
阅读更多2024-11-18
算法日记 26-27day 贪心算法
贪心算法
阅读更多2024-11-18

list容器

1.介绍（cv的，网上太多了）

2.使用

2.1构造函数

2.2迭代器

begin(),end(),rbegin(),rend(),cbegin(),cend(),crbegin(),crend()

遍历方式

2.3 容量

empty()

size()

max_size()

2.4元素遍历

front()

back()

2.5修改

assign()

push_front()

pop_front()

push_back()

pop_back()

insert()

erase()

swap()

resize()

clear()

2.6操作

reverse()

sort()

merge()

unique()

remove()

remove_if()

splice()

3.模拟

相关文章