Абстрактные типы данных

1.

Абстрактные типы данных

2.

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

3.

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

4.

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

5.

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

6.

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

7.

Определение функций-членов может
осуществляться двумя способами:
описание функции непосредственно при
описании структуры;
описание функции вне структуры.
Функции-члены, которые определены внутри
структуры, являются неявно встроенными
(inline). Как правило, только короткие, часто
используемые функции-члены, должны
определяться внутри структуры.
Поскольку разные структуры могут иметь
функции члены с одинаковыми именами,
при определении функции члена
необходимо указывать имя структуры,
связывая их с помощью оператора
разрешения контекста «::»

8.

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

9.

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

10.

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

11.

Классы
Классы в С++ определяются ключевым словом class. Они представляют собой форму
структуры, у которой спецификация доступа по умолчанию – private, то есть
class s { ...
есть сокращенная запись
struct s { private:
Хотя такое определение класса и справедливо, отметим все же, что базовым в языке
С++ является понятие класса. Соответственно в С++ принято считать, что struct – это
просто класс, все члены которого общие, то есть
struct s { ...
есть просто сокращенная запись
class s { public: ...

12.

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

13.

Структура
Класс
Единственное отличие — в использовании ключевых слов: private и public.

14.

Область видимости класса.
С++ поддерживает три области видимости:
область видимости файла;
локальная область видимости;
область видимости класса.

15.

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

16.

Каждый класс представляет отдельную область видимости. Имена членов класса
локальны в этом классе. Область видимости членов класса (данных и функций) не
зависит от точки их объявления, то есть член класса виден во всем классе. Каждая членфункция определяет свою собственную локальную область видимости, аналогично
обычной функции С. Можно явно указать область видимости в С++, используя оператор
разрешения контекста (области видимости) ::. Этот оператор имеет самый высокий
приоритет и применяется в двух формах:
унарная — ссылается на внешний контекст;
бинарная — ссылается на контекст класса.

17.

Форма записи первой:
:: <идентификатор>
второй:
<имя_класса> :: <идентификатор>
Одноместная форма используется для обращения к имени, относящемуся ко
внешнему контексту и скрытому локальным контекстом или контекстом класса.

18.

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

19.

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

20.

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

21.

Ключевое слово static может быть использовано при
объявлении членов-данных и функций-членов. Такие
члены классов называются статическими и, независимо
от количества объектов данного класса, существует
только одна копия статического элемента, поэтому к
нему можно обращаться с помощью оператора
разрешения контекста и имени класса
имя_класса::имя_элемента
Если x – статическое данное-член класса cl, то на него
можно ссылаться cl::x, и при этом не имеет значения
количество объектов класса cl. Аналогично можно
обращаться к статической функции-члену:

22.

Статические данные-члены класса можно рассматривать как глобальную
переменную класса. Но в отличие от обычных глобальных переменных на
статические члены распространяются правила видимости private и public. Поместив
статическую переменную в часть private, можно ограничить ее использование.
Объявление статического члена в объявлении класса не является определением, то
есть это объявление статического члена не обеспечивает распределения памяти и
инициализацию.

23.

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

24.

Константные объекты и члены-функции
Ключевое слово const служит для создания константных
переменных (именованных констант). Объявление константной
переменной гарантирует, что значение переменной в области
видимости не будет меняться. Аналогично встроенным типам
ключевое слово const может быть использовано при объявлении
определяемого пользователем объекта. Объявление объекта с
ключевым словом const делает его постоянным в данной
области видимости.
const stack dig_str= {“0123456789”,9};
С константным объектом могут работать функции-члены
класса, объявленные с ключевым словом const. Такие функциичлены не изменяют данные-члены класса. Слово const
помещается между списком аргументов и телом функциичлена. Если функция-член определяется вне тела класса, то
const указывается и в объявлении и в определении функции.

25.

Неявный указатель this
Ключевое слово this представляет собой неявно
определенный указатель на сам объект. С его
помощью функция-член определяет, с данными
какого объекта ей предстоит работать. Каждая
функция-член класса неявно содержит в качестве
данного-члена следующий указатель:
имя_класса *this;
При вызове функции-члена, ей передается
неявный аргумент, содержащий адрес объекта,
для которого эта функция вызывается. Например,

26.

В первом случае функции readm()неявно передается указатель на объект aa, а во
втором случае – bb. Использование this необходимо в функциях, которые
непосредственно работают с указателем на объект.

27.

Внутри тела класса могут
использоваться ссылки или
указатели на тот же класс. Это
позволяет строить рекурсивные
структуры класса. Рассмотрим
пример
Указатель this может быть
использован только для
нестатической функции-члена.

28.

Конструкторы и инициализация
Для начала обратимся к одному из наших прошлых
примеров – классу date. Использование для
обеспечения инициализации объекта класса функций
вроде set() (установить дату) неэлегантно и чревато
ошибками. Поскольку нигде не утверждается, что объект
должен быть инициализирован, то программист может
забыть это сделать, или (что приводит, как правило, к
столь же разрушительным последствиям) сделать это
дважды. Есть более хороший подход: дать возможность
программисту описать функцию, явно предназначенную
для инициализации объектов. Поскольку такая функция
конструирует значения данного типа, она
называется конструктором. Конструктор распознается
по тому, что имеет то же имя, что и сам класс.
Например:

29.

Когда класс имеет конструктор, все объекты этого класса будут инициализироваться.
Если конструктор требует аргументы, их следует указать:

30.

Часто бывает полезно обеспечить несколько способов инициализации объектов
класса. Это можно сделать, задав несколько конструкторов. Например:

31.

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

32.

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

33.

Конструктор копии.
Как правило, при создании объекта вызывается конструктор, за исключением случая,
когда объект создается как копия другого объекта этого же класса, например:
date date2 = date1;

34.

Однако имеются случаи, в которых создание объекта без вызова конструктора
осуществляется неявно:
формальный параметр – объект, передаваемый по значению, создается в стеке в момент вызова
функции и инициализируется копией фактического параметра;
результат функции – объект, передаваемый по значению, в момент выполнения оператора return
копируется во временный объект, сохраняющий результат функции.
Во всех этих случаях транслятор не вызывает конструктора для вновь создаваемого объекта:
dat2 в приведенном определении;
создаваемого в стеке формального параметра;
временного объекта, сохраняющего значение, возвращаемое функцией.

35.

Вместо этого в них копируется содержимое
объекта-источника:
dat1 в приведенном примере;
фактического параметра;
объекта-результата в операторе return.
При наличии в объекте указателей на
динамические переменные и массивы или
идентификаторов связанных ресурсов, такое
копирование требует дублирования этих
переменных или ресурсов в объекте-приемнике,
как это было сделано выше в операции
присваивания. С этой целью вводится конструктор
копии, который автоматически вызывается во всех
перечисленных случаях. Он имеет единственный
параметр-ссылку на объект-источник:

36.

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

37.

Деструкторы и очистка.
Определяемый пользователем тип чаще имеет, чем не
имеет, конструктор, который обеспечивает надлежащую
инициализацию. Для многих типов также требуется
обратное действие, деструктор, чтобы обеспечить
соответствующую очистку объектов этого типа. Имя
деструктора для класса X есть ~X(). В частности, многие
типы используют некоторый объем динамической
памяти, которая выделяется конструктором, а
освобождается деструктором. Напомним, что в C++ для
этих целей используются операторы new и delete.
Приведем пример конструктора и деструктора объекта
date:

38.

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

39.

Конструктор нового класса имеет пустое тело и список вызываемых конструкторов
класса vect, перечисленных после двоеточия (:) через запятую (,). Они выполняются с
целым аргументом i, создавая три объекта класса vect: a, b, c. Конструкторы членов
класса всегда выполняются до конструктора класса, в котором эти члены описаны.
Порядок выполнения конструкторов для членов класса определяется порядком
объявления членов класса. Если конструктору члена класса требуются аргументы,
этот член с нужными аргументами указывается в списке инициализации.
Деструкторы вызываются в обратном порядке.

40.

Проверим класс multy_v, написав
программу для хранения и вывода
набора значений возраста, веса и
роста

41.

Объявление multy_v dan(5) создает три члена типа vect, каждый из которых состоит из
пяти элементов. При выполнении программы перед выходом из блока main для
каждого члена vect будет вызываться индивидуальный деструктор. Результат работы
программы

42.

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

43.

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

44.

Кроме того, объединение, определенное
таким образом, нельзя инициализировать.
Например,
tok_val curr_val = 12; // ошибка: int присваивается
tok_val'у
является недопустимым. Для того чтобы это
преодолеть, можно воспользоваться
конструкторами:

45.

Это позволяет справляться с теми ситуациями,
когда типы членов могут быть разрешены по
правилам для перегрузки имени. Например:

46.

Когда это невозможно (например, для типов
char* и char[8], int и char, и т.п.), нужный член
может быть найден только посредством
анализа инициализатора в ходе выполнения или
с помощью задания дополнительного
параметра. Например:

47.

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

48.

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

49.

Тип tok_val можно использовать
таким образом:

50.

Задачи
1. Есть ли ошибки в приведенном фрагменте программы?
Если есть, то объясните, в чем они заключаются. Как изменить
описание класса А, не вводя новые методы и не меняя f(),
чтобы в f() не было ошибок? Что будет напечатано в
результате работы функции f()?

51.

Задачи
2. Описать конструктор для некоторого класса А
таким образом, чтобы были выполнены следующие
условия:
а) это единственный явно описанный конструктор
класса А,
б) справедливы следующие описания объектов
класса А:

52.

Пример А
Задачи
3. Если есть ошибки в
приведенном
фрагменте
программы, то
объясните, в чем они
заключаются, и
вычеркните
ошибочные
конструкции. Что
будет выдано в
стандартный канал
вывода при вызове
функции main ()?
Пример Б

53.

Задачи
4. Описать класс А таким образом, чтобы все
конструкции функции main () были верными, а
на экран выдалось 100 300.

54.

Задачи
5. Описать класс B таким образом,
чтобы все конструкции функции
main были верными, а на экран
выдалось 10 20 30.

55.

Задачи
6. Описать класс C таким образом,
чтобы все конструкции функции
main были верными, а на экран
выдалось 14 10 48.

56.

Задачи
7. Описать класс А так, чтобы:
-
все конструкции функции main
были верными,
-
явно в классе А можно описать не
более одного конструктора,
-
на экран выдалось 15 60 7.
Нельзя использовать исключения и
любые функции досрочного
завершения программы.

57.

Задачи
8. Описать класс В так, чтобы:
-
все конструкции функции main были
верными,
-
класс В содержал только один явно
описанный конструктор,
-
на экран выдалось 17 11 6.
Нельзя использовать исключения и любые
функции досрочного завершения
программы.

58.

Задачи
9. Описать класс С так, чтобы:
-
в main ошибочным было только
описание объекта с2,
-
класс C содержал только один явно
описанный конструктор,
-
после удаления описания с2 на экран
выдалось 14 56.
Нельзя использовать исключения и любые
функции досрочного завершения
программы.

59.

Задачи
10. . Даны описания структуры, переменной и функции:
Дополните описание структуры mystr (не изменяя описание
функции f ) так, чтобы только описание f стало ошибочным.

60.

Задачи
11. Опишите структуру с именем smartstr, удовлетворяющую двум условиям:
1. можно создать объект типа smartstr;
2. нельзя создать массив элементов типа smartstr в динамической памяти.

61.

Задачи
12. Внести добавления в описания заданных методов
(не меняя вывод на экран!) структур B и D так, чтобы все
конструкции main () были правильными, а на печать
выдалось 5535324242.