deque的實現細節

Question

我念叨雙端隊列的實施文章（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.因此，你需要保留一個索引到第一個塊。