当前位置： 首页 > article >正文

施磊老师c++(七)

article 2025/3/17 10:58:33

STL组件

文章目录

  • STL组件
    • 1.整体学习内容
    • 2.vector容器
    • 3.deque和list
      • deque--双端队列容器
      • list--链表容器
    • 4.vector,deque,list对比
      • 主要内容
      • 面经问题
    • 5.详解容器适配器--stack, queue, priority_queue
      • 容器适配器
      • stack-栈
      • queue-队列
      • priority_queue-优先级队列
      • 总结
    • 6.无序关联容器
      • 关联容器
      • unordered_set
      • unordered_map
      • 应用
    • 7.有序关联容器 - set,map
      • set
      • map
      • pair注意
    • 8.迭代器iterator
    • 9.函数对象--仿函数
    • 10.泛型算法和绑定器

1.整体学习内容

一、标准容器  c++11里提供了array   forword_list
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

2.vector容器

  1. vector— 向量容器
    底层数据结构—>动态开辟的数组, 每次以原来空间大小的2倍进行扩容

  2. 常用方法介绍:

    vector<int> vec;
1. 增加
vec.push_back(20); //末尾添加元素-O(1)-可能导致容器扩容-------回顾空间配置器allocator
vec.insert(it, 20); //指定位置增加元素--O(n)--因为后续的元素都要移动

2. 删除
vec.pop_back(); // 末尾删除-O(1) 
vec.erase(it); //删除指定位置元素 O(n)

3.查询:
operator[]  下标随机访问: vec[5] -- O(1) 
iterator迭代器遍历
find, for_each  --- 泛型查询
foreach ==> 通过迭代器实现的

注意: 对容器进行连续插入或者删除(insert,erase), 一定要更新迭代器, 否则会导致容器迭代器失效----回顾容器迭代器失效

常用方法:
1.size()
2.empty() //判断是否为空 , true(1)空, 0为非空
3.reserve(20) //给vector预留空间, 只开辟空间, 并不添加元素, 容器依然是空的, 元素是0, size()是0, empty()是1
4.resize(20)  //重置大小,扩容
5.swap: //交换两个元素

  3. 代码:
    注意区分 reserve和resize 的区别
    注意 insert和erase的逻辑问题

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

int main()
{
	vector<int> vec;

	//vec.reserve(20); // 预留空间
	//cout << vec.empty() << endl; // 1
	//cout << vec.size() << endl; // 0

	vec.resize(20); // 会放入元素0
	cout << vec.empty() << endl; // 0
	cout << vec.size() << endl; // 0

	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100+1);
	}
	cout << vec.empty() << endl; //0   0
	cout << vec.size() << endl;//20    40


	#if 0
	int size = vec.size();

	for (int i = 0; i < size; ++i)
	{
		cout << vec[i] << " ";
	}
	cout << endl;

	//删除所有偶数
	auto it2 = vec.begin();
	//for (; it2 != vec.end(); ++it2)
	//{
	//	if (*it2 % 2 == 0)
	//	{
	//		vec.erase(it2); //删除全部, 需要更新迭代器
	//		//break; //只删除一个, it2不用管了
	//	}
	//}
	for (; it2 != vec.end(); )
	{
		if (*it2 % 2 == 0)
		{
			it2 = vec.erase(it2); //删除全部, 需要更新迭代器
			//break; //只删除一个, it2不用管了
		}
		else  // 注意逻辑问题
		{ 
			++it2; //由于更新了, 要判断一下当前位置
		}
	}
	


	auto it = vec.begin();

	for (; it != vec.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

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

	for (; it != vec.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	#endif

	return 0;
}

3.deque和list

二者 比vector 多出来的 常用方法: push_front, pop_front

deque–双端队列容器

  1. deque–双端队列容器–分块存储 — 默认第二维开辟 4096/sizeof(int) = 1024个位置
    底层数据结构—> 动态开辟的二维数组, 第一维数组个数从2开始, 以2倍方式扩容, 每次扩容后, 原来第二维的数组, 从新的第一维数组的下标oldsize/2开始存放, 方便首尾元素添加

    第一维：中央映射表（指针数组），存储指向各个缓冲区的指针。

第二维：每个缓冲区（固定大小的数组），存储实际的数据元素.
(std::deque（双端队列）的底层实现可以理解为一个动态的二维数组，但这种描述需要进一步澄清。实际上，deque的底层数据结构是一个分段连续的空间，由多个固定大小的数组（称为缓冲区或块）组成，并通过一个中央映射表（通常是一个指针数组）来管理这些缓冲区。)---deepseek

中央映射表 (Map)   
+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
  |     |     |     |
  v     v     v     v
+---+ +---+ +---+ +---+
| B | | B | | B | | B |  <- 缓冲区 (Buffer)
+---+ +---+ +---+ +---+
  |     |     |     |
  v     v     v     v
+---+ +---+ +---+ +---+
| 1 | | 2 | | 3 | | 4 |  <- 缓冲区中的元素
| 2 | | 3 | | 4 | | 5 |
|...| |...| |...| |...|
+---+ +---+ +---+ +---+

一般first和last是在最中间, 因为是双端队列, 两边都能加元素
扩容后, 复制过去的旧数据也将会在中间位置(oldsize/2--用于计算放入的位置)
2->4  2/2=1 0,1,2,3 放在1,2处 
4->8  4/2=2 0,1,2,3,4,5,6,7 放到 2,3,4,5处

  2. 常用方法:

    #include<deque>
deque<int> deq;
1. 增加
deq.push_back(20); // last 末尾添加 - O(1)
deq.push_front(20);  // first 从首部添加 - O(1) //vec.insert(vec.begin(), 20) - O(n)
deq.insert(it, 20); // O(n)

2.删除
deq.pop_back(); //O(1)
deq.pop_front(); //O(1)
deq.erase(it); //O(n)

3.查询搜索
iterator(连续的insert和erase一定要考虑迭代器失效)
无 operator[]

list–链表容器

  1. list–链表容器
    底层数据结构–双向的循环链表 (pre,data,next)

  2. 常用方法:

    #include<list>
deque<int> mylist;
1. 增加   --- 与deque 一模一样, 除了insert时间复杂度
mylist.push_back(20); // last 末尾添加 - O(1)
mylist.push_front(20);  // first 从首部添加 - O(1) //vec.insert(vec.begin(), 20) - O(n)
mylist.insert(it, 20); // O(1)  --- 不涉及其他元素  //但是链表进行insert前 需要进行 query查询, 链表查询效率低

2.删除
mylist.pop_back(); //O(1)
mylist.pop_front(); //O(1)
mylist.erase(it); //O(1)

3.查询搜索
iterator(连续的insert和erase一定要考虑迭代器失效)
无 operator[]

4.vector,deque,list对比

主要内容

  1. 不要只学习表面, 多看看底层

  2. 特点回顾

    1.vector特点:
	动态数组,内存是连续的, 2倍的方式进行扩容, vector<int> vec; reserve和resize区别

2.deque特点:
	动态开辟的二维数组, 第一维数组个数从2开始, 以2倍方式扩容, 每次扩容后, 原来第二维的数组, 从新的第一维数组的下标oldsize/2开始存放, 方便首尾元素添加

面经问题

  1. deque的底层内存是不是连续的? – 分块存储
    并不是, 每一个 第二维的是 连续的, 但是 第二维之间 不是连续的

  2. vector 与 deque 区别?

    1. 底层数据结构不同
2. 前中后 插入删除元素的时间复杂度: 中间O(n)和结尾O(1)相同, 但是 前不同, deque-O(1) vector-O(n)
3. 对于内存的使用效率, vector需要的内存是连续的,  deque 可以分块 进行数据存储, 不需要内存空间 必须连续
4.在中间进行insert或erase, vector和deque他们的效率谁能好一点?
//虽然都是 都在一个量级O(n)   vetor更好, deque差
//由于deque的第二维空间不是连续的, 所以在deque中间进行元素的insert或者earse.造成元素移动要慢,

  3. vector 与 list 区别?

    1.  底层数据结构不同  list是双向循环链表
//一般的数组和链表,  数组:增加删除O(n), 查询O(n), 随机访问(1)
//链表, 增删本身是O(1), 但是还要查询,O(n), 没有随机访问

5.详解容器适配器–stack, queue, priority_queue

容器适配器

  1. 注意区别 容器适配器和容器空间配置器

    stack，queue，priority_queue之所以叫做适配器，是因为它们没有自己底层的数据结构，是依赖另外的容器来实现的功能，它们的方法，也是通过它们依赖的容器相应的方法实现的。

  2. 怎么理解适配器? –有一种设计模式就是适配器模式
    底层没有自己的数据结构, 他是对另外容器的封装, 他的方法 全部由 底层依赖 的容器 进行实现

    stack  源码, 底层用的就是deque
_EXPORT_STD template <class _Ty, class _Container = deque<_Ty>>

  3. 容器适配器:stack, queue, priority_queue ---- 重点, 使用频率高

stack-栈

  1. 常用方法: ===>依赖deque

    1. push---入栈
2. pop--出栈
3. top--查看栈顶元素
4. empty--判空
5. size--返回元素个数

  2. 代码:

    #include <iostream>
using namespace std;
#include <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.pop();
	}

	return 0;
}

queue-队列

  1. 常用方法: fifo 先入先出 ===>依赖deque

    1. push---入队列
2. pop--出队列, 队头出
3. front--查看队头
4. back--查看队尾
5. empty--判空
6. size--返回元素个数

priority_queue-优先级队列

  1. 常用方法: ===>依赖vector 默认大根堆

    1. push---入队列
2. pop--出队列
3. top--查看队顶元素
4. empty--判空
5. size--返回元素个数

总结

  1. 代码:

    #include <iostream>
using namespace std;
#include  <stack>
#include <queue>




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.pop();
	}
	cout << endl;
	cout << "------------------------------------------" << endl;

	queue<int> qe;
	for (int i = 0; i < 20; ++i)
	{
		qe.push(rand() % 100 + 1);
	}

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

	while (!qe.empty())
	{
		cout << qe.front() << " ";
		qe.pop();
	}

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

	priority_queue<int> pqe;
	for (int i = 0; i < 20; ++i)
	{
		pqe.push(rand() % 100 + 1);
	}

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

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

	return 0;
}

  2. 为什么有的依赖 deque(queue, strack), 有的依赖 vector(priority_queue)

    1. 为什么选择deque?
    首先vector初始内存使用效率低, 没有deque好, vector是 0-1-2-4-8慢慢扩容, deque则是先开辟好大的,   虽然vector有reserve函数, 但是有修改成本
	其次, queue需要支持 尾部插入, 头部删除, 因此在这两个操作上,需要时间复杂度要求, 而deque正好是O(1), vector却是O(n)和O(1)
	vector需要大片的连续内存, 而deque只需要分段内存, 当存储大数据时, deque内存利用率更高
    
2. 为什么选择vector?
    priority_queue 底层默认是大根堆结构, 使用 类似奇数和偶数下标的形式(了解二叉树应该明白这个), 来查找访问元素.   就像二叉树 是用数组存储的, 下标很重要-----------deque则不行, 第二维的数组,不同的块, 内存都不是连续的

6.无序关联容器

关联容器

关联容器分为: 无序和有序 关联容器
集合set, 映射表map

  1. 以链式哈希表作为底层数据结构的无序关联容器有：: — unordered_…
    增删查–O(1)

    unordered_set   单重集合   单重就是不允许数重复
unordered_multiset  多重集合   // #include<unordered_set>
unordered_map
unordered_multimap        // #include<unordered_map>

  2. 以红黑树作为底层数据结构的有序关联容器有：
    增删查–O(log2 n) 2是底数,树的高度

    set
multiset    // #include<set>
map
multimap    // #include<map>

  3. 关联容器 与 vector,deque, list的 函数使用注意点
    与 vector,deque, list不同,这些的insert是两个参数, 因为是线性表, 需要指定位置
    但是 由于关联容器 底层是 哈希表 或 红黑树, 插入的位置不是随机的,一个是按哈希公式, 一个是根据红黑树性质

    unordered_set<int> set1;

set1.insert(20)

unordered_set

  1. 切记: 单重集合不存储 重复元素!!!

  2. find()------有则返回迭代器, 不存在则返回末尾迭代器

  3. c++11 的 foreach 正规名叫 基于范围的 for 循环（range-based for loop）

  4. 关联容器常用方法:

    增: insert
删: erase(key), erase(it)  --- key和迭代器都行
遍历: iterator, find(key)

  5. 代码:

    #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;   // 65, 不是100, 单重集合不存储 重复元素
	/*=============================================================================*/

	unordered_multiset<int> mulset1;    // ---- 注意只有一个参数
	for (int i = 0; i < 100; ++i)
	{
		mulset1.insert(rand() % 100 + 1);  
	}
	cout << mulset1.size() << endl;   // 100

	/*=============================================================================*/
	
	auto it1 = set1.begin();
	for (;it1 != set1.end();++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;

	//c++11有 foreach形式用于遍历
	for (auto v : set1)
	{
		cout << v << " ";
	}
	cout << endl;
	/*=============================================================================*/

	set1.erase(20);  //按key值删除元素

	/*=============================================================================*/

	// 寻找是否存在20并删除
	it1 = set1.find(20);   // 有则返回迭代器, 不存在则返回末尾迭代器
	if (it1 != set1.end())
	{
		set1.erase(it1);
	}

	// count返回set中有几个50=》最多是1个
	cout << set1.count(50) << endl;
	return 0;
}

unordered_map

  1. map是存储键值对[key, val], set只存储 key

  2. first->key, second->val ===> 依赖于 pair 类

  3. operator[] 要注意, 看代码

  4. 代码:

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

int main()
{
	// 定义一个无序映射表
	unordered_map<int, string> map;
	// 无序映射表三种添加[key,value]的方式
	map.insert({ 1000, "aaa" });  // 注意打包键值对
	map.insert(make_pair(1001, "bbb"));
	map[1002] = "ccc"; // operator[]   添加

	//删除
	map.erase(1002);

	//查询
	cout << map.size() << endl;  //2
	cout << map[1000] << endl;
	cout << map[1003] << endl;   // []重载,不仅能查询, 而且key不存在时, 会添加这个键值对, string() , 实际打印出来就什么也没有, []还能修改
	cout << map.size() << endl;  //3 


	// 遍历map表1
	auto it = map.begin();    // 迭代器是 打包的 pair对象
	for (; it != map.end(); ++it)
	{
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
	// 遍历map表2
	for (pair<const int, string>& pair : map)   // 这里是const, map里key不可修改, 但是, 实际可以用auto更方便
	{
		cout << "key:" << pair.first << " value:" << pair.second << endl;
	}

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

	return 0;
}

应用

  1. 无序map的一个应用: 海量数据查重

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

int main()
{
	const int ARR_LEN = 100;
	int arr[ARR_LEN] = { 0 };
	for (int i = 0; i < ARR_LEN; ++i)
	{
		arr[i] = rand() % 20 + 1;
	}

	unordered_map<int, int> map1;
	for (int k : arr)
	{
		//auto it = map1.find(k);
		//if (it == map1.end())
		//{
		//	map1.insert({ k,1 });
		//}
		//else
		//{
		//	it->second++;  //出现过, 就增加次数
		//}
		map1[k]++; // 初始是[k,int()]即[k,0]
	}

	for (auto& pair : map1)
	{
		if (pair.second > 1)
		{
			cout << "key: " << pair.first << " count: " << pair.second << endl;
		}
	}


	return 0;
}

  2. set应用, 去重代码:

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

int main()
{
	const int ARR_LEN = 100;
	int arr[ARR_LEN] = { 0 };
	for (int i = 0; i < ARR_LEN; ++i)
	{
		arr[i] = rand() % 20 + 1;
	}

	//去重打印
	unordered_set<int> set1;

	for (int k : arr)
	{
		set1.insert(k);
	}

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


	return 0;
}

  3. 哈希桶? – 不是很明白这个到底是啥

    #include <iostream>
#include <string>
#include <unordered_map>
int main()
{
	std::unordered_map<std::string, std::string> mymap =
	{
		{ "house", "maison" },
		{ "apple", "pomme" },
		{ "tree", "arbre" },
		{ "book", "livre" },
		{ "door", "porte" },
		{ "grapefruit", "pamplemousse" }
	};
	unsigned n = mymap.bucket_count(); //获取哈希桶的个数
	std::cout << "mymap has " << n << " buckets.\n";
	for (unsigned i = 0; i < n; ++i) // 逐个遍历哈希桶中的链表
	{
		std::cout << "bucket #" << i << " contains: ";
		for (auto it = mymap.begin(i); it != mymap.end(i); ++it)
			std::cout << "[" << it->first << ":" << it->second << "] ";
		std::cout << "\n";
	}

	return 0;
}

7.有序关联容器 - set,map

  1. 单重set, 不重复元素, 但有序
  2. 常用方法 与 unordered 一模一样

set

  1. 自定义类型呢? 需要手动 提供自定义类型的 operator<.

    //不加入自己的 重载时, 会报以下错误
//二进制“<”:“const _Ty”不定义该运算符或到预定义运算符可接收的类型的转换


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

class Student
{
public:
	Student(int id, string name): _id(id), _name(name){}
	bool operator< (const Student& stu)const  //不修改成员变量, 只访问, 尽量写常方法
	{
		return _id < stu._id;
	}
private:
	int _id;
	string _name;
	friend ostream& operator<< (ostream& out, const Student& stu);
};

ostream& operator<< (ostream& out, const Student& stu)
{
	out << "id: " << stu._id << " name: " << stu._name << endl;
	return out;
}

int main()
{
	set<Student> set1;
	set1.insert(Student(1001, "hzh2"));
	set1.insert(Student(1000, "hzh1"));

	for (auto v : set1)
	{
		cout << v ;
	}
	cout << endl;


	return 0;
}

map

  1. 代码:

    #include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;

class Student
{
public:
	Student(int id=0, string name="hzh") : _id(id), _name(name){}
	
private:
	int _id;
	string _name;
	friend ostream& operator<< (ostream& out, const Student& stu);   
	friend ostream& operator<< (ostream& out, const pair<int, Student>& p);
};

ostream& operator<< (ostream& out, const Student& stu)
{
	out << "id: " << stu._id << " name: " << stu._name << endl;
	return out;
}

ostream& operator<< (ostream& out, const pair<int, Student>& p)
{
	out << "id: " << p.second._id << " name: " << p.second._name << endl;
	return out;
}

int main()
{
	map<int, Student> map1;   // map按key就可以自动排
	map1.insert({ 1001, Student(1001, "hzh1") });
	map1.insert({ 1000, Student(1000, "hzh0") });
	cout << map1[1000] << endl;   // 这样的 operator[] 需要有默认的构造函数, 不使用[], 是可以不需要 默认构造函数的

	for (auto& v : map1)
	{
		cout << v ;   // 对应第二个<<重载
	}
	cout << endl;

	//还有迭代器方式
	for (auto it = map1.begin(); it != map1.end(); ++it)
	{
		cout << "key: " << it->first << "value: " << it->second << endl; //后面的用到了<<重载     
	}


	return 0;
}

pair注意

  1. 元素访问, 可以是 it->first, 也可以是 (*it).first, 一般使用第一个, 更方便

8.迭代器iterator

iterator, const_iterator, reverse_iterator, const_reverse_iterator

  1. iterator 是 普通的 正向迭代器 ---- 不仅能读,还能修改

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


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

	//vector<int>::iterator it = vec.begin();  // 这个要会
	auto it = vec.begin();

	for (; it != vec.end(); ++it)
	{
		cout << *it << " "; 
		if (*it % 2 == 0)
		{
			*it = 0;
		}
	}
	cout << endl;

	it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		cout << *it << " ";
	}

	return 0;
}

  2. const_iterator常量的正向迭代器 ----- 只能读, 不能写

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


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

	vector<int>::const_iterator it = vec.begin();  // 这个要会

	for (; it != vec.end(); ++it)
	{
		cout << *it << " "; 
		//if (*it % 2 == 0)
		//{
		//	*it = 0;
		//}
	}
	cout << endl;

	it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		cout << *it << " ";
	}

	return 0;
}

  3. 为什么 iterator转化为const_iterator是对的?

    vector<int>::const_iterator it = vec.begin();

实际上, 源码里, const_iterator是iterator的基类 

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

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

  4. reverse_iterator 反向迭代器, 搭配rbegin()
    同样有 const_reverse_iterator

    rbegin()返回的最后一个元素的 反向迭代器
rend()返回的首元素前驱位置的 反向迭代器

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


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

	vector<int>::reverse_iterator it = vec.rbegin();  // 这个要会

	for (; it != vec.rend(); ++it)   // 这里还是++
	{
		cout << *it << " "; 
		//if (*it % 2 == 0)
		//{
		//	*it = 0;
		//}
	}
	cout << endl;



	return 0;
}

9.函数对象–仿函数

  1. 函数对象–> 就是 c里面的 函数指针
    函数对象（Function Object），也称为仿函数（Functor），是 C++ 中的一个重要概念。它是一个类或结构体，通过重载 operator() 运算符，使得该类的对象可以像函数一样被调用。

  2. 对比下面两个:

    int sum(int a, int b)
{
    return a + b;
}

int ret = sum(10, 20);

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

Sum sum;
int ret = sum(10, 20);

  3. 关于内联和函数指针代码:

    #include <iostream>
using namespace std;

template<typename T>
bool mygreater(T a, T b)
{
    return a > b;
}

template<typename T>
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;
    return 0;
}

    这段代码里, 如果把 myless和mygreater 换成内联函数, 编译阶段是comp识别不了用哪个函数的
因为 这是使用函数指针间接调用的, 运行时才会去找

下面这个是可以识别的, 编译阶段会展开
inline bool func()
{
    ...;
}
bool compare(T a, T b, Compare comp)
{
    func();
    return comp(a, b);
}

  4. 使用函数对象(仿函数)解决函数指针调用开销问题

    #include <iostream>
using namespace std;


//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;
    return 0;
}

  5. 函数对象好处

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

  6. priority_queue默认是大根堆, 即从大到小排列, 改为小根堆

    #include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 最大堆---默认的
    priority_queue<int> maxHeap;
    for (int i = 0; i < 10; ++i) {
        maxHeap.push(rand() % 100);
    }
    cout << "Max Heap: ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;

    // 最小堆  -- 看一下源代码参数, 改一下less
    //template <class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type>>
    using MinHeap = priority_queue<int, vector<int>, greater<int>>;
    MinHeap minHeap;
    for (int i = 0; i < 10; ++i) {
        minHeap.push(rand() % 100);
    }
    cout << "Min Heap: ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    return 0;
}

    同理, set也行
    stl里 这种一般都是 less 和 greater

  7. using

    using 是 C++ 中一个非常强大的关键字，主要用途包括：

类型别名：定义类型别名，类似于 typedef。

模板别名：为模板定义别名。

命名空间成员引入：引入命名空间中的特定成员。

命名空间整体引入：引入整个命名空间。

基类成员引入：在派生类中引入基类的成员。

构造函数继承：继承基类的构造函数。

模板中使用：在模板中定义类型别名。

函数中使用：在函数内部定义类型别名。

10.泛型算法和绑定器

  1. 泛型算法头文件

    #include <algorithm>

  2. 泛型算法特点: — c++ primer书里有很多 泛型算法

    1. 接收的都是 迭代器
	sort, find, find_if:有条件的find, binary_search:二分查找, for_each

2. 还能接受函数对象

3.模板实现的+迭代器+函数对象

  3. 绑定器:

    bind1st: 把二元函数对象的operator()的第一个形参绑定起来
bind2nd:把二元函数对象的operator()的第二个形参绑定起来
    
#include <functional>  包含函数对象和绑定器

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

  4. 代码:

    #include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int arr[] = { 1, 2, 5, 4, 3 };
    size_t size = sizeof(arr) / sizeof(arr[0]); // 计算数组大小

    // 使用范围构造函数将数组元素放入 vector
    vector<int> vec(arr, arr + size);

    // 输出 vector 中的元素
    for (int val : vec) {
        cout << val << " ";
    }
    cout << endl;

    sort(vec.begin(), vec.end());
    // 输出 vector 中的元素
    for (int val : vec) {
        cout << val << " ";
    }
    cout << endl;

    if (binary_search(vec.begin(), vec.end(), 5))
    {
        cout << "5 is yes" << endl;
    }

    //从大到小
    sort(vec.begin(), vec.end(), greater<int>());  // 这个可比自己写快多了
    for (int val : vec) {
        cout << val << " ";
    }
    cout << endl;

    //有序的容器, 使用二分查找是更快的   log2 n    二分查找默认是在升序的容器里找
    if (binary_search(vec.begin(), vec.end(), 5, greater<int>()))
    {
        cout << "5 is yes" << endl;
    }

    /*
    _EXPORT_STD template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD _CONSTEXPR20 bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred) {
    // test if _Val equivalent to some element
    _STD _Adl_verify_range(_First, _Last);
    auto _UFirst      = _STD _Get_unwrapped(_First);
    const auto _ULast = _STD _Get_unwrapped(_Last);
    _UFirst           = _STD lower_bound(_UFirst, _ULast, _Val, _STD _Pass_fn(_Pred));
    return _UFirst != _ULast && !_Pred(_Val, *_UFirst);
}

_EXPORT_STD template <class _FwdIt, class _Ty>
_NODISCARD _CONSTEXPR20 bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // test if _Val equivalent to some element
    return _STD binary_search(_First, _Last, _Val, less<>{});
}
    */

    // 使用find()  ,, 二分效率高
    auto it = find(vec.begin(), vec.end(), 4);
    if (it != vec.end())
    {
        cout << "4 is yes--find" << endl;
    }
    

    // find_if 有条件的find,  一元函数对象   greater和less是二元函数对象
    // 将4插入到vec里, 找第一个小于 4的(降序)    
    // 使用绑定器   找第一个小于4的   
    //greater表示大于, 则绑定第一个为4  即 4>b
    //less表示小于, 则绑定第二个为4  即 a<4


    /*auto it2 = find_if(vec.begin(), vec.end(), bind1st(greater<int>(), 4));
    vec.insert(it2, 4);*/

    auto it2 = find_if(vec.begin(), vec.end(), bind2nd(less<int>(), 4));
    vec.insert(it2, 4);
    for (int val : vec) {
        cout << val << " ";
    }
    cout << endl;

    //c++11提供了 比绑定器和函数对象更简便的   lamda表达式---底层就是函数对象
    // []表示捕获外部变量,val就是捕获的 bool是返回值类型
    auto it3 = find_if(vec.begin(), vec.end(), [](int val)->bool {return val < 6; });
    vec.insert(it3, 6);
    for (int val : vec) {
        cout << val << " ";
    }
    cout << endl;

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


    return 0;
}

http://www.kler.cn/a/588253.html

相关文章：

  • 游戏引擎学习第163天
  • 如何在 GitHub 上修改他人的分支
  • Java 大视界 -- Java 大数据在智慧交通自动驾驶仿真与测试数据处理中的应用（136）
  • 【MCU】芯片复位与软件复位 在生产工装上的应用
  • 苹果app上架app store 之苹果开发者账户在mac电脑上如何使用钥匙串访问-发行-APP发布证书ios_distribution.cer-优雅草卓伊凡
  • yungouos微信扫码登录demo示例(支持个人免费)
  • 使用 OpenSSL 生成的 RSA 私钥文件（如`prikey.pem`）可以用于加密和解密数据
  • 【Cadence软件技巧集萃】从Capture到Allergo——分布演示从原理符号导出到网络表
  • OrioleDB: 新一代PostgreSQL存储引擎
  • 增量数据同步怎么做
  • HTTPS 证书相关
  • 毕业设计程序调试部署反馈
  • 从零开始掌握接口测试：RESTful/WebSocket/gRPC实战宝典
  • 如何高效解决 Java 内存泄漏问题方法论
  • 【redis】reids 客户端的连接（Windows和mac）
  • 关系数据库设计基础：函数依赖、码与多值依赖详解
  • 机器语言基础
  • 单源最短路径问题的相关总结
  • Flask中的装饰器
  • PHP优化技术