【C++的vector、list、stack、queue用法简单介绍】

【知识预告】

  1. vector的介绍及使用
  2. list的介绍及使用
  3. list与vector的对比
  4. stack的介绍和使用
  5. queue的介绍和使用
  6. priority_queue的介绍和使用

1 vector的介绍及使用

1.1 vector的介绍

  1. vector是表示可变大小数组的序列容器
  2. 和数组类似,vector也采用连续存储空间来存储元素。意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  3. vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector每次都重新分配大小。
  4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。
  5. vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增
    长。
  6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。

1.2 vector的使用

vector的文档介绍

int main()
{
	vector<int> v1;
	vector<int> v2(10, 0);
	vector<int> v3(v2.begin(), v2.end());
	string str("hello world");
	vector<int> v4(str.begin(), str.end());
	vector<int> v5(v4);

	for (size_t i = 0; i < v3.size(); i++)
	{
		cout << v3[i] << " ";
	}
	cout << endl;   // 0 0 0 0 0 0 0 0 0 0

	//vector<int> ::iterator it = v4.begin();
	auto it = v4.begin();
	while (it != v4.end())
	{
		cout << *it << " ";
		it++;
	}              // 打印的是ASCII码("hello world")
	cout << endl;  // 104 101 108 108 111 32 119 111 114 108 100

	for (auto e : v5)
	{
		cout << e << " ";
	}
	cout << endl;  // 104 101 108 108 111 32 119 111 114 108 100
	return 0;
}
// VS喜欢1.5倍扩容
int main()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
	return 0;
}
//making v grow :
//capacity changed : 1
//capacity changed : 2
//capacity changed : 3
//capacity changed : 4
//capacity changed : 6
//capacity changed : 9
//capacity changed : 13
//capacity changed : 19
//capacity changed : 28
//capacity changed : 42
//capacity changed : 63
//capacity changed : 94
//capacity changed : 141
int main()
{
	vector<int> v1;
	cout << v1.max_size() << endl;
	// 1073741823

	vector<int> v;
	//v.reserve(100);  // size = 0   capacity 100
	v.resize(100);    // size = 100  capacity 100

	for (size_t i = 0; i < v.size(); i++)
	{
		v[i] = i;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}   // 打印0~99
	cout << endl;
	return 0;
}
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;  // 1 2 3 4

	v.insert(v.begin(), 0);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;  // 0 1 2 3 4

	auto it = find(v.begin(), v.end(), 3);   // [first,last)
	if (it != v.end())
	{
		v.insert(it, 30);
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;  // 0 1 2 30 3 4

	it = find(v.begin(), v.end(), 3);   // [first,last)
	if (it != v.end())
	{
		v.erase(it);
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;  // 0 1 2 30 4

	cout << v.size() << endl;   // 5
	cout << v.capacity() << endl;  // 6

	v.clear();
	//v.shrink_to_fit();   // 这个可以把capacity清空

	cout << v.size() << endl;     // 0
	cout << v.capacity() << endl; // 6
	return 0;
}
int main()
{
	// 1 2 3 4 5
	// VS2019会进行强制检查,erase和insert以后认为it失效了
	// 不能访问,访问就报错
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;  // 1 2 3 4 5

	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			//v.erase(it);
			it = v.erase(it);
		}
		//++it;
		else
		{
			++it;
		}
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;  // 1 3 5

	return 0;
}
int main()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);

	vector<int> v2(v1);

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;  // 1 2 3 4 5

	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;  // 1 2 3 4 5

	vector<int> v3;
	v3.push_back(10);
	v3.push_back(20);
	v3.push_back(30);
	v3.push_back(40);

	v1 = v3;
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;  // 10 20 30 40

	return 0;
}

2 list的介绍及使用

2.1 list的介绍

list的文档介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
  4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息。

2.2 list的使用

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;  // 1 2 3 4 5

	// 范围for的底层也是迭代器
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;  // 1 2 3 4 5

	return 0;
}
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;   // 1 2 3 4 5

	lt.reverse();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;  // 5 4 3 2 1

	//sort(lt.begin(), lt.end());   // 报错
	lt.sort();   // 默认是升序  使用小于号<
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;  // 1 2 3 4 5

	// 降序使用大于号 >
	//greater<int> gt;
	//lt.sort(gt);
	lt.sort(greater<int>());  // 底层是归并排序
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;  // 5 4 3 2 1

	// vector的sort更强

	lt.remove(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;  // 5 4 2 1

	return 0;
}
int main()
{
	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;

	for (int i = 1; i <= 4; i++)
		mylist1.push_back(i);   
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;   // mylist1:1 2 3 4

	for (int i = 1; i <= 3; i++)
		mylist2.push_back(i * 10);  
	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;  // mylist2:10 20 30

	it = mylist1.begin();
	it++;

	// splice有嫁接的意思
	//mylist1.splice(it, mylist2);  // mylist1:1 10 20 30 2 3 4
	//for (auto e : mylist1)
	//{
	//	cout << e << " ";
	//}
	//cout << endl;

	mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end());  // 1 20 30 2 3 4
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

3 list与vector的对比

vector与list都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及应用场景不同,其主要不同如下:

vectorlist
底层结构动态顺序表带头结点的双向循环链表
随机访问支持随机访问,访问某个元素效率O(1)不支持随机访问,访问某个元素效率O(N)
插入和删除任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容,增容:开辟新空间,拷贝元素,释放旧空间,导致效率更低任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1)
空间利用率底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭代器原生态指针对原生态指针(节点指针)进行封装
迭代器失效在插入元素时,要给所有的迭代器重新赋值,因为插入元素有可能会导致重新扩容,致使原来迭代器失效,删除时,当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
使用场景需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随机访问

4 stack的介绍和使用

4.1 stack的介绍

stack的文档介绍

  1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。

  2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。

  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:

    • empty:检测队列是否为空
    • back:获取尾部元素操作
    • push_back:尾部插入元素操作
    • pop_back:尾部删除元素操作
  4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

4.2 stack的使用

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;  // 4 3 2 1
	return 0;
}

例题:最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

class MinStack
{
public:
	void push(int x)
	{
		// 只要是压栈,先将元素保存到_elem中
		_elem.push(x);

		// 如果x小于_min中栈顶的元素,将x再压入_min中
		if (_min.empty() || x <= _min.top())
			_min.push(x);
	}

	void pop()
	{
		// 如果_min栈顶的元素等于出栈的元素,_min顶的元素要移除
		if (_min.top() == _elem.top())
			_min.pop();

		_elem.pop();
	}

	int top() { return _elem.top(); }
	int getMin() { return _min.top(); }
private:
	// 保存栈中的元素
	std::stack<int> _elem;

	// 保存栈的最小值
	std::stack<int> _min;
};

5 queue的介绍和使用

5.1 queue的介绍

queue的文档介绍

  1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
  2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
  3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
    • empty:检测队列是否为空
    • size:返回队列中有效元素的个数
    • front:返回队头元素的引用
    • back:返回队尾元素的引用
    • push_back:在队列尾部入队列
    • pop_front:在队列头部出队列
  4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

5.2 queue的使用

int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;  // 1 2 3 4

	return 0;
}

6 priority_queue的介绍和使用

priority_queue文档介绍

6.1 priority_queue的介绍

  1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
  2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
  3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
    • empty():检测容器是否为空
    • size():返回容器中有效元素个数
    • front():返回容器中第一个元素的引用
    • push_back():在容器尾部插入元素
    • pop_back():删除容器尾部元素
  5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
  6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

6.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。

函数声明接口说明
priority queue() / priority queue(first,last)构造一个空的优先级队列
empty()检测优先级队列是否为空,是返回true,否则返回false
top()返回优先级队列中最大(最小元素),即堆顶元素
push(x)在优先级队列中插入元素x
pop()删除优先级队列中最大(最小)元素,即堆顶元素
// shift+tab键整体缩进
int main()
{
	// 默认是大堆
	priority_queue<int> q;
	q.push(3);
	q.push(1);
	q.push(5);
	q.push(4);
	
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;  // 5 4 3 1

	return 0;
}
int main()
{
	// 小堆
	priority_queue<int, vector<int>, greater<int>> q;
	q.push(3);
	q.push(1);
	q.push(5);
	q.push(4);

	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;  // 1 3 4 5

	return 0;
}

例题:数组中第k个大的元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end());
        while (--k)
            pq.pop();

        return pq.top();
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/909460.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何记住美好的时刻,使用标准 SAP NetWeaver 日志的可能性

在本文中&#xff0c;我们将介绍一些常见的技巧&#xff0c;以及是否有针对它们的标准文档&#xff08;请参阅 Auding and Logging 寻求帮助&#xff09;。在本文中&#xff0c;我们将主要考虑标准工具。所有代码清单都可以在 ZABAPFILEOS_07 年的 github 上找到。 SAP NetWea…

ONLYOFFICE 8.2深度体验:高效协作与卓越性能的完美融合

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀ONLYOFFICE 8.2 &#x1f50d;引言&#x1f4d2;1. ONLYOFFICE 产品简介&#x1f4da;2. 功能与特点&#x1f341;协作编辑 PDF&#x1f342;…

[mysql]修改表和课后练习

目录 DDL数据定义语言 添加一个字段 添加一个字段到最后一个 添加到表中的第一个一个字段 选择其中一个位置: 修改一个字段:数据类型,长度,默认值(略) 重命名一个字段 删除一个字段 重命名表 删除表 清空表 DCL中事务相关内容 DCL中COMMIT和ROLLBACK的讲解 对比TR…

MinerU容器构建教程

一、介绍 MinerU作为一款智能数据提取工具&#xff0c;其核心功能之一是处理PDF文档和网页内容&#xff0c;将其中的文本、图像、表格、公式等信息提取出来&#xff0c;并转换为易于阅读和编辑的格式&#xff08;如Markdown&#xff09;。在这个过程中&#xff0c;MinerU需要利…

使用 OpenCV 实现图像的透视变换

概述 在计算机视觉领域&#xff0c;经常需要对图像进行各种几何变换&#xff0c;如旋转、缩放和平移等。其中&#xff0c;透视变换&#xff08;Perspective Transformation&#xff09;是一种非常重要的变换方式&#xff0c;它能够模拟三维空间中的视角变化&#xff0c;例如从…

三十二、Python基础语法(面向对象其他语法-上)

一、权限 权限&#xff1a;在 Python 中&#xff0c;可以对方法和属性设置访问权限,&#xff0c;即规定在什么地方可以使用这些属性和方法。 1.公有 公有&#xff1a;可以在任意的地方通过对象调用&#xff0c;按照之前的方式&#xff0c;直接定义的属性和方法都是公有的。 …

Jmeter命令监控CPU等指标

JMeter 命令行执行脚本得到的报告中&#xff0c;是没有CPU、内存使用率等监控数据的&#xff0c;但是可以使用JMeter插件帮忙。 一、下载jmeter-plugins-manager.jar 下载后将文件放到jmeter安装包lib/ext目录下。打开Jmeter》菜单栏》选项》Plugins Manager 二、安装PerfMon…

【IF-MMIN】利用模态不变性特征进行缺失模态的鲁棒多模态情感识别

代码地址&#xff1a;github地址传送 文章是基于MMIN的改进 -> MMIN传送 abstract 多模态情感识别利用跨模态的互补信息来获得性能。然而&#xff0c;我们不能保证所有模式的数据总是存在于实践中。在跨模态数据缺失预测研究中&#xff0c;异质性模态之间的固有差异即模态…

vueui vxe-form 分享实现表单项的联动禁用,配置式表单方式的用法

官网文档&#xff1a;https:/vxeui.com 实现表单项的联动禁用 在使用 vxe-form 时&#xff0c;有时候需要将表单项直接进行关联操作&#xff0c;比如某一项选择后&#xff0c;另外一项设置为禁用状态不可选择&#xff0c;使用插槽的话神容易实现&#xff0c;本章是分享配置式的…

架构师备考-系统分析与设计(面向对象方法)

定义 面向对象开发方法将面向对象的思想应用于软件开发过程中&#xff0c;指导开发活动&#xff0c;是建立在“对象”概念基础上的方法学。面向对象方法的本质是主张参照人们认知一个显示系统的方法&#xff0c;完成分析、设计与实现一个软件系统&#xff0c;提倡用人类…

【Melty是一款开源的AI编程助手,基于codellama,媲美cusor】

https://github.com/meltylabs/melty.git 对话进行代码重构

java项目之校园周边美食探索及分享平台(springboot)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的校园周边美食探索及分享平台。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 校园周边美食…

在Vue和OpenLayers中使用移动传感器实现飞机航线飞行模拟

项目实现的核心代码 项目概述 该项目的目标是使用Vue.js作为前端框架&#xff0c;结合OpenLayers用于地图显示&#xff0c;实时获取来自手机传感器的数据&#xff08;如经纬度、高度、速度&#xff09;来模拟飞机在地图上的飞行轨迹。整体架构如下&#xff1a; Vue.js 用于构建…

【系统配置】信创终端操作系统如何彻底禁用ssh _ 统信 _ 麒麟 _ 方德

原文链接&#xff1a;【系统配置】信创终端操作系统如何彻底禁用ssh | 统信 | 麒麟 | 方德 Hello&#xff0c;大家好啊&#xff01;今天带来一篇关于如何在信创终端操作系统中彻底禁用SSH的文章。在某些安全性要求较高的环境中&#xff0c;禁用SSH服务可以防止未经授权的远程访…

新一代跟踪器StrongSORT: Make DeepSORT Great Again论文解析—让 DeepSORT 再次伟大

新一代跟踪器StrongSORT: Make DeepSORT Great Again论文解析—让 DeepSORT 再次伟大 时间&#xff1a;2023年 机构:北京邮电大学 发表在&#xff1a;IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 25, 2023 代码源码地址&#xff1a; pytorch版本&#xff1a;https://github.com/dyh…

如何编写PHP代码以减少冗余?

在编程中&#xff0c;代码的冗余是一个常见的问题&#xff0c;不仅增加了代码的复杂性&#xff0c;还降低了可读性和可维护性。对于PHP这样的语言来说&#xff0c;减少代码冗余同样重要&#xff0c;尤其是当项目规模变得越来越大时。本文将探讨如何有效地减少PHP代码的冗余&…

苍穹外卖Bug集合

初始化后端项目运行出现以下问题 以上报错是因为maven和jdk版本不符合&#xff0c;需要将jdk改成17&#xff0c;mavne改成3.9.9

NC313 两个数组的交集

NC313 两个数组的交集 添加链接描述 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规定的值即可** * param nums1 int整型ArrayList * param nums2 int整型ArrayList * return int整型A…

【Unity】【游戏开发】Sprite背景闪烁怎么解决

【现象】 VR游戏中&#xff0c;给作为屏幕的3D板子加上Canvas后再加背景image&#xff0c;运行时总是发现image闪烁不定。 【分析】 两个带颜色的object在空间上完全重合时也遇到过这样的问题&#xff0c;所以推测是Canvas的image背景图与木板的面重合导致。 【解决方法】 …

【优选算法 — 双指针】双指针小专题

和为 s 的两个数 和为s的两个数 题目描述 解法一&#xff1a;暴力枚举 暴力枚举&#xff0c;先固定一个数&#xff0c;然后让这个数和另一个数匹配相加&#xff0c; 如果当前的数 所有剩余的数 target&#xff0c;则返回这两个数&#xff0c;否则固定下一个数&#…