2

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?

3
  • I think you're mistaken, end() and begin() will never be the same unless the collection is empty. Please explain your supposition.
    – david.pfx
    Feb 2, 2014 at 7:14
  • Suppose the deque has 4 elements and capacity of the array of the deque is also 4. Now the deque can be considered as full. Now suppose we are maintaining front and rear pointers on the array. So as the queue is full,front and rear should point next to each other. But as deq.end() points to past-the-end element, it will point to the element next to rear which is front. Hence,problem is that above for loop will never enter in its body. Please ask if further is required.
    – ganeshwani
    Feb 2, 2014 at 7:15
  • I suggest you write some code and satisfy yourself that this is not what happens. Feel free to amend your question accordingly.
    – david.pfx
    Feb 2, 2014 at 8:13

1 Answer 1

3

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.

3
  • you are right. But what if we are implementing a deque with array of elements as a circular buffer. Then where are you supposed to point the end()?
    – ganeshwani
    Feb 2, 2014 at 16:59
  • 1
    @ganeshwani: You can't really use a circular buffer as underlying container for a deque, as it is supposed to be able to grow (nearly) indefinitely. For how to implement iterators on a circular buffer, that is a topic for a separate question (on StackOverflow). Feb 2, 2014 at 17:34
  • :Thanks a lot.Thats was a great help. I will check it.
    – ganeshwani
    Feb 2, 2014 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.