Урок №105. Стек и Куча

Обновл. 2 Дек 2020 |

На этом уроке мы рассмотрим стек и кучу в языке C++.

Сегменты

Память, которую используют программы, состоит из нескольких частей — сегментов:

Сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения.

Сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и статические переменные, инициализированные нулем.

Сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные.

Куча, откуда выделяются динамические переменные.

Стек вызовов, где хранятся параметры функции, локальные переменные и другая информация, связанная с функциями.

Сегмент кучи (или просто «куча») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче на уроке о динамическом выделении памяти в языке С++.

В языке C++ при использовании оператора new динамическая память выделяется из сегмента кучи самой программы:

Адрес выделяемой памяти передается обратно оператором new и затем он может быть сохранен в указателе. О механизме хранения и выделения свободной памяти нам сейчас беспокоиться незачем. Однако стоит знать, что последовательные запросы памяти не всегда приводят к выделению последовательных адресов памяти!

При удалении динамически выделенной переменной, память возвращается обратно в кучу и затем может быть переназначена (исходя из последующих запросов). Помните, что удаление указателя не удаляет переменную, а просто приводит к возврату памяти по этому адресу обратно в операционную систему.

Куча имеет свои преимущества и недостатки:

Выделение памяти в куче сравнительно медленное.

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

Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую.

Поскольку куча представляет собой большой резервуар памяти, то именно она используется для выделения больших массивов, структур или классов.

Стек вызовов

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

Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое стек как структура данных.

Стек как структура данных

Структура данных в программировании — это механизм организации данных для их эффективного использования. Вы уже видели несколько типов структур данных, например, массивы или структуры. Существует множество других структур данных, которые используются в программировании. Некоторые из них реализованы в Стандартной библиотеке C++, и стек как раз является одним из таковых.

Например, рассмотрим стопку (аналогия стеку) тарелок на столе. Поскольку каждая тарелка тяжелая, а они еще и сложены друг на друге, то вы можете сделать лишь что-то одно из следующего:

Посмотреть на поверхность первой тарелки (которая находится на самом верху).

Взять верхнюю тарелку из стопки (обнажая таким образом следующую тарелку, которая находится под верхней, если она вообще существует).

Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку, если она вообще была).

В компьютерном программировании стек представляет собой контейнер (как структуру данных), который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ»), стек более ограничен.

В стеке вы можете:

Посмотреть на верхний элемент стека (используя функцию top() или peek() ).

Вытянуть верхний элемент стека (используя функцию pop() ).

Добавить новый элемент поверх стека (используя функцию push() ).

Стек — это структура данных типа LIFO (англ. «Last In, First Out» = «Последним пришел, первым ушел»). Последний элемент, который находится на вершине стека, первым и уйдет из него. Если положить новую тарелку поверх других тарелок, то именно эту тарелку вы первой и возьмете. По мере того, как элементы помещаются в стек — стек растет, по мере того, как элементы удаляются из стека — стек уменьшается.

Например, рассмотрим короткую последовательность, показывающую, как работает добавление и удаление в стеке:

Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1

Стопка тарелок довольно-таки хорошая аналогия работы стека, но есть лучшая аналогия. Например, рассмотрим несколько почтовых ящиков, которые расположены друг на друге. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается гвоздем к почтовому ящику снизу, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, то как мы получим поведение, подобное стеку?

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

Сегмент стека вызовов

Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске программы, функция main() помещается в стек вызовов операционной системой. Затем программа начинает свое выполнение.

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

Наша аналогия с почтовыми ящиками — это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем или вытягиваем из стека, называются фреймами (или «кадрами») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека. Указатель стека отслеживает вершину стека вызовов.

Единственное отличие фактического стека вызовов от нашего гипотетического стека почтовых ящиков заключается в том, что, когда мы вытягиваем элемент из стека вызовов, нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её. Поскольку указатель стека будет ниже этого адреса памяти, то, как мы уже знаем, эта ячейка памяти не будет находиться в стеке.

Стек вызовов на практике

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

Программа сталкивается с вызовом функции.

Создается фрейм стека, который помещается в стек. Он состоит из:

адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес»). Так процессор запоминает, куда ему возвращаться после выполнения функции;

памяти для локальных переменных;

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

Процессор переходит к точке начала выполнения функции.

Инструкции внутри функции начинают выполняться.

После завершения функции, выполняются следующие шаги:

Регистры восстанавливаются из стека вызовов.

Фрейм стека вытягивается из стека. Освобождается память, которая была выделена для всех локальных переменных и аргументов.

Обрабатывается возвращаемое значение.

ЦП возобновляет выполнение кода (исходя из обратного адреса).

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

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

Устанавливаем стеки в интерфейс Windows

Совсем недавно мы рассказывали о том, как добавить в Windows поддержку вкладок – простого, но при этом по-настоящему удобного элемента интерфейса, позволяющего свести к минимуму количество открытых окон и, соответственно, излишних действий с ними. В данной же статье речь пойдёт о другом, не менее полезном элементе интерфейса, который называется стек.

В отличие от вкладок, уже получивших широкое распространение во всевозможных программах и веб-сервисах, стеки где-либо применяются не так часто. Впервые (впрочем, тут мы можем и ошибаться), идею стеков в своей операционной системе реализовала компания Apple, добавившая данную функцию в Mac OS X Leopard ещё в 2007 году.

В Leopard стеки были интегрированы непосредственно в док (аналог панели задач в Windows) и позволяли группировать и сортировать информацию (будь то ярлыки программ, папки или документы любого формата), освобождая пространство на рабочем столе или в самом доке.

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

Стеки могли выглядеть по-разному в соответствии с предпочтениями пользователя. Например, в виде сетки

В ответ на это Microsoft уже в Windows 7 полностью переработала панель задач, попутно добавив туда функцию jump list – особые контекстные меню для каждой закреплённой на панели программы.

Jump list содержат список недавно или наиболее часто используемых файлов (а в некоторых случаях ещё и команды), к которым можно перейти всего одним кликом мыши напрямую из самого меню. Таким образом, функция избавляет пользователей от необходимости в буквальном смысле копаться в собственных папках и подпапках.

Согласитесь: это удобно. Но, с другой стороны, недостаток новой панели заключается в том, что выносить на неё можно исключительно приложения. В свою очередь, файл или папка будут автоматически направлены в jump list, что не всегда наглядно и удобно. Да и возможностями произвольной группировки taskbar в Windows 7 не обладает.

Вот тут и возникает мысль скрестить две удачные идеи, придуманные инженерами двух конкурирующих IT-корпораций. Конечно, добавить панель задач из Windows 7 в Mac OS X у нас вряд ли получится, но вот выполнить обратную операцию: добавить стеки в Windows, вполне возможно с помощью программ сторонних разработчиков, которых, к слову, уже достаточно много. О некоторых из них мы и расскажем далее.

Начнём, пожалуй, с небольшой утилиты Win7Stack, которая полностью выполняет возложенную на неё задачу, но при этом весит менее одного мегабайта и потребляет минимум системных ресурсов. Программа бесплатна и весьма проста в использовании.

Для того чтобы создать стек, нужно предварительно подготовить папку с ярлыками приложений, после чего указать её программе. Далее можно задать название стека и выбрать более подходящую для него иконку. Нажатие кнопки «Create link on Desktop» создаёт ярлык на рабочем столе, который можно переместить куда угодно, включая панель задач. Результат выглядит так:

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

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

Если от программы для создания стеков Вам хочется не столько простоты и минимализма, сколько настраиваемости и функциональности, то советуем обратить своё внимание на утилиту Standalone Stack.

Как и в случае с Win7Stack, Standalone Stack является абсолютно бесплатной программой, а к тому же ещё и портабельной, т.е. не нуждается в установке, достаточно лишь распаковать архив и запустить приложение.

Для того чтобы создать стек, необходимо открыть раздел «New Stack», в строке «Path» указать программе любую исходную папку. Далее – придумать название и нажать «Create Stack», после чего в появившемся новом разделе с именем Вашего стека кликнуть по кнопке «Create shortcut», которая создаст ярлык на рабочем столе, размещать который можно уже где угодно (мы для наглядности перенесли его на панель задач).

В возможности утилиты входит создание стеков, в которых отображаются не только ярлыки других программ, но и любые файлы и папки, причём навигацию по ним можно проводить непосредственно из самого стека. Отображение сгруппированных значков здесь возможно в форматах сетка (в опциях – Grid)

и веер (в опциях почему-то – Stack, хотя стеками, по сути, являются оба варианта).

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

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

Из недостатков нам сразу бросились в глаза несколько недоработок (скорее всего это временные баги), связанные с настройками уже созданного стека. Часто они срабатывали не сразу, а только по истечении какого-то времени. Кроме того, уж слишком неаккуратно выглядит иконка, автоматически присваиваемая каждому новому стеку.

Впрочем, заменить её не составит большого труда (что мы и сделали). Для этого нужно открыть свойства созданного ярлыка для стека, нажать кнопку «сменить значок» и в появившемся окне указать путь к любой приличной пиктограмме.

Кроме того, можно выбирать и из иконок уже встроенных в Windows, число которых весьма велико. Для этого достаточно лишь указать в строке «искать значки в…» адрес «C:WindowsSystem32imageres.dll» без кавычек. Именно там располагается большинство системных значков.

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

Для того чтобы сгруппировать элементы, в отличие от двух предыдущих программ, Bins не требует никаких заранее подготовленных папок или различных дополнительных настроек. Всё просто: сразу же после установки любые элементы панели задач можно перемещать друг на друга, что сразу же приводит к их группировке.

Точно также элементы на taskbar станет возможно перемещать прямо с рабочего стола или из любой папки Вашей файловой системы.

Если Вы хоть раз работали с реализацией стеков в браузере Opera (они появились там начиная с версии 11.0), то любые дальнейшие разъяснения уже излишни. Впрочем, вернёмся к Bins. Подобно превью открытых окон, для того чтобы увидеть содержимое стека достаточно лишь навести курсор на соответствующий элемент в панели задач, т.е. для этого не нужно делать ни единого клика.

Что касается настроек программы, то их немного, и они разделены на два раздела. Первый из них отвечает за работу непосредственно самого механизма группировки.

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

Второй раздел «Extras» отвечает за различные дополнительные настройки.

Наиболее важной из них, на наш взгляд, является возможность закреплять файлы и папки прямо на самой панели задач, а не в jump list, о чём мы говорили ещё в начале статьи. Разумеется, при работе с Bins сами jump list никуда не исчезают и сохраняют всю свою функциональность.

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

Пожалуй, единственный серьёзный недостаток программы заключается в том, что она является платной. Впрочем, бета-версией, которая на наш взгляд вполне стабильна, создатели Bins разрешают пользоваться бесплатно и сколько угодно.