[数据结构与算法] C++（25）—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C++（25）——STL -> 正文阅读

[数据结构与算法]C++（25）——STL

STL内容一览

c++ STL （standard template libaray）标准模板库

一：标准容器

1、顺序容器

vector（向量容器）
deque（双端链表容器）
list（链表容器）

2、容器适配器

stack
queue
priority_queue（基于大根堆实现的优先级队列）

3、关联容器（重点）

无序关联容器链式哈希表增删查O(1)

unordered_set（无序单重集合）
unordered_multiset（无序多重集合）
unordered_map（无序单重映射表）
unordered_multimap（无序多重映射表）

有序关联容器红黑树增删查O(log2n)，2是底数（树的层数，树的高度）

set
multiset
map
multimap

二：近容器（近似）数组、string、bitset（位容器）

三、迭代器 iterator和const_iterator reverse_iterator和const_reverse_iterator

四、函数对象（类似c的函数指针） greater,less

五、泛型算法 sort、find、find_if、binary_search、for_each

vector

底层数据结构：动态开辟的数组，每次以原来大小的2倍进行扩容；

再来复习一下基本使用：
注意：对容器进行连续插入或者删除操作（insert/erase）,一定要更新迭代器，

vector<int> vec;
//增加
vec.push_back(20); //末尾添加元素，时间复杂度O(1)
vec.insert(it,20);//it迭代器指向的位置添加一个元素20，时间复杂度O(n)，导致容器扩容

// 删除
vec.pop_back();//末尾删除元素，时间复杂度O(1)
vec.erase(it);//删除it迭代器指向的元素，时间复杂度O(n)

//查询
//operator[] 下标的随机访问vec[5] ,时间复杂度O(1)
//iterator 迭代器进行遍历
//find,for_each
//foreach ==>通过iterator来实现的

常用的方法介绍：

size()
empty()
reserve(20)：预留空间，只给容器底层开辟指定大小的内存空间，并不会添加新的元素
resize(20)：不仅会给容器底层开辟指定大小的内存空间，还添加新的元素
swap：两个容器进行元素交换

使用示例：

int main()
{
	vector<int> vec;//起初容量是0.随着插入变成1,2，4，8。。
	
	vec.reserve(20); //给vector预留空间为20
	cout<<vec.empty()<<endl;
	cout<<vec.size()<<end;
	
	vec.resize(20);
	cout<<vec.empty()<<endl;
	cout<<vec.size()<<end;
	
	for (int i = 0;i < 20;++i)
	{
		vec.push_back(rand() % 100);
	}

	//vector的operator[]运算符重载函数
	int size = vec.size();
	for (int i = 0;i < size;++i)
	{
		cout << vec[i] << " ";
	}
	cout << endl;
	
	auto it = vec.begin();
	
	for (it = vec.begin();it != vec.end();++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	//给vector容器中所有奇数前面都添加一个小于奇数1的偶数
	for (it1 = vec.begin();it1 != vec.end();++it1)
	{
		if (*it1 % 2 != 0)
		{
			it1 = vec.insert(it1, *it1 - 1);
			++it1;
		}
	}

	//把vec容器中所有的偶数都删除
	auto it2 = vec.begin();
	while(it2 != vec.end())
	{
		if(*it2 % 2 == 0)
		{
			it2 = vec.erase(it2);//会自动前移，继续判断即可
		}
		else
		{
			++it2;
		}
	}
	return 0;
}

deque

deque：双端队列容器

deque 是由一块一块的固定大小的连续空间构成（块与块之间是不连续）。一旦有必要在 deque的前端或尾端增加新的空间，便配置一块固定大小的连续空间，串接在整个deque 的头端或尾端。
deque 的最大任务，便是在这些分块的固定大小连续空间上，维护其整体连续的假象（每一个第二维是连续的），并提供随机存取的接口（随机迭代器），代价则是迭代器架构较为复杂。
deque 采用一块所谓的_M_map（注意，不是 STL 的 map 容器）作为主控。这里所谓_M_map 是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是 deque 的储存空间主体。
底层数据结构：动态开辟的二位数组，一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组从新的第一维数组的下标的oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素的添加

在这里插入图片描述

deque<int> deq;
//增加
deq.push_back(20);//末尾添加元素O（1）
deq.push_front(20);//首部添加元素O（1）
deq.insert(it,20);//在迭代器指向的位置添加元素O（n）

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

//查询搜索
//iterator(连续的insert和erase就一定要考虑迭代器失效的问题)

以下是deque的存储结构和其迭代器的存储结构：

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

template < class _Tp>
struct _Deque_iterator          //迭代器
{
	typedef _Tp** _Map_pointer;

	_Tp * _M_cur;
	_Tp * _M_first;
	_Tp * _M_last;
	_Map_pointer _M_node;
};

template < class _Tp>
class _Deque_base                //deque存储结构
{
	typedef _Deque_iterator<_Tp> iterator;
protected:
	_Tp * *_M_map;
	size_t _M_map_size;
	iterator _M_start;
	iterator _M_finish;
};

int main()
{
	std::deque<int> iqu;
	return 0;
}

请添加图片描述
常用成员函数如下：

iqu[ ]：用来访问双向队列中单个的元素。
iqu.front()：返回第一个元素的引用
iqu.back()：返回最后一个元素的引用
iqu.push_front(x)：把元素x插入到双向队列的头部。O(1)
iqu.pop_front()：弹出双向队列的第一个元素。O(1)
iqu.push_back(x)：把元素x插入到双向队列的尾部。O(1)
iqu.pop_back()：弹出双向队列的最后一个元素。O(1)
iqu.insert(it,20),O(n)
iqu.erase(it);从it指向的位置删除元素O(n)

示例：

int main()
{
	std::deque<int> iqu;
	for (int i = 1; i <= 5; ++i)
	{
		iqu.push_back(i);
	}
	deque<int>::iterator it;
	for (it = iqu.begin();it != iqu.end();it++)
	{
		cout << *it ;
	}
	cout << endl;
	cout << iqu.front() << endl;
	cout << iqu.back() << endl;
	iqu.push_front(0);
	iqu.push_back(6);
	for (it = iqu.begin();it != iqu.end();it++)
	{
		cout << *it ;
	}
	iqu.pop_front();
	iqu.pop_back();
	cout << endl;
	for (it = iqu.begin();it != iqu.end();it++)
	{
		cout << *it;
	}
	return 0;
}

在这里插入图片描述
图示deque的简单操作：

for (int i = 1; i <= 5; ++i)
{
	iqu.push_back(i);
}

请添加图片描述

iqu.pop_front();

请添加图片描述

 for (int i = 6; i <= 16; ++i)
 {
     iqu.push_back(i);
 }

请添加图片描述

list

list：链表容器
底层数据结构：双向的循环链表

list<int> lis;
//增加
lis.push_back(20);//末尾添加元素O（1）
lis.push_front(20);//首部添加元素O（1）
lis.insert(it,20);//在迭代器指向的位置添加元素O（1），往往在进行list的insert操作时，先要进行一个query的查询操作
//对于链表来说，查询操作效率就比较低了

//删除
lis.pop_back();//从末尾删除元素O（1）
lis.pop_front();//从首部删除元素O（1）
lis.erase(it);//从it指向的位置删除元素O

//查询搜索
//iterator(连续的insert和erase就一定要考虑迭代器失效的问题)

deque、list和vector对比

vector和deque之间的区别

vector特点：动态数组，内存连续，以二倍的方式扩容，
deque特点：动态开辟的二维数组空间，内存并不连续，第二维是独立new出来的，属于分段连续。固定长度，扩容的时候，第一维的数组进行二倍扩容

deque 两端都能够快速插入和删除元素 O（1），vector 只在尾端进行插入和删除 O（1）。
对于内存的使用效率：vector需要的内存空间必须是连续的（低），deque可以分块进行数据存储，不需要内存空间必须是一片连续的。
在中间进行insert或erase时，时间复杂度都是O（n），但是由于deque的第二维内存空间不是连续的，所以在deque中间进行元素的insert或erase操作，造成元素的移动要比vector慢（deque 的元素存取和迭代器操作会稍微慢一些，因为 deque 的内部结构会多一个间接过程。）deque 中的迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。因为 deque 使用不止一块内存（而 vector 必须使用一块连续内存）。
deque 不支持对容量和内存重分配时机的控制，除了首尾两端安插、删除元素外，其他地方安插、删除元素都将导致元素的 pointer、reference、iterator 失效。不过，deque 的内存重分配机制优于 vector，因为 deque 不必在内存重分配时复制所有的元素。deque 的内存区块不再被使用时，会被释放
deque和list，比vector容器多出来的增加删除函数接口：push_front和pop_front.

vector和list之间的区别

list特点：双向循环链表
（问到这里一般就是问什么时候用数组好，什么时候用链表好？）

数组：增加删除O（n），随机访问O（1），链表：增加删除一个节点O（1），但是此时还要考虑搜索的时间

容器适配器

如何理解容器适配器？
比如stack：

template<typename T,typename Container=deque<T>>
class Stack
{
public:
	void push(const T &val)
	{
		con,push_back(val);
	}
	void pop()
	{
		con.pop_back();
	}
	T top()const
	{
		return con.back();
	}
private:
	Container con;
};

stack，queue，priority_queue之所以叫做适配器，是因为它们没有自己底层的数据结构，是依赖另外的容器来实现的功能，它们的方法，也是通过它们依赖的容器相应的方法实现的。
容器适配器没有实现自己的迭代器
stack：默认依赖deque实现，提供了push，pop，top，size，empty这几个栈常用的方法。依赖deque容器的原因：①deque的第二维是按固定大小开辟的，相比于vector，初始内存使用效率高②deque的内存是分段的，而vector需要一大片连续的空间，内存利用率高
queue：默认依赖deque实现，提供了push，pop，front，back，size，empty这几个单向队列常用的方法，依赖deque容器的原因：①deque的第二维是按固定大小开辟的，相比于vector，初始内存使用效率高②deque的内存是分段的，而vector需要一大片连续的空间，内存利用率高③deque本身支持O(1)时间复杂度的头尾增加删除元素，适合实现队列结构
priority_queue：默认依赖vector实现，提供了push，pop，top，size，empty这几个优先级队列常用的方法。依赖vector容器的原因，是priority_queue默认需要在一个内存连续的数组中构建一个大根堆，所以使用vector最合适（底层就是一个数组，堆结构需要按下标计算根节点和左右孩子节点在数组中的位置）。

使用示例：

#include<stack>
int main()
{
	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.top();
	}
	return 0;
}

#include<queue>
int main()
{
	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();
	}
	return 0;
}

#include<queue>
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<<que.top()<<" ";
		pque.pop();
	}
	return 0;
}

在这里插入图片描述

无序关联容器

底层数据结构;链式哈希表增删查O(1)

unordered_set（无序单重集合）
unordered_multiset（无序多重集合）
unordered_map（无序单重映射表）
unordered_multimap（无序多重映射表）

需要的头文件：

#include <unordered_set>
#include<unordered_map>

无序容器增删查代码示例：

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

int main()
{
	// 不允许key重复 改成unordered_multiset自行测试
	unordered_set<int> set1; 
	for (int i = 0; i < 100; ++i)
	{
		set1.insert(rand()%100+1);//不需要传入插入的位置，哈希表或者红黑树自己灰操作
	}
	cout << set1.size() << endl;
	cout << set1.count(15) << endl;//返回key为15的元素的个数，单重集合所以一定为1，多重集合可能大于1
	
	autoit = set。begin();
	for(;it1 != est1.end();++it1)
	{
		cout<<*it1<<" ";
	}
	couit<<endl;

	// 寻找是否存在20并删除:erase(it)/erase(key)
	set1.erase(20);
	/
	for(it1 = set1.begin();it1 != set1.end();++it1)
	{
		if(*it1 == 30)
		{
			it1 = set1.erase(it1);
		}
		else
		{
			it1++;
		}
	}
	//
	auto it1 = set1.find(20);
	if (it1 != set1.end())
	{
		set1.erase(it1);
	}

	for(int v:set1)
	{
		cout<<v<<" ";
	}
	cout<<endl;
	
	return 0;
}

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

int main()
{
	// 定义一个无序映射表// 不允许key重复
	unordered_map<int, string> map;
	// 无序映射表三种添加[key,value]的方式，增加元素时需要你打包成一个pair类型的对象而不是两个值
	//底层如下的结构：
	/*
	struct pair
	{
	first;//key
	second;//value
	};
	*/
	map.insert({ 1000, "aaa" });
	map.insert(make_pair(1001, "bbb"));
	map[1002] = "ccc";
	
	cout<<map[1000]<<endl;
	map[2888];
	//map的operator[]可用作查询，但是如果key不存在，它会插入一对数据[key,V()],V()为类型的默认值
	// 遍历map表1
	auto it = map.begin();//查不到返回末尾迭代器
	for (; it != map.end(); ++it)
	{
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
	// 遍历map表2
	for (pair<int, string> &pair : map)
	{
		cout << "key:" << pair.first << " value:" << pair.second << endl;
	}

	// 查找key为1000的键值对，并且删除
	map.erase(1000);
	///
	auto it1 = map.find(1000);
	if (it1 != map.end())
	{
		map.erase(it1);
	}

	return 0;
}

因为哈希表的增删查复杂度都为O（1），在处理海量数据查重复，去重复的时候，比如下面示例：

int main()
{
	const int ARR_LEN = 100000;
	intarr[ARR_LEN] = {0};
	for(int i - 0;i<ARR_LEN;++i)
	{
		arr[i] = rand()&10000 + 1;
	}
	//将上面的十万个整数中，统计哪些数字重复，并且统计数字重复的次数
	unordered_map<int,int>map;
	for(int k:arr)
	{
		auto it = map.find(k);
		if(it == map.end())//不存在
		{
			map.insert({k,1});
		}
		else
		{
			it->second++;
		}
		//上述代码可用map[k]++;直接代替
	}
	for(const pair<int,int>&p:map)
	{
		if(p.second > 1)
		{
			cout<<"key:"<<p.first<<"count"<<p.second;
		}
	}
	//或者
	auto it = map.begin();
	for(;it != map.end();++it)
	{
		if(it->second > 1)
		{
			cout<<"key:"<<it->first<<"count"<<it->second;
		}
	}


	//去重
	//上面的十万个整数中，对数字进行去重后打印
	unordered_set<int> set;
	for(int v:arr)
	{
		set.insert(v);
	}
	for(int v:set)
	{
		cout<<v<<" ";
	}
	cout<<endl;
}

有序关联容器

底层数据结构：红黑树增删查O(log2n)，2是底数（树的层数，树的高度）

set
multiset
map
multimap

需要的头文件：

#include <set>
#include<umap>

set、multiset、map、multimap和上面的无序容器相比较，除了底层的数据结构不同，其它的操作几乎都是一样的，上面无序容器的演示代码，换成有序容器同样可以正常执行。一般对于数据有序性没有要求的话，基本上都选择无序容器来使用；如果应用场景对于数据的有序性有所要求，那么就得选择有序关联容器了。

考察有序容器的时候，经常会考察红黑树的结构定义，特征，增加删除操作具体怎么执行，这属于高级数据结构里面的知识，后续我的博客里面会更新红黑树知识的讲解。

迭代器

/*
容器的迭代器
const_iterator:常量的正向迭代器  只能读，而不能写了
iterator:普通的正向迭代器
reverse_iterator:普通的反向迭代器
const_reverse_iterator:常量的反向迭代器
*/
#if 0
int main()
{
	vector<int> vec;
	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	// 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;}
	}
	*/
	vector<int>::const_iterator it1 = vec.begin();
	for (; it1 != vec.end(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;

	// rbegin()：返回的是最后一个元素的反向迭代器表示
	// rend：返回的是首元素前驱位置的迭代器的表示
	// vector<int>::reverse_iterator
	vector<int>::const_reverse_iterator rit = vec.rbegin();
	for (; rit != vec.rend(); ++rit)
	{
		cout << *rit << " ";
	}
	cout << endl;

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

	return 0;
}

函数对象

函数对象就是C语言里面的函数指针

class Sum
{
public:
	int operator()(int a, int b)
	{
		return a + b;
	}
};

int main()
{
	Sum sum;
	int ret = sum(10, 20);//sum.operator()(10,20)
	cout << ret << endl;
	return 0;
}

把有operator()小括号运算符重载函数的对象，称作函数对象或者称作仿函数。

对于下面的情境，我们只能比较大小的情况下，为了处理不同的比较方式，我们写了两个比较函数：

template<typename T>
bool compare(T a, T b)
{
	return a > b;
}
template<typename T>
bool compare(T a, T b)
{
	return a < b;
}
int main()
{
	cout << compare(10, 20) << endl;
	cout << compare('b', 'y') << endl;
	return 0;
}

其实这样完全没有必要，其实C语言的函数指针就可以解决这个问题：
使用C的函数指针解决方案：

template<typename T>
bool mygreater(T a, T b)
{
	return a > b;
}
bool myless(T a, T b)
{
	return a < b;
}
//compare是C++库中的库函数模板
template<typename T, typename Compare>
bool compare(T a, T b, Compare comp)
{
	return comp(a, b);
}
int main()
{
	cout << compare(10, 20, mygreater<int>) << endl;
	cout << compare(10, 20, myless<int>) << endl;
}

通过函数指针调用函数，是没有办法内联的，效率很低，因为会有函数调用开销，因此：
使用C++的函数对象解决方案：

template<typename T>
class mygreater
{
public:
	bool operator()(T a, T b)//二元函数对象
	{

		return a > b;
	}
};
template<typename T>
class myless
{
public:
	bool operator()(T a, T b)
	{

		return a < b;
	}
};
template<typename T, typename Compare>
bool compare(T a, T b, Compare comp)
{
	return comp(a, b);
}
int main()
{
	cout << compare(10, 20, mygreater<int>()) << endl;
	cout << compare(10, 20, myless<int>()) << endl;
}

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

泛型算法和绑定器

包含头文件#include<algorithm>

泛型算法：template + 迭代器 + 函数对象

sort, find, find_if, binary_search, for_each —— 做到所有容器通用

特点一：泛型算法的参数接收的都是迭代器
特点二：泛型算法的参数还可以接收函数对象（c语言函数指针）

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

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>//包含了函数对象和绑定器
using namespace std;

int main()
{
	int arr[] = { 23,12,5,6,547,8,7,45,7,4,523,4,3 };
	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;

	//log(2n)有序容器中进行二分查找
	if (binary_search(vec.begin(), vec.end(), 547))
	{
		cout << "所要查找的数547存在" << endl;
	}

	//O(n)
	auto it = find(vec.begin(), vec.end(), 547);
	if (it != vec.end())
	{
		cout << "所要查找的数547存在" << endl;
	}

	//传入函数对象greater，改变容器元素排列时的比较方式
	sort(vec.begin(), vec.end(), greater<int>());
	for (int v : vec)
	{
		cout << v << " ";
	}
	cout << endl;
	//547 523 45 23 12 8 7 7 6 5 4 4 3
	//把48按序插入到vector容器中,找到第一个小于48的数字
	//find_if需要的是一个一元函数对象
	auto it1 = find_if(vec.begin(), vec.end(), 
	                   bind1st(greater<int>(), 48));
	vec.insert(it1, 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 << " ";
			}
		});
	return 0;
}