deque是如何实现的？如何实现的双端快速插入和删除

deque是怎么实现的？怎么实现的双端快速插入和删除？
deque是怎么实现的？怎么实现的双端快速插入和删除？
采用了什么数据结构？具体思路是如何？
------解决方案--------------------
分块存储，push_back时可能会创建新块加到末尾，push_front时可能会创建新块放在开头。随机访问时用总索引号计算块号和局部索引号。

它其实就是个数组的数组。
------解决方案--------------------
他们不是连续的一块内存，是很多块内存，这些内存块的指针再放在一个指针数组中，访问时要用index进行计算，算出块索引和局部索引，然后：
return data[block_index][local_index];
------解决方案--------------------

unsigned int begin_index;//第一个元素在第一个数组中的位置

unsigned int const block_size = 64;//每个块的大小

T data**;//数据是数组的数组

T & operator[]( unsigned index )

{

  index += begin_index;

  unsigned int block_index = index / block_size;

  index %= block_size;

  return data[block_size][index];

}

一般情况下，第一个块的前面是空的，最后一个块的后面是空的，其余块都是64个元素。
------解决方案--------------------
你们都用的什么编译器

------解决方案--------------------
数组的链表。
------解决方案--------------------
STLport里是数组的数组，不是链表：

template <class _Tp>

struct _Deque_iterator_base {


  enum _Constants {

    _blocksize = _MAX_BYTES,

    __buffer_size = (sizeof(_Tp) < (size_t)_blocksize ?

                  ( (size_t)_blocksize / sizeof(_Tp)) : size_t(1))

  };


  typedef random_access_iterator_tag iterator_category;


  typedef _Tp value_type;

  typedef size_t size_type;

  typedef ptrdiff_t difference_type;


  typedef value_type** _Map_pointer;//关键就是它


  typedef _Deque_iterator_base< _Tp > _Self;


  value_type* _M_cur;

  value_type* _M_first;

  value_type* _M_last;

  _Map_pointer _M_node;//数据在这里


//...


  void _M_advance(difference_type __n) {

  //这个函数的作用是让迭代器加上一个偏移量

  //它是容器实现随机访问的关键

  //STLport中容器的operator[]基本上就一句：return * (begin() + i );


    difference_type __offset = __n + (_M_cur - _M_first);

    if (__offset >= 0 && __offset < difference_type(__buffer_size))

    //如果与当前迭代器在同一块内

      _M_cur += __n;

    else {

    //否则要找到目标块

      difference_type __node_offset = //

        __offset > 0 ? __offset / __buffer_size

                   : -difference_type((-__offset - 1) / __buffer_size) - 1;