文章目录
- 前言
- 1. 适配器的介绍
- 2. 仿函数
- 2.1 sort函数的模板参数
- 2.2 priority_queue类的模板参数
- 3. priority_queue模拟实现
- 3. stack & queue 模拟实现
- 3.1 deque的介绍
- 3.2 deque的优点与缺陷
- 3.3 STL标准库中对于stack和queue的模拟实现
前言
C++中的适配器是一种设计模式，用于将一个类或对象的接口转换为另一个接口，以便不同的类或对象可以相互协作。适配器模式可以分为类适配器和对象适配器两种形式。
类适配器通过继承源类并实现目标接口来实现适配。在类适配器中，适配器类同时继承自源类和目标接口，并重新实现目标接口的方法，以将源类的方法转换为目标接口的方法。
对象适配器则通过在适配器类中包装一个源对象来实现适配。在对象适配器中，适配器类持有一个源对象的引用，并实现目标接口的方法，在方法内部调用源对象的相应方法来完成适配。
适配器模式的主要作用是解决接口不兼容的问题，使得不同的类或对象可以在一起工作，提高了代码的复用性和可维护性。
1. 适配器的介绍
- stack的文档介绍
- queue的文档介绍
- priority_queue的文档介绍
大家也可以看看这篇博客：《STL使用详解》中stack、queue以及priority_queue部分。
虽然stack、queue和priority_queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack、queue和priority_queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，priority_queue默认使用vector，比如：
从这三组对比中，我们可以看到，stack，queue只有两个模板参数，并且第二个模板参数都deque容器（是一个双端队列），而priority_queue有三个模板参数，并且第二个模板参数是vector容器（第三个模板参数，在后面讲）。
如图这里我创建了三个栈，它们的底层形式是不一样的，但是在功能上结果都是一样的
用同样的方式创建队列，可以看到我们使用vector创建队列时，就不能调用队列的pop函数。因为，顺序表的头插头删效率太低了，所以在STL中的vector并没有提供头插头删的接口。但如果我们自己实现queue的话，可以将队列的pop函数改成调用容器的erase函数，用该函数删掉容器中的第一个位置的元素，也能达到队列pop的功能。
由此我们可以总结：
如果不考虑效率问题的话，只要一个容器能够满足某个适配器所有的接口功能，那么我们就可以用这个适配器来适配该容器。
2. 仿函数
C++中的仿函数是一种通过在类中重载 () 运算符来实现的特殊类。它的行为类似于函数，可以像使用函数一样创建类的对象，并通过调用对象来执行相应的操作。
仿函数的主要用途是与 STL中的算法进行配合，为算法提供特定的行为或比较规则。例如，在排序算法中，可以使用仿函数来定义排序的顺序。
通过使用仿函数，可以将一些常见的操作（如加减、比较大小等）定义为类的成员函数，并将这些类的对象作为参数传递给算法，使算法能够根据仿函数的定义进行相应的处理。
与普通函数相比，仿函数具有以下优点：
- 可以存储和处理更多的有用信息，例如与操作相关的数据。
- 可以通过类的继承和多态性来实现更灵活的行为。
- 可以在不同的上下文环境中重复使用，提高代码的复用性。
在 C++中，可以通过以下方式创建仿函数：
- 定义一个类，并在类中重载 () 运算符。
- 在 () 运算符的实现中，根据需要执行相应的操作。
- 创建类的对象，并像使用函数一样调用该对象。
需要注意的是，要使仿函数能够与 STL 中的算法完美配合，还需要满足一些特定的条件，例如可配接性等。
这里先简单的介绍一下仿函数怎么使用。
2.1 sort函数的模板参数
从这里可以看出，我们使用sort函数时，默认是升序排序（是因为默认第三个参数传了个less<T>()的默认参数）。但如果我们想让这组数据降序排序，就得再后面再加一个参数
这样排序下来的结果就是降序了。我们可以看到，最后传的这个参数是一个匿名对象，在这里也叫做仿函数，因为它具有和函数相似的功能，但又不是函数。我们在这里模拟实现一下用于比较大小的两个仿函数：
namespace hyt
{
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;
}
};
}
我用一个命名空间封装起来了，在这里我们可以看到和std命名空间里面的效果是一样的
2.2 priority_queue类的模板参数
我们再来看看priority_queue，它底层就是一个堆，默认情况下是大堆，关于堆的知识，这篇博客有详细的讲解：堆的实现
在前面，我们看到了priority_queue的模板参数
这里的第三个模板参数，就是传一个类型，来确定是大堆还是小堆，我们来举例试一下：
再来用我上面写的less和greater试一下：
可以看到效果是一样的。
这里有一个比较简单的小问题，可能有些刚学的老铁会对此有些疑惑，我在这里简单提一下：
这里可以看到，sort函数这里，我们是传一个类型为greater<int>的匿名对象，而priority_queue是传一个greater<int>类型。
这里解释下，因为priority_queue是一个类模板，需要将具体的类型传过去，才是一个具体的类名，而模板参数绝大多数情况都是传递类型。sort是一个函数模板，而函数传参一般都是将已经实例化的个体传递过去（例如：实例化的对象，普通变量，常量等）。所以sort就是需要传递一个对象（可以传仿函数对象，也可以传函数指针），而priority_queue需要传递一个类型。
3. priority_queue模拟实现
我们在前面已经说过，priority_queue的底层就是一个堆，它默认使用的容器是vector，原因是因为堆这个数据结构会经常用到[]来访问数据。下
#include<vector>
#include<functional>
namespace hyt
{
template <class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
priority_queue() // 默认调用默认成员函数
{}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last) // 拷贝构造
{
if (first != last)
{
_c.insert(_c.begin(), first, last); // 将一组数据放入到数组中
// 进行向下调整算法
size_t pos = _c.size();
while (pos > 0)
{
AdJustDown(pos - 1);
--pos;
}
}
}
bool empty() const
{
return _c.empty();
}
size_t size() const
{
return _c.size();
}
const T& top() const
{
return _c[0];
}
T& top()
{
return _c[0];
}
void push(const T& x)
{
_c.push_back(x);
// 进行向上调整算法
AdJustUp(_c.size() - 1);
}
void pop()
{
swap(_c[0], _c[_c.size() - 1]); // 将两个元素交换位置
_c.pop_back();
// 进行向下调整算法
AdJustDown(0);
}
private:
Container _c;
Compare _comp;
// 向上调整算法
void AdJustUp(size_t child)
{
size_t parents = (child - 1) / 2;
while (child > 0)
{
if (_comp(_c[parents], _c[child]))
{
swap(_c[parents], _c[child]);
child = parents;
parents = (child - 1) / 2;
}
else
break;
}
}
// 向下调整算法
void AdJustDown(size_t parents)
{
size_t child = parents * 2 + 1;
while (child < _c.size())
{
if (child + 1 < _c.size() && _comp(_c[child], _c[child + 1]))
++child;
if (_comp(_c[parents], _c[child]))
{
swap(_c[parents], _c[child]);
parents = child;
child = parents * 2 + 1;
}
else
break;
}
}
};
}
3. stack & queue 模拟实现
3.1 deque的介绍
deque的文档介绍
deque（双端队列）的底层实现通常由以下几个部分组成：
- 分段连续空间：
deque的存储空间由一段段定量的连续空间构成，而这些连续空间可能并不连续，它们分布在内存的不同区域。 - 中控器：用于管理和组织这些分段连续空间，维持整体连续假象的状态。
- 缓冲区：
deque的主存储体，每个缓冲区都是一段连续的空间。 - 迭代器：
deque的迭代器需要具备指出当前缓冲区位置、判断是否在缓冲区边缘以及访问和操作当前元素等功能。
deque 的分段存储结构提高了在序列两端添加或删除元素的效率，但也使迭代器的底层实现变得更复杂。迭代器需要能够在不同的连续空间中进行跳转，并正确处理缓冲区边缘的情况。
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
那deque是如何借助其迭代器维护其假想连续的结构呢？
deque 的迭代器主要由四个元素构成：cur（当前指向的元素地址）、first（元素所属缓冲区的头）、last（元素所属缓冲区的尾）、node（指向缓冲区所属的 map 的位置）。
在缓冲区内，迭代器的遍历方式和普通迭代器相同。当进行到缓冲区边缘时，迭代器需要调用 set_node() 跳到下一个缓冲区，以维持整体连续的假象。
deque 中控器采用一块所谓的 map（非 STL map）作为主控，map 是一小块连续空间，其中每个元素都是一个指针，指向另一段较大的连续线性空间，称为缓冲区。缓冲区才是 deque 的存储主体。
这种结构使得 deque 在头尾两端进行插入和删除操作时，时间复杂度为 O(1)，同时也提供了随机存取的接口。但代价是迭代器结构的复杂性。
3.2 deque的优点与缺陷
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
写一组测试用例来测试一下效率：
void test_op1()
{
srand(time(0));
const int N = 1000000;
deque<int> dq;
vector<int> v;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
v.push_back(e);
dq.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
sort(dq.begin(), dq.end());
int end2 = clock();
printf("vector:%d\n", end1 - begin1);
printf("deque:%d\n", end2 - begin2);
}
这组测试用例的目的是生成一百万个随机数，分别存放到vector和deque中，然后再分别将这两个容器中的数据进行排序看一下它们的效率：
void test_op2()
{
srand(time(0));
const int N = 1000000;
deque<int> dq1;
deque<int> dq2;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
dq1.push_back(e);
dq2.push_back(e);
}
int begin1 = clock();
sort(dq1.begin(), dq1.end());
int end1 = clock();
int begin2 = clock();
// 拷贝到vector
vector<int> v(dq2.begin(), dq2.end());
sort(v.begin(), v.end());
dq2.assign(v.begin(), v.end());
int end2 = clock();
printf("deque sort:%d\n", end1 - begin1);
printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}
这组测试用例的目的是生成一百万个随机数，分别存入到两个不同的deque中，将其中一个deque中的数据进行排序。将另一个deque中的数据拷贝到一个vector中，再将该vector中的数据进行排序，最后再将排序完的数据拷贝回原来的deque中。看一下它们的效率：
为什么选择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不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。
3.3 STL标准库中对于stack和queue的模拟实现
#include<deque>
namespace hyt
{
// stack 实现
template<class T, class Con = std::deque<T>>
class stack
{
public:
stack() // 默认调用自定义类的默认构造函数
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_back();
}
T& top()
{
return _c.back();
}
const T& top()const
{
return _c.back();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
Con _c;
};
// queue 实现
template<class T, class Con = std::deque<T>>
class queue
{
public:
queue() // 默认调用自定义类的默认构造函数
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_front();
}
T& back()
{
return _c.back();
}
const T& back()const
{
return _c.back();
}
T& front()
{
return _c.front();
}
const T& front()const
{
return _c.front();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
Con _c;
};
};