C++基础(三) —— STL组件

news/2024/6/16 7:22:24 标签: c++, 数据结构, 开发语言

文章目录


一、C++ STL standard template libaray 标准模板库

1.顺序容器

vector:
底层数据结构:动态开辟的数组
扩容方式:每次以原来空间大小的2倍进行扩容
具体过程:
当需要在 std::vector 中插入元素时,如果当前容量足够,则直接在当前内存空间进行插入操作。
如果当前容量不足以容纳新元素,则需要进行扩容操作。
std::vector 会分配一个新的更大的内存空间,通常是当前容量的两倍或根据具体实现策略进行动态调整。
接下来,std::vector 将会将原来的元素逐个复制到新的内存空间中。
扩容完成后,原来的内存空间将会被释放,而新的内存空间将会成为 std::vector 的内部存储空间。

vec.push_back(20); vec.erase(it迭代器);

deque:
底层数据结构:动态开辟的二维数组
扩容方式:一维数组从2开始,以2倍的方式进行扩容,每次扩容后,原来第二维的数组,从新的第一维数组的下标oldsize/2开始存放,上下都预留相同的空行,方便支持deque的首尾元素添加;
通过动态增加内存块来实现的。当需要在 std::deque 的前端或后端插入元素时,如果当前内存块已满,std::deque 将会分配一个新的内存块。

添加:
deq.push_back(20); 从末尾添加元素 O(1)
deq.push_front(20); 从首部添加元素 O(1) // vec.insert(vec.begin(), 20) O(n)
deq.insert(it, 20); it指向的位置添加元素 O(n)

删除:
deq.pop_back(); 从末尾删除元素 O(1)
deq.pop_front(); 从首部删除元素 O(1)
deq.erase(it); 从it指向的位置删除元素 O(n)

list:
底层数据结构:双向的循环链表 pre data next

区别:
vector特点:动态数组,内存是连续的,2倍的方式进行扩容,
vector vec; 0-1-2-4-8… reserve(20)/resize
deque特点:动态开辟的二维数组空间,第二维是固定长度的数组空间,扩容的时候(第一维的数组进行2倍扩容)

deque底层内存是否是连续的?并不是,每一个第二维是连续的

容器的纵向考察:容器掌握的深度
容器的横向考察:各个相似容器之间的对比

vector和deque之间的区别?
1.底层数据结构
2.前中后插入删除元素的时间复杂度: 中间和末尾 O(1) 前 deque O(1) vector O(n)
3.对于内存的使用效率: vector 需要的内存空间必须是连续的, deque 可以分块进行数据存储,不需要内存空间必须是一片连续的
4.在中间进行insert或者erase,vector和deque它们的效率谁能好一点(vector)?谁能差一点(deque)? O(n)

vector和list之间的区别?
数组:增加删除O(n) 查询O(n) 随机访问O(1) 链表:(考虑搜索的时间)增加删除O(1) 查询O(n)

2.容器适配器
stack
queue
priority_queue
什么是适配器?为什么叫适配器?

  1. 适配器底层没有自己的数据结构,它是另外一个容器的封装,它的方法全部由底层依赖的容器进行实现的
  2. 没有实现自己的迭代器

stack: push入栈 pop出栈 top查看栈顶元素 empty判断栈空 size返回元素个数
queue: push入队 pop出队 front查看队头元素 back查看队尾元素 empty判断队空 size返回元素个数
priority_queue: push入队 pop出队 top查看队顶元素 empty判断队空 size返回元素个数 默认:大根

问:queue => deque 为什么不依赖vector呢???stack => deque 为什么不依赖vector呢???
1.vector的初始内存使用效率太低了!没有deque好 queue stack vector 0-1-2-4-8 deque 4096/sizeof(int) = 1024
2.对于queue来说,需要支持尾部插入,头部删除,O(1) 如果queue依赖vector,其出队效率很低
3.vector需要大片的连续内存,而deque只需要分段的内存,当存储大量数据时,显然deque对于内存的利用率更好一些

问:priority_queue => vector,为什么依赖vector???
底层默认把数据组成一个大根堆结构,在一个内存连续的数组上构建一个大根堆或者小根堆的

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main()
{
	priority_queue<int> pque;
	for (int i = 0; i < 20; ++i)
	{
		pque.push(rand() % 100 + 1);
	}
	cout << pque.size() << endl;
	while (!pque.empty())
	{
		cout << pque.top() << " ";
		pque.pop();
	}


	cout << endl;
	cout << "---------------------------" << endl;

	queue<int> que;
	for (int i = 0; i < 20; ++i)
	{
		que.push(rand() % 100 + 1);
	}
	cout << que.size() << endl;
	while (!que.empty())
	{
		cout << que.front() << " ";
		que.pop();
	}

	cout << endl;
	cout << "---------------------------" << endl;
	
	stack<int> s1;
	for (int i = 0; i < 20; ++i)
	{
		s1.push(rand() % 100 + 1);
	}

	cout << s1.size() << endl;

	while (!s1.empty())
	{
		cout << s1.top() << " ";
		s1.pop();
	}
    cout << endl;

	system("pause");
	return 0;
}


3.关联容器

3.1 无序关联容器 => 链式哈希表 增删查O(1)
unordered_set set1
不会存储key值重复的元素:利用此特征进行海量数据去重
插入:set1.insert(15) 查找:set1.count(15)

海量数据去重

#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;

int main()
{
	// 处理海量数据查重复;去重复的时候
	const int ARR_LEN = 100000;
	int arr[ARR_LEN] = { 0 };
	for (int i = 0; i < ARR_LEN; ++i)
	{
		arr[i] = rand() % 20 + 1;
	}

	// 上面的10万个整数中,把数字进行去重打印  set  map
	unordered_set<int> set;
	for (int v : arr) // O(n)
	{
		set.insert(v); // O(1)
	}

	for (int v : set)
	{
		cout << v << " ";
	}
	cout << endl;

    return 0;
}

统计重复次数

#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;

int main()
{
	// 处理海量数据查重复;去重复的时候
	const int ARR_LEN = 100000;
	int arr[ARR_LEN] = { 0 };
	for (int i = 0; i < ARR_LEN; ++i)
	{
		arr[i] = rand() % 20 + 1;
	}

	// 上面的10万个整数中,统计哪些数字重复了,并且统计数字重复的次数
	unordered_map<int, int> map1;
	for (int k : arr)
	{
		map1[k]++; // map1[k]  [k, 1]
	}


	auto it = map1.begin();
	for (; it != map1.end(); ++it)
	{
		if (it->second > 1)
		{
			cout << "key:" << it->first <<
				" count:" << it->second << endl;
		}
	}

    return 0;
}

set:集合 key map:映射表 [key,value]
unordered_set 单重集合
unordered_multiset 多重集合
unordered_map 单重映射表
unordered_multimap 多重映射表

3.2 有序关联容器 => 红黑树 增删查O(log2n) 2是底数(树的层数,树的高度)

set
multiset
map
multimap
有序关联容器(如 std::set 和 std::map)使用红黑树作为底层实现的主要原因是红黑树能够提供高效的查找、插入和删除操作,同时保持元素有序。

红黑树是一种自平衡二叉搜索树,具有以下特点:

每个节点都有一个颜色属性,通常为红色或黑色。
根节点和叶子节点(即空节点)都是黑色的。
如果一个节点是红色的,则它的子节点必须是黑色的。
对于任意节点,从该节点到其后代叶子节点的每条路径上,黑色节点的数量必须相同。
通过这些特性,红黑树能够保持树的平衡,使得查找、插入和删除操作的平均时间复杂度为 O(log n),其中 n 是树中元素的数量。

在有序关联容器中,元素按照键的顺序进行存储和组织。通过使用红黑树作为底层实现,可以在 O(log n) 的时间复杂度内快速查找和插入元素,同时保持元素有序。红黑树的自平衡特性确保了树的高度相对较低,从而提供了高效的操作性能。

此外,红黑树还支持一些其他的操作,如范围查询和遍历有序元素。这使得红黑树成为实现有序关联容器的理想选择。

需要注意的是,虽然红黑树是常用的底层实现方式,但具体的实现细节可能因不同的标准库或实现而有所差异。但无论如何,红黑树提供了一种高效且可靠的数据结构,用于实现有序关联容器。

二、近容器
数组,string,bitset(位容器)

三、迭代器
iterator和const_iterator
reverse_iterator和const_reverse_iterator

const_iterator:常量的正向迭代器 只能读,不能进行写操作
iterator:普通的正向迭代器
reverse_iterator:普通的反向迭代器
const_reverse_iterator:常量的反向迭代器

const_iterator底层代码:

//底层代码
// vector<int>::iterator
// auto it1 = vec.begin(); 
// const_iterator   <=   iterator

class const_iterator
{
    public:
    const T& operator*(){return *_ptr;}
}

class iterator : public const_iterator
{
    T& operator*(){return *_ptr;}
}
    
// rbegin():返回的是最后一个元素的反向迭代器表示
// rend:返回的是首元素前驱位置的迭代器的表示
// vector<int>::reverse_iterator

其实一般都auto = vec.begin();

vector<int> vec;
for (int i = 0; i < 20; ++i)
{
	vec.push_back(rand() % 100);
}

vector<int>::const_iterator it1 = vec.begin();
for (; it1 != vec.end(); ++it1)
{
	cout << *it1 << " ";
}
cout << endl;

四、函数对象(类似C的函数指针)

greater,less

1.通过函数对象调用operator(),可以省略函数的调用开销,比通过函数指针调用函数(不能够inline内联调用)效率高
2.因为函数对象是用类生成的,所以可以添加相关的成员变量,用来记录函数对象使用时更多的信息

C与C++的提升
类和对象:C++ 引入了类和对象的概念,支持面向对象编程。C 语言没有类和对象的概念,只有结构体和函数。

封装和继承:C++ 支持封装和继承,使得开发者能够更好地组织和管理代码。C 语言没有直接的封装和继承机制。

模板:C++ 引入了模板(template)机制,支持泛型编程,使得代码可以在不同的类型上进行通用操作。C 语言没有模板机制。

异常处理:C++ 引入了异常处理机制,允许开发者捕获和处理异常情况。C 语言没有内置的异常处理机制。

五、泛型算法(C++特性)
sort,find,find_if,binary_search,for_each
泛型算法 = template + 迭代器 + 函数对象

特点一:泛型算法的参数接收的都是迭代器

特点二:泛型算法的参数还可以接收函数对象(C函数指针)

sort,find,find_if,binary_search,for_each

绑定器 + 二元函数对象 =》 一元函数对象

bind1st:把二元函数对象的operator()(a, b)的第一个形参绑定起来

bind2nd:把二元函数对象的operator()(a, b)的第二个形参绑定起来

#include <iostream>
#include <vector>
#include <algorithm> // 包含了C++ STL里面的泛型算法
#include <functional> // 包含了函数对象和绑定器
using namespace std;


int main()
{
	int arr[] = { 12,4,78,9,21,43,56,52,42,31};
	vector<int> vec(arr, arr+sizeof(arr)/sizeof(arr[0]));

	for (int v : vec)
	{
		cout << v << " ";
	}
	cout << endl;

	// 默认小到大的排序
	sort(vec.begin(), vec.end());

	for (int v : vec)
	{
		cout << v << " ";
	}
	cout << endl;

	// 有序容器中进行二分查找
	if (binary_search(vec.begin(), vec.end(), 21)) 
	{
		cout << "binary_search 21" << endl;
	}

	auto it1 = find(vec.begin(), vec.end(), 21);
	if (it1 != vec.end())
	{
		cout << "find 21" << endl;
	}

	// 传入函数对象greater,改变容器元素排序时的比较方式
	sort(vec.begin(), vec.end(), greater<int>());
	for (int v : vec)
	{
		cout << v << " ";
	}
	cout << endl;

	// 78 56 52 43 42 31 21 12 9 4
	// 把48按序插入到vector容器当中  找第一个小于48的数字
	// find_if需要的是一个一元函数对象
	// greater a(48) > b    less a < b(48)
	auto it2 = find_if(vec.begin(), vec.end(),
		//bind1st(greater<int>(), 48));
		//bind2nd(less<int>(), 48));
		[](int val)->bool {return val < 48; });
	vec.insert(it2, 48);
	for (int v : vec)
	{
		cout << v << " ";
	}
	cout << endl;

	// for_each可以遍历容器的所有元素,可以自行添加合适的函数对象对容器
	// 的元素进行过滤
	for_each(vec.begin(), vec.end(), 
		[](int val)->void
	{
		if (val % 2 == 0)
		{
			cout << val << " ";
		}
	});
	cout << endl;

    system("pause");
	return 0;
}

http://www.niftyadmin.cn/n/409359.html

相关文章

网络通信 --- HTTP 协议初识

目录 &#x1f332;一、HTTP 协议是什么 &#x1f333;二、HTTP协议格式 &#x1f9aa;1.抓包工具的使用(以 Fiddler 为例) &#x1f363;2. 抓包工具的原理 (以 Fiddler 为例) &#x1f364;3. 抓包结果 &#x1f365;① HTTP 请求(request) &#x1f96e;②HTTP响应(re…

【科技素养题】少儿编程 蓝桥杯青少组科技素养题真题及解析第20套

少儿编程 蓝桥杯青少组科技素养题真题及解析第20套 1、“唐纳德特朗普 (Donald Trump) 曾经是美国总统”是一个 (),“特朗普关于新冠肺炎疫情的不实言论”是一个 ()。 A、事实;事实 B、观点;事实 C、观点;观点 D、事实;观点 答案:D 考点分析:主要考查小朋友们对时事的…

模板方法设计模式的学习和使用

1、模板方法设计模式的学习 当涉及到一系列具有相似行为的算法或操作时,模板方法设计模式是一种有效的设计模式。它允许你定义一个算法的骨架,同时将某些步骤的实现细节交给子类来实现。   模板方法模式基于以下两个核心原则&#xff1a; 抽象类定义模板方法骨架&#xff1a…

chatgpt赋能python:Python屏幕截图:完美的方法记录你的屏幕

Python屏幕截图&#xff1a;完美的方法记录你的屏幕 Python作为一种高级编程语言&#xff0c;被广泛用于开发各种应用程序和游戏&#xff0c;其中之一就是屏幕截图。 在本文中&#xff0c;我们将介绍使用Python进行屏幕截图的方法和技巧。 什么是屏幕截图&#xff1f; 屏幕截…

宝塔反代教程+国内服务器访问openai api接口+502 Bad Gateway问题解决!

前言 宝塔反代教程国内服务器访问openai api接口502 Bad Gateway问题解决! 此方法最简单快捷&#xff0c;没有复杂步骤&#xff0c;不容易出错&#xff0c;即最简单&#xff0c;零代码、零部署的方法。 实现前提 一台海外VPSOpenAI官方的API_KEYChatGPT网站系统源码 ChatGP…

STL——string模拟实现(一)

目录 构造函数的实现 拷贝构造 赋值重载 const问题 迭代器打印 范围for打印 运算符重载 reserve模拟 插入数据 push_back append 构造函数的实现 先贴出一段错误代码&#xff1a; #include<iostream> #include<assert.h> namespace zzl//避免与库冲突 {…

某电机修造厂变电所一次系统设计

摘要 由于国内人民生活水平的提高&#xff0c;科技不断地进步&#xff0c;控制不断地完善&#xff0c;从而促使变电所设计技术在电气系统领域占据主导权&#xff0c;也使得110kV变电所被广泛应用。在变电所系统设计领域中&#xff0c;110kV变电所成为目前一处亮丽的风景线&…

C++作业day1

思维导图 有以下定义&#xff0c;说明哪些量可以改变哪些不可以改变&#xff1f; const char *p; p指向的指向不能修改 const (char *) p; char *const p; p不能改 const char* const p; 都不能修改 …