stack
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.
上述描述出自cplusplus.
重点是stack是一个container adaptor也就是容器适配器。
这意味着我们不需要也没有必要从0开始实现stack的方法，而可以通过一个模板，来调用其他容器来实现，以下是stack的部分从成员函数：
template<class T, class Container = deque<int>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& top()
{
return _con.back();
}
private:
Container _con;
};
可以发现只需要调用传来的模板参数即可。
这里的默认容器是deque，这是一个均衡的容器，整体效率没有vector高，但是可以实现push_front。这是vector做不到的，或者说vector的头插效率是O(n)，过低。
值得注意的是，所有容器适配器都不支持迭代器。
就以stack举例，如果支持迭代器，那是否意味着破坏了他的FILO特性呢？是的。因此不支持迭代器。
reverse_iterator
上文提到容器适配器，那就不得不提到反向迭代器了。
之前我们实现vector和list的时候都没有实现反向迭代器，因为两者内容过于相似，现在了解了反向迭代器的机制后我们知道，是否可以通过穿入迭代器容器，然后实现反向迭代器。
这意味着，我们可以同时实现所有容器的反向迭代器，也就是实现他们的模板：
template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Iterator _it;
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator tmp = _it;
return *((--tmp));
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
return --_it;
}
Self& operator--()
{
return ++_it;
}
bool operator!=(const Self& it)
{
return _it != it;
}
};
需要注意的一点是，我们的operator*返回的是 *（--tmp)，而不是 *（tmp).
原因是，我们的rbegin（）和rend（）返回的是end()和begin（）。这是基于代码对称性考虑的，正常而言我们的rbegin（）和rend（）理应返回end()-1和begin（）-1.
为了解决这个问题，就只能令operator*返回 *（--tmp)。
注：以上实现是visual studio的实现方式。
queue
template<class T, class Container = deque<int>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
private:
Container _con;
};
priority_queue
priority_queue实质上就是一个堆，并且是默认大根堆。那么我们想要将其改变为小根堆改如何实现？
如果是C语言的话，我们会增加一个函数指针的参数来实现。
在C++中，我们通过传入一个仿函数来实现。
仿函数
所谓仿函数就是指能够像函数一样使用的对象，如下：
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
void test(int x,int y)
{
less l;
if(l(x,y))cout<<"x<y";
else cout<<"x>=y";
}
本质上，我们重载了 ()，因此能够将这个对象像函数一样使用。
具体代码
堆的实现，我们已经讲过，这里就不做赘述，感兴趣的读者可以翻阅我前面的文章。
template<class T,class Container=vector<T>,class Compare = less<T>>
class priority_queue
{
public:
//默认大堆
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
Compare com;
while (child >0)
{
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
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(size_t parent)
{
size_t child = parent * 2 + 1;
while (child<_con.size())
{
if (child + 1 < _con.size() && com(_con[child],_con[child+1]))
{
++child;
}
if (com(_con[parent],_con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
const T& top()
{
return _con[0];
}
private:
Container _con;
};
说起来这里比较奇怪的点是，默认传入less<T>是大根堆，而穿入greater<T>却是小根堆。
但sort穿入，less<T>却是升序排序：
int main()
{
vector<int>v = { 1,5,4,3,2 };
sort(v.begin(), v.end(),less<int>());//传入less的匿名对象
for (auto& e : v)cout << e << ' ';
cout << endl;
return 0;
}
Output:1 2 3 4 5