Стек с максимальным размером, который перезаписывает C ++

Question

Если бы я делал что-то вроде стека отмены и хотел бы поддерживать только 30 операций отмены, было бы неплохо иметь стек, максимальная глубина которого равна 30.

Очевидно, вы бы этого не сделалиесли вы хотите, чтобы стек ограничивал добавления на данном этапе, вы просто хотите, чтобы он отбрасывал самый нижний элемент при добавлении 31-го числа.

Я знаю, что я могу имитировать такую ​​функцию с помощью списка, ноМне было интересно, есть ли способ сделать это с помощью STL или есть другие предварительно реализованные варианты для этого?

Answer 1

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

Другой способ сделать это - выделить массив (или обернуть вокруг vector) вместо динамического выделения памяти и модулировать ваши индексы на 30, когда вы хотите продвинуть индекс.

В любом случае, вам никогда не придется выделять или освобождать память, кроме как в начале, и вы можете справиться с переполнением действительно хорошо. Вы можете прочитать подробности на странице Википедии о кольцевых буферах .

Answer 2

Если вы готовы работать за пределами STL, в boost есть контейнер под названием circular_buffer, который идеально подойдет для ваших нужд: http://www.boost.org/doc/libs/1_49_0/libs/circular_buffer/doc/circular_buffer.html#briefexample

Answer 3

std::deque или std::list оба работают.Вы можете использовать их как стек, используя push_back / pop_back, и устаревать старые элементы с помощью pop_front

.

Answer 4

Я бы использовал std::deque и удалял элемент, когда размер превышал ограничение. Конечно, список будет работать так же хорошо, как вы заметили.

Нет стандартного контейнера для этого.

Answer 5

Я не знаю, хотите ли вы сделать это, но мне кажется, что вы хотите циклический буфер. Это не STL afaik, но он будет делать именно то, что вы хотите. Посмотрите на http://en.wikipedia.org/wiki/Circular_buffer