c++ vector和deque的区别

用c++解Min Stack的时候被Memory Limit Exceeded搞的很头痛，自己写过链表、空间可增长的数组，用了stl的vector、deque，最后是deque的实现可以通过，搜了下也有用stack过的。
在这里记录下deque&stack跟其他实现的区别。

这是cplusplus deque页面的讲的vector和deque实现的区别：

Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators). Therefore, deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.

vector用的是一个数组，剩余空间不够时申请一个size-doubled的新数组，然后把原数据拷贝过来。而deque因为是双向的，如果还是像vector这种实现方式空间浪费会比较多，所以使用了多个chunk存储数据，然后用一个T*进行索引，当空间不够时新分配一个chunk，chunk大小也是固定的。

leetcode一组测试数据共插入7w个整数，需要空间28w bytes，大于等于该值的最小的2的幂次方是2^18=524288，使用vector消耗的差不多就是这么大，额外消耗238kb，即使用vector::resize()预分配空间也依赖于内存分配器的行为。
使用deque的话，数据存储空间大约是(28w/512+1)*512 byte，最多浪费512字节；索引的话，28w/512=546， 索引占用1024*sizeof(int*)，额外消耗4.5kb(64位8.5kb)。deque里每个chunk大小的计算公式如下：

item_size = sizeof(T)
(item_size < 512 ? (512 / item_size) : 1) * item_size

stl里的stack是一种container adaptor，底层使用deque实现，因此内存消耗与deque相同。

这篇文章link介绍了deque的实现，图画的很好。
stl的实现原理可以参考侯捷的《STL源码剖析》和stl代码。

min stack实现代码：

#include <cstddef>
#include <deque>

using namespace std;

class MinStack {
    deque<int> stack;
    deque<int> min;
public:
    void push(int x) {
        stack.push_back(x);
        if (min.size() <= 0 || x <= min.back()) {
            min.push_back(x);
        }   
    }   
    void pop() {
        int stack_last = stack.back();
        stack.pop_back();
        int min_last = min.back();
        if (stack_last == min_last) {
            min.pop_back();
        }   
    }   
    int top() {
        return stack.back();
    }   
    int getMin() {
        return min.back();
    }   
};