Производные типы данных

Структуры

Структуры – это не что иное, как классы, у которых разрешен доступ ко всем их элементам (доступ к определенным атрибутам класса может быть ограничен, о чем мы узнаем в лекции 11). Пример структуры:

struct Record {
     int number;
     char name[20];
};

Так же, как и для классов, операция " ." обозначает обращение к элементу структуры.

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

struct {
     double x;
     double y;
} coord;

Обратиться к атрибутам переменной coord можно coord.x и coord.y.

Битовые поля

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

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

struct TimeAndDate
{
unsigned hours    :5; // часы от 0 до 24 
unsigned mins     :6; // минуты 
unsigned secs     :6; // секунды от 0 до 60
unsigned weekDay  :3; // день недели
unsigned monthDay :6; // день месяца от 1 до 31
unsigned month    :5; // месяц от 1 до 12
unsigned year     :8; // год от 0 до 100  
};

Одна структура   TimeAndDate требует всего 39 битов, т.е. 5 байтов (один байт — 8 битов). Если бы мы использовали для каждого атрибута этой структуры тип char, нам бы потребовалось 7 байтов.

Объединения

Особым видом структур данных является объединение. Определение объединения напоминает определение структуры, только вместо ключевого слова struct используется union:

union number {
     short sx;
     long lx;
     double dx;
};

В отличие от структуры, все атрибуты объединения располагаются по одному адресу. Под объединение выделяется столько памяти, сколько нужно для хранения наибольшего атрибута объединения. Объединения применяются в тех случаях, когда в один момент времени используется только один атрибут объединения и, прежде всего, для экономии памяти. Предположим, нам нужно определить структуру, которая хранит "универсальное" число, т.е. число одного из предопределенных типов, и признак типа. Это можно сделать следующим образом:

struct Value {
  enum NumberType { ShortType, LongType,
                    DoubleType };
  NumberType type;  
  short sx;      // если type равен ShortType
  long lx;       // если type равен LongType
  double dx;     // если type равен DoubleType
};

Атрибут type содержит тип хранимого числа, а соответствующий атрибут структуры – значение числа.

Value shortVal;
shortVal.type = Value::ShortType;
shortVal.sx = 15;

Хотя память выделяется под все три атрибута sx, lx и dx, реально используется только один из них. Сэкономить память можно, используя объединение:

struct Value {
     enum NumberType { ShortType, LongType, 
                       DoubleType };
     NumberType type;
     union number {  
          short sx;      // если type равен ShortType
          long lx;       // если type равен LongType
          double dx;     // если type равен DoubleType
     } val;
};

Теперь память выделена только для максимального из этих трех атрибутов (в данном случае dx ). Однако и обращаться с объединением надо осторожно. Поскольку все три атрибута делят одну и ту же область памяти, изменение одного из них означает изменение всех остальных. На рисунке поясняется выделение памяти под объединение. В обоих случаях мы предполагаем, что структура расположена по адресу 1000. Объединение располагает все три своих атрибута по одному и тому же адресу.

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

Указатели

Указатель – это производный тип, который представляет собой адрес какого-либо значения. В языке Си++ используется понятие адреса переменных. Работа с адресами досталась Си++ в наследство от языка Си. Предположим, что в программе определена переменная типа int:

int x;

Можно определить переменную типа " указатель " на целое число:

int* xptr;

и присвоить переменной xptr адрес переменной x:

xptr = x;

Операция , примененная к переменной, – это операция взятия адреса. Операция *, примененная к адресу, – это операция обращения по адресу . Таким образом, два оператора эквивалентны:

int y = x;          
// присвоить переменной y значение x
int y = *xptr;      
// присвоить переменной y значение, 
// находящееся по адресу xptr

С помощью операции обращения по адресу можно записывать значения:

*xptr = 10;  
// записать число 10 по адресу xptr

После выполнения этого оператора значение переменной x станет равным 10, поскольку xptr указывает на переменную x.

Указатель – это не просто адрес, а адрес величины определенного типа. Указатель xptr – адрес целой величины. Определить адреса величин других типов можно следующим образом:

unsigned long* lPtr;      
// указатель на целое число без знака

char* cp;                 
// указатель на байт

Complex* p;               
// указатель на объект класса Complex

Если указатель ссылается на объект некоторого класса, то операция обращения к атрибуту класса вместо точки обозначается " -> ", например p->real. Если вспомнить один из предыдущих примеров:

void
Complex::Add(Complex x)
{
  this->real = this->real + x.real;
  this->imaginary = this->imaginary + 
                          x.imaginary;
}

то this – это указатель на текущий объект, т.е. объект, который выполняет метод Add. Запись this-> означает обращение к атрибуту текущего объекта.

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

int foo(long x);
int bar(long x);

можно определить переменную типа указатель на функцию и вызывать эти функции не напрямую, а косвенно, через указатель:

int (*functptr)(long x);
functptr = foo;
(*functptr)(2);
functptr = bar;
(*functptr)(4);

Для чего нужны указатели? Указатели появились, прежде всего, для нужд системного программирования. Поскольку язык Си предназначался для "низкоуровневого" программирования, на нем нужно было обращаться, например, к регистрам устройств. У этих регистров вполне определенные адреса, т.е. необходимо было прочитать или записать значение по определенному адресу. Благодаря механизму указателей, такие операции не требуют никаких дополнительных средств языка.

int* hardwareRegister =0x80000;
*hardwareRegister =12;

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

struct TempResults {
     double x1;
     double x2;
} tempArea;
  // Функция calc возвращает истину, если 
  // вычисления были успешны, и ложь – при 
  // наличии ошибки. Вычисленные результаты 
  // записываются на место аргументов по 
  // адресу, переданному в указателе trPtr
bool
calc(TempResults* trPtr)
{
     // вычисления
     if (noerrors) {
          trPtr->x1 = res1;
          trPtr->x2 = res2;
          return true;
     } else {
          return false;
     }
}
void
fun1(void)
{
     . . .
     TempResults tr;
     tr.x1 = 3.4;
     tr.x2 = 5.4;
     if (calc(tr) == false) {
          // обработка ошибки
     }
     . . .
}

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

Упомянутые примеры использования указателей никак не связаны с объектно-ориентированным программированием. Казалось бы, объектно-ориентированное программирование должно уменьшить зависимость от низкоуровневых конструкций типа указателей. На самом деле программирование с классами нисколько не уменьшило потребность в указателях, и даже наоборот, нашло им дополнительное применение, о чем мы будем рассказывать по ходу изложения.

Адресная арифметика

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

int x = 10;
int y = 10;
int* xptr = x;
int* yptr = y;
// сравниваем указатели
if (xptr == yptr) {
    cout << "Указатели равны" << endl;
} else {
    cout << "Указатели не равны" << endl;
}
// сравниваем значения, на которые указывают
// указатели
if (*xptr == *yptr) {
     cout << "Значения равны" << endl;
} else {
     cout << "Значения не равны" << endl;
}

Однако результат второй операции сравнения будет истинным, поскольку переменные x и y имеют одно и то же значение.

Кроме того, над указателями можно выполнять ограниченный набор арифметических операций. К указателю можно прибавить целое число или вычесть из него целое число. Результатом прибавления к указателю единицы является адрес следующей величины типа, на который ссылается указатель, в памяти. Поясним это на рисунке. Пусть xPtr – указатель на целое число типа long, а cp – указатель на тип char. Начиная с адреса 1000, в памяти расположены два целых числа. Адрес второго — 1004 (в большинстве реализаций Си++ под тип long выделяется четыре байта). Начиная с адреса 2000, в памяти расположены объекты типа char.

Размер памяти, выделяемой для числа типа long и для char, различен. Поэтому адрес при увеличении xPtr и cp тоже изменяется по-разному. Однако и в том, и в другом случае увеличение указателя на единицу означает переход к следующей в памяти величине того же типа. Прибавление или вычитание любого целого числа работает по тому же принципу, что и увеличение на единицу. Указатель сдвигается вперед (при прибавлении положительного числа) или назад (при вычитании положительного числа) на соответствующее количество объектов того типа, на который показывает указатель. Вообще говоря, неважно, объекты какого типа на самом деле находятся в памяти — адрес просто увеличивается или уменьшается на необходимую величину. На самом деле значение указателя   ptr всегда изменяется на число, кратное sizeof(*ptr).

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

Связь между массивами и указателями

Между указателями и массивами существует определенная связь. Предположим, имеется массив из 100 целых чисел. Запишем двумя способами программу суммирования элементов этого массива:

long array[100];
long sum = 0;
for (int i = 0; i < 100; i++)
     sum += array[i];

То же самое можно сделать с помощью указателей:

long array[100];
long sum = 0;
for (long* ptr = array[0]; 
     ptr < array[99] + 1; ptr++)
     sum += *ptr;

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

for (long* ptr = array; 
     ptr < array[99] + 1; ptr++)
     sum += *ptr;

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

При использовании многомерных массивов указатели позволяют обращаться к срезам или подмассивам. Если мы объявим трехмерный массив exmpl:

long exmpl[5][6][7]

то выражение вида exmpl[1][1][2] – это целое число, exmpl[1][1] – вектор целых чисел ( адрес первого элемента вектора, т.е. имеет тип *long ), exmpl[1] – двухмерная матрица или указатель на вектор (тип (*long)[7] ). Таким образом, задавая не все индексы массива, мы получаем указатели на массивы меньшей размерности.

Безтиповый (нетипизированный) указатель

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

void* ptr;

Для указателя на тип void не определена операция ->, не определена операция обращения по адресу   *, не определена адресная арифметика. Использование безтиповых указателей ограничено работой с памятью при использовании ряда системных функций, передачей адресов в функции, написанные на языках программирования более низкого уровня, например на ассемблере.

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

void
printbytes(void* ptr, int nbytes)
{
  if (nbytes == 1) {
     char* cptr = (char*)ptr;
     cout << *cptr;
  } else if (nbytes == 2) {
     short* sptr = (short*)ptr;
     cout << *sptr;
  } else if (nbytes == 4) {
     long* lptr = (long*)ptr;
     cout << *lptr;
  } else {
     cout << "Неверное значение аргумента";
  }
}

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

Нулевой указатель

В программах на языке Си++ значение указателя, равное нулю, используется в качестве "неопределенного" значения. Например, если какая-то функция вычисляет значение указателя, то чаще всего нулевое значение возвращается в случае ошибки.

long* foo(void);
. . .
long* resPtr;
if ((resPtr = foo()) != 0) {
          // использовать результат
} else {
          // ошибка
}

В языке Си++ определена символическая константа   NULL для обозначения нулевого значения указателя.

Такое использование нулевого указателя было основано на том, что по адресу 0 данные программы располагаться не могут, он зарезервирован операционной системой для своих нужд. Однако во многом нулевой указатель – просто удобное соглашение, которого все придерживаются.

Строки и литералы

Для того чтобы работать с текстом, в языке Си++ не существует особого встроенного типа данных. Текст представляется в виде последовательности знаков (байтов), заканчивающейся нулевым байтом. Иногда такое представление называют Си-строки, поскольку оно появилось в языке Си. Кроме того, в Си++ можно создать классы для более удобной работы с текстами (готовые классы для представления строк имеются в стандартной библиотеке шаблонов).

Строки представляются в виде массива байтов:

char string[20];
string[0] = 'H';
string[1] = 'e';
string[2] = 'l';
string[3] = 'l';
string[4] = 'o';
string[5] = 0;

В массиве   string записана строка "Hello". При этом мы использовали только 6 из 20 элементов массива.

Для записи строковых констант в программе используются литералы. Литерал – это последовательность знаков, заключенная в двойные кавычки:

"Это строка"
"0123456789"
"*"

Заметим, что символ, заключенный в двойные кавычки, отличается от символа, заключенного в апострофы. Литерал "*" обозначает два байта: первый байт содержит символ звездочки, второй байт содержит ноль. Константа '*' обозначает один байт, содержащий знак звездочки.

С помощью литералов можно инициализировать массивы:

char alldigits[] = "0123456789";

Размер массива явно не задан, он определяется исходя из размера инициализирующего его литерала, в данном случае 11 (10 символов плюс нулевой байт).

При работе со строками особенно часто используется связь между массивами и указателями. Значение литерала – это массив неизменяемых байтов нужного размера. Строковый литерал может быть присвоен указателю на char:

const char* message = "Сообщение программы";

Значение литерала – это адрес его первого байта, указатель на начало строки. В следующем примере функция CopyString копирует первую строку во вторую:

void
CopyString(char* src, char* dst)
{
     while (*dst++ = *src++)
          ;
     *dst = 0;
}
int
main()
{
     char first[] = "Первая строка";
     char second[100];
     CopyString(first, second);
     return 1;
}

Указатель на байт (тип char* ) указывает на начало строки. Предположим, нам нужно подсчитать количество цифр в строке, на которую показывает указатель str:

#include <ctype.h>
int count = 0;  
while (*str != 0) {         
    // признак конца строки – ноль

     if (isdigit(*str++))   
	      count++;          

    // проверить байт, на который
    // указывает str, и сдвинуть
    // указатель на следующий байт  
}

При выходе из цикла while переменная count содержит количество цифр в строке str, а сам указатель str указывает на конец строки – нулевой байт. Чтобы проверить, является ли текущий символ цифрой, используется функция isdigit. Это одна из многих стандартных функций языка, предназначенных для работы с символами и строками.

С помощью функций стандартной библиотеки языка реализованы многие часто используемые операции над символьными строками. В большинстве своем в качестве строк они воспринимают указатели. Приведем ряд наиболее употребительных. Прежде чем использовать эти указатели в программе, нужно подключить их описания с помощью операторов #include <string.h> и #include <ctype.h>.

char* strcpy(char* target, 
             const char* source);

Копировать строку   source по адресу   target, включая завершающий нулевой байт. Функция предполагает, что памяти, выделенной по адресу target, достаточно для копируемой строки. В качестве результата функция возвращает адрес первой строки.

char* strcat(char* target, 
             const char* source);

Присоединить вторую строку с конца первой, включая завершающий нулевой байт. На место завершающего нулевого байта первой строки переписывается первый символ второй строки. В результате по адресу   target получается строка, образованная слиянием первой со второй. В качестве результата функция возвращает адрес первой строки.

int strcmp(const char* string1, 
           const char* string2);

Сравнить две строки в лексикографическом порядке (по алфавиту). Если первая строка должна стоять по алфавиту раньше, чем вторая, то результат функции меньше нуля, если позже – больше нуля, и ноль, если две строки равны.

size_t strlen(const char* string);

Определить длину строки в байтах, не считая завершающего нулевого байта.

В следующем примере, использующем приведенные функции, в массиве   result будет образована строка "1 января 1998 года, 12 часов":

char result[100];
char* date = "1 января 1998 года";
char* time = "12 часов";
strcpy(result, date);
strcat(result, ", ");
strcat(result, time);

Как видно из этого примера, литералы можно непосредственно использовать в выражениях.

Определить массив строк можно с помощью следующего объявления:

char* StrArray[5] = 
  { "one", "two", "three", "four", "five" };