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?
}
}
Кто-нибудь может объяснить, как это сделать?
A linked list is not a very efficient implementation for a queue
?? Никаких массовых копий/перемещений... - person Massa   schedule 23.04.2014queue
использует в качестве базового контейнераdeque
, а неlist
. Дляdeque
типичные реализации используют последовательность отдельно выделенных массивов фиксированного размера. - person ooga   schedule 23.04.2014[000XXX][XXXXXX][XXXXXX][XXXX00]
будет таким макетом для типичных страниц очереди (размер страницы = 6, заполнено =X
, пусто =0
). Точка вставки на первой странице перемещается назад при перемещении вперед, точка вставки последней страницы перемещается вперед при перемещении назад. По крайней мере, большинство из тех, что я анализировал, делают это именно так, и это очень эффективно для подлинной дек-активности. - person WhozCraig   schedule 24.04.2014