施磊老师c++(七)

STL组件

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; // 0vec.resize(20); // 会放入元素0cout << vec.empty() << endl; // 0cout << vec.size() << endl; // 0for (int i = 0; i < 20; ++i){vec.push_back(rand() % 100+1);}cout << vec.empty() << endl; //0   0cout << vec.size() << endl;//20    40#if 0int 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;#endifreturn 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;  //2cout << map[1000] << endl;cout << map[1003] << endl;   // []重载,不仅能查询, 而且key不存在时, 会添加这个键值对, string() , 实际打印出来就什么也没有, []还能修改cout << map.size() << endl;  //3 // 遍历map表1auto it = map.begin();    // 迭代器是 打包的 pair对象for (; it != map.end(); ++it){cout << "key:" << it->first << " value:" << it->second << endl;}// 遍历map表2for (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_each2. 还能接受函数对象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]); // 计算数组大小// 使用范围构造函数将数组元素放入 vectorvector<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 elementreturn _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;
   }