C++ – Implementation of deque in C++ with an array

c

How is the end() function implemented in deque-STL of C++ with array?

As per my knowledge it returns past-the-end element. But when a loop is run like, for(i=deq.begin();i!=deq.end();i++) and the whole array is full (suppose size=4), then I think end() will point to the position where begin() is pointing, in this way it won't go in the for loop.

How to resolve this problem?

Best Answer

You seem to be confusing a deque (double ended queue) with a circular buffer.

In a circular buffer you are right that when the buffer is full, the 'one past the last' element coincides with the first element. When implementing iterators for a circular buffer, this needs to be taken into account to avoid confusing an empty buffer with a completely filled one.

A deque can best be visualised as a row of elements where you can add elements at either end. This should also make it clear that there is no way for end() to equal begin() except for an empty queue, because there is no point where the two ends come together again.

Related Topic