当前位置： 首页 > article >正文

C++系列-STL容器之list

article 2025/3/6 21:14:21

STL容器之list

  • list容器的基本结构
  • list容器的特点
    • list容器的优点
    • list容器的缺点
  • list容器的构造函数
  • list容器的常用接口
    • list赋值操作
    • list大小及空否
    • list访问
    • list迭代器相关
    • list增删查改
      • push and pop
      • insert
      • 其它

寄扬州韩绰判官
杜牧〔唐代〕

青山隐隐水迢迢，秋尽江南草未凋。
二十四桥明月夜，玉人何处教吹箫？

list容器的基本结构

list容器的内部结构是双向循环链表，主要由一系列的节点组成，每个节点包含3个部分

  • 数据域：存储实际的元素值。
  • 前向指针：指向链表中的前一个节点。
  • 后向指针：指向链表中的后一个节点。
  • 整个list通过这些节点的指针指向互相连接，形成一个有序的序列。头节点不放实际数据，只放下一个节点的指针。
  • 每个节点中的previous指针指向前一个节点，next指针指向后一个节点。最后一个节点的next指向头节点，头节点的previous指针最后一个节点。
    在这里插入图片描述

list容器的特点

list容器的优点

  • 采用动态存储分配，内存分配更灵活，不会造成内存的浪费和溢出。
  • 执行插入和删除不需要移动大量的元素，只需要修改节点中的指针，在频繁插入和删除的情况下，高效。
  • 提供反向迭代器，可以方便地从后向前遍历list。
  • 插入操作不会造成原有的list迭代器失效，只是修改了节点中的指针指向关系。
  • 删除操作中指向被删除节点的迭代器会失效，其余的迭代器并不失效。

list容器的缺点

  • 空间(指针域占用空间)和时间(遍历)额外耗费较大，不如vector。
  • 不能支持迭代器任意位置，迭代器计算只支持++或者–。

list容器的构造函数

构造函数说明
list (n, elem)创建的对象中含有n个elem
list{}创建的对象中的内容是花括号中的元素
list ()默认构造，空list
list (const list& x)拷贝构造
list (InputIterator first, InputIterator last)用迭代区间 [first, last) 区间中的元素构造list
code:
#include <iostream>
#include <list>
#include <vector>
using namespace std;

template<typename T>
void print_list(const list<T>& lst)
{
	for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)  // 不能<哪个迭代器
	{
		cout << *it << " ";	
	}
	cout << endl;
}

void test01()
{
	list<int> lst1(5, 10);		// list (n, elem), 创建的对象中含有n个elem 
	cout << "---------- lst1 ----------" << lst1.size() << endl;
	cout << "lst1.size(): " << lst1.size() << endl;
	print_list(lst1);

	list<int> lst2{1, 2, 3};	// list{}, 利用{}创建对象
	cout << "---------- lst2 ----------" << lst1.size() << endl;
	print_list(lst2);

	list<int> lst3(lst2);		// 拷贝构造
	cout << "---------- lst3 ----------" << lst1.size() << endl;
	print_list(lst3);

	list<int> lst4;				// 默认构造
	lst4.push_back(666);
	lst4.push_back(888);
	lst4.push_front(1);
	cout << "---------- lst4 ----------" << lst4.size() << endl;
	print_list(lst4);

	vector<int> v1{ 11, 22, 33, 44, 55 };
	list<int> lst5(v1.begin(), v1.begin() + 3);	// 迭代区间构造
	cout << "---------- lst5 ----------" << lst5.size() << endl;
	print_list(lst5);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- lst1 ----------5
lst1.size(): 5
10 10 10 10 10
---------- lst2 ----------5
1 2 3
---------- lst3 ----------5
1 2 3
---------- lst4 ----------3
1 666 888
---------- lst5 ----------3
11 22 33

list容器的常用接口

list赋值操作

形式说明
=重载lst2=lst1
assign({})用初始化列表中的元素替换容器中原有的内容
assign(n elem)用n个elem替换容器中原有的内容
assign(iterator first, iterator last)用[first, last)前闭后开区间的元素替换容器中原有的内容
code:
#include <iostream>
#include <list>
#include <vector>
using namespace std;

template<typename T>
void print_list(const list<T>& lst)
{
	for (typename list<T>::const_iterator it = lst.begin(); it != lst.end(); it++)
	{
		cout << *it << " ";	// 返回第一个元素
	}
	cout << endl;
}
// 在这里存在模板的嵌套，list<T>::const_iterator这个类型就是list模板中的类型，而且嵌套在了模板函数func当中，
// 当实例化func时，vector<T>变成了vector<int>，但是这并不意味着vector已经被实例化了，也就是说当编译器解析
// func时，尚未清楚list到底是什么东西，那么当然也就无法确认list<T>::const_iterator是什么东西了。它可能是
// 一个类型，也可能是static成员。这就会导致歧义出现，编译器无法判断，因此解决方法就是，在嵌套从属类型前面
// 加上typename，告诉编译器这就是一个类型，于是编译器就不会爆出语法错误了。

void test01()
{
	list<int> lst1(5, 10);			// list (n, elem)， 创建的对象中含有n个elem 
	cout << "---------- lst1 ----------" << lst1.size() << endl;
	print_list<int>(lst1);

	list<int> lst2 = lst1;			// =重载
	cout << "---------- lst2 ----------" << lst2.size() << endl;
	print_list(lst2);				// 函数模板自动类型推导

	list<int> lst3;
	lst3.assign(5, 666);			// assign(n, elem)
	cout << "---------- lst3 ----------" << lst3.size() << endl;
	print_list(lst3);
	
	list<char> lst4;				// assign{初始化列表}
	lst4.assign({'a', 'b', 'c'});
	cout << "---------- lst4 ----------" << lst4.size() << endl;
	print_list<char>(lst4);

	vector<int> vct1{100, 200, 300, 400};
	list<int> lst5;					
	lst5.assign(vct1.begin(), vct1.begin()+2);	// assign(iterator first, iterator last)
	cout << "---------- lst5 ----------" << lst5.size() << endl;
	print_list(lst5);				// 函数模板自动类型推导
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- lst1 ----------5
10 10 10 10 10
---------- lst2 ----------5
10 10 10 10 10
---------- lst3 ----------5
666 666 666 666 666
---------- lst4 ----------3
a b c
---------- lst5 ----------2
100 200

list大小及空否

接口函数说明
empty()检测list是否为空，是返回true，否则返回false
size()返回list中有效节点的个数
resize(num)重新指定容器的长度为num，若容器变长，则以默认值填充新位置，若容器变短，则末尾超出原容器长度的元素被删除
resize(num，elem)重新指定容器的长度为num，若容器变长，则以elem填充新位置，若容器变短，则末尾超出原容器长度的元素被删除

list访问

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

list迭代器相关

接口函数说明
begin()返回指向列表第一个元素的迭代器
end()返回指向列表尾端元素的下一个的迭代器
rbegin()返回指向从反向数的第一个元素的迭代器
rend()返回指向从反向数的尾端元素的下一个的迭代器
code:
#include <iostream>
#include <list>
using namespace std;

template<typename T>
void print_list(const list<T>& lst)
{
	for (typename list<T>::const_iterator it = lst.begin(); it != lst.end(); it++)	// 在模板嵌套中，这里要加上typename 表明T是一个模板参数
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	list<int> lst1;			
	if (lst1.empty())			// 判断是否为空
	{
		cout << "lst1 is empty!" << endl;
	}
	cout << "---------- lst1, lst1.size() ----------" << lst1.size() << endl;	// 有效节点个数
	lst1.assign({ 1,2,3,4 });								// assign初始化赋值
	cout << "lst1.assign({ 1,2,3,4 })" << endl;
	print_list<int>(lst1);
	cout << "lst1.front(): " << lst1.front() << endl;		// front() 头元素
	cout << "lst1.back(): " << lst1.back() << endl;			// back() 尾元素

	cout << "* lst1.begin(): " << *lst1.begin() << endl;	// lst1.begin()迭代器指向第一个元素
	cout << "* (--lst1.end()): " << *(--lst1.end()) << endl;// lst1.end()迭代器指向末尾元素的下一个,--lst1.end()指向末尾元素
	cout << "* lst1.rbegin(): " << *lst1.rbegin() << endl;
	cout << "*(--lst1.rend()): " << *(--lst1.rend()) << endl;

	// resize(num), 添加默认元素
	lst1.resize(8);
	cout << "---------- lst1.resize(8), lst1.size()  ----------" << lst1.size() << endl;
	print_list<int>(lst1);

	//resize(num，elem), 添加elem元素
	lst1.resize(10, 666);
	cout << "---------- lst1.resize(10, 666)), lst1.size()  ----------" << lst1.size() << endl;
	print_list<int>(lst1);

	//resize(num，elem), 添加elem元素
	lst1.resize(3);
	cout << "---------- lst1.resize(3), lst1.size()  ----------" << lst1.size() << endl;
	print_list<int>(lst1);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
lst1 is empty!
---------- lst1, lst1.size() ----------0
lst1.assign({ 1,2,3,4 })
1 2 3 4
lst1.front(): 1
lst1.back(): 4
* lst1.begin(): 1
* (--lst1.end()): 4
* lst1.rbegin(): 4
*(--lst1.rend()): 1
---------- lst1.resize(8), lst1.size()  ----------8
1 2 3 4 0 0 0 0
---------- lst1.resize(10, 666)), lst1.size()  ----------10
1 2 3 4 0 0 0 0 666 666
---------- lst1.resize(3), lst1.size()  ----------3
1 2 3

list增删查改

push and pop

接口函数说明
push_front(const T &val)在list首元素前插入值为val的元素
pop_front()删除list中第一个元素
push_back(const T &val)在list尾部插入值为val的元素
pop_back()删除list中最后一个元素

insert

接口函数说明
insert(iterator pos, const T &val)在list position 位置前插入值为val的元素
insert(iterator pos, num, const T &val)在list position 位置前插入值为num个值为val的元素
insert(iterator pos, begin, end)在list position 位置前插入值为num个值为val的元素
code:
#include <iostream>
#include <list>
#include <vector>
using namespace std;

template<typename T>
void print_list(const list<T>& lst)
{
	for (typename list<T>::const_iterator it = lst.begin(); it != lst.end(); it++)
	{
		cout << *it << " ";	// 返回第一个元素
	}
	cout << endl;
}

void test01()
{
	// push pop举例
	list<string> lst1;
	lst1.push_back("push_back");
	cout << "---------- push_back ---------- " << lst1.size() << endl;
	print_list(lst1);

	lst1.push_front("push_front");
	cout << "---------- push_front ---------- " << lst1.size() << endl;
	print_list(lst1);

	lst1.pop_back();
	cout << "---------- pop_back ---------- " << lst1.size() << endl;
	print_list(lst1);

	lst1.pop_front();
	cout << "---------- pop_front, lst1.size() ---------- " << lst1.size() << endl;
	print_list(lst1);

	// insert举例
	list<int> lst2{1, 2, 3, 4, 5, 6};
	lst2.insert(++lst2.begin(), 222);		// insert(iterator pos, const T &val)
	cout << "---------- lst2.insert(++lst2.begin(), 222), lst2.size() ---------- " << lst2.size() << endl;
	print_list(lst2);

	lst2.insert(--lst2.end(), 3, 666);		// insert(iterator pos, num, const T &val)
	cout << "---------- lst2.insert(--lst2.end(), 3, 666), lst2.size() ---------- " << lst2.size() << endl;
	print_list(lst2);

	vector<int> vec1{11, 22, 33, 44};
	lst2.insert(lst2.end(), vec1.begin(), vec1.begin() + 3);		// insert(iterator pos, begin, end)
	cout << "---------- lst2.insert(lst2.end(), vec1.begin(), vec1.begin()+3), lst2.size() ---------- " << lst2.size() << endl;
	print_list(lst2);

	// erase举例
	lst2.erase(++lst2.begin());		// erase(iterator pos)
	cout << "---------- lst2.erase(++lst2.begin()), lst2.size() ---------- " << lst2.size() << endl;
	print_list(lst2);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- push_back ---------- 1
push_back
---------- push_front ---------- 2
push_front push_back
---------- pop_back ---------- 1
push_front
---------- pop_front, lst1.size() ---------- 0

---------- lst2.insert(++lst2.begin(), 222), lst2.size() ---------- 7
1 222 2 3 4 5 6
---------- lst2.insert(--lst2.end(), 3, 666), lst2.size() ---------- 10
1 222 2 3 4 5 666 666 666 6
---------- lst2.insert(lst2.end(), vec1.begin(), vec1.begin()+3), lst2.size() ---------- 13
1 222 2 3 4 5 666 666 666 6 11 22 33
---------- lst2.erase(++lst2.begin()), lst2.size() ---------- 12
1 2 3 4 5 666 666 666 6 11 22 33

其它

接口函数说明
erase(iterator pos)删除list position位置的元素
lst1.swap(lst2)交换两个list中的元素
clear()清空list中的有效元素
remove(const T &val)删除列表中所有指为val的元素
reverse()反转列表
sort()对列表排序
code:
#include <iostream>
#include <list>
using namespace std;

template<typename T>
void print_list(const list<T>& lst)
{
	for (typename list<T>::const_iterator it = lst.begin(); it != lst.end(); it++)
	{
		cout << *it << " ";	
	}
	cout << endl;
}

void test01()
{
	list<int> lst1{1,2,3,4,5,6};
	list<int> lst2{99, 88, 77, 66};

	// swap 举例
	cout << "---------- before swap,lst1, lst2 ---------- " << endl;
	print_list(lst1);
	print_list(lst2);
	cout << "---------- after swap,lst1, lst2 ---------- " << endl;
	lst1.swap(lst2);
	print_list(lst1);
	print_list(lst2);

	// remove举例
	cout << "---------- lst2.insert(--(--lst2.end()), 3, 666) ---------- " << endl;
	lst2.insert(--(--lst2.end()), 3, 666);
	print_list(lst2);
	
	lst2.remove(666);
	cout << "---------- lst2.remove(666), lst2.size() ---------- " << lst2.size() << endl;
	print_list(lst2);

	// reverse举例
	lst2.reverse();
	cout << "---------- lst2.reverse() ---------- " << endl;
	print_list(lst2);

	// clear举例
	lst2.clear();
	cout << "---------- lst2.clear(), lst2.size() ---------- " << lst2.size() << endl;
	print_list(lst2);

	// sort举例
	list<int> lst4{23, 1, 56, 78, 44, 35, 99, 76};
	cout << "---------- before sort, lst4 ---------- " << endl;
	print_list(lst4);
	cout << "---------- after sort, lst4 ---------- " << endl;
	lst4.sort();
	print_list(lst4);
}
int main()
{
	test01();
	system("pause");
	return 0;
}

result:
---------- push_back ---------- 1
push_back
---------- push_front ---------- 2
push_front push_back
---------- pop_back ---------- 1
push_front
---------- pop_front, lst1.size() ---------- 0

---------- lst2.insert(++lst2.begin(), 222), lst2.size() ---------- 7
1 222 2 3 4 5 6
---------- lst2.insert(--lst2.end(), 3, 666), lst2.size() ---------- 10
1 222 2 3 4 5 666 666 666 6
---------- lst2.insert(lst2.end(), vec1.begin(), vec1.begin()+3), lst2.size() ---------- 13
1 222 2 3 4 5 666 666 666 6 11 22 33
---------- lst2.erase(++lst2.begin()), lst2.size() ---------- 12
1 2 3 4 5 666 666 666 6 11 22 33

http://www.kler.cn/a/286090.html

相关文章：

  • docker 镜像导出命令（支持所有镜像导出为独立的包）
  • springboot 接口接收参数的注解介绍（@RequestParam，@PathVariable，@RequestBody 等）
  • Golang | Leetcode Golang题解之第377题组合总和IV
  • 欧科云链： Web3浪潮下合规是“必选项”， 技术创新成发展重点
  • 计算机毕业设计推荐-基于python的公司员工考勤管理系统
  • 【区块链 + 司法存证】链节区块链数字卷宗管理系统 | FISCO BCOS应用案例
  • 金融科技初创企业建设指南
  • 常使用的前端构建优化策略
  • phpstudy怎么用
  • 某东协议算法剖析 - H5st4.7.4
  • 初始MYSQL数据库（1）——创建、删除数据库和数据表的相关操作
  • Windows下Nacos安装与配置
  • HarmonyOS开发实战（ Beta5版）小程序场景性能优化开发指导
  • python 实现一个简单的网页爬虫程序
  • 深度学习项目实践——QQ聊天机器人（transformer）（三）功能实现的方法——NoneBot2插件结构与编写
  • 怎样通过bs4找出程序中 标签＜div class=“List2“＞的内容？
  • 网络各层的安全实例：从物理层到应用层的保护
  • CPU、MPU、MCU、SOC分别是什么？
  • 代码随想录算法训练营第32天 | 509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯
  • 银行卡四要素验证如何用C#调用