C++ list的基本使用

目录

1.list简要介绍

2. list的构造

3. list中迭代器的使用

 (1). 双向迭代器与随机访问迭代器使用区别

4.判空、获取元素个数

 5. list头、尾元素的访问

6. 插入与删除操作

 (1). 头插头删，尾插尾删

(2). 插入，删除与清空

 (3). 交换

 7. list容器迭代器失效问题

---

1.list简要介绍

在C++标准库中list是基于双向链表实现的

 

 其特点主要包括

1. 双向链表结构，插入和删除元素时非常高效，因为不需要移动元素
2. 内存分配并不是连续的，和vector不同
3. 不支持随机访问的迭代器，提供的迭代器是双向迭代器(下文会详细介绍)
4. 可以动态增容，不受容量的限制
5. 由于每个元素都需要额外的内存来存储指向相邻元素的指针(或引用)，因此list可能会比基于数组的容器(如vector)使用更多的内存

2. list的构造

构造函数	接口说明
list(size_type  n, const  val_type&  val = value_type() )	构造的list中包含n个值为val的元素
list()	构造空的list
list(const  list&  x)	拷贝构造函数
list(InputIterator first,InputIterator  last)	用[first,last)区间中的元素构造list (左闭右开)

演示代码如下

#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);for (auto ll : l1){cout << ll << "  ";}cout << endl;list<int> l2(10, 3);for (auto ll : l2){cout << ll << "  ";}cout << endl;list<int> l3(l1);for (auto ll : l3){cout << ll << "  ";}cout << endl;list<int> l4(l2.begin(), l2.end());for (auto ll : l4){cout << ll << "  ";}cout << endl;}

3. list中迭代器的使用

函数	接口说明
begin+end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一位的reverse_iterator，即begin位置

 演示代码如下

#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);l1.push_back(1);list<int>::iterator il = l1.begin();while (il != l1.end()){cout << *il << "  ";il++;}cout << endl;list<int>::reverse_iterator it = l1.rbegin();while(it!=l1.rend()){cout << *it << "  ";it++;}cout << endl;}

输出结果为

 这里的迭代器是双向迭代器（Bidirectional Iterator），vector与string等支持随机访问迭代器（Random Access Iterator）存在差异

 (1). 双向迭代器与随机访问迭代器使用区别

双向迭代器可以使用++向前，使用--向后移动。支持基本迭代器操作如解引用( * )、自增自减(++ , --)和比较操作( == , != )

随机访问迭代器除了支持双向迭代器所有的功能外，还提供了快速随机访问容器中任意元素的能力。这意味着它支持指针算数运算，(假设v是一个对象)如v.begin()+n (向前移动n个位置)，v.end()-n (向后移动n个位置)，以及比较操作(< , <= , > , >=)

4.判空、获取元素个数

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

简单演示代码如下

#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);list<int> l2;cout << "l1元素个数为：" << l1.size() << endl;cout << "l2元素个数为：" << l2.size() << endl;cout << "l1是否为空?" << endl;if (l1.empty())cout << "yes" << endl;elsecout << "no" << endl;cout << "l2是否为空?" << endl;if (l2.empty())cout << "yes" << endl;elsecout << "no" << endl;l1.push_back(1);l2.push_back(66);cout << "l1元素个数为：" << l1.size() << endl;cout << "l2元素个数为：" << l2.size() << endl;cout << "l1是否为空?" << endl;if (l1.empty())cout << "yes" << endl;elsecout << "no" << endl;cout << "l2是否为空?" << endl;if (l2.empty())cout << "yes" << endl;elsecout << "no" << endl;}

输出结果如下

 5. list头、尾元素的访问

函数声明	接口说明
front	返回list第一个节点中值的引用
back	返回list的最后一个节点中值的引用

演示代码如下

#include<iostream>
#include<list>using namespace std;int main()
{list<int> l1(10);list<int> l2;cout<<l1.front()<<endl;int& f = l1.front();//可用引用接收l1.push_front(4);cout << f<<endl;cout << l1.front() << endl;cout << l1.back() << endl;int& t = l1.back();cout << t << endl;l1.push_back(6);cout << l1.back();//cout << l2.front();//cout << l2.back();return 0;
}

特别注意如果list为空使用会报错

6. 插入与删除操作

函数	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list 中的指定位置pos插入值为val的元素
erase	删除list指定位置pos的元素
clear	清空list中的有效元素
swap	交换两个list中的元素

 (1). 头插头删，尾插尾删

代码简单演示

#include<iostream>
#include<list>using namespace std;int main()
{list<int> ll;ll.push_back(8);ll.push_back(5);ll.push_back(2);ll.push_front(9);ll.push_front(6);ll.push_front(3);for (auto l : ll){cout << l << "  ";}cout << endl;ll.pop_back();ll.pop_front();for (auto l : ll){cout << l << "  ";}cout << endl;
}

(2). 插入，删除与清空

演示代码如下

#include<iostream>
#include<list>
#include<vector>
using namespace std;template<class T>
void print_list(list<T> ll)
{for (auto l : ll){cout << l << "  ";}cout << endl;
}
int main()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;print_list(L);
// 在pos前插入值为4的元素L.insert(pos, 4);print_list(L);
// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);print_list(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());print_list(L);// 删除pos位置上的元素L.erase(pos);print_list(L);list<int> LL(L);
// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());print_list(L);cout << "LL元素个数为:  " << LL.size() << endl;LL.clear();cout << "LL元素个数为:  " << LL.size() << endl;}

输出结果为

 (3). 交换

演示代码如下

#include<iostream>
#include<list>
#include<vector>
using namespace std;template<class T>
void print_list(list<T> ll)
{for (auto l : ll){cout << l << "  ";}cout << endl;
}
int main()
{int array1[] = { 1, 2, 3 };list<int> L1(array1, array1 + sizeof(array1) / sizeof(array1[0]));list<int> L2;cout << "L1: ";print_list(L1);cout << "L2: ";print_list(L2);L1.swap(L2);cout << "L1: ";print_list(L1);cout << "L2: ";print_list(L2);return 0;
}

输出结果如下

 list提供的swap成员函数优化了交换操作，使其可以在常数时间内完成std::swap 也可以交换list对象，但不如list自己的成员函数，实际上它只用交换两个list对象的头指针和尾指针时间复杂度通常为O(1)，不涉及元素的实际移动或复制

 7. list容器迭代器失效问题

迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为list底层结构为带头节点的双向循环链表，所以在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响(与vector不同，list每个节点存储不是连续的)。

 eraser比较容易触发

#include<iostream>
#include<list>
using namespace std;
int main()
{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()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给//其赋值cout << *it << "  ";l.erase(it);++it;}return 0;
}

输出结果如下

 在执行删除后迭代器就失效了

解决方法1

#include<iostream>
#include<list>
using namespace std;
int main()
{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()){cout << *it << "  ";l.erase(it++); }return 0;
}

利用后置++先使用，在迭代器失效前提前改变了迭代器的值

解决方法2

	while (it != l.end()){cout << *it << "  ";it=l.erase(it); // it = l.erase(it);}

使用it来接收删除数据后的返回的迭代器

8. list与vector的区别

	vector	list
底层结构	动态顺序表，一段连续空间	带头节点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N),插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行了封装
迭代器失效	在插入元素时，要给所有迭代器重新赋值，因为插入元素有可能会导致重新扩容，导致原来迭代器失效。删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效需要重新赋值，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除的效率	大量插入和删除操作，不关心随机访问

---

这篇就到这里啦，感谢阅读

(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤