что такое раскрутка стека
О стеке простыми словами — для студентов и просто начинающих
Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»
Теория
На Википедии определение стека звучит так:
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Поэтому первое, на чем бы я хотел заострить внимание, это представление стека в виде вещей из жизни. Первой на ум мне пришла интерпретация в виде стопки книг, где верхняя книга — это вершина.
На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.
Итак, из чего же состоит стек.
Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.
На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.
С теорией закончили, перейдем к практике.
Практика
Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»
Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.
После того как у нас задана «Ячейка», перейдем к созданию функций.
Функции
Функция создания «Стека»/добавления элемента в «Стек»
При добавлении элемента у нас возникнет две ситуации:
Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.
-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.
Функция удаления элемента из «Стека» по данным
Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.
Здесь могут быть такие варианты:
Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);
Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).
Так же стоит отметить, что если не провести данную связь, участок ячеек, который лежит после удаленной ячейки станет недоступным, так как потеряется та самая связь, которая соединяет одну ячейку с другой и данный участок просто затеряется в памяти
Функция вывода данных стека на экран
Самая простая функция:
Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.
Главная функция
Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:
Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.
Заключение
Полный код программы:
Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке
В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.
Что же там такого тяжелого в обработке исключений C++?
Исключения и связанная с ними раскрутка стека – одна из самых приятных методик в C++. Обработка исключений интуитивно понятно согласуется с блочной структурой программы. Внешне, обработка исключений представляется очень логичной и естественной.
Аккуратное использование стековых объектов позволяет создавать очень эффективный и безопасный код, где, в отличие от систем со сборкой мусора, сохраняется локальность ссылок, что дает возможность уменьшить число обращений к системе за памятью, снизить её фрагментацию, более эффективно использовать кэш памяти.
Тем не менее, в C++, исключения традиционно рассматриваются буквально как исключительные ситуации, связанные с восстановлением после ошибок. Трудно сказать, является ли это причиной или следствием того, что реализация обработки исключений компиляторами чрезвычайно дорога. Попробуем разобраться почему.
Продолжение здесь.
Как обстоят дела.
Существует предубеждение, что данный метод является весьма дорогостоящим. Уже в силу того, что на каждый try-блок вызывается setjmp, который недёшев. В самом деле, нужно полностью сохранить состояние процессора, где могут быть десятки регистров. Тогда как на момент возникновения исключения, содержимое большей части этих регистров уже бесполезно. В действительности же, компилятор поступает весьма рационально. Он разворачивает setjmp, причем, сохраняет только полезные регистры (уж эта информация у него есть). Автор сомневается, что издержки на setjmp так уж высоки.
Концептуально, на каждый адрес кода программы хранится информация о том, как попасть в вышестоящий фрейм вызова. На практике ввиду объемности этой информации, она сжимается, фактически, вычисляется с помощью интерпретации байт-кода. Этот байт-код исполняется при возникновении исключения. Расположено всё это в секциях «.eh_frame» и «.eh_frame_hdr».
Да, помимо всего прочего, DWARF интерпретатор представляет собой отличный backdoor, с помощью которого, подменив байт-код, можно перехватить исключение и отправить его на обработку куда душе угодно.
GCC/DW2 использует практически такую же секцию LSDA, что и GCC/SJLJ.
PS: Отдельное спасибо Александру Артюшину за содержательное обсуждение.
Исключения и освобождение стека в C++
В механизме исключений C++ элемент управления перемещается из оператора throw в первый оператор catch, который может обработать выданный тип. При достижении оператора Catch все автоматические переменные, которые находятся в области между операторами Throw и catch, уничтожаются в процессе, известном как Очистка стека. При очистке стека выполнение продолжается следующим образом.
Управление достигает try оператора с помощью обычного последовательного выполнения. В try блоке выполняется защищенный раздел.
Если во время выполнения защищенного раздела исключение не возникает, то catch предложения, следующие за try блоком, не выполняются. Выполнение продолжится в операторе после последнего catch предложения, следующего за соответствующим try блоком.
Если исключение возникает во время выполнения защищенного раздела или в любой подпрограмме, что защищенный раздел вызывает напрямую или косвенно, объект исключения создается из объекта, созданного throw операндом. (Это означает, что может быть вовлечен конструктор копии.) На этом этапе компилятор ищет catch предложение в более высоком контексте выполнения, который может управлять исключением вызываемого типа или catch обработчиком, который может обработать любые типы исключений. catch Обработчики анализируются в порядке их отображения после try блока. Если соответствующий обработчик не найден, проверяется следующий динамически охватывающий try блок. Этот процесс будет продолжен до тех пор, пока try не будет проверен внешний внешний блок.
Если найден соответствующий catch обработчик, который перехватывается по значению, его формальный параметр инициализируется путем копирования объекта исключения. Если обработчик выполняет перехват по ссылке, параметр инициализируется для ссылки на объект исключения. После инициализации формального параметра начинается процесс очистки стека. Это подразумевает уничтожение всех автоматически созданных объектов, которые были полностью созданы, но еще не были удалены, между началом try блока, который связан с catch обработчиком, и исключением из-за исключения. Удаление происходит в порядке, обратном созданию. catch Обработчик выполняется, и программа возобновляет выполнение после последнего обработчика, то есть в первой инструкции или конструкции, которая не является catch обработчиком. Элемент управления может вводить catch обработчик только через выданное исключение, никогда через goto оператор или case метку в switch инструкции.
Пример раскрутки стека
Что такое раскручивание стека?
Что такое раскручивание стека? Искал, но не смог найти поучительный ответ!
ОТВЕТЫ
Ответ 1
Об размотке стека обычно говорят в связи с обработкой исключений. Вот пример:
Теперь это очень мощная концепция, ведущая к технике под названием RAII, то есть Resource Acquisition Is Initialization, которая помогает нам управлять такими ресурсами, как память, соединения с базой данных, дескрипторы открытых файлов и т.д. В C++.
Теперь это позволяет нам предоставлять гарантии безопасности исключений.
Ответ 2
Все это относится к C++:
Определение: когда вы создаете объекты статически (в стеке, а не размещаете их в динамической памяти) и выполняете вызовы функций, они «складываются».
При выходе из области (что-либо, ограниченное < и >) (используя return XXX; достижение конца области или создание исключения) все в этой области уничтожается (для всего вызывается деструктор). Этот процесс уничтожения локальных объектов и вызова деструкторов называется разматыванием стека.
У вас есть следующие проблемы, связанные с размоткой стека:
согласованность программы: спецификации C++ гласят, что вы никогда не должны вызывать исключение до того, как будет обработано любое существующее исключение. Это означает, что процесс разматывания стека никогда не должен генерировать исключение (либо использовать только код, гарантированно не выбрасывающий деструкторы, либо окружать все в деструкторах с помощью try < и >catch(. ) <> ).
Если какой-либо деструктор генерирует исключение во время раскручивания стека, вы попадаете в страну неопределенного поведения, которое может привести к неожиданному завершению вашей программы (наиболее распространенное поведение) или к завершению юниверса (теоретически возможно, но пока не наблюдалось на практике).
Ответ 3
В общем смысле стоп «разматывать» в значительной степени является синонимом конца вызова функции и последующего всплытия стека.
Однако, в частности, в случае С++, разворачивание стека связано с тем, как С++ вызывает деструкторы для объектов, выделенных с момента запуска любого блока кода. Объекты, созданные в блоке, освобождаются в порядке, обратном порядку их выделения.
Ответ 4
Скажем, у вас есть этот фрагмент кода:
Ответ 5
Я не знаю, прочитали ли вы это, но Статья в Википедии о стеке вызовов имеет достойное объяснение.
разматывать:
Возврат из вызываемой функции вытолкнет верхний кадр из стека, возможно, оставив возвращаемое значение. Более общий поступок выталкивания одного или нескольких кадров из стека для возобновления выполнения в другом месте программы называется отказом стека и должен выполняться при использовании нелокальных структур управления, таких как используемые для исключения обработки. В этом случае фрейм стека функции содержит одну или несколько записей, определяющих обработчики исключений. Когда генерируется исключение, стек разматывается до тех пор, пока не будет найден обработчик, который готов обработать (уловить) тип вызванного исключения.
Некоторые языки имеют другие структуры управления, требующие общего разматывания. Паскаль позволяет глобальному оператору goto передавать управление из вложенной функции и в ранее вызываемую внешнюю функцию. Эта операция требует, чтобы стек был размотан, удалив столько кадров стека, сколько необходимо, чтобы восстановить надлежащий контекст для передачи управления в целевой оператор внутри внешней внешней функции. Аналогично, C имеет функции setjmp и longjmp, которые действуют как нелокальные gotos. Общий Lisp позволяет контролировать то, что происходит, когда стек разматывается с помощью специального оператора размотки защиты.
При применении продолжения стек (логически) разматывается, а затем перематывается со стеком продолжения. Это не единственный способ реализации продолжений; например, используя множественные явные стеки, применение продолжения может просто активировать свой стек и намотать значение, которое нужно передать. Язык программирования Схемы позволяет выполнять произвольные thunks в определенных точках при «разматывании» или «перемотке» стека управления при вызове продолжения.
Ответ 6
Я прочитал сообщение в блоге, которое помогло мне понять.
Что такое стирание стека?
На любом языке, который поддерживает рекурсивные функции (т.е. в значительной степени все, кроме Fortran 77 и Brainf * ck), язык исполнения сохраняется стек функций, выполняемых в настоящее время. Распаковка стека способ проверки и, возможно, изменения этого стека.
Зачем вам это нужно?
Ответ может показаться очевидным, но есть несколько связанных, но тонких разные ситуации, когда разматывание полезно или необходимо:
Вы можете найти полный пост здесь.
Ответ 7
Все говорили об обработке исключений на С++. Но, я думаю, есть еще одна коннотация для разворачивания стека, и это связано с отладкой. Отладчик должен выполнять разворачивание стека, когда он должен перейти в кадр, предшествующий текущему кадру. Тем не менее, это своего рода виртуальная размотка, поскольку она должна перемотать назад, когда она вернется к текущему кадру. Примером этого может быть команда up/down/bt в gdb.
Ответ 8
Ответ 9
Среда выполнения С++ уничтожает все автоматические переменные, созданные между броском и catch. В этом простом примере ниже f1() throw и main() уловы между объектами типа B и A создаются в стеке в этом порядке. Когда вызывается f1(), вызывается деструкторы B и A.
Выход этой программы будет
Это связано с тем, что стоп-код программы, когда f1() выбрасывается, выглядит как
Итак, когда вызывается f1(), автоматическая переменная b уничтожается, а затем, когда f() выставляется автоматически, переменная a уничтожается.
Надеюсь, это поможет, счастливое кодирование!
Ответ 10
Если при построении объекта, состоящего из подобъектов или элементов массива, создается исключение, деструкторы вызываются только для тех подобъектов или элементов массива, которые были успешно созданы до того, как было выбрано исключение. Деструктор для локального статического объекта будет вызываться только в том случае, если объект был успешно сконструирован.
Ответ 11
Урок №183. Исключения, Функции и Раскручивание стека
Обновл. 15 Сен 2021 |
На предыдущем уроке мы говорили о том, как, используя ключевые слова throw, try и catch, обрабатывать исключения. На этом уроке мы рассмотрим, как взаимодействуют функции во время обработки исключений в языке С++.
Генерация исключений за пределами блока try
На предыдущем уроке операторы throw помещались непосредственно в блок try. Если бы это было обязательным условием, то согласитесь, что обработка исключений не была бы гибкой вообще.
На самом деле стейтменты throw вовсе не обязаны находиться непосредственно в блоке try, благодаря выполнению такой операции, как «раскручивание стека». Это предоставляет нам необходимую гибкость в разделении общего потока выполнения кода программы и обработки исключений. Продемонстрируем это, переписав программу из предыдущего урока, вынеся генерацию исключения и вычисление квадратного корня в отдельную функцию:
Здесь мы переместили генерацию исключения и операцию вычисления квадратного корня в отдельную функцию mySqrt(). Затем мы вызываем эту функцию в блоке try. Убедимся, что всё работает, как нужно:
Ура! Однако, давайте вернемся к моменту генерации исключения и рассмотрим ход выполнения программы. Во-первых, при генерации исключения компилятор смотрит, можно ли сразу же обработать это исключение (для этого нужно, чтобы исключение выбрасывалось внутри блока try). Поскольку точка выполнения не находится внутри блока try, то и обработать исключение немедленно не получится. Таким образом, выполнение функции mySqrt() приостанавливается, и программа смотрит, может ли caller (который и вызывает mySqrt()) обработать это исключение.
Если нет, то компилятор завершает выполнение caller-а и переходит на уровень выше — к caller-у, который вызывает текущего caller-а, чтобы проверить, сможет ли тот обработать исключение. И так последовательно до тех пор, пока не будет найден соответствующий обработчик исключения, или пока функция main() не завершит свое выполнение без обработки исключения. Этот процесс называется раскручиванием стека.
Теперь рассмотрим детально, как это относится к нашей программе. Сначала компилятор проверяет, генерируется ли исключение внутри блока try. В нашем случае — нет, поэтому стек начинает раскручиваться. При этом функция mySqrt() завершает свою работу и точка выполнения перемещается обратно в функцию main(). Теперь компилятор проверяет снова, находимся ли мы внутри блока try. Поскольку вызов функции mySqrt() был выполнен из блока try, то компилятор начинает искать соответствующий обработчик catch. Он находит обработчик типа const char*, и исключение обрабатывается блоком catch внутри main().
Подводя итог, функция mySqrt() генерирует исключение, но блоки try/catch, которые находятся в main(), ловят и обрабатывают это исключение. Другими словами, блок try ловит исключения не только внутри себя, но и внутри функций, которые вызываются в этом блоке try.
Самое интересное здесь в том, что mySqrt() как бы говорит: «Эй, компилятор, здесь проблема!». Но обрабатывать эту проблему mySqrt() отказывается. Это, по сути, делегирование ответственности за обработку исключения на caller (аналогично тому, как при использовании кодов завершения ответственность за обработку ошибок перекладывается обратно на caller).
Сейчас некоторые из вас, вероятно, спросят: «Зачем передавать ошибки обратно в caller? Почему бы просто не заставить функцию mySqrt() обрабатывать собственные исключения?». Проблема в том, что разные программы обрабатывают ошибки/исключения по-разному. Консольная программа выводит сообщение об ошибке. Приложение Windows выводит диалоговое окно с ошибкой. В одной программе это может быть фатальной ошибкой, а в другой — нет. Передавая ошибку обратно в стек, каждое приложение может обрабатывать исключение mySqrt() таким образом, который является наиболее подходящим по контексту! В конечном счете, это позволяет отделить функционал mySqrt() от кода обработки исключений, который можно разместить в других (менее важных) частях кода.
Еще один пример раскручивания стека
Здесь у нас стек уже побольше. Хотя всё кажется слишком сложным, но на самом деле это не так: