双端队列实现细节

Question

我正在阅读有关 deque(Deques) 实现的文章

对应代码如下：

 template <class T>
    class deque
    {
    public:
      ⋮
    private:
      size_type theSize;
      T** blockmap;
      size_type mapSize;
      size_type firstBlock;
      size_type firstElement;

      const static size_type BlockSize = 4096;
      static size_type numElementsInBlock;
    };

    template <class T>
    deque<T>::dqPosition  
        deque<T>::indexAt (deque<T>::size_type n) const
    {
      dqPosition pos;
      pos.blockNum = firstBlock;
      if (n < numElementsInBlock - firstElement)
        {
          pos.elementNum = n + firstElement;
        }
      else
        {
          n -= numElementsInBlock - firstElement;
          ++pos.blockNum;
          int k = n / numElementsInBlock;
          pos.blockNum += k;
          pos.elementNum = n - k*numElementsInBlock;
        }
      return pos;
    }

在插图中很明显，firstBlock 和 firstElement 的初始值为 2。为什么 firstBlock 和 firstElement 最初不为 0？

Answer 1

因为每次你想从前面的双端队列中取出一些东西，你不想移动内存或将所有东西都移回位置 0。所以你保留一个索引到双端队列的第一个块.

双端队列实现细节

deque implementation details

c++

deque