Ошибка реализации Circular DeQueue

Question

В основном динамический массив, который имеет круговое вращение при заполнении. У вас есть доступ к каждому элементу, и вы можете изменить его значение, однако вы можете вставлять и удалять только с обоих концов (постоянное время). Большинство методов, похоже, работают нормально, однако при некоторых «push» числах я получаю неправильный вывод.
Например, первый вход 1,2,3, затем я вставляю 4 в конец. Следующий выход: 2,3,4 Однако после ввода 5 в конце выход 2, 3, 5

Я понятия не имею, что вызывает это. Я размещаю весь исходный код ниже (по крайней мере функции, которые связаны с тестами, где ошибка должна скрываться). В файле есть какая-то документация и пример ошибки, если я не объяснил ситуацию четко.

#include <iostream> 

using namespace std; 

template <typename Object> 
class ArrayVector { 
private: 
    int capacity; // capacity 
    int sz; // number of elements 
    Object* a; 
    int f; // start of the indexes 
    int b; // end of the indexes 
public: 
    ArrayVector(int initCap); 
    ~ArrayVector(); 

    int size() const { return sz; } 
    bool isEmpty() const { return size() == 0; } 
    Object elemAtRank(int r); 
    void pushBack(const Object& e); 
    void pushFront(const Object& e); 
    void popBack(); 
    void popFront(); 
}; 

template <typename Object> // constructor 
ArrayVector<Object>:: 
ArrayVector(int initCap) { 
    capacity = initCap; 
    sz = 0; 
    a = new Object[capacity]; 
    f = 0; 
    b = 0; 
} 

template <typename Object> // gets the element at a certain rank 
Object ArrayVector<Object>:: elemAtRank(int r) 
{ 
    return a[(f + r) % sz]; // starting position in real array + r % number of elements 
} 




template <typename Object> 
void ArrayVector<Object>:: pushBack(const Object& e) 
{ 
    if(sz == capacity && sz > 0) // if the array is full time to spin it 
    { 
     if(f == capacity){   // Handles the front. 
      f = 0;    // if the front is equal to the capacity 
         // set it to zero, else increment 
     }else{ 
      f++; 
     } 
     if(b == capacity){  //Handles the back 
      b = 0;    //if the back is equal to the capacity 
      // cout<< "SC insert "<< e << " at "<< b <<endl; 
      a[b] = e; 
     }else{     // set it to zero, else increment 
      a[b] = e; 
      // cout<< "SC insert "<< e << " at "<< b <<endl; 
      b++; 
     } 
    }else{ 

     a[b] = e; 
     // cout<< "insert "<< e << " at "<< b <<endl; 
     b++; 
     sz++; 
    } 

} 

template <typename Object> 
    void ArrayVector<Object>:: pushFront(const Object& e) 
    { 
     if(f == 0){ 
      f = capacity-1; 
     }else{ 
      f--; 
     } 
     a[f] = e; 
     if(sz< capacity) 
      sz++; 
    } 

int main() 
{ 
    // Fill array and print it 
    cout << "Fill with numbers" << endl; 
    ArrayVector<int> asd(3); 
    asd.pushBack(1); 
    asd.pushBack(2); 
    asd.pushBack(3); 
    for(int i =0; i < asd.size(); i++) 
     cout << asd.elemAtRank(i) << endl; 
    //Test if it spins 
    cout << "BEGIN Spin TEST " << endl; 
    asd.pushBack(4); 
    cout << "First test is ok" << endl; 
    for(int i =0; i < asd.size(); i++) 
     cout << asd.elemAtRank(i) << endl; 
    // here the error comes 
    asd.pushBack(5); 
    cout << "On the second iteration things crash and burn" << endl; 
for(int i =0; i < asd.size(); i++) 
     cout << asd.elemAtRank(i) << endl; 
    return 0; 
} 

Answer 1

В дополнении к вашему времени вставки не соответствует вашим желаемым требованиям, ваш вопрос здесь:

template <typename Object> 
void ArrayVector<Object>:: pushFront(const Object& e) 
{ 
    if(f == 0) 
    { 
     f = capacity-1; 
    } 
    else 
    { 
     f--; 
    } 
    a[f] = e; // problem lies here! 

    if(sz < capacity) 
     sz++; 
} 

Вы выяснить, где сделать вставку, но вы не выдвигая другие элементы вокруг вектор; то есть вы просто перезаписываете элемент в точке ввода. Если вы хотите надавить на передний план, вам нужно будет скопировать остальные элементы по 1 позиции каждый, а затем сделать свою вставку. Лучшее решение (которое соответствовало бы вашему постоянному требованию времени ввода) было бы реализовать его как список с двойной связью. Нажимать на концах просто потребуется следующий псевдокод:

void push_front(const Object& o) 
{ 
    if (size == capacity) 
     l.pop_back(); 
    l.push_front(o); 
} 

Если вы действительно должны использовать непрерывный блок памяти, вы не получите вставки постоянного времени, но это будет выглядеть следующим образом:

// Assumptions: 0 is always the front, capacity-1 is always the maximum back 
template <typename Object> 
void ArrayVector<Object>:: pushFront(const Object& e) 
{ 
    // assume capacity > 0, move all the elements to the right one slot 
    for (int i = capacity - 1; i > 0; --i) 
    { 
     a[i] = a[i - 1]; 
    } 

    a[0] = e; 

    if(sz < capacity) 
     sz++; 
}