Мы с вами изучили
базовые принципы оптимизации кода,
а также познакомились с асимптотической сложностью алгоритмов.
Теперь давайте зададимся новой целью.
Давайте изучим, как эффективно использовать основные типы
языка C++: вектор, строку, map и так далее.
Для этого нам надо изучить, как они устроены внутри.
Зачем нам это нужно?
Вот давайте вспомним, что мы на протяжении наших
курсов давали вам некоторые советы по написанию быстрого кода.
Например, мы говорили,
что метод lower_bound у мапа или у сета он эффективнее,
быстрее, чем глобальный алгоритм lower_bound, примененный к сету.
Или же мы, например, говорили,
что вставка в начало дека работает быстрее, чем вставка в начало вектора.
Вот эти советы, они, конечно, хорошие и правильные — им надо следовать,
но все их трудно запомнить, удержать в голове.
Гораздо эффективнее понимать, как вектор,
дек, мап устроены внутри, и тогда вы будете понимать,
почему советы, которые мы даем именно такие, и вы будете понимать,
почему вставка в начало дека работает быстрее, чем вставка в начало вектора.
Зная внутреннее устройство контейнеров,
вам будет проще оценивать эффективность кода,
который вы пишете и проще его ускорять.
Однако прежде чем мы перейдем к рассмотрению внутреннего устройства
контейнеров, нам нужно решить другую задачу: нам нужно
познакомиться с моделью памяти в языке C++.
Это нужно, чтобы вы знали, как хранятся объекты,
создаваемые в процессе работы программ, и как программы на
C++ взаимодействуют с оперативной памятью компьютера.
До сиз пор мы не задавались вопросом, как хранятся в памяти создаваемые объекты.
И сейчас давайте уделим этому внимание и рассмотрим пример.
Вот у нас есть программа, состоящая из трех функций: функции main,
first и second.
У каждой из этих функций есть локальные переменные.
У фукнции main это переменные a и c, у функции first это f_a и f_c,
и у second тоже есть две переменные, одна типа int, другая double.
Давайте зададимся вопросом: где в памяти хранятся вот эти вот локальные переменные?
И ответ достаточно прост: они хранятся в специальной области
оперативной памяти, которая называется стек.
Когда в программе запускается очередная функция, то на стеке
резервируется блок памяти, достаточный для хранения ее локальных переменных.
Кроме того, в этом блоке хранится служебная информация — такая,
как, например, адрес возврата.
Вот этот блок памяти, эта область памяти, называется стековым фреймом функции.
Когда у нас одна функция, в данном случае функция main,
запускает другую функцию — функцию first в нашем примере —
то на стеке ниже фрейма функции main резервируется фрейм для функции first.
То же самое происходит, когда, например,
функция first запускает, вызывает функцию second.
Под фреймом функции first выделяется фрейм для функции second.
Когда же функция завершает свою работу,
то вершина стека просто перемещается на фрейм предыдущей функции.
То есть вот давайте рассмотрим ситуацию,
когда вызов функции second из функции first завершился.
Тогда фрейм функции second, он у нас вот стал таким
бледным — это говорит о том, что вершина стека поднялась до фрейма функции first.
При этом сам фрейм функции second, он просто остается на стеке,
то есть данные, которые создала функция second на стеке, они никак не удаляются,
не чистятся — просто происходит перемещение вершины стека и все.
И это, на самом деле, интересный момент.
Давайте мы дальше продвинемся по нашему примеру.
Выйдем из функции first в функцию main.
И теперь рассмотрим, как происходит запуск функции second из функции main.
Стековый фрейм фукнции second просто перетирает те данные,
которые были в стеке от предыдущих вызовов.
Мы специально на презентации оставили бледненький фрейм
первого запуска функции second, чтобы было видно, что переменная s_d,
локальная переменная s_d от второго запуска ложится на ту область памяти,
где раньше была переменная s_a, локальная переменная s_a.
Давайте вспомним: мы еще в нашем первом курсе, в белом поясе по C++,
говорили, что когда мы объявляем неинициализированную переменную базового
типа, например объявляем переменную типа int и не присваиваем ей никакого значения.
Мы говорили, что в этом случае значение неинициализированной переменной не
определено.
Вот теперь вы знаете, почему это происходит именно так.
Потому что когда вы объявляете локальную неинициализированную переменную,
она размещается на стеке в какой-то произвольной области памяти, в которой
могут находится данные от предыдущих вызовов каких-то других функций.
Соответственно, какие данные там будут, никто не знает.
Именно поэтому значение локальной переменной не определено.
Хорошо, давайте закончим наш пример.
Давайте выйдем из фукнции second, и выйдем из функции main,
и тем самым как бы мы завершим работу нашей программы и увидим,
что когда программа завершается,
то все стековые фреймы как бы становятся бледными,
то есть вершина стека поднимается до самого верха.
Давайте подведем промежуточные итоги.
В этом видео мы с вами узнали, что локальные переменные функций хранятся
в стеке — специальной области памяти.
И блок памяти, который выделяется для каждой функции,
называется стековым фреймом.
И мы знаем теперь, почему локальные переменные,
которые ничем не проинициализированы, почему их значения не определены — потому
что стековые фреймы, когда они заводятся, они просто перетирают данные,
вернее даже кладутся поверх прежних стековых фреймов.
Полднев Антон Вячеславович
Шишков Илья Ивановичкандидат технических наук
