本章将介绍STL六大组件中的 —— 适配器,在此基础上再学习stack、queue和priority_queue的模拟实现和仿函数的应用场景,最后介绍一下一个新的数据结构deque……
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口

stack的学习文档:👉 传送门
操作:

stack对其容器的接口进行了包装,默认使用deque:

直接见代码:
void test_stack()
{
std::stack<int, vector<int>> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}
运行结果是:4 3 2 1
注意:
直接运用适配器,复用别的容器,stack默认是复用deque这个容器
namespace Joker
{
//deque,既有vector的优先,又有list的有点
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
我们复用的是deque的功能来实现stack的功能。
测试一下:
void test_stack1()
{
//可以复用以前容器的代码
//stack s;
stack<int, vector<int>> s;
//stack s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}
运行结果是:4 3 2 1
测试时候适配器用的是vector的容器,基于queue的结构而去适配合理的容器,因为vector尾插尾删除时间复杂度为〇(1),很方便…
注意:
queue的学习文档:👉 传送门

queue对其容器的接口进行了包装,默认使用deque:

直接见代码:
void test_queue()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
//不支持迭代器了,因为栈让随便遍历是不好的
//后进先出不好保证,性质就无法维护了
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
运行结果是:1 2 3 4
直接运用适配器,复用别的容器,queue默认是复用deque这个容器
namespace Joker
{
//队列的实现:
//deque,既有vector的优点,又有list的有点
//队列不支持vector的适配,因为vector是不支持pop_front的接口
//用适配器来适配 -- 不用自己实现
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
我们复用的是deque的功能来实现queue的功能。
测试一下:
void test_queue()
{
//queue q;
queue<int, list<int>> q;
//queue> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
运行结果:1 2 3 4
测试时候适配器用的是list,基于queue的结构而去适配合理的容器,因为list头插头删时间复杂度为〇(1),很方便…
注意:
仿函数 – 更高维度的泛型思想(不仅是数据类型的控制,更是逻辑的控制)
什么是仿函数:
仿函数(greater)为例:


这里就用到了仿函数:
假如我们给一个商品自定义类型:
//商品
struct Goods
{
string _name;
double _price;
size_t _saleNum;
//...
/*bool operator<(const Goods& g) const
{
return _price < g._price;
}*/
};
//仿函数 -- 更高维度的泛型思想(不仅是数据类型的控制,更是逻辑的控制)
struct LessPrice
{
bool operator()(const Goods& g1, const Goods& g2) const
{
return g1._price < g2._price;
}
};
struct GreaterPrice
{
bool operator()(const Goods& g1, const Goods& g2) const
{
return g1._price > g2._price;
}
};
struct LessSaleNum
{
bool operator()(const Goods& g1, const Goods& g2) const
{
return g1._saleNum < g2._saleNum;
}
};
测试:
void test_Functional()
{
//vector v = { 1, 2, 3, 4 }; -- C++11的用法
vector<int> v;
v.push_back(2);
v.push_back(1);
v.push_back(4);
v.push_back(5);
v.push_back(3);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//默认是升序 -- 默认传的是less
sort(v.begin(), v.end());
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//greater
sort(v.begin(), v.end(), greater<int>());
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//在优先级队列中是按照类的模板参数传的,在这里传的是对象,是函数模板自动推导
//指向数组的原生指针,本身就是天然迭代器
int a[6] = { 1, 2, 5, 2, 5, 7 };
sort(a, a + 6);
sort(a, a + 6, greater<int>());
//自定义类型就需要我们写仿函数了
Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
sort(gds, gds + 4, LessPrice());
sort(gds, gds + 4, GreaterPrice());
sort(gds, gds + 4, LessSaleNum());
sort(gds, gds + 4, GreaterSaleNum());
}
传仿函数的时候,我们只需要传自己写的那个仿函数就可以了…
补充:
priority_queue的学习文档:👉 传送门
底层是一个堆的结构,默认是一个大堆:

数据结构 — 堆 ,还不熟悉的同学看这里👀:👉 堆复习 - 传送门

直接见代码:
//底层是个堆(默认是个大堆) -- 底层用了vector
void test_priority_queue()
{
//greater库里写好了的仿函数
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(2);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
运行结果:1 2 5 6 8
注意:
默认仿函数传的是less – 应该是是个小于的仿函数
问题:
我们有吐槽的权利,但是没有质疑的权利~ 😁😁😁
1.模拟实现:
template<class T>
struct less
{
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
//缺省了两个参数,相传第三个参数必须传第三个参数,因为是从右往左缺省
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
priority_queue(const Compare& comFunc = Compare())
:_comFunc(comFunc)
{}
//优先级队列的另一个构造函数 -- 用一个区间去构造
//兼容使用函数指针
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Compare& comFunc = Compare())
:_comFunc(comFunc)
{
while (first != last)
{
_con.push_back(*first);
first++;
}
//建堆 -- 向下建堆
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}
//默认做个大堆
void AdjustUp(size_t child)
{
//Compare comFunc; //是一个仿函数
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (_comFunc(_con[parent], _con[child])) //空指针的话调用不到东西
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void AdjustDown(size_t parent)
{
//Compare comFunc;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
{
//默认认为左孩子大
child++;
}
//if (_con[parent] < _con[child])
if (_comFunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
//向下调整,时间复杂度logN
AdjustDown(0);
}
//避免拷贝构造提高效率,加上const是为了不让外部修改 -- 堆是不允许随便修改的
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Compare _comFunc;
Container _con;
};
这里用到了堆排序算法,不熟悉的小伙伴还看这里:👉 堆排序复习 - 传送门
2.测试:
(1) 不用仿函数,直接通过函数来比较大小,传函数指针:

(2) 传自己写的 仿函数/函数指针:
template<class T>
bool ComInitLess(T x1, T x2)
{
return x1 > x2;
}
//这里是写死了,只能写降序,不能写升序 -- C++引入了仿函数来解决这个问题
void test_priority_queue1()
{
//看着像函数名,其实是个对象,可以像调用函数一样去使用,实际上调用的是运算符重载
//less LessCom;
//cout << LessCom(1, 2) << endl;
//greater GreaterCom;
//cout << GreaterCom(1, 2) << endl;
//greater库里写好了的仿函数
//通过模板类型推导
priority_queue<int, vector<int>, greater<int>> pq;
//通过函数指针调用
//priority_queue, bool(*)(int, int)> pq(ComInitLess);
//priority_queue pq;
pq.push(2);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
运行结果:1 2 5 6
(3) 不传仿函数,用默认的缺省值仿函数:
void test_priority_queue2()
{
int a[] = { 1, 4, 2, 7, 8, 9 };
priority_queue<int> pq(a, a + 6);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
运行结果:9 8 7 4 2 1
适配:
(1) vector:
优点: 适合尾插尾删,随机访问,CPU高速缓存命中高
缺点:
a. 不适合头部或者中部插入删除,效率低,需要挪动数据
b. 扩容有一定性能消耗,还存在一定程度空间浪费。-- 因为删除数据不缩容
(2) list:
优点:
a.任意位置插入删除效率高。〇(1)
b.按需申请释放空间。
缺点:
a.不支持随机访问
b.CPU高速命中低
(3) deque:
deque是结合vector和list的优缺点产生的双端队列
优点:
a.头部和尾部插入删除数据效率不错
b.支持随机访问
c.扩容代价小
d.cpu高速缓存命中高
缺点:
a.中部的插入删除效率不行
b.虽然支持随机访问,但是效率相比vector而言还是有差距,频繁随机访问要小心