Указатель (тип данных)

Изобретение указателей приписывают Гарольду Лоусону в 1964 году^[2]. В 2000 году Лоусон был удостоен премии Pioneer Award IEEE Computer Society «за изобретение переменной-указателя и внедрение этой концепции в язык PL/I, что впервые обеспечило гибкую работу со связанными списками в языке высокого уровня общего назначения»^[3]. Согласно Оксфордскому словарю английского языка, термин pointer впервые зафиксирован в печати как stack pointer в техническом отчёте компании System Development Corporation.

В информатике указатель — это разновидность ссылки.

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

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

Указатель на память (или просто указатель) — это примитивное значение, предназначенное для использования в качестве адреса памяти; говорят, что указатель указывает на этот адрес. Если значение указателя совпадает с адресом некоторого объекта в памяти, указатель считается указывающим на этот объект.

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

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

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

Относительные адреса — разновидность ручной сегментации памяти, со своими преимуществами и недостатками. Например, двухбайтовый сдвиг (16-битное беззнаковое целое) позволяет адресовать до 64 Кбайт данных, причём можно увеличить диапазон до 128К, 256К или 512К, если адрес предоставить некоторому выравниванию и корректировать смещение (например, сдвиг влево на 1, 2 или 3 бита для выравнивания по словам/двойным словам).

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

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

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

Как правило, разрядность указателя превышает количество реально адресуемых ячеек памяти, поэтому попытка обращения к несуществующему адресу приведёт к ошибке — так, на архитектуре x86 это называется нарушение сегментации, а на AMD64 (длина указателя 64 бита при физических адресах 48 бит) особое значение имеет соблюдение правил каноничности адресов (иначе возникнет общая ошибка защиты).

Современные архитектуры поддерживают схемы сегментации либо пейджинга, иногда с физическими адресами шире виртуальных, что позволяет в каждый момент времени адресовать только часть памяти (пример — расширение PAE для x86, позволяющее работать с адресами до 36 бит при 32-битных указателях).

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

Указатели свободно поддерживаются без ограничений в языках PL/I, C, C++, Паскаль и во многих ассемблерах. Указатели лежат в основе реализации большинства структур данных и используются для передачи данных между частями программы.

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

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

Указатели позволяют реализовать передачу параметров по ссылке (call by reference): изменение значения внутри подпрограммы отражается вне её тела, а также позволяют возвращать несколько значений из функции.

Указатели применяются для динамического выделения и освобождения памяти. Невыделенная после использования память приводит к утечке памяти.

Базовый синтаксис объявления указателя:^[4]

int *ptr;

Это определяет ptr как указатель на объект типа int.

В C переменные с автоматическим временем жизни не получают значения по умолчанию — необходимо следить за корректностью (валидностью) адреса, на который указывает ptr; часто рекомендуется инициализировать указатель явно значением NULL:^[5]

int *ptr = NULL;

Попытка разыменования нулевого указателя (NULL) в C приводит к неопределённому поведению^[6] — зачастую программа завершается с ошибкой сегментации.

Пример — инициализация и присваивание адреса:

int a = 5;
int *ptr = NULL;

ptr = &a;

Теперь ptr содержит адрес переменной a. Если, например, a хранится в ячейке 0x8130, то ptr примет значение 0x8130. Разыменование (операция со звёздочкой):

*ptr = 8;

Запишет значение 8 по адресу, на который ссылается ptr (т. е. переменной a).

Операция показана в таблицах:

Адрес	Содержимое
0x8130	0x00000005
0x8134	0x00000000

(Здесь NULL представлен как 0x00000000.)

Адрес	Содержимое
0x8130	0x00000005
0x8134	0x00008130

Адрес	Содержимое
0x8130	0x00000008
0x8134	0x00008130

Обращение к элементам массива в языке C определяется через арифметику указателей: array[i] эквивалентно *(array+i)^[7].

Пример:

int array[5];
int *ptr = array;
ptr[0] = 1;
*(array + 1) = 2;
*(1 + array) = 3;
2[array] = 4;

Массив array — это блок из пяти целых чисел, а имя массива можно использовать как указатель на его начало.

Для машины с little endian структура размещения элементов (предполагая начало адреса 0x1000):

	0	1	2	3
1000	2	0	0	0
1004	4	0	0	0
1008	3	0	0	0
100C	1	0	0	0
1010	5	0	0	0

• array — 0x1000
• array+1 — 0x1004 (добавляется размер int)
• *array — разыменовывает содержимое по адресу 0x1000.
• array[i] ≡ *(array + i)

Пример определяет связанный список на C:

#define EMPTY_LIST  NULL

struct link {
    void        *data;
    struct link *next;
};

Эквивалентная рекурсивная ссылка на Haskell:

 data Link a = Nil
             | Cons a (Link a)

В C требуется аккуратная работа с функциями-обёртками.

Передача переменной по адресу позволяет менять её значение внутри функции:

#include <stdio.h>
void passbyvalue(int n) {
    n = 12;
}
void passbyaddress(int *m) {
    *m = 14;
}

int main(void) {
    int x = 3;
    passbyvalue(x);      // x остаётся равен 3
    passbyaddress(&x);   // x становится 14
    return 0;
}

Указатели используются для хранения адресов динамически выделенных блоков памяти, например, с помощью malloc():

struct Item {
    int         id;
    char *      name;
    float       cost;
};

struct Item * make_item(const char *name) {
    struct Item *Item = (struct Item *)malloc(sizeof(struct Item));
    if (Item == NULL)
        return NULL;
    memset(Item, 0, sizeof(struct Item));
    Item->id =   -1;
    Item->name = NULL;
    Item->cost = 0.0;
    Item->name = (char *)malloc(strlen(name) + 1);
    if (Item->name == NULL) {
        free(Item);
        return NULL;
    }
    strcpy(Item->name, name);
    return Item;
}

Освобождение динамической памяти — free():

void destroy_item(struct Item *item) {
    if (item == NULL)
        return;
    if (item->name != NULL) {
        free(item->name);
        item->name = NULL;
    }
    free(item);
}

В некоторых архитектурах указатели применяются для работы с адресами периферии и устройств:

int *hardware_address = (int *)0x7FFF;

Пример обращения к видеопамяти PC (CGA):

#define VID ((unsigned short (*)[80])0xB8000)
void foo() {
    VID[4][1] = 0x1F00 | 'A';
}

Во многих языках указатель строго связывается с типом объекта, на который он указывает. Например:

int *money;
char *bags;
bags = (char *)money;

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

В стандарте C 2005 года^[8] отмечено, что приведение указателя между типами должно сохранять корректность выравнивания.

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

Дикий указатель (wild/dangling pointer) — указатель, которому не присвоен валидный адрес; попытки разыменования такого указателя ведут к сбоям и нештатным ситуациям (нарушение доступа, утечка памяти, ветвление по ошибочному адресу).

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

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

Нулевой указатель (англ. null pointer) — специальное зарезервированное значение, показывающее, что указатель не ссылается на валидный объект. Используется, например, для маркировки конца списка или указания на провал операции. Аналоги можно встретить в СУБД (NULL), хотя семантика обычно разная.

В C макрос NULL определяет нулевое значение, обычно эквивалентно (void*)0. Разыменование нулевого указателя — чтение или запись в невыделенную память — приводит к ошибкам выполнения (сегментам ошибкам/исключениям).

В C++11 появился специальный литерал nullptr для явного указания нулевого указателя.

Базовый указатель (base pointer) — указатель, трактующийся как смещение относительно другого указателя (например, базового адреса блока данных)^[9].

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

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

int sum(int n1, int n2);
int (*fp)(int, int);
fp = ∑
x = (*fp)(a, b);

Дикий указатель (англ. wild pointer) — неинициализированный указатель, содержащий случайное (или устаревшее) значение и ведущий к ошибкам при разыменовании.

int func(void)
{
    char *p1 = malloc(sizeof(char));
    char *p2;
    *p1 = 'a';      /* OK */
    *p2 = 'b';      /* Undefined behavior */
}

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

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

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

Массив резервирует память для всех своих элементов подряд, адрес i-го элемента вычисляется как сумма базового адреса и i × размера элемента.

Ada — строго типизированный язык, где все указатели имеют тип и по умолчанию инициализируются значением null; попытка разыменования null вызывает исключение. Указатели называются типы доступа.

В некоторых реализациях BASIC (Windows) имеются функции STRPTR(), VARPTR(), OBJPTR(), ADDRESSOF — все возвращают целые числа с адресом, которые можно интерпретировать как указатель. Современные диалекты (FreeBASIC, BlitzMax) реализуют полноценные указатели с ограничениями, аналогичными void* в C.

dim as integer f = 257
dim as any ptr g = @f
dim as integer ptr i = g
assert(*i = 257)
assert( (g + 4) = (@f + 1) )

Указатели — переменные, хранящие адреса. Для универсальности применяются void*. В C++11 стандартная библиотека предоставляет ряд умных указателей (unique_ptr, shared_ptr). Арифметика указателей ограничена возможностями языка (разрешены только переходы внутри массива).

int x = 4;
void* q = &x;
int* p = q; /* в C — допустимо; в C++ — только с кастом */
int i = *p;
int j = *(int*)q;

В C# указатели поддерживаются только внутри блоков кода, помеченных unsafe, и требуют специальных прав. Для работы с памятью вне "безопасной" среды используют IntPtr:

IntPtr pointer = System.Runtime.InteropServices.Marshal.AllocHGlobal(16);
// ...
System.Runtime.InteropServices.Marshal.FreeHGlobal(pointer);

В COBOL указатели используются для обращения к переменным, объявленным в разделе LINKAGE, а также для работы с динамически выделенной памятью.

PL/I поддерживает указатели ко всем типам данных, включая структуры; развитые средства рекурсии, управления строками, встроенные функции.

В D указатели совместимы с указателями из C.

В Eiffel указатели существуют в виде ссылок, арифметика над ними запрещена.

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

type real_list_t
  real :: sample_data(100)
  type (real_list_t), pointer :: next => null ()
end type

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

В Java указателей нет: любые переменные, не являющиеся примитивными, реализуются как ссылки; прямого доступа к памяти язык не предоставляет. Освобождение памяти происходит автоматически с помощью сборщика мусора^[10].

В Modula-2 указатели реализованы, как и параметры VAR; некоторые варианты языка (например, Modula-3) внедряют сборщик мусора.

Ограничивает возможности по обходу системы типов; встроена сборка мусора.

В Паскале формально указатели разрешены только для работы с динамически выделяемыми анонимными переменными без арифметики указателей; типизация жёсткая, конвертация между указателями разных типов невозможна^[11]. В коммерческих реализациях доступны расширения.

В Pauscal поддерживаются указатели на переменные, структуры, процедуры, прототипы, объединения, классы и методы; возможно преобразование типов с помощью указателей.

В Perl указатели имеются в виде упаковки/распаковки структур низкоуровневых данных, чаще используются ссылки, не поддерживающие арифметику.