STL学习之——vector和deque

依据标准模板库（STL）-由惠普公司提供。
基于ANSI/ISO标准C++，在windows平台（C++ Builder\Visual C++）和Unix平台（G++）测试通过。

vector（向量）：是一个灵巧的数组，自动调整大小，并提供方法在任意位置插入和删除元素，而且向量是模板化的，将int类型元素插入int类型向量的方法和将string类型元素插入string类型向量的方法是完全相同的。有了向量之后可能再也不想用数组了。
向量比数组使用起来方便的多，向量是一个有限序列（连续存储）特色如下：

1. 给出序列中任何项的下标，可以在常数时间内完成访问或修改该下标对应的项。
2. 在向量尾部插入元素平均只需要常数时间，其中worstTime(n)是O(n)，n代表序列中项的数量。
3. 对序列尾部进行的删除操作，worstTime(n)是常数。
4. 任意的插入和删除，worstTime(n)和averageTime(n)都是是O(n)

实例：
    vectorwords;
    string word;
    for (int i = 0; i < 5; i++)
    {
        cin >> word;
        words.push_back (word);
    } // reading in words
    words.erase (words.begin());
    words.pop_back();
    for (unsigned i = 0; i < words.size(); i++)
        cout << words [i] << endl;

deque（双端队列）：队列（double end queue双端队列）和向量很相似，但是实现细节上有较大的差别。
双端队列是一个有限序列，特色如下：

1. 给出序列中任何项的下标，可以在常数时间内完成访问或修改该下标对应的项（与向量相同）。
2. 平均情况下，在序列头或尾部插入只耗费常数时间，但是worstTime(n)是O(n)，n代表序列中项的数量。（与向量不同，向量在头部插入代价比较大）
3. 对序列尾部进行的插入和删除操作，worstTime(n)是常数。
4. 任意的插入和删除，worstTime(n)和averageTime(n)都是是O(n)

由此可见，双端队列对象可以在他自身的首尾快速的插入和删除，而向量对象只有在尾部才能快速的插入和删除。deque类比vector类多了两个方法：
//在双端队列的开头插入一个x的拷贝，averageTime(n)是常数，worstTime(n)是O(n)
void push_front(const T& x);
//删除双端队列开头的项,worstTime(n)是常数
void pop_front();
实例：
    dequewords;
    string word;
    for (int i = 0; i < 5; i++)
    {
        cin >> word;
        words.push_back (word);
    } // for
    words.pop_front( );
    words.pop_back( );
    for (unsigned i = 0; i < words.size(); i++)
        cout << words [i] << endl;
总结：
除非大多数操作都位于或者接近容器的开头，否则向量是比双端队列快的。向量比数组功能强大的多。向量自动调整大小，当超出当前容量时候就创建一个双倍大小的数组，并把向量copy到这个大的数组里。更大的优势在于插入和删除。