Увеличение емкости циклической очереди в C++

Я изучаю очереди и пытаюсь написать метод для изменения максимальной емкости циклической очереди с использованием динамического массива. Вот как выглядит мой код прямо сейчас.

void ArrayQueue::setCapacity(unsigned newCapacity){
if(newCapacity == 0 || newCapacity < this->getSize()){
    throw QueueException("setCapacity()", "invalid new capacity");
} else if(newCapacity != this->getSize()){
    Item * tempArray = new Item[newCapacity];
    for(unsigned i=0; i<newCapacity; i++){
        tempArray[i] = myArray[i];
    }
    Item * oldArray = myArray;
    myArray = tempArray;
    delete [] oldArray;
}
this->myCapacity = newCapacity;
}

Однако, когда я уменьшаю емкость, мне не удается получить значения myFirst и myLast. Я понимаю, что мне нужно написать код для учета случая, когда записи перевернуты, но не понимаю, как это сделать.

Тест, который я пытаюсь пройти, имеет следующий код:

    ArrayQueue q5(10);
for (int i = 0; i < 10; i++){
    q5.append(i+1);
}
for (int i = 0; i < 7; i++){
    q5.remove();
}
assert( q5.getCapacity() == 10 );
assert( q5.getSize() == 3 );
assert( !q5.isEmpty() );
assert( !q5.isFull() );
assert( q5.getFirst() == 8 );
assert( q5.getLast() == 10 );

//reduce the capacity
q5.setCapacity(5);
assert( q5.getCapacity() == 5 );
assert( q5.getSize() == 3 );
assert( !q5.isEmpty() );
assert( !q5.isFull() );
assert( q5.getFirst() == 8 );
assert( q5.getLast() == 10 );

Я передаю свой первый набор утверждений, но второе утверждение getFirst терпит неудачу.

Не могли бы вы дать мне указатель в правильном направлении? Спасибо.


c++ arrays dynamic queue capacity
person TheFaceOfBoe    schedule 16.11.2014    source источник
comment
ваш цикл for неверен, myArray[i] будет считываться за пределы, если вы когда-нибудь увеличите очередь.   -  person Red Alert    schedule 16.11.2014
comment
Если у вашего ArrayQueue есть конструктор, который принимает емкость, вы могли бы написать эту функцию намного проще, чем то, что вы опубликовали.   -  person PaulMcKenzie    schedule 16.11.2014

Ответы (3)


arrow_upward
1
arrow_downward

Могу ли я предложить переписать это, используя следующее:

#include <algorithm>
//...
void ArrayQueue::setCapacity(unsigned newCapacity)
{
    if(newCapacity == 0 || newCapacity < this->getSize()){
        throw QueueException("setCapacity()", "invalid new capacity");
    ArrayQueue tempQ(newCapacity);
    for(unsigned i=0; i< capacity; i++)
        tempQ.append(myArray[i]);
    std::swap(myArray, tempQ.myArray);
    std::swap(capacity, tempQ.capacity);
    std::swap(size, tempQ.size);
}

Как это работает? Что ж, создаем временную ArrayQueue с нужной мощностью. Затем все, что мы делаем, это копируем данные во временный объект. После этого мы заменяем временный объект на this.

Сделанный.

Временный объект умирает со старыми данными, а this устанавливается с новыми данными. Это вариант идиомы copy/swap. Для этого требуется работающий деструктор для ArrayQueue — как только он у вас есть, он становится куском пирога.

Обратите внимание, что если переменных-членов больше, их также необходимо поменять местами. Я просто заменил те, которые вы разместили. Я предположил, что у вас есть переменная-член size, поэтому, если вы назвали ее по-другому, замените ее именем, которое вы использовали. Итог — поменяйте все местами на tempQ, и все будет в порядке.

Если вы не знаете, что делает std::swap, он делает то, что говорит. Он просто меняет местами два элемента друг с другом — ничего особенного, просто удобно использовать для этого функцию.

person PaulMcKenzie    schedule 16.11.2014

arrow_upward
0
arrow_downward 

for(unsigned i=0; i<newCapacity; i++){
    tempArray[i] = myArray[i];
}

Если ваша новая емкость больше, вы получите доступ к моему массиву с недопустимыми индексами.

person Eric    schedule 16.11.2014

arrow_upward
0
arrow_downward

Насколько я могу понять ваш вопрос, вы ссылаетесь на утверждения, брошенные в другом месте, кроме фрагмента кода, который вы разместили. Поскольку вы не разместили код, который считаете проблематичным, вряд ли кто-то даст вам ответ.

Однако я вижу вероятную ошибку в фрагменте кода, который вы разместили. Ваш код, увеличивающий размер массива:

Item * tempArray = new Item[newCapacity];
for(unsigned i=0; i<newCapacity; i++){
    tempArray[i] = myArray[i];
}
Item * oldArray = myArray;
myArray = tempArray;
delete [] oldArray;

Допустим, например, что старый размер myArray был 20, а вы увеличили его до 40.

Вы собираетесь выделить новый tempArray из 40 элементов.

Затем скопируйте первые 40 элементов из myArray в tempArray.

Неопределенное поведение.

person Sam Varshavchik    schedule 16.11.2014
comment
Я только что обновил свой вопрос с кодом теста, который не работает. В утверждении, что это не так, я уменьшил емкость. Значения myFirst и myLast верны с исходной емкостью, но после уменьшения емкости вдвое они не работают. myFirst равно 0, а myLast равно 5, чего быть не должно. - person TheFaceOfBoe; 16.11.2014
comment
@TheFaceOfBoe Устанавливает ли это емкость на 10? ArrayQueue q5(10); Если это так, мой первоначальный комментарий остается в силе — вы можете кодировать setCapacity гораздо более простым способом, чем то, что вы написали. Настолько просто, что было бы очень трудно, если не невозможно, допустить ошибку. Я бы отправил ответ, но нужно подтверждение того, что этот конструктор устанавливает емкость... - person PaulMcKenzie; 16.11.2014
comment
@PaulMcKenzie Да, это устанавливает емкость на 10. Однако я не уверен, о каком более простом способе вы думаете. Мне все равно нужно выделить новый массив и скопировать каждый элемент в новый массив, что я и пытаюсь сделать здесь. - person TheFaceOfBoe; 16.11.2014
comment
@TheFaceOfBoe Смотрите мой ответ ниже. Используйте то, что уже было закодировано в ваших интересах, и именно это делает ответ, который я дал... - person PaulMcKenzie; 16.11.2014