【C++ STL】容器适配器（Stack & Queue & Priotity_Queue）-- 详解（上）https://developer.aliyun.com/article/1514695?spm=a2c6h.13148508.setting.23.4b904f0ejdbHoA
🔺4、仿函数
（1）什么是仿函数
仿函数（Functor）又称为函数对象（Function Object），使一个类的使用看上去像一个函数，其实就是在类中重载了 operator() 运算符，这个类就有了类似函数的行为，就是一个仿函数类了。
仿函数的语法几乎和我们普通的函数调用一样，调用仿函数时，实际上就是通过仿函数类对象调用重载后的 operator() 运算符，这种行为类似函数调用。
// 仿函数(函数对象) --自定义类型 struct Less { bool operator()(const int& x, const int& y) // 重载()运算符 { return x < y; } }; void test_functor() { // 方式(1) Less less; // 构造函数对象 cout << less(1, 2) << endl; // 编译器会解释成:less.operator()(1, 2); // 方式(2) cout << Less()(1, 2) << endl; // 构造一个匿名函数对象 }
cplusplus.com/reference/functional/greater/
cplusplus.com/reference/functional/less/
仿函数类还可以写成类模板，适应更多的类型：
template<class T> // 用于小于(<)不等式比较的函数对象类 struct Less { bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> // 用于大于(>)不等式比较的函数对象类 struct Greater { bool operator()(const T& x, const T& y) { return x > y; } }; void test_functor() { Less<int> less; cout << less(1, 2) << endl; // true Greater<int> greater; cout << greater(1, 2) << endl; // false }
仿函数 less 和 greater 是继承的 binary_function，可以看作是对于一类函数的总体声明，这是函数做不到的。
template <class T> struct greater : binary_function <T, T, bool> { bool operator() (const T& x, const T& y) const { return x > y; } }; template <class T> struct less : binary_function <T, T, bool> { bool operator() (const T& x, const T& y) const { return x < y; } };
（2）模板实例化时，仿函数的使用
类模板一般是显式实例化的，在 <> 中指定模板参数的实际类型，所以类模板是传类型。比如： priority_queue。
//第1个模板参数是：存储数据的类型 //第2个模板参数是：基础容器的类型 //第3个模板参数是：仿函数的类型 template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>> class priority_queue; void test() { // 建小堆 priority_queue<int, vector<int>, greater<int>> pq; // 传仿函数greater<int>类型 }
而函数模板一般是隐式实例化，让编译器根据实参推演模板参数的实际类型，所以函数模板是传对象。比如：sort。
// 第1个模板参数：迭代器的类型 // 第2个模板参数是：仿函数的类型 template <class RandomAccessIterator, class Compare> // 函数的第1、2个参数是：迭代器对象 // 函数的第3个参数是：仿函数类的对象 void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); void test() { vector<int> v { 5,3,2,4,1 }; // 排降序(>) sort (v.begin(), b.end(), greater<int>()); // 传仿函数类greater<int>的匿名对象 for (const auto& x : v) cout << x << " "; cout << endl; }
四、容器适配器
stack 和 queue 和 priority_queue 往往不被认为是一个容器，而是一个容器适配。
adapter 原意是插座、适配器、接合器的意思。
1、什么是适配器
适配器 是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另外一个接口。
2、STL 标准库中 stack 和 queue 的底层结构
虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和 queue 只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque ， 而 priority_queue 默认使用 vector。
3、deque的简单介绍（了解）
cplusplus.com/reference/deque/deque/
（1）deque 的原理介绍
deque（ 双端队列 ）：是一种双开口的 “连续” 空间的数据结构。
双开口的含义是：可以在头尾两端进行插入和删除操作，且 时间复杂度为 O(1) ，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。
- vector 是一段连续的物理空间。
优点：
- 支持随机访问。
- 空间利用率高，底层是连续空间，不容易造成内存碎片。
- CPU 高速缓存命中率很高。
缺点：
- 空间不够时需要增容，增容代价很大（需要经过重新配置空间、元素搬移、释放原空间等），同时还存在一定的空间浪费。
- 头部和中间插入删除，效率很低 O(n)。
- list 不是连续的物理空间，而是由一个个节点 “链接” 起来的。
优点：
- 按需申请释放空间，不会浪费空间。
- 任意位置插入和删除数据都是 O(1)，因为不需要移动数据，插入删除效率高。
缺点：
- 不支持随机访问。
- 空间利用率低，底层不是连续的空间，小节点容易造成内存碎片。
- CPU 高速缓存命中率很低。
- deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组。
- deque 支持很多操作，比如 vector 不支持头插头删（因为效率太低），而 deque 支持。
- list 不支持随机访问，而 deque 支持。
看起来就像完美融合了 vector 和 list 的操作。
当需要增容时，只需要经过重新配置空间、元素搬移、释放原空间等过程，而是新增一个 buffer，存入数据，然后让中控数组指向新增的 buffer，将其管理起来。
deque 的底层是一段假象的连续空间，实际是分段连续的，为了维护其 “整体连续” 以及随机访问的假象，落在了 deque 的迭代器身上，因此 deque 的迭代器设计就比较复杂（包含4个指针） ，如下图所示：（deque 的中控器、缓冲区、迭代器的相互关系： ）
（2）deque 的优点和缺陷
与 vector 比较，deque 的 优势 是：
- 头部插入和删除时，不需要搬移元素，效率特别高。
- 在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的。
与 list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是， deque 有一个 致命缺陷 ：
- 不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。
- 同时，deque 在中间插入删除数据，非常麻烦，效率很低。
deque 是一种折中方案的（妥协）设计，不够极致，随机访问效率不及 vector，任意位置插入删除不及 list，所以它能替代 vector 和 list 吗？
不能。
4、为什么选择deque作为stack和queue的底层默认容器
- stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以；
- queue 是先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_front() 操作的线性结构，都可以作为 queue 的底层容器，比如 list。
但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：
- stack 和 queue 不需要遍历（因此 stack 和 queue 没有迭代器），只需要在固定的一端或者两端进行操作。
- 在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）。
- queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。
