statck

1.statck 不是容器，而是适配器（container adaptor）,并且遵循后进先出的原则

statck的模拟实现

stack 就是一个特殊的vector，因此使用vector可以模拟实现stack

namespace bite
{template<class T>class stack{public:stack(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_back();}T& top(){return _c.back();}const T& top()const{return _c.back();}size_t size()const{return _c.size();}bool empty()const{return _c.empty();}private:std::vector<T> _c;};

这里面有一些关于二叉树的复习

首先

1.向上调整和向下调整都是需要你的左右子树都是一个堆

2.访函数的本质是一个类，里面重载了一个operator（），对象可以像函数一样使用。

3.一般c++不怎么使用函数指针，都是使用仿函数。

优先级队列

优先级队列是一种容器适配器，他的第一个元素都是他所包含的最大的元素。

也可以使用

<int vector<int>>
greater<int>

容器适配器

是一种设计模式，将一个类的接口转换成客户希望的接口

deque

是一个融合怪，将list和vector给融合了起来，头插和尾插的效率比较高，而且不需要搬运元素

deque不是一个真正的连续的空间，是有一个map带着一段又一段的像连续的数组

vector和list的优缺点

vector的优点

1.尾插和尾删的效率更高，而且由于像数组一样可以支持下标

2.物理空间是连续的，所以高速缓存利用率高

vector的缺点

1.空间要扩容，扩容有代价，比如说空间的浪费和效率都会受到影响

2.头部和中间要是像插入的话效率比较低

3.vector不支持头删

List的优点

1.按需申请空间，不需要扩容

2.支持任一位置的删除和插入

List的缺点

1.之前测试，vector和List的sort还是有差距的

deque的缺点

deque不适合遍历，遍历的效率比较低，中间的插入和删除的效率是O（n）。

编译器只会检查打的框架，最后会按需实例化，而不会全部实例化，