Указатели, адресная арифметика

Лекция 7 Указатели, адресная арифметика Если до этого момента программирование казалось очень легким, то теперь начинаются действительно сложные темы. Я уже несколько раз упоминал слово «указатель», но просил не зацикливаться на этом термине. Что же это это такое? Ох, какой же это мощный инструмент! Столько всего он позволяет делать, но начнем с самого простого. Стек и куча Если вы видите в коде объявленную переменную, вроде int i = 0; знайте, что переменная создана на стеке. Что это значит? Я не буду вдаваться в подробности, ибо это отдельный курс, посвященный архитектуре ЭВМ, остановлюсь только на основных вещах. Учебники делят память на статическую и динамическую. Я не буду объяснять, что такое «статическая память», потому что этот термин не в ходу. Но если проводить аналогии с другими учебниками и статьями, то стек — «статическая память», куча — «динамическая». Их принципиальные отличия, важные в разработке: – Доступ к памяти на стеке быстрее – За переменными созданными на стеке программисту не нужно следить: память выделяется автоматически, очищается также автоматически – Стек, как память, меньшего объема, чем куча – При работе со стеком возможно непреднамеренное дублирование данных, особенно это важно, когда эти данные огромны. – Переменные на стеке «живут» только внутри блока. Соответственно, для кучи справедливы обратные утверждения (естественно, дублирование данных и в куче возможно, но там сложно это сделать непреднамеренно) Да, следует упомянуть, что изначально: стек — это абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO... Но эту тему я продолжу в следующий раз. Итак, мы работали со стеком до этого момента и все было замечательно. Но у стека, с его плюсами, есть существенный минус: Переменные на стеке «живут» только внутри блока. Также не забываем про его небольшой объем. И менее очевидное: при работе со стеком возможно непреднамеренное дублирование данных. Все это накладывает некоторые ограничения, какие-то можно обойти, какие-то сложно без накладных расходов. Давайте разберемся, что в действительности происходит, когда вызывается функция: int func(int n) { return n; } int main(void) { int m = 10; func(m); } return 0; Если опустить самые низкоуровневые детали, то можно выделить две проблемы этой функции, они пока не критичны, но станут, когда мы будем использовать собственные типы. Сейчас происходит 2 лишних копирования m. Первое на этапе передачи параметра, второе — при возвращении значения из функции. Т.е. На каком-то этапе у нас будет 2 или даже 4 дубликата переменной m. (Почему 4, а не 3 — это связано с тем, как осуществляется передача параметров и возвращаемого значения. В Си мы сможем работать только с двумя дубликатами, остальные нам не доступны и живут очень мало). Причем совершенно независимых, давайте приведу пример: int func(int n) { n++; return n; } int main(void) { int m = 10; printf("%i\n", func(m)); printf("%i", m); return 0; } Вывод будет 11 и 10. Но мы не хотим создавать лишние дубликаты, почему? Это все «тормозит» программу: совершаются лишние действия, выделяется на программу больше памяти и т. п. Более того, а если мы хотим, чтобы функция меняла, передаваемые ей переменные? С одной то еще можно справиться, в данном примере можно было написать m = func(m); Но переменная может быть не одна. Тут на помощь приходят ссылки. Указатели и ссылки Объяснить что такое ссылка было бы проще, но беда в том, что в Си ссылок нет. Однако есть операция взятия адреса. Например, мы не можем обозначить передачу аргумента по ссылке в функцию, хотя ссылку на переменную передать мы можем, что особо нам ничего не даст. int func(int n) { n++; return n; } int main(void) { int m = 10; printf("%i\n", func(&m)); //&m передача адреса printf("%i", m); return 0; } Между ссылкой и значением переменной огромная разница, но такой язык, как Си, разницу эту не замечает. Такой код, например, не скомпилируется в С++, потому что он не имеет смысла. Ссылка — это адрес переменной, если мы напишем: printf("%i", &m); то мы увидим, какое-то число, возможно и отрицательное. Для нас оно ничего не значит, но значит для компьютера и выполняемой на нем программы. По этому адресу содержится значение переменной, т. е. 10. Для Си адрес это просто число типа int. Поэтому предыдущий код брал адрес переменной и увеличивал его на единицу. Если вы скомпилируете программу, добавив во второй printf амперсанд перед m, то вы увидите, что адреса будут различаться на единицу. Что делать с адресом? Кроме арифметических действий, что очевидно, можно еще брать значение, которое хранится по этому адресу, и делается это при помощи оператора *. Да — это тот самый указатель. Например, мы можем написать: printf("%i", *&m); И увидим 10. Операторы * и & противоположные, поэтому вместе их нет смысла применять. Это как прибавить к 10 единицу и тут же ее отнять. Но для указателей есть специальный тип в Си, чтобы можно было хранить адреса в переменной: int *ptr; присваивать числовое значение такой переменной — глупо. Вы ведь не знаете, что лежит по тому адресу, что вы присваиваете, более того вы и не должны этого знать. Но вы можете присваивать адреса обычных переменных или другие указатели. int m = 10; int *ptr = &m; printf("%i, %i", m, *ptr); Результат: 10, 10 Обратите внимание на *ptr в printf, если не поставить звездочку, вы увидите не значение, а адрес. Если вы работаете с указателями, для получения значения их необходимо «разыменовывать», и делается это оператором *, как в примере. Конечно, у вас возникнет вопрос, зачем это все? Ну вот мы и подобрались к ответу на предыдущий вопрос, как заставить функцию менять значение переменной на стеке, которая передается в качестве аргумента. Мы можем передать не значение переменной, а ее адрес (указатель на нее), затем мы разыменовываем указатель, получая значение. Увеличиваем значение на единицу, результат у нас сохранится по адресу, а не в дубликате, поэтому изменится и оригинал. Вот код: int func(int *n) { (*n)++; return *n; } int main(void) { int m = 10; func(&m); printf("%i", m); return 0; } Результат 11. Обратите внимание на строку (*n)++; Мы разыменовываем указатель, получая значение, т. е. 10 и увеличиваем 10 на 1. Я еще раз повторю, что в случае с указателем без звездочки мы работаем с адресом. И скобки тоже важны, потому что операция ++ имеет более высокий приоритет, так что без скобок, мы сначала увеличим адрес на 1, а потом возьмем значение по этому адресу и все. Также обратите внимание, что код становится совсем не безопасным, оперируя адресами, а не значениями можно легко «залезть не туда» и поменять то, что вообще нельзя трогать. К счастью, современные ОС не дадут вам вылезти из адресного пространства вашей программы, так что синий экран смерти вы вряд ли вызовите. Но программа может крашнуться. Например, если забудете поставить & в строке func(&m); К счастью в С++ вы получите ошибку компиляции. Это был самый простой пример использования указателей. Давайте вспомним, что переменная массива это тоже указатель, разыменуем его: int mas[] = {1,2,3,4,5}; printf("%i", *mas); Результат: 1. Как уже раньше и говорилось mas — это указатель на первый элемент последовательности. Если мы его разыменовываем, то получаем значение по этому адресу, а это и есть первый элемент. Чтобы получить доступ ко второму элементу нужно увеличить адрес. И тут самое интересное, нам не обязательно знать, сколько байт нужно прибавить, чтобы получить адрес следующего элемента, за нас это может сделать Си. int mas[] = {1,2,3,4,5}; printf("%i", *(mas+1)); Мы получаем значение второго элемента, а Си уже само решает сколько байт нужно добавить, на основе типа. Именно поэтому для указателей и нет единого типа, иначе Си бы не смог разобраться, сколько памяти реально выделено по текущему адресу. Или, как в данном случае, не мог бы найти следующий элемент массива: int mas[] = {1,2,3,4,5}; int *ptr = mas; //mas и так адрес, & - не нужен //или int *ptr = &mas[0], что эквивалентно printf("%i", *(ptr+1)); Логично было бы еще исправить второе копирование при возвращении из функции. Ну тут все еще интересней. Дело в том, что совсем избежать его мы не можем, но мы можем сократить накладные расходы, если тип возвращаемого значения будет отличен от int. Представим, что мы написали свой тип, который занимает 256 байт памяти, в обычной ситуации копировались бы все 256 байт, но если возвращать указатель на тип, то копироваться будет только 4 байта. Выигрыш в 64 раза. Но все не так легко, как кажется. Тут мы переходим к следующему применению указателей — создание объектов на куче. Динамическое выделение памяти В этой терминологии больше смысла, поэтому я применю ее. Почему динамически? Потому что мы теперь сами решаем: как, когда и сколько памяти будет выделено. Естественно, теперь мы также обязаны и очищать память, которая нам больше не нужна, так как компилятор сам не сможет этого понять. И важно, что память выделяется в куче, а не в стеке при этом способе. Чтобы выделить память в Си, достаточно написать следующее: malloc(sizeof(int)); В С++ это выглядит несколько иначе, из-за более строгой типизации: (int *)malloc(sizeof(int)); Как видите, мы выделяем блок памяти размера int и преобразуем его в тип int *. Так что «динамические» переменные мы вынуждены хранить, как указатели. int *b = (int *)malloc(sizeof(int)); //выделение памяти free(b); // очистка памяти Если память не очищать, то когда-нибудь она кончится. И снова вам повезло, современные ОС при завершении программы, освободят всю неочищенную вами память, так что перезапуская программу, вы память не забьете, но если программа не будет завершаться, тогда память рано или поздно кончится. Загвоздка со вторым копированием в том, что выделение памяти руками программиста, это процесс долгий, и, вероятно, 256 байт скопируются на стеке даже быстрее, чем выделится 4 байта памяти при использовании malloc. Поэтому возвращение указателей — не панацея, подробности проблемы копирования в возвращаемом значении мы разберем в следующем семестре, пока стоит забыть о ней. Выделение памяти для int через malloc смысла мало имеет, а вот выделение памяти для массива уже интересней. Допустим вы создали массив из 10 элементов: int mas[10]; Все, теперь он у вас всегда из 10 элементов и будет состоять, а если хочется больше? Удобство динамического выделения памяти состоит в том, что оно не обязательно одноразовое. Вот выделили мы память на 10 элементов, а потом захотели и выделили на 11. Нет ничего проще: int *mas = (int *)malloc(sizeof(int)*2); //выделение памяти на 2 элемента mas[0] = 1; mas[1] = 2; printf("%i ", mas[1]); free(mas); mas = (int *)malloc(sizeof(int)*3); //выделение памяти на 3 элемента mas[0] = 1; mas[1] = 2; mas[2] = 3; printf("%i", mas[2]); free(mas); Есть еще одна функция calloc, которая выделяет блок памяти для массива: int * arrayPtr = (int*) calloc(size,sizeof(int)); Работает по сути также, как и в предыдущем примере. Предыдущий пример также можно переписать с функцией realloc, которая может изменить размер блока памяти или переместить блок памяти в другое место. #include #include int main () { int input,n; int count = 0; int* numbers = 0; int* more_numbers = 0; do { printf ("Enter an integer value (-1 to end): "); fflush(stdout); scanf ("%d", &input); if (input != -1) { count++; more_numbers = (int*) realloc (numbers, count * sizeof(int)); if (more_numbers!=0) { numbers=more_numbers; numbers[count-1]=input; } else { free (numbers); puts ("Error (re)allocating memory"); return 1; } } } while (input!=-1); printf ("Numbers entered: "); for (n = 0;n < count; ++n) printf ("%d ",numbers[n]); free (numbers); } return 0; В этом примере фраза «динамическое выделение памяти» полностью оправдана. Обратите внимание, что память, выделенная через malloc, calloc, realloc, не очищается автоматически, в этом плюс и минус. Плюс в том, что теперь мы не ограничены блоком и можем, например, возвращать из функций указатель на массив, если память для него была динамически выделена. А минус в том, что мы можем забыть очистить память. Плюс слишком важен, так как, например, такой код работать может и будет, но с увеличением программы в какой-то момент перестанет: int *newarray() { int mas[10] = {1,2,3,4,5}; return mas; } int main () { } int *mas = newarray(); for (int n=0;n<10;++n) printf ("%d ",mas[n]); return 0; Что здесь происходит? Мы пытаемся вернуть адрес локальной переменной, после окончания работы функции память по этому адресу будет очищена, но мы все же используем значение по этому адресу в другой функции. Компилятор может вас предупредить об этом, но это всего лишь warning, а не error. Писать такой код категорически воспрещается, потому что его поведение непредсказуемо. Почему код может работать? Дело в том, что Си безразлично, была ли выделена память по этому адресу или нет, если вы захотите записать туда значение, то он сделает это. Если это вас смущает, то Си всегда предполагает, что вы знаете, что делаете. Избегая ненужных проверок, он и обрел свою славу, как язык для быстрых программ. Другой вопрос, успела ли память по данному адресу заняться чем-то другим? Как уже говорилось, все локальные переменные создаются на стеке, и массив — не исключение. Для каждой функции свой стек, поэтому имена локальных переменных у нас спокойно могут пересекаться, программа не запутается. Но после окончания работы функции стека уже нет, и на его месте может выделиться память под что-то другое, в этом случае — краш. Следующая программа может и не крашиться: int *newarray() { int *mas = calloc(10, sizeof(int)); for(int i = 0; i < 10; ++i) mas[i] = i; return mas; } int main () { int *mas = newarray(); free(mas); //очистим память for (int n=0;n<10;++n) printf ("%d ",mas[n]); return 0; } Тем не менее писать так тоже не следует! Строки Теперь мы можем писать алгоритмы работы со строками более элегантно. Приведу пример копирования строки: char * strcpy(char *strDest, const char *strSrc) { char *temp = strDest; while(*strDest++ = *strSrc++); return temp; } int main () { char *str = "123456789"; char str2[256]; strcpy(str2, str); printf("%s", str2); return 0; } Обратите внимание на строку while(*strDest++ = *strSrc++); Теперь вам должно быть понятно, почему это работает. Цикл закончится, когда указатель станет указывать на '\0', что интерпретируется ложью в данном контексте. В этом и проявляется лаконичность языка Си. В других языках такого вы не увидите. Указатели на указатели Если мозг еще не взорвался, то пора перейти к действительно опасным вещам. Что если мы хотим взять адрес у переменной a, которая содержит адрес на другую переменную b, и при этом иметь возможность узнать значение переменной b? Нам помогут указатели на указатели. (Кстати, тут можно продолжать бесконечно и ввести указатель на указатель на указатель на указатель …......) int main () { int b = 10; int *a = &b; int **c = &a; printf("%i ", c); //адрес a printf("%i ", *c); //адрес b printf("%i", **c);//значение b return 0; } Так пишут редко, но иногда есть и в этом смысл. Чаще указатели на указатели применяют для выделения память на двумерные динамические массивы и работу с ними. Т.е. сначала мы выделяем память на массив указателей, а затем для каждого указателя выделяем память на массив. Так мы можем получать не только прямоугольные массивы, но и ступенчатые, например: 1, 2, 3, 4 3, 4, 5, 6 0, 0, 0, 0 прямоугольный 1, 2 3, 4, 5, 6 ступенчатый int main () { int n = 10, m = 10; int **mas = (int **)malloc(n*sizeof(int *)); for(int i = 0; i < n; i++) { mas[i] = (int *)malloc(m*sizeof(int)); } for(int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { mas[i][j] = i+j; printf("%i ", mas[i][j]); } printf("\n"); } //очистка памяти for(int i = 0; i < n; ++i) { free(mas[i]); } free(mas); return 0; } Освобождать память тоже стало сложнее. С учетом того, что строка — это указатель, то массив строк — указатель на указатель. Тогда двумерный массив строк... Ну вы поняли. Теперь еще интересней, что означает запись char *str[]? По логике, это указатель на массив, но, возможно, что это и двумерный массив. Также можно это назвать указателем на строку или массивом строк. Теперь вспомним, как правильно писать функцию main int main(int argc, char *argv[]) Эта запись стала понятней. В функцию main можно передавать параметры. Действительно, если запустить программу через консоль (либо в ярлыке указать), то можно передать стартовые параметры. Наверняка, вы сталкивались с этим, если играли в игры. Иногда в ярлык нужно было прописать -w для запуска в окне или -game cstrike для запуска cs1.6 вместо half life. Впрочем, даже в самых современных играх в стиме этим еще пользуются. Итак, argc — это количество переданных параметров, argv — сами параметры. Запуск в консоли может выглядеть так: 1.exe param1 param2 10 Не стоит забывать, что минимум 1 параметр всегда передается в main — это имя самой программы (”1.exe”). Так что ваши параметры будут начинаться с 1, а не с 0. argc = 4; argv = {“1.exe”, “param1”, “param2”, “10”} Вот так будет заполнен argv (не нужно это в программу прописывать!). Имейте это ввиду, когда передаете числовые параметры. Они будут представлены в виде строк. Указатели на функции Если мозг еще не отключился, то пора узнать самое изощренное применение указателей. У функции есть адрес, если вы не понимаете зачем, то вы не программировали на asm. Но даже в самых высокоуровневых языках очень удобно, что у функции есть адрес. Значит можно держать адрес в переменной, т. е. в указателе на функцию: void inc(int *i) { (*i)++; } int main () { void (*fptr)(int *) = &inc; //указатель на функцию int a = 0; fptr(&a); //использование указателя для вызова функции printf("%i", a); return 0; } Указатель на функцию выглядит довольно сложно, но это только первое впечатление. Приглядитесь: void – тип возвращаемого значения, *fptr — ну, мы уже такое не раз писали, (int *) - параметры функции, в данном случае он 1. Так как мы объявляем по сути сигнатуру, то указывать имя аргумента не нужно. Т.е. эта запись не сложнее объявления сигнатуры, просто пара скобок и * добавились. Затем мы используем указатель, как функцию, в этом нет вообще ничего необычного. Зачем могут понадобиться указатели на функцию? Вдруг, вы захотите передавать функции в качестве аргументов. Это может быть очень удобным, и это активно используется в функциональном программировании. Пример: нужно вывести массив в прямом порядке и обратном, но, используя одну и ту же функцию. Решение: void inc(int *i) { (*i)++; } void dec(int *i) { (*i)--; } void PrintMas(int *mas, void (*fptr)(int *), int startindex, int endindex) { for (int i = startindex; i != endindex; fptr(&i)) { printf("%i ", mas[i]); } printf("\n"); } int main () { int mas[] = {1,2,3,4,5,6,7,8,9}; PrintMas(mas, &inc, 0, 9); PrintMas(mas, &dec, 8, -1); return 0; } Как видите, очень элегантно. Мы просто передаем первый индекс и последний и определяем функцией, что нужно делать со счетчиком. Лабораторная работа №7 Задание 0. Выбрать максимальный элемент матрицы С (размер m*n), элементы четных строк разделить на максимальный элемент, а к элементам нечетных прибавить максимальный элемент. Задание 1. Дан двумерный массив, хранящийся в файле в следующем формате: 3 123 456 789 Первое число — количество строк и столбцов массива, далее идет сам массив. Программа должна разделить массив из файла на два ступенчатых треугольных массива по главной диагонали. Для данного массива результат выглядит так: 1 массив 123 56 9 2 массив 1 45 789 Массив может быть любым, но всегда количество столбцов = количеству строк. В данной лабораторной запрещается применять оператор []. Т.е. при обращении к элементам массива вы должны использовать адресную арифметику. Задание 2. Написать вторую программу, которая составляет из двух треугольных массивов один квадратный. Читать она должна их из файла, и сохранять в файл.