Непрерывно ли std :: stack?

Question

Я хотел найти максимальный элемент в стеке и подумал об использовании std::max_element.

Затем я узнал, что std::stack не имеет функций begin() и end(). После просмотра net я увидел хак:

stack<int> s({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
auto end = &s.top() + 1;     // instead of std::end
auto begin = end - s.size(); // instead of std::begin
cout << "Max = " << *max_element(begin, end);

Кажется, он работает, вы можете увидеть его в Интернете .

Но когда я отправил свой код, он не прошел некоторые из тестовых случаев. std::stack действительно смежный?

Answer 1

Это зависит от базового контейнера std::stack:

template <class T, class Container = deque<T>> class stack;

Шаблон класса действует как оболочка для базового контейнера

По умолчанию Container = deque<T>. И std::deque не является смежным:

элементы двухсторонней очереди не хранятся непрерывно

Следовательно,

stack<int> s;

является не непрерывным , потому что std::deque не является непрерывным.

Однако

типичные реализации (из std::deque) используют последовательность индивидуально выделенных массивы фиксированного размера

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

Если нижележащий контейнер указан явно (стандартные контейнеры std::vector и std::list удовлетворяют требованиям, кроме std::deque), и если этот контейнер является непрерывным, то этот стек также является непрерывным.

Например,

stack<int, vector<int>> s;

является смежным , потому что std::vector является смежным.

TL; DR

Смежность std::stack определяется смежностью его нижележащего контейнера.

_{Я также хотел бы поблагодарить сообщество за то, что оно показало мне способы, как люди находят ответы на такие вопросы по программированию, и это заставляет меня искать решения по ссылкам.}

Answer 2

Является ли std::stack смежным? Я бы сказал, это неважно. std::stack - это не контейнер, а адаптер, и его идея - абстракция стека и преднамеренное ограничение интерфейсов.

Даже если бы он был смежным, доступ к элементам std::stack любыми способами, но .top() будет нарушением его семантики. Если вам нужен такой доступ, вам вообще не следует использовать std::stack. Не запутайте читателя вашего кода.