【C++】list(上):list类的常用接口介绍

发布于:2025-03-14 ⋅ 阅读:(26) ⋅ 点赞:(0)


前言

一、list的介绍(包含list类中typedef的部分类型别名介绍)
二、list类的常用接口说明(vector类对象的 常见构造、容量操作、遍历操作 和 修改操作等接口,以及一些list特有的操作(比如 splice、merge、remove、remove_if 等)介绍)
三、list类的成员函数sort和reverse 与 算法库中sort和reverse的差异


一、list的介绍

C++中的 std::list 是标准模板库(STL)提供的双向链表容器,其接口设计专注于高效插入和删除操作。std::list 底层通常实现为一个带哨兵节点的双向循环链表,这种设计显著简化了边界条件的处理。 它的接口包括构造函数、元素访问方法、修改容器的操作、迭代器相关的函数,还有一些list特有的操作(比如 splice、merge、remove、remove_if 等)。
在这里插入图片描述

在C++标准库的 std::list 中,allocator(内存分配器)是模板的第二个参数,通常可以忽略,使用默认的即可。但在需要特殊内存管理时,可以自定义allocator,不过这种情况相对少见。
默认内存分配器已足够高效,自定义内存分配器应仅在性能分析表明有必要时才会使用,所以后续介绍list接口时,只会考虑大多数情况,忽略allocator(直接使用默认的)这个参数,简化list的使用。

list 类中typedef了很多类型别名,以下代码展示了一些常用的类型别名:

typedef T value_type;// 其中 T 是 vector 的第一个模板参数
typedef size_t size_type;
// size_t 是 C++ 标准库中定义的一个类型别名,它通常是一个无符号整数类型。其可能的定义方式如下:
// 64 位系统下: typedef unsigned long long size_t; 
// 32 位系统下: typedef unsigned int size_t; 
typedef T& reference;
typedef const T& const_reference;
typedef Allocator allocator_type;

二、list的常用接口介绍

1.list类对象的常见构造

在这里插入图片描述
忽略allocator相关参数后的简化接口:

(constructor)构造函数声明 接口说明
list () 构造空的list
list ( size_type n, const value_type& val =value_type() ) 构造的list中包含n个值为val的元素
list ( const list& x ) 拷贝构造函数
template < class InputIterator > list (InputIterator first, InputIterator last ) 用迭代器范围 [begin, end) 内的元素构造链表
list ( initializer_list< value_type > il ) 初始化列表构造(C++11新增,了解用法)

示例一:
list ( ) ;
list ( size_t n, const T& val =T() );
list ( const list& x );

#include <list>
using namespace std;

int main()
{
	// list();
	list<int> it1;// 构造空的list,size为0

	// list( size_t n, const T& val =T() );
	list<int> it2(5, 22); // 构造的list中包含5个值为22的元素

	// list( const list& x );
	list<int> it3(it2); // 用it2拷贝构造it3
	return 0;
}

在这里插入图片描述

示例二:
template < class InputIterator >
list (InputIterator first, InputIterator last );

#include <vector>
#include <list>
using namespace std;

int main()
{
	list<int> it = { 1, 2, 3, 4 }; // 初始化列表的构造方式
	list<int> it1(it.begin(), it.end());  // list的迭代器是双向迭代器

	int arr[] = { 4, 5, 6, 7, 8, 9 };
	list<int> it2(arr + 2, arr + 5); // 指针作为随机访问迭代器 

	vector<int> vec = { 10, 11, 12, 13, 14, 15 }; 
	list<int> it3(vec.begin() + 1, vec.end() - 2); // vector的迭代器是随机访问迭代器
	return 0;
}

在这里插入图片描述
示例三:
list ( initializer_list< value_type > il );

#include <list>
using namespace std;

int main()
{
	list<int> it1{ 1, 2, 3 }; // 调用初始化列表构造vector对象时要使用花括号

	list<int> it2 = { 5, 6, 7 };
	return 0;
}

在这里插入图片描述

2.list iterator 的使用

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

接口 功能
begin 获取第一个数据位置的iterator/const_iterator
end 获取最后一个数据的下一个位置的iterator/const_iterator
#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1 = { 1,3,5,7,9 };
	list<int>::iterator it1 = ls1.begin();
	// 普通list对象调用 iterator begin();
	// 返回指向list对象中第一个元素的普通迭代器,允许修改list对象中的元素
	while (it1 != ls1.end())
	{
		(*it1)++;
		cout << *it1 << ' ';
		++it1;
	}
	cout << endl;

	const list<int> ls2 = { 1,3,5,7,9 };
	list<int>::const_iterator it2 = ls2.begin();
	// const list对象调用 const_iterator begin() const;
	// 返回指向const list对象第一个元素的const迭代器,只允许读取const list对象中的元素,不能修改
	while (it2 != ls2.end())
	{
		cout << *it2 << ' ';
		++it2;
	}
	cout << endl;
	return 0;
}

在这里插入图片描述

3.list类对象的容量操作

在这里插入图片描述

接口 功能
empty 检测list是否为空,是返回true,否则返回false
size 返回list中有效节点的个数
#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "ls1的有效节点个数:" << ls1.size() << endl;
	cout << "ls1是否为空:" << ls1.empty() << endl;
	

	list<int> ls2;
	cout << "ls2的有效节点个数:" << ls2.size() << endl;
	cout << "ls2是否为空:" << ls2.empty() << endl;
	return 0;
}

在这里插入图片描述

4.list类对象的访问

在这里插入图片描述

接口 功能
front 返回list的第一个节点中值的引用
back 返回list的最后一个节点中值的引用
#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "ls1的首节点中的值:" << ls1.front() << endl;
	cout << "ls1的尾节点中的值:" << ls1.back() << endl;

	return 0;
}

在这里插入图片描述

5.list类对象的修改操作

在这里插入图片描述

5.1 push_front、push_back、insert 和 resize(插入)

接口 功能
push_front 在list首元素前插入值为val的元素
push_back 在list尾部插入值为val的元素
insert 在指定迭代器位置前插入元素,返回新插入元素的迭代器
resize 用于调整链表的大小

示例一(push_front 和 push_back的使用):

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.push_front(10);
	cout << "在list首元素前插入值为10的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.push_back(20);
	cout << "在list尾部插入值为20的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

在这里插入图片描述
示例二(insert的使用):
iterator insert (const_iterator position, const T& val);

#include <list>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	auto it = find(ls1.begin(), ls1.end(), 3); // algorithm库里的find函数
	ls1.insert(it, 100);
	cout << "在元素3位置前插入值为100的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

在这里插入图片描述
示例三(resize的使用):
void resize (size_t n, T val = T());

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.resize(3);
	cout << "把有效节点的个数缩到3个:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.resize(6, 10);
	cout << "把有效节点的个数扩到6个,并且全用元素10扩充:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

在这里插入图片描述

5.2 pop_front、pop_back、clear 和 erase(删除)

接口 功能
pop_front 删除list中第一个元素
pop_back 删除list中最后一个元素
clear 清空list中的有效元素
erase 移除 pos 处元素,返回下一元素的迭代器

示例一(pop_front、pop_back 和 clear的使用):

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5,6,7,8,9 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.pop_front();
	cout << "删除list中第一个元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.pop_back();
	cout << "删除list中最后一个元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.clear();
	cout << "清空list中的有效元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

示例二(erase的使用):
iterator erase (iterator position);

#include <list>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	auto it = find(ls1.begin(), ls1.end(), 3); // algorithm库里的find函数
	ls1.erase(it);
	cout << "移除值为3的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

在这里插入图片描述

5.3 成员函数swap

swap成员函数是用于高效交换两个list对象的内容的函数
在这里插入图片描述

#include <list>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3 };
	list<int> ls2{ 10,20,30,40 };
	ls1.swap(ls2);
	return 0;
}

在这里插入图片描述
在这里插入图片描述

6.list类对象的其它操作

在这里插入图片描述

6.1 splice

将元素从一个链表转移到另一个链表,无需拷贝或移动元素,操作高效
在这里插入图片描述

示例一(将 x 链表中 i 指向的元素转移到当前链表的 pos 位置前):
void splice (iterator position, list& x, iterator i);

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 9,5,2,7 };
	list<int> lst2 = { 5,2,0 };
	lst1.splice(--lst1.end(), lst2, lst2.begin()); 
	// 将 lst2 链表中起始位置的元素转移到当前链表的最后一个元素前
	return 0;
}

在这里插入图片描述

示例二(将 x 链表中 [first, last) 范围的元素转移到当前链表的 pos 位置前):
void splice (iterator position, list& x, iterator first, iterator last);

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 9,5,2,7 };
	list<int> lst2 = { 5,2,0 };
	lst1.splice(--lst1.end(), lst2, lst2.begin(), --lst2.end());
	// 将 lst2 链表中指定范围的元素转移到当前链表的最后一个元素前
	return 0;
}

在这里插入图片描述

示例三(将 x 链表的所有元素转移到当前链表的 pos 位置前):
void splice (iterator position, list& x);

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 9,5,2,7 };
	list<int> lst2 = { 5,2,0 };
	lst1.splice(--lst1.end(), lst2);
	// 将 lst2 链表的所有元素转移到当前链表的最后一个元素前
	return 0;
}

在这里插入图片描述

6.2 remove

删除链表中所有与给定值匹配的元素
在这里插入图片描述

#include <list>
using namespace std;

int main()
{
	list<int> lst = { 1,2,3,2,5,2 };
	lst.remove(2);
	return 0;
}

在这里插入图片描述

6.3 unique

删除有序链表中连续重复的元素,所以使用前通常需先排序
在这里插入图片描述

#include <list>
using namespace std;

int main()
{
	list<int> lst = { 1, 2, 2, 3, 3, 3, 4 };
	lst.unique(); // void unique();
	return 0;
}

在这里插入图片描述

6.4 merge

合并两个已排序的链表,合并后目标链表仍有序,原链表被清空
在这里插入图片描述

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 1, 3, 5 };
	list<int> lst2 = { 2, 4, 6 };
	lst1.merge(lst2); // 默认排升序 
	// 合并结果: lst1 {1,2,3,4,5,6}, lst2 为空

	// 自定义降序合并
	list<int> lst3 = { 5, 3, 1 };
	list<int> lst4 = { 6, 4, 2 };
	lst3.merge(lst4, greater<int>()); // 传 greater<int>() 仿函数自定义降序排序
	// 合并结果: lst3 {6,5,4,3,2,1}, lst4 为空
	return 0;
}

在这里插入图片描述
在这里插入图片描述

6.5 成员函数sort和reverse 与 算法库中sort和reverse的差异

其实标准算法库中实现了std::sort和std::reverse这样的算法,那么list为什么还要自己再创建一套sort和reverse 成员函数呢?为什么不直接调用算法库里的 sort和reverse 函数?
解释如下:

  1. 迭代器类型限制
  • 标准算法std::sort的局限性
    通用算法std::sort要求输入迭代器为随机访问迭代器(如std::vectorstd::deque的迭代器),因为它需要快速跳转到任意位置(例如快速排序的分区操作)。

    std::list的迭代器是双向迭代器,仅支持顺序移动(++--),无法直接支持随机访问操作。
    因此,std::list必须实现自己的sort()成员函数,使用适合链表结构的排序算法(如归并排序)。

  • std::reverse的可用性
    std::reverse只需要双向迭代器,理论上可以直接用于std::list,但作为成员函数的reverse()可能在实现上更高效,比如通过交换指针而不是移动元素。这样对于链表结构来说,操作更高效。


  1. 操作效率优化
  • 链表结构的特殊性
    链表节点在内存中非连续分布,但每个节点包含前驱和后继指针。成员函数sort()reverse()可以通过修改指针指向高效重组链表,无需移动元素本身。

    • 例如,reverse()只需遍历链表并交换每个节点的前驱和后继指针,时间复杂度为 O ( n ) O(n) O(n)
    • sort()使用归并排序,通过分割和合并链表片段实现,时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn)
  • 避免元素拷贝开销
    通用算法std::sort需要交换元素值,而链表排序通过调整指针即可完成,避免了拷贝或移动元素的成本。


总结
std::list的成员函数sort()reverse()是因其数据结构特性效率优化需求而存在的,既弥补了通用算法的局限性,也充分利用了链表的操作优势。



网站公告

今日签到

点亮在社区的每一天
去签到