Как получить std :: stack на основе стека? (с фиксированным максимальным размером) - PullRequest
Новая
       6

Как получить std :: stack на основе стека? (с фиксированным максимальным размером)

1 голос
/ 08 октября 2019

Согласно std::stack ссылка:

Тип нижележащего контейнера для хранения элементов. Контейнер должен удовлетворять требованиям SequenceContainer. Кроме того, он должен предоставлять следующие функции с обычной семантикой: 

back()
push_back()
pop_back()

Стандартные контейнеры std :: vector, std :: deque и std :: list удовлетворяют этим требованиям. По умолчанию, если для конкретного экземпляра класса стека не указан класс контейнера, используется стандартный контейнер std :: deque.

Все из них являются контейнерами на основе кучи.

следующие фактически компилируются (): 

std::stack<int, std::array<int, 12> > stack_of_months;

До тех пор, пока не будет вызван push.

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

Ответы [ 2 ]

3 голосов
/ 08 октября 2019

Вы должны быть в состоянии использовать Boost's static_vector:

static_vector - это контейнер последовательности, как со смежным хранилищем, который может меняться в размере вместе с статическое распределение , низкие накладные расходы и фиксированная емкость .

Рабочий пример: 

std::stack<int, boost::container::static_vector<int, 4>> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
// s.push(5); // would throw

@ PaulMcKenzie И да, он использует стек в качестве хранилища (если, конечно, сам объект хранится в стеке):

Количество элементов в static_vector может динамически варьироваться до фиксированной емкости потому что элементы хранятся внутри самого объекта аналогично массиву.

Демонстрационная версия: https://wandbox.org/permlink/Gi40FrB0yX8dIwfA.

0 голосов
/ 08 октября 2019

Нет ничего сложного в том, чтобы обернуть std::array во что-то, пригодное для использования std::stack, вам просто нужно отслеживать, сколько элементов было нажато и вытолкнуто: 

#include <array>
#include <stack>
#include <iostream>

template < typename T, size_t Size >
struct static_vector
{
  using value_type = T;
  using reference = T&;
  using const_reference = const T &;
  using size_type = size_t;

  static_vector()
    : size( 0 )
  {
  }

  std::array< T, Size > data;
  size_t size;

  void push_back( const_reference value )
  {
    data.at( size ) = value;
    size++;
  }

  void pop_back()
  {
    if ( size == 0 )
    {
      throw std::runtime_error( "empty" );
    }
    size--;
  }

  const_reference back() const
  {
    if ( size == 0 )
    {
      throw std::runtime_error( "empty" );
    }
    return data[ size - 1 ];
  }

  reference back()
  {
    if ( size == 0 )
    {
      throw std::runtime_error( "empty" );
    }
    return data[ size - 1 ];
  }
};

int main()
{
  std::stack< int, static_vector< int, 4 > > stack;
  stack.push( 1 );
  std::cout << stack.top() << "\n";
  stack.push( 2 );
  std::cout << stack.top() << "\n";
  stack.pop();
  std::cout << stack.top() << "\n";
  stack.pop();
}
...