Все встроенные типы данных, являются абстрактными, хотя так их называют редко.

Понятие абстракции

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

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

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

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

Инкапсуляция

Разделение программы на синтаксические контейнеры, ко­торые содержат группы логически связанных подпрограмм и данных. Эти синтаксические контейнеры называются модулями, а процесс их разработки- модуляризацией.

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

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

Абстрактные типы данных, определяемые пользователем

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

1) определение типа, позволяющее про­граммным модулям объявлять переменные этого типа, создавая при этом реальное пред­ставление этих переменных в памяти.

2) набор операций для манипуляций с объектами данного типа.

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

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

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

Упаковка представления типа и операций в отдельную син­таксическую единицу, позволяет организо­вывать программу в виде логических единиц, которые можно компилировать отдельно. Во-вторых, появляется возможность модифицировать представления объектов данного типа или операции с ними в отдельной части программы. У сокрытия деталей представ­ления типа есть преимущества. Клиенты не мо­гут "видеть" детали представления объектов, и их код не зависит от это­го представления. Таким образом, представления объектов можно изменять в любое время, не требуя при этом вносить изменения в код клиентов. Другим очевидным и важным преимуществом сокрытия информации является повы­шенная надежность. Клиенты не могут непосредственно изменять основные представле­ния объектов ни преднамеренно, ни случайно, следовательно, возрастает целостность та­ких объектов. Объекты можно изменять только с помощью предусмотренных для этого операций.

Вопросы разработки типов

Должна существовать воз­можность делать имя типа и заголовки подпрограмм видимыми в клиентах абстракции. Это позволяет клиентам объявлять переменные абстрактного типа и манипулировать их значе­ниями. Несмотря на то что имя типа должно быть видимым извне, его определение должно быть скрыто.

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

Языки Smalltalk, C++ и Java непосредственно поддерживают абстрактные типы данных.

Абстрактные типы данных в языке C++

Языки Ada и Modula-2 обеспечивают инкапсуляцию, которая может использоваться при моделировании абстрактных типов данных, в языке C++ введено по­нятие класса, который непосредственно поддерживает абстрактные типы данных. В язы­ке C++ классы - это типы, а пакеты языка Ada и модули языка Modula-2 типами не являют­ся. Пакеты и модули импортируются, позволяя импортирующей программной единице объявлять переменные любого типа, определенного в пакете или модуле. В программе на языке C++ переменные объявляются как сущности, имеющие тип данного класса. Таким образом, классы гораздо больше похожи на встроенные типы, чем пакеты или модули. Программная единица, которая видит пакет в языке Ada или модуль в языке Modula-2, имеет доступ к любым открытым сущностям просто по их именам. Программная едини­ца на языке C++, которая объявляет экземпляр класса, также имеет доступ к любым от­крытым сущностям в этом классе, но только через экземпляр этого класса.

Разработка абстрактных моделей для данных и способов обработки этих данных является важнейшим компонентом в процессе решения задач с помощью компьютера. Примеры этого мы видим и на низком уровне в повседневном программировании (например, при использовании массивов и связных списков, рассмотренных в ), и на высоком уровне при решении прикладных задач (как при решении задачи связности с помощью леса объединение-поиск в "Введение"). В настоящей лекции рассматриваются абстрактные типы данных ( abstract data type , в дальнейшем АТД), позволяющие создавать программы с использованием высокоуровневых абстракций. Абстрактные типы данных позволяют отделять абстрактные (концептуальные) преобразования, которые программы выполняют над данными, от любого конкретного представления структуры данных и любой конкретной реализации алгоритма.

Все вычислительные системы основаны на уровнях абстракции: определенные физические свойства кремния и других материалов позволяют принять абстрактную модель бита, который может принимать двоичные значения 0-1; затем на динамических свойствах значений определенного набора битов строится абстрактная модель машины; далее, на основе принципа работы машины под управлением программы на машинном языке строится абстрактная модель языка программирования; и, наконец, строится абстрактное понятие алгоритма, реализуемое в виде программы на языке C++. Абстрактные типы данных дают возможность продолжать этот процесс дальше и разрабатывать абстрактные механизмы для определенных вычислительных задач на более высоком уровне, чем это обеспечивается системой C++, разрабатывать абстрактные механизмы , ориентированные на конкретные приложения и подходящие для решения задач в многочисленных прикладных областях, а также создавать абстрактные механизмы более высокого уровня, в которых используются эти базовые конструкции. Абстрактные типы данных предоставляют в наше распоряжение расширяемый до бесконечности набор инструментальных средств для решения все новых и новых задач.

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

Для разработки нового уровня абстракции потребуется (1) определить абстрактные объекты, с которыми необходимо манипулировать, и операции , которые должны выполняться над ними; (2) представить данные в некоторой структуре данных и реализовать операции ; (3) и (самое главное) обеспечить, чтобы эти объекты было удобно использовать для решения прикладных задач. Эти пункты применимы и к простым типам данных, так что базовые механизмы для поддержки типов данных, которые были рассмотрены в "Элементарные структуры данных" , можно адаптировать для наших целей. Однако язык C++ предлагает важное расширение механизма структур, называемое классом ( class ). Классы исключительно полезны при создании уровней абстракции и поэтому рассматриваются в качестве основного инструмента, который используется для этой цели в оставшейся части книги.

Определение 4.1. Абстрактный тип данных (АТД) - это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс. Программу, которая использует АТД, будем называть клиентом, а программу, содержащую спецификацию этого типа данных - реализацией.

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

В программах на языке C++ это различие обычно проводится немного четче, так как проще всего создать интерфейс , включив в него представление данных , но указав, что клиентским программам не разрешен прямой доступ к данным. Другими словами, разработчики клиентских программ могут знать представление данных , но никоим образом не могут его использовать.

В качестве примера рассмотрим интерфейс типа данных для точек ( программа 3.3) из раздела 3.1 "Элементарные структуры данных" . В этом интерфейсе явно объявляется, что точки представлены как структуры, состоящие из пары чисел с плавающей точкой, обозначаемых x и у. Подобное применение типов данных является обычным в больших системах программного обеспечения: мы разрабатываем набор соглашений о представлении данных (а также определяем ряд связанных с ними операций) и делаем эти правила доступными через интерфейс , чтобы ими могли пользоваться клиентские программы, входящие в состав большой системы. Тип данных обеспечивает согласованность всех частей системы с представлением основных общесистемных структур данных. Какой бы хорошей такая стратегия ни была, она имеет один изъян: если необходимо изменить представление данных , то потребуется изменить и все клиентские программы. Программа 3.3 снова дает нам простой пример: одна из причин разработки этого типа данных - удобство работы клиентских программ с точками, и мы ожидаем, что в случае необходимости у клиентов будет доступ к отдельным координатам точки. Но мы не можем перейти к другому представлению данных (скажем, к полярным координатам, или трехмерным координатам, или даже к другим типам данных для отдельных координат) без изменения всех клиентских программ.

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

Когда мы пишем в программе определение наподобие int i, мы указываем системе зарезервировать область памяти для данных (встроенного) типа int , к которой можно обращаться по имени i. В языке C++ для подобных сущностей имеется термин объект . При записи в программе такого определения, как POINT p, говорят, что создается объект класса POINT , к которому можно обращаться по имени p. В нашем примере каждый объект содержит два элемента данных, с именами x и у. Как и в случае структур, к ним можно обращаться по именам вроде p.y.

Элементы данных x и у называются данными-членами класса. В классе могут быть также определены функции-члены, которые реализуют операции , связанные с этим типом данных. Например, класс , определенный в программе 4.1, имеет две функции-члена с именами POINT и distance .

Клиентские программы, такие как программа 4.2, могут вызывать функции-члены, связанные с объектом, указывая их имена точно так же, как и имена данных, находящихся в какой-нибудь структуре struct. Например, выражение p.distance(q) вычисляет расстояние между точками p и q (такое же расстояние должен возвращать и вызов q.distance(p) ). Функция POINT() - первая функция в программе 4.1 - является особой функцией-членом, называемой конструктором: у нее такое же имя, как и у класса, и она вызывается тогда, когда требуется создать объект этого класса.

Программа 4.1. Реализация класса POINT (точка)

В этом классе определен тип данных , который состоит из набора значений, представляющих собой "пары чисел с плавающей точкой" (предполагается, что они интерпретируются как точки на декартовой плоскости), а также две функции-члена, определенные для всех экземпляров класса POINT : функция POINT() , которая является конструктором, инициализирующим координаты случайными значениями от 0 до 1, и функция distance(POINT) , вычисляющая расстояние до другой точки. Представление данных является приватным ( private ), и обращаться к нему или модифицировать его могут только функции-члены. Сами функции-члены являются общедоступными ( public ) и доступны для любого клиента. Код можно сохранить, например, в файле с именем POINT .cxx.

#include class POINT { private: float x, у; public: POINT() { x = 1.0*rand()/RAND_MAX; у = 1.0*rand()/RAND_MAX; } float distance(POINT a) { float dx = x-a.x, dy = y-a.y; return sqrt(dx*dx + dy*dy); } };

Программа 4.2. Программа-клиент для класса POINT (нахождение ближайшей точки)

Эта версия программы 3.8 является клиентом, который использует АТД POINT , определенный в программе 4.3. Операция new создает массив объектов POINT (вызывая конструктор POINT () для инициализации каждого объекта случайными значениями координат). Выражение a[i].distance(a[j]) вызывает для объекта a[i] функцию-член distance с аргументом a[j] .

#include #include #include "POINT.cxx" int main(int argc, char *argv) { float d = atof(argv); int i, cnt = 0, N = atoi(argv); POINT *a = new POINT[N]; for (i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (a[i].distance(a[j]) < d) cnt+ + ; cout << cnt << " пар в радиусе " << d << endl; }

Определение POINT p в программе-клиенте приводит к выделению области памяти под новый объект и затем (с помощью функции POINT() ) к присвоению каждому из двух его элементов данных случайного значения в диапазоне от 0 до 1.

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

Мы рассматриваем описанный выше пример небольшого класса просто чтобы познакомиться с основными чертами классов; поэтому он далеко не полон. В реальном коде для класса точки у нас будет намного больше операций. Например, в программе 4.1 отсутствуют даже операции , позволяющие узнавать значения координат x и y . Как мы увидим, добавление этих и других операций - довольно простая задача. В части 5 мы более подробно рассмотрим классы для точки и других геометрических абстракций, например, линий и многоугольников.

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

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

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

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

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

#include
struct date
{
int month; // месяц
int day; // день
int year; // год
};
void set_date(date* f, int d, int m, int y)
{
f->day = d;
f->month = m;
f->year = y;
}
void print_date(date* f)
{
printf("%d.%d.%d" , f->day, f->month, f->year);
}
int main()
{
date today;
set_date(&today, 2, 4, 2014);
print_date(&today);
getchar();
return 0;
}


Результат выполнения

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include
struct date
{
int month; // месяц
int day; // день
int year; // год
void set_date(int d, int m, int y)
{
day = d; month = m; year = y;
}
void print_date(void );
};
void date::print_date(void )
{
printf("%d.%d.%d" , day, month, year);
}
int main()
{
date today;
today.set_date(2, 4, 2014);
today.print_date();
getchar();
return 0;
}

Функции-члены и данные-члены

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

Определение функций-членов может осуществляться двумя способами:

  • описание функции непосредственно при описании структуры;
  • описание функции вне структуры.

Функции-члены, которые определены внутри структуры, являются неявно встроенными (). Как правило, только короткие, часто используемые функции-члены, должны определяться внутри структуры:

void set(int m, int d, int y) {month = m; day = d; year = y;};



Поскольку разные структуры могут иметь функции-члены с одинаковыми именами, при определении функции члена необходимо указывать имя структуры, связывая их с помощью оператора разрешения контекста (двойное двоеточие)::
тип АТД::имя(список аргументов) {
тело функции-члена; }
  • тип — тип возвращаемого значения функции-члена
  • АТД — имя абстрактного типа данных (имя структуры или класса)
  • имя — имя функции-члена

void date::print_date(void )
{ printf("%d.%d.%d" ,day, month, year);}

В функции-члене имена членов могут использоваться без явной ссылки на объект. В этом случае имя относится к члену того объекта, для которого функция была вызвана.

Функции-члены, одной и той же структуры могут быть полиморфными, то есть перегруженными.

Права доступа

Концепция структуры в языке С++ (в отличие от Си) позволяет членам структуры быть общими, частными или защищенными:

  • public – общие;
  • private – частные;
  • protected – защищенные.

Использование ключевого слова protected связано с понятием наследования .

Использование ключевого слова private ограничивает доступ к членам, которые следуют за этой конструкцией. Члены private могут использоваться только несколькими категориями функций, в привилегии которых входит доступ к этим членам. В основном это функции-члены той же структуры.
Ключевое слово public образует интерфейс к объекту структуры.

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

Изменим структуру date так, чтобы скрыть представление данных (инкапсуляция данных):

1
2
3
4
5
6
7
8

struct date
{
private :
int month, day, year;
public :
void set(int , int , int );
void print();
};