目录
容器适配器
deque的原理介绍
stack模拟实现
queue模拟实现
priority_queue模拟实现
仿函数
容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。AI给出这样解释：
可以这样理解：通过适配器模式，可以将不兼容的接口正常运作。
STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配 器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：
那么这里的deque是什么东西呢？
deque的原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。
我们假设一个buff是10个int大小的空间数组，map中存放了每个buff数组的地址，buff数组用来存放数据，可以理解他从中间开始利用空间，向左右扩容。
我们可以理解为他在map中间进行插入删除操作：
- 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
- 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
为什么选择deque作为stack和queue的底层默认容器？我们给出了以下两点原因：
- stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
- 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长 时，deque不仅效率高，而且内存使用率高。
stack模拟实现
目前为止，我们已经了解了两种模式：
- 适配器模式 -- 封装转换
- 迭代器模式 -- 封装统一访问方式（数据结构访问都可以用）
接下来试着通过运用适配器来模拟实现stack和queue：
//Stack.h
#pragma once
namespace bit
{
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();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
_con.size();
}
private:
Container _con;
};
}
我们只需要定义一个适配器类型的成员变量_con，他默认可以使用push_back，pop_back等常规接口，直接利用接口实现操作即可。stack用vector和list都可以实现，测试代码如下：
void test_stack()
{
//bit::stack<int, vector<int>> s;
//bit::stack<int, list<int>> s;
bit::stack<int, deque<int>> s;
//bit::stack<int> s; //不传第二个参数默认使用deque
s.push(1);
s.push(2);
s.push(3);
s.push(4);
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}queue模拟实现
//Queue.h
#pragma once
namespace bit
{
// deque list
// 不支持vector
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
// 这样就可以支持vector了，但是效率就很低了
//_con.erase(_con.begin());
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
_con.size();
}
private:
Container _con;
};
}注意：queue不支持vector适配器，原因是vector没有pop_front的接口，如果要实现要用erase接口，但是头删完后面所有数据要往前挪，消耗时间太大，不建议这样做。测试代码如下：
void test_queue()
{
bit::queue<int> q;
//bit::queue<int,list<int>> q;
// 不支持
//bit::queue<int, vector<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}priority_queue模拟实现
仿函数
在实现之前先了解仿函数的概念：重载了operator（）的类
特点：参数个数和返回值根据需求确定，不固定，很灵活
通过这个概念可以实现STL库里的greater和less同等效果的仿函数。
//priority_queue.h
#pragma once
namespace bit
{
template<class T>
class myless
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class mygreater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T, class Container = vector<T>, class Comapre = myless<T>>
class priority_queue
{
public:
priority_queue() = default;
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
void adjust_up(int child)
{
Comapre comfunc;
int parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (comfunc(_con[parent], _con[child]))
//if (comfunc.operator()(_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);
adjust_up(_con.size() - 1);
}
void adjust_down(int parent)
{
Comapre 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()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}我们可以通过显式调用greater仿函数来实现小堆，测试代码如下：
void test_priority_queue()
{
//vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
//priority_queue<int> q1(v.begin(), v.end());
int a[] = { 3,2,7,6,0,4,1,9,8,5 };
// 默认是大堆
//bit::priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));
// 小堆
bit::priority_queue<int, vector<int>, bit::mygreater<int>> q1(a, a + sizeof(a) / sizeof(int));
while (!q1.empty())
{
cout << q1.top() << " ";
q1.pop();
}
cout << endl;
}
