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 &lt;class _Tp&gt;
struct _Deque_iterator_base {

  enum _Constants {
    _blocksize = _MAX_BYTES,
    __buffer_size = (sizeof(_Tp) &lt; (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&lt; _Tp &gt; _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 &gt;= 0 && __offset &lt; difference_type(__buffer_size))
    //如果与当前迭代器在同一块内
      _M_cur += __n;
    else {
    //否则要找到目标块
      difference_type __node_offset = //
        __offset &gt; 0 ? __offset / __buffer_size
                   : -difference_type((-__offset - 1) / __buffer_size) - 1; 
 
    //计算块号，与我上面写的block_index = index / block_size;功能相当，
    //不过它是相对索引，要处理负数情况

      _M_set_node(_M_node + __node_offset);
    //上面这一句找到所需的块，用的也是随机访问，
    //_M_node看成数组的话，上面的代码可以理解为set_node( & m_node[node_offset] );

      _M_cur = _M_first +
        (__offset - __node_offset * difference_type(__buffer_size));
     //cur = first + offset % buffer_size
     //由于商__node_offse已经知道了，用乘法和减法代替模运算计算速度会快一些。
    }
  }

用链表每次随机访问都慢，用数组则是某一次push_front时稍慢，还是用数组合理。

[解决办法]
stl源码剖析里有详细讲解

deque是如何实现的？如何实现的双端快

热点推荐