Метод изменения емкости очереди C++

unsigned mySize;       // number of items I contain
unsigned myCapacity;   // how many items I can store
unsigned myFirst;      // index of oldest item (if any)
unsigned myLast;       // index of next available spot for append (if any)
Item*    myArray;      // dynamic array of items

Я создаю класс очереди на основе динамического массива, и мне нужно создать метод, который изменяет количество элементов, которые может содержать очередь. Мне нужно, чтобы «myLast» оставался точным после изменения емкости, особенно в очереди, в которой уже были элементы, удаленные из очереди с начала.

void ArrayQueue<Item>::setCapacity(unsigned cap) {
if (cap < getSize() || cap == 0){
    throw QueueException("setCapacity()", "New capacity must be greater than size");
} else {
    Item * nq = new Item[cap];
    for (unsigned i = 0; i < cap; i++){
        nq[i] = myArray[i];
    }
    delete [] myArray;
    myArray = nq;
    myCapacity = cap;
//what do I put here to make myFirst and myLast be correct for the new capcacity?
       }
    }

Кто-нибудь может объяснить, как это сделать?


person user3020033    schedule 23.04.2014    source источник
comment
Разве весь смысл очереди не в том, что она растет за постоянное время и может расти бесконечно? Большинство реализаций очередей представляют собой просто связанные списки.   -  person cppguy    schedule 23.04.2014
comment
@cppguy Связанный список - не очень эффективная реализация очереди.   -  person ooga    schedule 23.04.2014
comment
разве myLast не должен обновляться только во время вставки и удаления?   -  person Bruno Ferreira    schedule 23.04.2014
comment
^ да... Почему они были бы неверны в этот момент? Это индексы в массиве, а не указатели на элементы.   -  person Alex Reinking    schedule 23.04.2014
comment
Должно быть, я делаю что-то не так, потому что метод не проходит тесты, которые я даю для правильного элемента в myLast. Извините, я новичок в использовании очередей.   -  person user3020033    schedule 23.04.2014
comment
@ooga не могли бы вы подробнее рассказать о A linked list is not a very efficient implementation for a queue ?? Никаких массовых копий/перемещений...   -  person Massa    schedule 23.04.2014
comment
@ Масса Не совсем, нет. Обратите внимание, однако, что класс адаптера контейнера STL queue использует в качестве базового контейнера deque, а не list. Для deque типичные реализации используют последовательность отдельно выделенных массивов фиксированного размера.   -  person ooga    schedule 23.04.2014
comment
@ooga прав в отношении deque. [000XXX][XXXXXX][XXXXXX][XXXX00] будет таким макетом для типичных страниц очереди (размер страницы = 6, заполнено = X, пусто = 0). Точка вставки на первой странице перемещается назад при перемещении вперед, точка вставки последней страницы перемещается вперед при перемещении назад. По крайней мере, большинство из тех, что я анализировал, делают это именно так, и это очень эффективно для подлинной дек-активности.   -  person WhozCraig    schedule 24.04.2014
comment
Независимо от реализации с использованием списка или очереди (что на самом деле является проблемой, связанной с избеганием фрагментации и сложности вставки, что не имеет значения, поскольку очереди изменяются только в их голове и хвосте). Очередь фиксированного размера требует массовых копий/перемещений для изменения размера   -  person cppguy    schedule 24.04.2014


Ответы (2)


Ничего — ни myFirst, ни myLast не меняются с тем, что у вас есть — если только вы не используете циклическую очередь (и я уверен, что вы используете), и в этом случае вы не можете просто скопировать исходный массив над новым массивом. Если вы просто скопируете старый массив поверх нового, любые записи, которые будут обернуты вокруг него, окажутся неуместными. Вы должны справиться с возможностью того, что он обернулся вокруг.

И у вас есть проблема с циклом for:

for (unsigned i = 0; i < cap; i++){
    nq[i] = myArray[i];
}

Он будет работать с конца myArray, если cap больше, чем myCapacity (например, размер myArray).

person Rob K    schedule 23.04.2014

Вы можете изменить свой контейнер в очереди, если хотите.

 std::queue<int,std::list<int>> myQueue

как это...

person hgedek    schedule 24.04.2014