CODEWITHSUNDEEP
c++arraysvectorstl
molinab297
molinab297

Reputation: 241

Advice on how to implement std::vector using a circular array?

I am to write a C++ program that :

"Implements the vector ADT by means of an extendable array used in a circular fashion, so that insertions and deletions at the beginning and end run in constant time. (So not O(n)). Print the circular array before and after each insertion and deletion, You cannot use the STL."

This task seems very confusing to me. A std::vector is implemented using a dynamic array that is based off the concept of a stack, correct? Performing a deletion or insertion at the front seems to me that this should be implemented as a Queue or maybe a Dequeue, not a Vector. Also, a circular array would mean that when data is pushed onto an array that is Full, old data becomes overwritten, right? So when should I know to expand the vector's capacity?

If I'm not making sense here, Basically I need help in understanding how I should go about implementing a dynamic circular array..

Yes, this is a homework assignment. No, I do not expect anyone to provide code for me, I only wish for someone to give me a push in the right direction as to how I should think about implementing this. Thank you.

Upvotes: 2

Views: 1521

Answers (2)

2785528
2785528

Reputation: 5576

1) m_nextIn and m_nextOut - data attributes of class queue;

I find it useful to have two integers, with label m_nextIn and m_nextOut ... these identify where in the circular array you 'insert' the next (i.e. youngest) obj instance into the queue, and where you 'delete' the oldest obj instance from the queue.

These two items also provide constant time insert and delete.

Don't get confused as to where the beginning or end of the queue is. The array starts at index 0, but this is not the beginning of your queue. The beginning of your queue is at nextIn (which probably is not 0, but may be). Technique also known as round-robin (a research term).

2) empty and full - method attributes

Determining queue full / empty can be easily computed from m_nextIn and m_nextOut.

3) extendable

Since you are prohibited from using vector (which itself is extendable) you must implement this functionality yourself.

Note about your comment: The "dynamic memory" concept is not related to stack. (another research term)

Extendable issues occur when your user code invokes the 'insert' AND the array is already full. (capture this test effort) You will need to detect this issue, then do 4 things:

3.1) allocate a new array (use new, and simply pick an appropriate size.)

Hint - std::vector() doubles it's capacity each time a push_back() would overflow the current capacity

3.2) transfer the entire contents of the array to the new array, fixing all the index's as you go. Since the new array is bigger, just insert trivially.

3.3) delete the old array - i.e. you copied from the old array to the new array, so do you 'delete' them? or simply delete the array?

3.4) finish the 'insert' - you were in the middle of inserting another instance, right?

Good luck.

Upvotes: 1

Oskar Hýbl
Oskar Hýbl

Reputation: 401

I think you are actually being asked to implement deque. The point of the "circularity" is that in normal vector you cannot add an element at the beginning since there is no free space and you would have to move all other elements to the right. So what you can do is you simulate a circle by putting the element to the end the base array and remember that's where the first element is.

Example: 2, 3, -, -, 1 where 1 is first and 3 is last

So, basically you insert elements circullary, and remember where the first and the last elements are so you can add to beginning/end in O(1). Also when the array is full, you have to move all the elements to a larger one. If you double the size, you still get amortized time of O(1)

Upvotes: 2

Related Questions