STL之顺序容器 deque 动态数组

　　deque是一个动态数组，deque与vector非常类似，vector是一个单向开口的连续线性空间，deque则是双向开口的连续线性空间。两者唯一的区别是deque可以在数组的开头和末尾插入和删除数据，而vector只能在末尾插入删除数据（当然，从技术层面上，vector也可以从首尾两端进行操作，但是其从头部操作效率奇差，无法接受）。

　　　　

　　　　　　　　　　　　　　　　　deque示意图

实质：

　　deque(包含头文件#include<deque>)由若干段连续空间串接而成，一旦有必要在deque的头部或尾端增加新的空间，便配置一段定量连续的空间，串接在deque的头部或尾端。deque的最大任务，就是在这些分段连续的空间上维护其整体连续的假象，并提供随机存取的接口。

　　实际上。deque内部会维护一个map作为主控（注意！不是STL中的map容器），即一小块连续的空间，该空间中每个元素都是指针，指向另一段（较大的）区域，这个区域称为缓冲区（deque的存储主体），缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。它首次插入一个元素，默认会动态分配512字节空间，当这512字节空间用完后，它会再动态分配自己另外的512字节空间，然后虚拟地连在一起。deque的这种设计使得它具有比vector复杂得多的架构、算法和迭代器设计。它的随机访问和遍历性能比vector差。

deque是一种优化了的对序列两端元素进行添加和删除操作的基本序列容器。通常由一些独立的区块组成，第一区块朝某方向扩展，最后一个区块朝另一方向扩展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块，而是多个连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。

　　deque没有所谓的容量观念，因为他是动态的一分段连续的空间组合而成，随时可以增加一段新的空间并链接起来。

　　虽然deque也提供了随机访问迭代器（Ramdon Acces Iterator)，但是它的迭代器并不是普通的指针，这当然会影响各个运算层面。因此，除非必要，我们尽可能地选择vector而非deque.

　　在对deque进行排序操作的时候，为了提高效率先将deque中的元素完整地复制到vector中，然后再vector中进行排序，在复制回到deque中.

　　

一.成员函数

构造函数与析构函数：

迭代器访问操作函数

这里c代表常量const，r代表reverse逆操作.

值访问操作和状态判定操作

注意没有提供容量操作capacity()。除了at()，没有任何成员函数会检查索引或迭代器是否有效。元素的插入或删除可能导致内存重新分配，所以任何插入或删除动作都会使所有指向deque元素的指针、引用和迭代器失效。惟一例外的是在头部或尾部插入元素，操作之后，指针和引用仍然有效，但迭代器将失效。

值修改操作

注意，pos为迭代器类型。仅仅只有使用erase操作及删除数据操作才会返回指向下一个数据的迭代器。push_back()或push_front()插入元素时发生异常，不会抛出异常。另外还包括赋值函数assign()，如下：

#include <iostream>

#include <deque>

int main ()

{

  std::deque<int> first;

  std::deque<int> second;

  std::deque<int> third;

  first.assign (,);             // 7 ints with a value of 100

  std::deque<int>::iterator it;

  it=first.begin()+;

  second.assign (it,first.end()-); // the 5 central values of first

  int myints[] = {,,};

  third.assign (myints,myints+);   // assigning from array.

  std::cout << "Size of first: " << int (first.size()) << '\n';

  std::cout << "Size of second: " << int (second.size()) << '\n';

  std::cout << "Size of third: " << int (third.size()) << '\n';

  return ;

}

代码2：常见操作

#include <deque>

#include <cstdio>

#include <algorithm>

using namespace std;

int main()

{

    deque<int> ideq(); //Create a deque ideq with 20 elements of default value 0

    deque<int>::iterator pos;

    int i;

    for (i = ; i < ; ++i)

        ideq[i] = i;

    printf("输出deque中数据:\n");

    for (i = ; i < ; ++i)

        printf("%d ", ideq[i]);

    putchar('\n');

    //在头尾加入新数据

    printf("\n在头尾加入新数据...\n");

    ideq.push_back();

    ideq.push_front(i);

    //输出deque

    printf("\n输出deque中数据:\n");

    for (pos = ideq.begin(); pos != ideq.end(); pos++)

        printf("%d ", *pos);

    putchar('\n');

    //查找

    const int FINDNUMBER = ;

    printf("\n查找%d\n", FINDNUMBER);

    pos = find(ideq.begin(), ideq.end(), FINDNUMBER);//注意迭代器类型在此查找

    if (pos != ideq.end())

        printf("find %d success\n", *pos);

    else

        printf("find failed\n");

    //在头尾删除数据

    printf("\n在头尾删除数据...\n");

    ideq.pop_back();

    ideq.pop_front();

    //输出deque

    printf("\n输出deque中数据:\n");

    for (pos = ideq.begin(); pos != ideq.end(); pos++)

        printf("%d ", *pos);

    putchar('\n');

    return ;

}

二.容器的选择

1.强调快速随机访问。则vector要比list好得多 。
          2.已知要存储元素的个数。vector 好于list。  
          3.强调增删且不要在两端插入修改元素。则list显然要比vector好。  
          4.除非我们需要在容器首部插入和删除元素，deque好于vector。因为vector仅仅在尾部增删快速。
          6.如果只需要在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑输入时将元素读入到一个List容器，然后排序，然后将排序后的list容器复制到一个vector容器中。
          5.如果只在容易的首部和尾部插入数据元素，则选择deque.