我要评论目录
⑦ reverse()——将该链表的所有元素的顺序反转 【c++11】
一、前言
二、 什么是 list ?
💦 list 的存储结构
💦 list 容器的优点
- 高效的插入和删除：由于std::list是基于带头双向循环链表实现的，插入和删除操作在任意位置都具有常数时间复杂度o(1)，不需要移动其他元素。这使得std::list在需要频繁插入和删除元素的场景下非常高效。
- 稳定的迭代器：在std::list中进行插入和删除操作不会使得迭代器失效。这意味着在插入或删除元素后，仍然可以继续使用之前获取的迭代器进行遍历和操作。
- 动态内存管理：std::list可以动态调整大小，根据需要分配和释放内存。这使得std::list能够有效地处理大量元素的情况，而不会浪费过多的内存空间。
💦 list 容器的缺点
- 低效的随机访问：由于std::list的存储结构是带头双向循环链表，访问元素时需要从头或尾开始遍历链表，因此在列表中进行随机访问的效率较低。获取特定位置的元素需要遍历链表，时间复杂度为o(n)，其中n是元素的总数量。
- 占用额外内存：相较于其他容器，std::list在存储上需要额外的指针来维护链表结构，因此在存储大量元素时，它可能占用更多的内存空间。
- 迭代器不支持指针算术：std::list的迭代器不支持指针算术运算，无法像指针那样直接进行加减操作，这限制了一些操作的灵活性。
头文件：
list是c++ 标准模板库的一部分，因此，想要使用list，需要在程序中包含头文件 list
#include<list>
三、list 容器的定义
四、list 容器常用接口的使用
💦list 的常见构造（初始化）
| 接口名称 | 接口说明 |
| list() （⭐） | 构造空的list |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list (const list& x)（⭐） | 拷贝构造函数 |
| list (inputiterator first, inputiterator last | 用[first, last)区间中的元素构造list |
注意： ⭐表示重点掌握
💦list 的遍历及迭代器的操作
| 接口名称 | 接口说明 |
| 迭代器（⭐） | begin() + end() 或者 rbegin() + rend() |
| 范围for | c++11支持更简单的for的新遍历方式（底层还是借用迭代器实现） |
① 迭代器
| 接口名称 | 接口说明 |
| begin()（⭐） | 返回第一个元素的迭代器 |
| end()（⭐） | 返回最后一个元素下一个位置的迭代器 |
| rbegin() | 返回最后一个元素的迭代器 |
| rend() | 返回第一个元素的前一个位置额迭代器 |
② 范围for
💦list 容器的常见容量操作
| 接口名称 | 接口说明 |
| size | 返回容器中有效元素个数 |
| resize（⭐） | 调整容器的有效元素大小(size) |
| empty | 判断容器是否为空 |
| clear | 用于清空容器,清空后容器的size为0, 但是头结点(哨兵位)不会被清除 |
① size
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
cout << lt.size() << endl; //4
return 0;
}
② resize
resize()方法有两种重载形式：
- void resize(size_type count, const t& value = t()):
这个重载会将列表的大小调整为count。如果count大于当前列表的大小，则在列表末尾插入足够数量的值为value的元素。如果count小于当前列表的大小，则删除超出count的元素。
- void resize(size_type count):
这个重载会将列表的大小调整为count。如果count大于当前列表的大小，则在列表末尾插入默认构造的元素。如果count小于当前列表的大小，则删除超出count的元素。
代码示例：
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> mylist = { 1, 2 };
// 把mylist的大小设为5
mylist.resize(5);
cout << "第一次resize后list中元素为：";
for (auto a : mylist) {
cout << a << " ";
}
cout << endl;
// 把mylist的大小设为1
mylist.resize(1);
cout << "第二次resize后list中元素为：";
for (auto a : mylist) {
cout << a << " ";
}
cout << endl;
// 把list大小设为4，不足部分填充5
mylist.resize(4, 5);
cout << "第三次resize后list中元素为：";
for (auto a : mylist) {
cout << a << " ";
}
cout << endl;
}效果展示：
③ empty
💻示例代码💻
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
int main () {
list<int> mylist1;
list<int> mylist2 = {1, 2};
cout<< "mylist1是否为空？"<< mylist1.empty() << endl;
cout<< "mylist2是否为空？"<< mylist2.empty() << endl;
}
📄效果展示📄
④ clear
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> lt(5, 2);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl; //2 2 2 2 2
cout << lt.size() << endl; //5
lt.clear(); //清空容器
for (auto e : lt)
{
cout << e << " ";
}
cout << endl; //(无数据)
cout << lt.size() << endl; //0
return 0;
}
💦list 容量的常见访问操作
① front()——访问list头元素
💻示例代码💻
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
int main() {
list<int> mylist {1, 2, 3, 4, 5, 6, 7, 8};
cout<< "初始化后的mylist为：";
for (auto num : mylist) {
cout<< num<< " ";
}
int front = mylist.front(); // 1
cout<< "\nmylist的头元素为："<< front;
}
② back()——访问list尾元素
💻示例代码💻
#include<iostream>
#include<list>
using std::cout;
using std::endl;
using std::list;
int main() {
list<int> mylist {1, 2, 3, 4, 5, 6, 7, 8};
cout<< "初始化后的mylist为：";
for (auto num : mylist) {
cout<< num<< " ";
}
int front = mylist.front(); // 8
cout<< "\nmylist的头元素为："<< front;
}
💦list 容器的常见修改操作
| 接口名称 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert（⭐） | 在list position 位置中插入值为val的元素 |
| erase（⭐） | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
① push_back()——添加元素（list尾部)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// 在list尾部插入一个元素8
mylist.push_back(8);
cout << "\n尾部插入一个元素后的mylist为：";
for (auto num : mylist) {
cout << num << " "; // 1 2 3 4 8
}
}
② pop_back()——移除list元素(尾部)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// 删除mydeue尾部一个元素
mylist.pop_back();
cout << "\n尾部删除一个元素后的mylist为：";
for (auto num : mylist) {
cout << num << " "; // 1 2 3
}
}
③ pop_front()——删除list元素(头部)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// 删除mydeue头部一个元素
mylist.pop_front();
cout << "\n头部删除一个元素后的mylist为：";
for (auto num : mylist) {
cout << num << " "; // 2 3 4
}
}
④ push_front()——添加元素（list头部)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// 在list头部插入一个元素8
mylist.push_front(8);
cout << "\n头部插入一个元素后的mylist为：";
for (auto num : mylist) {
cout << num << " "; // 8 1 2 3 4
}
}
⑤ insert()——添加元素（任意位置）
用法一：list.insert(iterator,value)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// it指向mylist的第二个元素
list<int>::iterator it = mylist.begin() + 1;
// 使用insert添加一个元素
list<int>::iterator itnew = mylist.insert(it, 10);
cout << "\n返回的迭代器指向的元素为" << *itnew;
cout << "\ninsert添加一个元素后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
}
📄输出📄
用法二：list.insert(iterator,num,value)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// it指向mylist的第二个元素
list<int>::iterator it = mylist.begin() + 1;
// 使用insert添加2个元素，value为20
mylist.insert(it, 2, 20);
cout << "\n使用insert插入元素后：";
for (auto num : mylist) {
cout << num << " ";
}
}
📄输出📄
用法三：insert(iterator, iterator1, iterator2)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// it指向mylist的第二个元素
list<int>::iterator it = mylist.begin() + 1;
// 定义一个辅助list
list<int> list2{10, 20, 30};
// it1指向list2的第一个元素
list<int>::iterator it1 = list2.begin();
// it2指向list2的最后一个元素后一个位置
list<int>::iterator it2 = list2.end();
// 使用insert在2之前添加[it1,it2)之间的元素
mylist.insert(it, it1, it2);
cout << "\n使用insert插入元素后：";
for (auto num : mylist) {
cout << num << " ";
}
}
📄输出📄
⑥ erase()——删除元素（任意位置）
用法一：list.erase(iterator)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// it指向mylist的第二个元素
list<int>::iterator it = mylist.begin() + 1;
// 删除it指向的元素，即2，并返回一个迭代器指向2之后的元素
list<int>::iterator itnew = mylist.erase(it);
cout << "\n删除元素后返回的迭代器itnew指向的元素为：" << *itnew;
cout << "\n使用erase删除元素后：";
for (auto num : mylist) {
cout << num << " ";
}
}
📄输出📄
用法二：list.erase(iterator1,iterator2)
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist{1, 2, 3, 4};
cout << "初始化后的mylist为：";
for (auto num : mylist) {
cout << num << " ";
}
// it1指向mylist的第二个元素
list<int>::iterator it1 = mylist.begin() + 1;
// it2指向mylist的最后一个元素后一个位置
list<int>::iterator it2 = mylist.end();
// 删除[it1,it2)之间的元素,即删除2，3，4
mylist.erase(it1, it2);
cout << "\n使用erase删除元素后：";
for (auto num : mylist) {
cout << num << " ";
}
}
📄输出📄
⑦ swap()——交换元素
❤swap的作用就是交换两个list的元素❤
💻示例代码💻
#include <list>
#include <iostream>
using std::cout;
using std::list;
using std::endl;
int main() {
list<int> mylist1{1, 11, 111, 1111};
list<int> mylist2{2, 22, 222};
cout << "初始化后的mylist1为：";
for (auto num : mylist1) {
cout << num << " ";
}
cout << "\n初始化后的mylist1为：";
for (auto num : mylist2) {
cout << num << " ";
}
// 交换mylist1和mylist2的元素
mylist1.swap(mylist2);
cout << "\n使用swap交换元素后mylist1：";
for (auto num : mylist1) {
cout << num << " ";
}
cout << "\n使用swap交换元素后mylist2：";
for (auto num : mylist2) {
cout << num << " ";
}
}
📄输出📄
💦list 容器的常见操作函数
| 函数声明 | 接口说明 |
| splice | 将元素从列表转移到其它列表 |
| remove | 删除具有特定值的元素 |
| remove_if | 删除满足条件的元素 |
| unique | 删除重复值 |
| sort | 容器中的元素排序 |
| merge | 合并排序列表 |
| reverse | 反转元素的顺序 |
① splice()——从另一个list中移动元素
splice共有四种形式，分别为：
- splice(iterator_pos, otherlist) : 将otherlist中的所有元素移动到iterator_pos指向元素之前
- splice(iterator_pos, otherlist, iter1): 从 otherlist转移 iter1 指向的元素到当前list。元素被插入到 iterator_pos指向的元素之前。
- splice(iterator_pos, otherlist, iter_start, iter_end) : 从 otherlist转移范围 [iter_start, iter_end) 中的元素到 当前列表。元素被插入到 iterator_pos指向的元素之前。
注意：
💻示例代码💻
#include <iostream>
#include <list>
int main() {
std::list<int> list1 = {1, 2, 3, 4, 5};
std::list<int> list2 = {10, 20, 30};
std::list<int> list3 = {1, 2, 3, 4, 5};
std::list<int> list4 = {10, 20, 30};
std::list<int> list5 = {1, 2, 3, 4, 5};
std::list<int> list6 = {10, 20, 30};
/*
用法一 : splice(iterator_pos, otherlist)
*/
// 将list2中所有元素插入到list1的第一个位置
list1.splice(list1.begin(), list2);
// 输出结果
std::cout<< "转移list2元素到list1之后的list1: ";
for (int i : list1) {
std::cout << i << " ";
}
std::cout << std::endl;
std::cout<< "转移list2元素到list1之后的list1: ";
for (int i : list2) {
std::cout << i << " ";
}
std::cout << std::endl;
/*
用法二：splice(iterator_pos, otherlist, iter1)
*/
auto it = list3.begin();
// 将迭代器向后移动两个位置，指向第三个元素
std::advance(it, 2);
// 将list4的第一个元素(10)插入到list3的第三个位置
list3.splice(it, list4, list4.begin());
// 输出结果
std::cout<< "转移list4元素到list3之后的list3: ";
for (int i : list3) {
std::cout << i << " ";
}
std::cout << std::endl;
std::cout<< "转移list4元素到list3之后的list4: ";
for (int i : list4) {
std::cout << i << " ";
}
std::cout << std::endl;
/*
用法三：splice(iterator_pos, otherlist, iter_start, iter_end)
*/
// 将list5中第二个到第四个元素移动到list6的末尾
auto first = list5.begin();
std::advance(first, 1);
auto last = list5.begin();
std::advance(last, 4);
list6.splice(list6.end(), list5, first, last);
// 输出结果
std::cout<< "转移list5元素到list6之后的list5: ";
for (int i : list5) {
std::cout << i << " ";
}
std::cout << std::endl;
std::cout<< "转移list5元素到list6之后的list6: ";
for (int i : list6) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
📄初始化的值📄
std::list<int> list1 = {1, 2, 3, 4, 5};
std::list<int> list2 = {10, 20, 30};
std::list<int> list3 = {1, 2, 3, 4, 5};
std::list<int> list4 = {10, 20, 30};
std::list<int> list5 = {1, 2, 3, 4, 5};
std::list<int> list6 = {10, 20, 30};
📄输出📄
② remove()——移除特定值的元素
💻示例代码💻
#include <iostream>
#include <list>
int main() {
std::list<int> mylist {1, 2, 3, 4, 5};
// 移除列表中所有值为2的元素
mylist.remove(2);
std::cout << "移除之后的mylist: ";
for (const auto& element : mylist) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
📄输出📄
③ remove_if()——移除满足特定标准的元素
使用方式：remove_if(func)
💻示例代码💻
#include <iostream>
#include <list>
bool iseven(int n) {
return n % 2 == 0;
}
int main() {
std::list<int> mylist {1, 2, 3, 4, 5};
// 移除列表中所有满足 iseven 的元素（偶数）
mylist.remove_if(iseven);
std::cout << "移除之后的mylist: ";
for (const auto& element : mylist) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
📄输出📄
④ unique()——删除连续的重复元素
💻示例代码💻
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {1, 2, 2, 3, 3, 4, 5, 5, 5};
std::cout << "初始化后的list为: ";
for (auto i : mylist) {
std::cout << i << " ";
}
std::cout << std::endl;
mylist.unique();
std::cout << "执行unique后的list为: ";
for (auto i : mylist) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
📄输出📄
⑤ sort()——对元素进行排序
💻示例代码💻
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {5, 3, 2, 4, 1};
std::cout << "初始化后的list为 ";
for (auto i : mylist) {
std::cout << i << " ";
}
std::cout << std::endl;
mylist.sort();
std::cout << "排序后的list为: ";
for (auto i : mylist) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
📄输出📄
⑥ merge()——合并list
注意：merge()方法只能用于已排序的list。如果list未排序，则合并的结果将是不正确的。
💻示例代码💻
#include <iostream>
#include <list>
using namespace std;
int main() {
std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};
cout << "初始化后的list1为：";
for (auto num : list1) {
cout << num << " ";
}
std::cout << std::endl;
cout << "初始化后的list2为：";
for (auto num : list2) {
cout << num << " ";
}
std::cout << std::endl;
// 将 list2 合并到 list1 中
list1.merge(list2);
// 输出合并后的列表
cout << "合并后的list1为：";
for (const auto& element : list1) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
📄输出📄
⑦ reverse()——将该链表的所有元素的顺序反转 【c++11】
💻示例代码💻
#include <iostream>
#include <list>
int main() {
std::list<int> mylist = {1, 2, 3, 4, 5};
std::cout << "初始化list为: ";
for (const auto& element : mylist) {
std::cout << element << " ";
}
std::cout << std::endl;
mylist.reverse();
std::cout << "reversed后的list为: ";
for (const auto& element : mylist) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
📄输出📄
⑧ assign()——将值赋给容器
💻示例代码💻
#include <iostream>
#include <vector>
#include <list>
int main() {
std::list<int> mylist;
// 使用迭代器范围进行分配
std::vector<int> numbers = {1, 2, 3, 4, 5};
mylist.assign(numbers.begin(), numbers.end());
std::cout << "第一次执行assign之后的list为: ";
for (auto i : mylist) {
std::cout << i << " ";
}
std::cout << std::endl;
// 使用元素数量和值进行分配
mylist.assign(3, 100);
std::cout << "第二次执行assign之后的list为: ";
for (auto i : mylist) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
📄输出📄
五、vector 与 list 的对比
| 对比 | vector | list |
| 底层结构 | 动态顺序表，连续空间 | 带头结点的双向循环链表 |
| 访问 | 支持随机访问，首地址+下标 | 不能随机访问，可通过find查找，访问随即元素时间复杂度o(n) |
| 插入删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为o(n)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为o(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率较高，缓存利用率高。可以一次将一个数据附近的空间都加载到缓存，不用频繁地从内存读取数据 | 底层节点动态开辟，容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对指针进行了封装 |
| 迭代器失效 | 容量相关的操作都有可能导致迭代器失效，如插入引起的扩容，删除元素等 | 插入元素不会导致迭代器失效，删除节点会导致，且只影响当前迭代器，其他迭代器不受影响 |
| 使用场景 | 不关心插入和删除效率，支持随机访问 | 大量插入和删除操作，不关心随机访问的场景 |
六、共勉
以下就是我对 list 容器 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 c++ list容器的模拟实现 ，请持续关注我哦！！！
发表评论