Vardan Hovhannisyan Vardan Hovhannisyan -4 years ago 154
C++ Question

deque implementation details

I am reading article about the implementation of deque(Deques)

Here is the corresponding 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 the illustrations it is clear that initial value for firstBlock and firstElement is 2.
Why firstBlock and firstElement initially are not 0?

Answer Source

Because every time you want to take something off the deque from the front, you dont want to have to move the memory or shift everything back up to position 0. So you keep an index to the first block of the deque.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download