适配器：适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
stack和queue
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack和queue只是对其他容器的接口进行了包装 ，STL中stack和queue默认使用deque
deque（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，相比list增加[]运算符重载。
详细介绍：deque概述
使用vector的接口实现stack的功能
#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace zwj
{
template<typename T, typename Contaner = vector<T>>
class stack
{
public:
size_t size() const
{
return _con.size();
}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
const T& top() const
{
return _con.back();
}
bool empty() const
{
return _con.empty();
}
void swap(stack& st)
{
_con.swap(st._con);
}
private:
Contaner _con;
};
}
使用list的接口实现queue的功能
#pragma once
#include <iostream>
#include <list>
using namespace std;
namespace zwj
{
template<typename T, typename Contaner = list<T>>
class queue
{
public:
size_t size() const
{
return _con.size();
}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
const T& back() const
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& front() const
{
return _con.front();
}
bool empty() const
{
return _con.empty();
}
void swap(queue& q)
{
_con.swap(q._con);
}
private:
Contaner _con;
};
}
优先级队列，底层就是一个堆结构。
priority_queue比stack和queue多了一个比较类的函数，默认传的是less<T>（大端），传greater<T>才会是小堆。
比较类的函数就是重载了operator()的类
#pragma once
#include <iostream>
#include <vector>
#include <functional>
#include <assert.h>
using namespace std;
namespace zwj
{
template<typename T, typename Contaner = vector<T>, typename Compare = less<T>>
class priority_queue
{
public:
void adjust_down(size_t parent)
{
assert(parent <= _con.size());
size_t child = parent * 2 + 1;
size_t sz = _con.size();
Compare com;
while (child < sz)
{
if (child + 1 < sz && com(_con[child], _con[child + 1]))
child++;
if (com(_con[parent], _con[child]))
{
::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void adjust_up(size_t child)
{
assert(child < _con.size());
size_t parent = (child - 1) / 2;
Compare com;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
priority_queue()
{}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: _con(first, last)
{
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
const T& top() const
{
return _con[0];
}
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
void pop()
{
::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
void swap(priority_queue& pq)
{
_con.swap(pq._con);
}
private:
Contaner _con;
};
}
反向迭代器的功能与正向迭代器是一样的，只是遍历的顺序不同，符合适配器模式，所以可以通过正向迭代器的接口实现反向迭代器。
注意事项：
begin和end是相对的，所以反向迭代器总是指向需要访问元素的后一个元素以list的反向迭代器为例：
template<typename Iterator, typename Ref, typename Ptr>
class __reserve_iterator
{
public:
typedef __reserve_iterator<Iterator, Ref, Ptr> self;
// 正向迭代器
Iterator _cur;
// 通过正向迭代器构造反向迭代器
__reserve_iterator(Iterator cur)
: _cur(cur)
{}
// 反向操作
self& operator++()
{
--_cur;
return *this;
}
self operator++(int)
{
self tmp(_cur);
--_cur;
return tmp;
}
self& operator--()
{
++_cur;
return *this;
}
self operator--(int)
{
self tmp(_cur);
++_cur;
return tmp;
}
// 先++(反向++）后访问
Ref operator*()
{
auto tmp = _cur;
--tmp;
//self tmp(_cur);
//++tmp;
return *tmp;
}
Ptr operator->()
{
return &(operator*());
}
bool operator!=(const self& it)
{
return _cur != it._cur;
}
};