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

Предоставляя определённые лексические средства для работы с указателями, языки уровня C/C++ обеспечивают потенциал для производительности сопоставимой с программами на языках ассемблера. Тем не менее, начинающим и не очень искушённым программистам, не желающим углубляться в детали, эта тема зачастую кажется избыточно-инженерной. Всё же, по моим наблюдениям, человеческие ошибки при работе с указателями находятся где-то на втором месте по частоте, после ошибок в тривиальных логических условиях¹. В этой заметке я постараюсь объяснить только необходимую суть, от которой затем, руководствуясь индуктивной логикой, читатель сам сможет предсказать некоторые тонкости. Хотелось бы часто ссылаться на различия между физическим уровнем представления данных и лексическими конструкциями языка — по этой причине я написал, очень беглую и общую заметку о теории формальных языков. Тем не менее, должен извиниться за некоторую избыточность материала: сейчас это неясно, но на отношениях внутри системы типов Си, лучше всего раскрывающейся именно в теме указателей, будет построена вся последующая работа с классами C++, в Geant4, ROOT и любых других библиотеке или фреймворке.

Уровни представления указателей

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

Физический

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

• тип целого числа в смысле его длины может различаться между платформами (это будет четырёхбайтное целое, для 32-битных платформ, длинное восьмибайтное целое для 64-битных и пр.)
• структура памяти, на которую ссылается указатель может быть виртуальной, и, попробовав распечатать в консоль несколько произвольных указателей из своей программы как целые числа, вы не обнаружите какой-то очевидной системы в размещении произвольно-выбранных объектов на страницах памяти. Тем не менее, удобно мыслить себе память, как (одномерную) последовательность нумерованных байтовых ячеек, число которых в известном смысле и соответствует адресу записанному в указатель.

Практическая иллюстрация того тезиса что указатель всегда представим как целое число (лексика описана ниже):

1
2
3
4
5
6
7
8
9

# include <stdio.h>

int main(int argc, char * argv[]) {
    float a;
    void * aPtr;
    aPtr = &a;
    printf("%ld\n", (unsigned long int) aPtr );
    return 0;
}

В ней мы объявляем две переменных — a, типа числа с плавающей точкой (запятой), и aPtr — типа указателя. Затем выставляем значение переменной aPtr на адрес памяти, хранящей значение переменной a. В C/C++ этот адрес всегда будет соответствовать первому байту из нескольких хранящих значение переменной. Затем мы печатаем в консоль длину типа данных void * (который для 64-битных платформ будет составлять восемь байт) и, собственно, само численное значение этого указателя.

Замечание: в силу этих двух причин, практически всегда жизненный цикл указателя в программе выглядит довольно непрозрачно: какой-то объект с контринтуитивной на первый взгляд лексикой, может быть извлечён на основе какой-то переменной (или возвращён из функции), в основном используется только для того чтобы его разыменовать (англ. dereference, здесь — "обратиться по адресу"), и никаких, собственно, численных операций не поддерживает... За исключением небогатой арифметики указателей, о которой ниже.

Лексический

На лексическом уровне с указателем связывается некоторая дополнительная семантика — указатель обычно представлен специальным типом. Хотя в примере выше мы объявили "просто указатель" (void *), практически, принято привлекать дополнительную семантику к объявлениям указателей за счёт лексических возможностей C/C++ — компилятор может учитывать информацию о том, какого типа данные находятся по этому адресу, однако эта информация остаётся доступна коду только на этапе сборки. Делается же это указанием, собственно, типа данных перед астериском (*). Так, тип указателя на блок данных хранящих значение float будет выглядеть как float *, и переменную aPtr выше следовало бы типировать как float * aPtr. Соответственно, и для любого другого типа данных: int * — для данных типа int, etc.

Получение адреса любой переменной в C осуществляется через оператор (извлечения адреса) который выглядит как знак амперсанда перед именем переменной:

1
2

float a;
float * aPtr = &a;

Напротив, разыменование (dereferencing) выглядит как знак-астериск перед переменной-указателем:

1

float b = *aPtr;

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

Важно помнить, что в C/C++ не предусмотрено никакой системы интроспекции простейших типов, то есть, ничто не помешает вам в какой-то момент разыменовать указатель типа int * как указатель ссылающийся на тип float. Взгляните на следующий фрагмент:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# include <stdio.h>

int main(int argc, char * argv[]) {
    float a = 0.123;
    float b;
    float * aPtr;
    aPtr = &a;
    printf("%d\n",  ((int ) *aPtr) );
    printf("%d\n", *((int*)  aPtr) );
    return 0;
}

Вывод этой программы выглядит так:

$ ./a.out 
0
1039918957

Я верю что теперь, пусть и не без некоторого труда, вы можете объяснить, такой результат. Проделайте это упражнение — оно очень похоже на то с чем вам придётся столкнуться множество раз при чтении или написании кода на C/C++: разница между строками 8 и 9 объясняется сугубо порядком лексических операций приведения типа и разыменования указателя. Пока наши семинары приостановлены, можете воспользоваться комментариями здесь, если вы не преуспели.

Разыменование слева

Конечно же, ничто не мешает, имея какой-то адрес доступной памяти, производить по нему не только чтение данных, но и запись. Лексика C/C++ в этом отношении старается быть достаточно интуитивной:

1
2
3
4
5
6
7
8
9

# include <stdio.h>

int main(int argc, char * argv[]) {
    float a = 0.123;
    float * aPtr = &a;
    *aPtr = 0.321;
    printf("%f\n", a);
    return 0;
}

Строка 6 разыменовывает указатель aPtr ссылающийся на адрес переменной a и производит запись значения с плавающей точкой соответствующего литералу 0.321.

Распространённым приёмом построенным на "разыменовании слева" (имеется в виду слева от оператора присваивания, знака равенства =) является передача некоторого адреса для записи значений в функцию, с тем чтобы внутри последней производить запись в данный адрес. Таким образом, вы можете снабжать свою функцию некоторыми, как говорят, побочными эффектами (англ. side effects), имея здесь в виду, что функция оказывается способной производить изменения объектов существующих дольше чем её собственное время выполнения, изменять что-то помимо переменных объявленных внутри неё самой (используя для этого адреса памяти работа с которыми обеспечивается посредством указателей). Несколько надуманный пример счётчика от нуля до десяти:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# include <stdio.h>

int increment_to_10( float * resultPtr ) {
    if( *resultPtr < 10 ) {
        *resultPtr = *resultPtr + 1;
    } else {
        return 0;
    }
    return 1;
}

int main(int argc, char * argv[]) {
    float a = 0;
    while(increment_to_10(&a)) {
        printf( "...%f\n", a);
    }
    return 0;
}

Здесь функция increment_to10() принимает указатель на число с плавающей точкой, и использует его для того чтобы производить последовательный инкремент (увеличение на единицу) до тех пор, пока число по данному адресу не сделается больше 9. В случае, если инкремент был произведён такая функция вернёт 1, если же нет — 0. Это возвращаемое значение мы используем из вызывающей функции main(), внутри цикла while(), тело которого печатает значения после инкремента: от 1 до 9.

Не нужно опасаться здесь термина "разыменование слева" (left-side dereferencing, lvalue, см. напр. SO) поскольку это вполне принятое различие в искусственных языках, где операция присваивания предполагает различное поведение для идентификаторов слева и справа от инфиксного оператора присваивания (=).

Массивы и указатели

Частым практическим случаем является ситуация, когда, в некоторой области памяти, следом за одним каким-то элементом фиксированной длины, записывается следующий, того же типа. Хотя, вообще говоря, понятие массива (array) как структуры данных в которой одному или нескольким индексам сопоставляется последовательное множество элементов, не подразумевает каких-то требований к физическому размещению элементов в памяти, массив в смысле C/C++ реализован именно так. Для работы с массивами предусмотрена специальная лексика:

• Объявление массива производится с обязательным указанием числа элементов. Это может быть сделано явно, указанием числа элементов в угловых скобках, например float a[10], или неявно, посредством инициализации массива: int b[] = {42, 42, 15}. Если подумать, это естественное требование, происходящее из необходимости компилятору на этапе генерации машинного кода предусмотреть выделение участка памяти фиксированной длины. В случае неявной инициализации, он сам способен немедленно посчитать число элементов справа.
• Для обращения к элементу массива пишут его индекс в угловых скобках после имени переменной-массива: a[5]; b[1].
• Элементы обычного массива в C/C++ нумеруются от нуля. То есть, в примерах выше, первым элементам соответствуют a[0] и b[0], последним — a[9] и b[2].

Интересной и важной чертой C/C++ является (неполная) взаимозаменяемость одномерных массивов и указателей, происходящая из того факта, что оба они физически соответствуют только лишь какому-то определённому адресу в памяти, и на физическом уровне абсолютно тождественны. Что до лексики — вы можете разыменовать массив как указатель чтобы получить первый элемент, или обращаться к элементу смещённому относительно какого-то адреса на n элементов, используя переменную с этим адресом как имя массива:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# include <stdio.h>

int main(int argc, char * argv[]) {
    float   a = 42;
    float   myArr[] = { 4.0, 5.0, 3.0 };
    float * myPtr = &a;

    printf( "*myPtr=%f\n", *myPtr );
    printf( "*myArr=%f\n", *myArr );
    myPtr = myArr;
    printf( "*myPtr=%f\n", *myPtr );
    printf( "myPtr[1]=%f\n", myPtr[1] );
}

Вывод:

$ ./a.out 
*myPtr=42.000000
*myArr=4.000000
*myPtr=4.000000
myPtr[1]=5.000000

Этот код абсолютно корректен с точки зрения C/C++, хотя для практической применимости этих выразительных средств необходимо будет узнать ещё одну деталь.

Под неполнотой взаимозаменяемости следует понимать лишь то что на этапе трансляции вы можете запросить длину массива: для переменной-массива a объявленной как int a[12], возможно получить общее число байт в массиве, как sizeof(a). В то же время, для какой-нибудь переменной b объявленной как int * b = a (указывающей на первый элемент массива a), нет возможности запросить подобную информацию в силу определения указателя как только лишь типированного адреса.

Ну и важный пример — знакомая вам по сигнатуре точки входа main() составная конструкция, объявляющая типом аргумента argv массив неизвестной длины элементами которого являются указатели типа char *: char * argv[]. В литературе, впрочем, вы можете встретить объявление char ** argv (указатель на указатель), которое эффективно во всём эквивалентно char * argv[]. Какой из этих вариантов использовать -- вопрос полностью лишь одного вкуса.

Разумеется, вы можете объявлять указатели произвольной вложенности (int *** a, etc.), многомерные массивы (float matrix[3][3]), сочетать указатели и массивы, однако ранг вложенности больше двух появившийся в программе, за редким исключением, есть индикатор переусложнённости кода.

Арифметика указателей

Для указателей определяется простая алгебра:

• Сумма указателя myPtr и целого числа n даст указатель того же типа на адрес смещённый относительно myPtr на n элементов (в общем случае — элементов, не байт!). Так, если myPtr имеет тип int * myPtr, то myPtr + 4 будет соответствовать элементу смещённому на 16 байт относительно myPtr (размер int — четыре байта).
• То же верно и для разности указателя и целого числа, с тем отличием, что смещение будет производится в обратную сторону. Так указатель (&a[3]) - 3 будет указывать на первый (с индексом 0 элемент некоторого массива int a[3]).
• Разность двух указателей даёт число элементов определённого (одного) типа между ними (distance)².

Для указателей определены и стандартные операции сокращённого целочисленного инкремента/декремента, в смысле той же алгебры:

1
2
3
4

myPtr ++;
++ myPtr;
myPtr += 2;
myPtr -= n;

Вообще говоря, операции единичного инкремента и декремента в C/C++ могут быть записаны слева (++i) и справа (i++). О незначительном различии в их поведении вам можно не задумываться до тех пор пока вы не будете использовать результат этого выражения (в смысле его собственного значения, например: int a = ++i;, а не значения переменной i, которое ничем не отличается).

Примеры

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

Итерирование элементов массива

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

Итерирование через индекс массива

Этому способу вас, вероятно, уже учили. Итерирование через индекс чуть медленнее итерирования по указателю, зато считается наиболее понятной записью:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# include <stdio.h>

float lambdas[] = { 1.23, 4.56, 7.58 };

void do_something( float lambda ) {
    /* ... do something here */
    printf( "..doing with lambda=%f\n", lambda );
}

int main(int argc, char * argv[]) {
    int i;
    for( i = 0; i < sizeof(lambdas)/sizeof(lambdas[0]); ++i ) {
        do_something(lambdas[i]);
    }
    return 0;
}

Привожу этот пример здесь я в основном чтобы сказать о конструкции for(). В C/C++ это довольно полезная конструкция: часто говорят даже о предложении for() имея в виду, что внутри неё объединены три блока-инструкции с семантикой типичной для конструкций-циклов.

Понимать её следует так:

1. В первой части предложения (до первой точки с запятой, ;) происходит инициализация. Обычно здесь инициализируется (или даже объявляется) объект используемый для итерирования. Сейчас мы просто выставляем начальное значение переменной i которую будем использовать для индексирования элементов.
2. Вторая часть — логическое условие, которое будет проверено всякий раз по завершении итерации цикла. В нашем случае производится проверка, не превышает ли значение переменной-индекса i числа элементов в массиве, которое мы получили при помощи оператора sizeof().
3. Третья часть — императивная инструкция, выполняемая всякий раз по завершении цикла, но перед проверкой условия из второго блока. В нашем случае это инкремент (увеличение на единицу) значения переменной-индекса.

Вы можете убедиться, что третий блок всегда выполняется перед вторым, например, добавив printf("%d\n", i); в строку 14.

Любая часть (и даже все) предложения for() может быть опущена, так что, наверное, простейший способ организовать бесконечный цикл в C/C++ выглядит как for(;;){}.

Значения из массива имеют "запрещённый символ" (sentinel)

Под "запрещённым символом" здесь понимается некоторое специальное значение, которое не имеет смысла в силу каких-то причин. В этом случае, вы можете связать со значением семантику терминирующего (завершающего) последовательность символа. Так, например, для набора каких-то физических коэффициентов $\lambda_i$, может быть, окажутся не имеющими физического смысла значения $\lambda_i<1$. Тогда появляется возможность при итерировании интерпретировать $\lambda < 0$ как "конец последовательности", и записать итерирование массива достаточно элегантным — простым и лаконичным образом, с привлечением арифметики указателей:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# include <stdio.h>

/* <0 terminates sequence: */
float lambdas[] = { 1.23, 4.56, 7.58, -1 };

void do_something( float * lambdaPtr ) {
    /* ... do something here */
    printf( "..doing with lambda=%f\n", *lambdaPtr );
}

int main(int argc, char * argv[]) {
    for( float * lPtr = lambdas; *lPtr > 0; ++lPtr ) {
        do_something(lPtr);
    }
    return 0;
}

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

В частности, в строках (strings, в смысле данных) в C/C++, являющихся по сути массивами целых однобайтных чисел, используют нулевое значение для отметки конца строки: всякий литерал объявленный в коде C/C++ неявно добавляет этот символ к последовательности ASCII-символов составляющих строку.

1

char word = "word";

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# include <stdio.h>

char word[] = "some";

int main(int argc, char * argv[]) {
    char c;
    for(int i = 0; i < sizeof(word); i++) {
        printf( "%d\n", word[i] );
    }
    return 0;
}

Вывод:

115
111
109
101
0

И по указателю, чтобы закрепить практику использования sentinels:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# include <stdio.h>

char word[] = "some";

int main(int argc, char * argv[]) {
    char * c;
    for(c = word; *c; ++c) {
        printf( "%d\n", *c );
    }
    return 0;
}

Вывод:

115
111
109
101

Понятно, что в последнем примере sentinel прерывает цикл на том шаге когда указатель c ссылается на символ с нулевым значением.

Гистограмма

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

• Интервал определения исследуемой величины $x$ может быть, вообще говоря, любым[^4] конечным: $x \in [x_{min}, x_{max})$. В предыдущем примере исследуемая величина была нормирована на единицу, и мы не делали перенормировку в явном виде.
• В реальных гистограммах обычно предусматривают ещё и специальные overflow/underflow бины, служащие для диагностики возможного несоответствия области определения реальным данным. Это может выглядеть как два дополнительных элемента по краям определённого массива.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/* Considers given pointer to be an array of bins of some histogram. For given
 * `value', increases corresponding bin on `weight' value.
 * Traits:
 *   - The `xMin' and `xMax' arguments corresponds the definition range of
 *     histogram.
 *   - The `nBins` has to correspond number of elements allocated by `hstPtr`
 *     plus two. First and last elements will be used for overflow/underflow
 *     bins.
 * Retrurns:
 *  0 — if value was accounted in ordinary bin
 *  -1 — underflow
 *  1 — overflow
 * */
int
hst_fill( int * hstPtr, short nBins, float xMin, float xMax,
          float x ) {
    /* check for under-/overflow */
    if( x < xMin ) {
        ++hstPtr[0];
        return -1;  /* underflow */
    }
    if( x >= xMax ) {
        ++hstPtr[nBins+1];
        return 1;  /* overflow */
    }
    /* calculate normed value */
    float nx = (x - xMin)/(xMax - xMin);
    /* obtain array index using math-like rounding */
    int idx = nx * nBins + 1;
    /* increment bin */
    hstPtr[idx] ++;
    return 0;  /* normal termination */
}

Протестируем функцию следующим образом: для гистограммы из десяти бинов определённой на отрезке $x \in [-1/2, +1/2)$ разыграем множество раз число $\tilde{x} \in [0, 1]$, и напечатаем число отсчётов для каждого бина.

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// ...

int
main( int argc, char * argv[] ) {
    const int nBins = 10;
    int i, hst[nBins + 2];
    float xMin = -.5, xMax = .5;
    bzero( hst, sizeof(hst) );

    for( i = 0; i < 5e6; ++i ) {
        hst_fill( hst, nBins, xMin, xMax, rand()/((float) RAND_MAX + 1) );
    }
    for( i = 0; i < nBins + 2; ++i ) {
        printf( "%2d  %d\n", i, hst[i] );
    }
    return 0;
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void
print_normed( int * hstPtr, short nBins, float xMin, float xMax,
        FILE * stream ) {
    int * c;
    /* Calculate sum */
    int sum = 0;
    for( c = hstPtr + 1; c != hstPtr + nBins + 1; ++c ) {
        sum += *c;
    }
    for( c = hstPtr + 1; c != hstPtr + nBins + 1; ++c ) {
        fprintf( stream, "%e\n", *c/(float) sum );
    }
    fprintf( stream, "       sum : %d\n", sum );
    fprintf( stream, " underflow : %d\n", *hstPtr );
    fprintf( stream, "  overflow : %d\n", hstPtr[nBins+1] );
}

Вы можете дополнить точку входа вызовом этой функции (в строке 31) чтобы увидеть результат:

$ ./a.out 
 0  0
 1  0
 2  0
 3  0
 4  0
 5  0
 6  501106
 7  498895
 8  499408
 9  499552
10  500423
11  2500616
0.000000e+00
0.000000e+00
0.000000e+00
0.000000e+00
0.000000e+00
2.004918e-01
1.996072e-01
1.998124e-01
1.998700e-01
2.002185e-01
       sum : 2499384
 underflow : 0
  overflow : 2500616

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

• Расчёт суммы (включён в подсчёт плотностей)
• Запись и чтение в файл в виде точных значений
• Ребиннинг (уменьшение числа бинов — вдвое, втрое, и т.д., выполняемый посредством суммирования)
• Расчёт среднего, максимума, дисперсии, etc.

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

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

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