deque Implementierungsdetails

Question

ich Artikel über die Umsetzung der deque lese (Deques)

Hier ist der entsprechende Code:

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; 
    } 

In den Abbildungen ist klar, dass Anfangswert für firstBlock und first 2 Warum FirstBlock und FirstElement sind zunächst nicht 0?

Answer 1

Weil Sie jedes Mal, wenn Sie etwas von der Deque von der Vorderseite nehmen wollen, den Speicher nicht verschieben oder alles wieder auf Position 0 verschieben müssen. So behalten Sie einen Index zum ersten Block der Deque.