适配器是一种设计模式,设计模式是一套被反复使用的、多数人知道的、经过分类编目的、代码设计经验的总结,该模式是将一个类的接口转换成客户希望的另外一个接口。
电源适配器:
在STL中将stack
和queue
划分为容器适配器,STL中的stack
和queue
只是对其他容器的接口进行了封装。
stack
的特点是后进先出,我们完全可以用vector
分装一个栈出来。但是STL中stack
和queue
默认是使用deque
缺省的。
//container会适配出stack
//template<class T, class container = deque<T>>
template<class T, class container = vector<T>>
class stack
{
public:
//vector是类类型,会自动调用它的构造和析构
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
container _con;
};
deque
(双端队列):是一种双开口的“连续”空间的数据结构,可以在头尾两端进行插入和删除,且时间复杂度为O(1)。与vector
比较,头插效率高,不需要搬移元素;与list
比较,空间利用率较高。
deque
并不是真正连续的空间,而是由一段段连续的小空间拼接而成,实际deque
类似于一个动态二维数组。
| vector
和list
优缺点比较:
vector | list | |
---|---|---|
优点 | 尾删尾插效率较高,支持下标随机访问;物理空间连续,高速缓存利用率高 | 按需申请空间,不需要扩容;任意位置插入删除 |
缺点 | 扩容导致效率和空间浪费;头部中部插入删除效率低 | 不支持下标随机访问 |
| 选择deque
做stack
和queue
底层默认容器的理由:
stack
和queue
不需要遍历(因为stack
和queue
没有迭代器),只需要在固定的一端或者两端进行操作。stack
中元素增长时,deque
比vector
的效率高(扩容时不需要搬移大量数据);queue
中的元素增长时,deque
不仅效率高,而且内存使用率高。所以优先级队列不是简单的先进先出:
int main()
{
priority_queue<int> pq;
pq.push(1);
pq.push(6);
pq.push(3);
pq.push(2);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}
make_heap
、push_heap
和pop_heap
来自动完成此操作vector
作为其底层存储数据的容器,在vector
上又使用了堆算法将vector
中元素构造成堆的结构,因此priority_queue
就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue
。所以默认情况下priority_queue
是大堆优先级队列可以简单地说就是在维持堆的结构下不断的取堆顶数据。
namespace yjz
{
template<class T, class container = vector<T>>
class priority_queue
{
public:
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(size() - 1);
}
void AdjustDown(size_t parent)
{
//假设左孩子小
size_t child = 2 * parent + 1;
while (child < size())
{
if ((child + 1) < size() && _con[child] < _con[child + 1])
{
child++;
}
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
container _con;
};
}
上面实现的priority_queue
是大堆,如果想让我们的pritrity_queue
可以在大堆小堆之间随意切换,需要用到仿函数。
仿函数是一个类,重载了operator()
,它的对象可以像函数一样使用,大多都是没有成员变量的类。
比较两个数的大小:
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;
}
};
在我们实现的priority_queue
中加入上面的仿函数:
#include <iostream>
#include <vector>
using namespace std;
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;
}
};
namespace yjz
{
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
void AdjustUp(size_t child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[child] > _con[parent])
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(size() - 1);
}
void AdjustDown(size_t parent)
{
Compare com;
//假设左孩子小
size_t child = 2 * parent + 1;
while (child < size())
{
//if ((child + 1) < size() && _con[child] < _con[child + 1])
if ((child + 1) < size() && com(_con[child], _con[child + 1]))
{
child++;
}
//if (_con[child] > _con[parent])
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
需要注意的是:
Less<T>
,如果不传参数,默认还是大堆如果要建小堆需要传对应的仿函数:
template<class T, class Container = vector<T>, class Compare = Less<T>>
模版参数中仿函数的缺省值给的是类类型,所以在调用了仿函数的函数中首先应该先用Compare
实例化出仿函数的对象,再用这个对象调用仿函数。以向上调整函数为例: