STL(三)(list篇)

本文介绍: erase():从链表中移除指定位置的一个或多个元素。push_front():将元素插入到链表的开头。.begin():返回指向链表第一个元素的迭代器。end():返回指向链表末尾的下一个位置的迭代器。push_back():将元素插入到链表的末尾。pop_front():移除链表开头的元素。front():返回链表中第一个元素的引用。back():返回链表中最后一个元素的引用。pop_back():移除链表末尾的元素。clear():清空链表中的所有元素。size():返回链表中元素的个数。

1.list的定义和结构

list的使用频率不高,在做题时极少遇到需要使用list的情景
list是一种双向链表容器,它是标准模板库(STL)提供的一种序列容器
list容器以节点(node)的形式存储元素,并使用指针将这些节点链接在一起,形成一个链表结构

list容器的定义和结构如下:

template<class T,class Allocator std::allocator<T>> 
class list;

list容器模板接受两个参数：

T:指定容器中存储的元素类型。
Allocator(可选):指定用于分配内存的分配器类型,默认为std::allocator<T>

list容器的特点包括:

双向性:每个节点都包含指向前一个节点和后一个节点的指针,因此可以在常数时间内在链表中的任意位置进行插入,删除和访问操作
动态大小:链表的大小可以根据需要动态扩展或收缩,不需要预先指定容器的大小
不连续存储:链表中的节点可以在内存中的任意位置分布,不要求连续存健因此插入和删除操作不会导致元素的移动
list容器提供了一系列成员函数和迭代器来操作和访问链表中的元素,包括插入、删除、访问、反转等操作(可以使用迭代器来遍历链表中的元素)

示例:list容器

#include<iostream>
#include<list>
int main(){
	std::list<int> myList;
	//在链表尾部插入元素
	myList.push_back(1); 
	myList.push_back(2); 
	myList.push_back(3); 
	//在链表头部插入元素
	myList.push_back(0); 
	//遍历链表并输出元素
	for(int num:myList){
		std::cout<<num<<" ";
	} 
	std::cout<<"n";
	return 0;
}

在上述示例中,我们首先创建了一个list容器myList,然后使用push_back()和push_front()函数分别在链表尾部和头部插入元素,最后,使用范围基于范围的for循环遍历链表并输出元素
### 需要注意的是,由于list是双向链表,因此插入和删除操作的时间复杂度是常量时间0(1),但访问和查找操作的时间复杂度是线性时间0(n)其中n是链表的大小,因此,如果需要频繁进行随机访问操作,可能更适合使用支持随机访问的容器,如vector或deque

2.list的常用函数

### list容器提供了多个常用的成员函数来操作和访问链表中的元素

以下是一些常用的list()函数的解释:

1.push_back():将元素插入到链表的末尾
2.push_front():将元素插入到链表的开头
3.pop_back():移除链表末尾的元素
4.pop_front():移除链表开头的元素
5.size():返回链表中元素的个数
6.empty():检查链表是否为空
7.clear():清空链表中的所有元素
8.front():返回链表中第一个元素的引用
9.back():返回链表中最后一个元素的引用
10.begin():返回指向链表第一个元素的迭代器
11.end():返回指向链表末尾的下一个位置的迭代器
12.insert():在指定位置之前插入一个或多个元素
13.erase():从链表中移除指定位置的一个或多个元素

3.代码示例:

#include<bits/stdc++.h>
using namespace std;
int main(){
	//创建一个list<int>对象myList
	list<int> myList;
	
	//向myList尾部加元素 
	for(int i=1;i<=5;++i){
		myList.push_back(i);
	} 
	
	//从头到尾输出myList中的元素
	for(const auto&i:myList){
		cout<<i<<" ";
	} 
	cout<<"n";
	
	//将myList中的元素反转
	reverse(myList.begin(),myList.end());
	
	for(const auto&i:myList){
		cout<<i<<" ";
	} 
	cout<<"n";
	
	//在第一个元素的后一个位置上加上元素0
	myList.insert(++myList.begin(),0);
	for(const auto&i:myList){
		cout<<i<<" ";
	} 
	cout<<"n";
	
	myList.erase(++ ++myList.begin(),--myList.end());
	
	//输出myList的大小
	cout<<"链表的大小为:"<<myList.size()<<" ";
	cout<<"n"; 
	return 0;
}

这里的++begin()可以得到第二个位置的迭代器,它并不会真正的++,它得到的是一个拷贝过来的结果
### 注意:如果要使用myList.size()-1时,一定要转换为unsigned int类型

输出: