首页 > 编程语言 >【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )

【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )

时间:2024-01-02 12:05:19浏览次数:38  
标签:容器 list 链表 lstInt 双向 构造函数



文章目录

  • 一、 list 双向链表容器简介
  • 1、容器特点
  • 2、容器操作时间复杂度
  • 3、遍历访问
  • 5、头文件
  • 二、 list 双向链表容器 构造函数
  • 1、默认无参构造函数
  • 2、创建包含 n 个相同元素的 list 双向链表
  • 3、使用初始化列表构造 list 双向链表
  • 4、使用另外一个 list 容器 构造 list 双向链表容器








一、 list 双向链表容器简介



1、容器特点



list 双向链表容器 可以在 任意位置 高效的 进行 插入 / 删除 元素 ;

list 双向链表容器 的 元素的指针 : 容器 中的元素 , 包含 2 个指针 , 一个指向该元素的前驱 , 一个指向该元素的后继 ;



2、容器操作时间复杂度



list 双向链表容器 操作时间复杂度 :

  • 头部和尾部插入或删除元素的时间复杂度是 O(1) ;
  • 表中间插入或删除元素 , 最坏情况可能需要移动 n 个元素 , 时间复杂度是 O(n) ;


3、遍历访问



迭代器 : list 双向链表容器 提供了 迭代器 功能 , 可以使用 迭代器 遍历 容器中的元素 ;



list 双向链表容器 不能 随机存储访问 , 也就是 不能 根据下标 获取元素 , 不能使用 at() 函数 和 [] 操作符访问容器中的元素 ;



5、头文件



使用 list 双向链表容器 , 需要导入 <list> 头文件 ;

#include <list>






二、 list 双向链表容器 构造函数



list 双向链表容器 常用操作 , 基本与 vector 相同 , 这里进行简单介绍 ;



1、默认无参构造函数



list 双向链表容器 默认的无参构造函数 , 构造格式如下 :

list<T> lstT

在尖括号中的 T 泛型类型是 list 双向链表 容器中存储的元素类型 ;

lstT 是双向链表容器的 变量名 ;



该默认无参构造函数 会创建空的 list 双向链表 ;



代码示例 :

#include "iostream"
using namespace std;
#include "list"

int main() {

	// 默认无参构造函数 会创建空的 list 双向链表

	// list 双向链表容器, 存储 int 类型元素
	list<int> lstInt;

	// list 双向链表容器, 存储 float 类型元素
	list<float> lstFloat;

	// list 双向链表容器, 存储 string 类型元素
	list<string> lstString;

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )_list



2、创建包含 n 个相同元素的 list 双向链表



创建包含 n 个相同元素的 list 双向链表 , 构造函数会将 n 个相同的元素 拷贝到 容器中 ;

函数原型如下 :

list(size_type n, const value_type& value = value_type(), const allocator_type& alloc = allocator_type());

该 构造函数会创建一个包含 n 个元素的新列表 , 每个元素的值都初始化为 value ;

如果没有提供 value , 则元素初始化为默认值 , 使用提供的 alloc 来分配内存 ;

如 : 如果是 int 类型的元素 , 则初始化为 0 ;

代码示例 :

// list 双向链表容器, 存储 3 个 int 类型元素 666
	list<int> lstInt(3, 666);



完整代码示例 :

#include "iostream"
using namespace std;
#include "list"

// 打印 list 容器内容
void printL(list<int>& lst) {
	// 获取迭代器起始位置
	list<int>::iterator it = lst.begin();

	cout << "list 容器内容 : ";

	// 循环判定, 如果没有迭代到最后一个元素的后一个位置, 那么一直循环
	while (it != lst.end())
	{
		// 获取元素值
		cout << *it << " ";
		// 迭代器指向下一个元素
		it++;
	}
	// 回车换行
	cout << endl;
}

int main() {

	// list 双向链表容器, 存储 3 个 int 类型元素 666
	list<int> lstInt(3, 666);

	// 打印 list 容器内容
	printL(lstInt);

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

list 容器内容 : 666 666 666
请按任意键继续. . .

【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )_STL_02



3、使用初始化列表构造 list 双向链表



使用初始化列表构造 list 双向链表 函数原型如下 :

list(std::initializer_list<value_type> init, const allocator_type& alloc = allocator_type());

该 构造函数会创建一个列表 , 其元素是从 init 初始化器列表复制的 ;

代码示例 :

// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};



完整代码示例 :

#include "iostream"
using namespace std;
#include "list"

// 打印 list 容器内容
void printL(list<int>& lst) {
	// 获取迭代器起始位置
	list<int>::iterator it = lst.begin();

	cout << "list 容器内容 : ";

	// 循环判定, 如果没有迭代到最后一个元素的后一个位置, 那么一直循环
	while (it != lst.end())
	{
		// 获取元素值
		cout << *it << " ";
		// 迭代器指向下一个元素
		it++;
	}
	// 回车换行
	cout << endl;
}

int main() {

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 打印 list 容器内容
	printL(lstInt);

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

list 容器内容 : 1 2 3 4 5
请按任意键继续. . .

【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )_list_03



4、使用另外一个 list 容器 构造 list 双向链表容器



使用另外一个 list 容器 构造 list 双向链表容器 , 有 3 种方式 :

  • 参数为另一个 list 容器引用 : 构造函数会创建一个新的列表 , 它是另一个列表 other 的副本 ;
list(const list& other);

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 是 lstInt 的副本
	list<int> lstInt2 (lstInt);
  • 参数为另一个 list 容器 指定区间范围的 迭代器 : 该 构造函数会创建一个新的列表 , 其元素是从范围 [first, last) 复制的 , 注意是 前闭后开区间 ; 这个范围可以是任何类型的输入迭代器 , 包括但不限于指针和 std::vector、std::deque 等容器的迭代器 ;
list(InputIt first, InputIt last);

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 注意是前闭后开区间
	list<int> lstInt3( ++lstInt.begin(), lstInt.end());



代码示例 :

#include "iostream"
using namespace std;
#include "list"

// 打印 list 容器内容
void printL(list<int>& lst) {
	// 获取迭代器起始位置
	list<int>::iterator it = lst.begin();

	cout << "list 容器内容 : ";

	// 循环判定, 如果没有迭代到最后一个元素的后一个位置, 那么一直循环
	while (it != lst.end())
	{
		// 获取元素值
		cout << *it << " ";
		// 迭代器指向下一个元素
		it++;
	}
	// 回车换行
	cout << endl;
}

int main() {

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 是 lstInt 的副本
	list<int> lstInt2 (lstInt);

	// 注意是前闭后开区间
	list<int> lstInt3( ++lstInt.begin(), lstInt.end());

	// 打印 list 容器内容
	printL(lstInt);
	printL(lstInt2);
	printL(lstInt3);

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

list 容器内容 : 1 2 3 4 5
list 容器内容 : 1 2 3 4 5
list 容器内容 : 2 3 4 5
请按任意键继续. . .

【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )_list_04


标签:容器,list,链表,lstInt,双向,构造函数
From: https://blog.51cto.com/u_14202100/9066909

相关文章

  • 【C++】STL 容器 - list 双向链表容器 ③ ( list 常用 api 简介 | 中间位置 插入 / 删
    文章目录一、list双向链表容器的中间位置插入元素1、在指定位置插入1个元素-insert函数2、在指定位置插入n个相同元素-insert函数3、中间位置插入另一个容器的指定范围内的元素-insert函数二、list双向链表容器的中间位置删除元素1、删除容器中所有元素......
  • 【C++】STL 容器 - queue 队列容器 ( queue 容器简介 | queue 容器特点 | push 函数 |
    文章目录一、queue队列容器简介1、queue队列容器引入2、queue队列容器特点二、queue队列常用api函数1、队尾插入函数-queue#push函数2、队头删除函数-queue#pop函数3、获取队首元素-queue#front函数一、queue队列容器简介1、queue队列容器引入queue队列容......
  • 【C++】STL 容器 - stack 堆栈容器 ① ( stack 堆栈容器特点 | stack 堆栈容器与 dequ
    文章目录一、stack堆栈容器简介1、stack堆栈容器引入2、stack堆栈容器特点3、stack堆栈容器与deque双端数组容器对比二、代码示例-stack堆栈容器简单示例1、代码示例2、执行结果一、stack堆栈容器简介1、stack堆栈容器引入C++语言中的STL标准模板库中的stac......
  • LeetCode-23 合并 K 个升序链表
    LeetCode-23合并K个升序链表给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。示例1:输入:lists=[[1,4,5],[1,3,4],[2,6]]输出:[1,1,2,3,4,4,5,6]解释:链表数组如下:[1->4->5,1->3->4,2->6]将它们合并到一个有序链......
  • 【LeetCode】23. 合并K个升序链表
    一、题目描述给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。示例1:输入:lists=[[1,4,5],[1,3,4],[2,6]]输出:[1,1,2,3,4,4,5,6]解释:链表数组如下:[1->4->5,1->3->4,2->6]将它们合并到一个有序链表中得到。1->1->2......
  • 使用容器快速在阿里云 ECS 多节点上搭建 Citus 12.1 集群
    阿里云ECS机器节点这里我们使用两台同一区域的ECS机器。机器配置:2核2G。(ps:阿里云99元一年的活动)一台安装coordinator(协调器),这里内网IP为172.18.60.11一台安装worker,这里内网IP为172.18.60.12操作系统两台机器分别安装了厂商的AlibabaCloudLinux3系统......
  • 代码随想录 小结02 链表
    第一题移除链表元素这题比较简单使用dummyHead的方式会比较简单不需要对头指针进行单独处理但是空间开销会大一些第二题设计链表类这个没什么好说的感觉有可能一些细节会忘记需要经常复习的一块第三题反转链表这题难度不大用一个tmp指针存储一下当前指针的next......
  • C++STL常用容器queue和stack
    2.5stack容器2.5.1stack基本概念概念:stack是一种先进后出(FirstInLastOut,FILO)的数据结构,它只有一个出口栈中只有顶端的元素才可以被外界使用,因此栈不允许有遍历行为栈中进入数据称为---入栈push栈中弹出数据称为---出栈pop生活中的栈:子弹进弹夹出弹夹的过程2.5.2s......
  • 链表相交问题
    链表链表相交问题思路来源一周刷爆LeetCode,算法大神左神(左程云)耗时100天打造算法与数据结构基础到笔记内容问题描述:现有两个单向链表,需要判断两个链表是否相交,若相交,返回链表最开始的交点,若不相交,则返回null算法思路:首先需要判断两个链表是否是环形链表,并获取环形链......
  • day03 代码随想录算法训练营 203. 移除链表元素
    题目:203.移除链表元素我的感悟:题目里的节点是已经给好的,创建虚拟节点,是为了方便处理头节点。加油,我可以的!!!!!理解难点:节点已经给好的创建虚拟节点代码难点:p是临时变量,类似于foriinrange(10)这里的i,本身是用完就扔的。返回值为什么不能是p.next?因为p是一个指针,......