Программа 4.18 АТД первого класса для комплексных чисел

Этот код реализует АТД, определенный в программе 4.18. Для представления вещественной и мнимой частей комплексного числа используются данные типа float. Это тип данных первого класса, так как в представлении данных отсутртвуют указатели. Когда объект класса Complex применяется либо в операторе присваивания, либо в аргументе функции, либо как ее значение возврата, система делает его копию, размещая в памяти новый объект и копируя данные в точности как в случае встроенных типов данных.

Перегруженная операция в текущей реализации выходные данные не форматирует (см. упр. 4.70).

#include <iostream.h> class Со1ф1ех

private:

float re, im; p\jblic:

Сопф1ех(float x, float y)

{ re s x; im = y; } float Re() const

{ return re; } float Im() const

{ return im; } Complexfi operator(const Complexfi rhs) { float t = Re();

re = Re() *rhs.Re() - Im() *rhs.Im() ; im = t*rhs.Im() + Im() *rhs.Re () ; return *this;

ostreamfi operator (ostreamfi t, const Со1ф1ех& с) { t c.ReO c.Im(); return t; }

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

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

Программа 4.20 является примером клиентской программы, которая оперирует с очередями FIFO как с типами данных первого класса. Она моделирует процесс поступления и обслуживания клиентов в совокупности М очередей. На рис. 4.13 показан пример выходных данных этой программы. Интерес к этой программе объясняется желанием проиллюстрировать, как механизм типов данных первого класса позволяет работать с таким высокоуровневым объектом, как очередь - можно также представить себе написание подобных программ для проверки различных методов организации очереди по обслуживанию клиентов и т.п.

Предположим, что используется рассмотренная ранее реализация очереди на базе связного списка из программы 4.14. Когда встречается запись р = q, где р и q являются объектами класса QUEUE, система распределяет память для нового объекта и копирует в новый объект значения, относящиеся к объекту q. Но это указатели head и tail - сам связный список не копируется. Если впоследствии связный список, относящийся к объекту р, изменяется, тем самым изменяется и связный список, относящийся к объекту q. Безусловно, в программе 4.20 результат должен быть не таким. Опять же, если использовать объект класса QUEUE как аргумент функции, процесс будет выглядеть так же. В случае встроенных типов данных мы рассчитываем на то, что внутри функции будет свой собственный объект, который можно использовать по своему усмотрению. Следствием этих ожиданий будет то, что в случае структуры данных с указателями потребуется делать копию. Однако система не знает, как это сделать - именно мы должны предоставить необходимый код. То же самое справедливо и для возвращаемых значений функций.

75 in 74 out

0: 58 59 60 67 68 73 1:

2: 64 66 72 3: 75

76 in

0: 58 59 60 67 68 73 i:

2: 64 66 72 3; 75 76

77 in 58j out

0: 59 60 67 68 73 1: 77

2: 64 66 72 3: 75 76

78 in 77 out

0: 59 60 67 68 73

1: 78

2: 64 66 72

3: 75 76

79 in 78 out

0: 59 60 67 68 73

1: 79

2: 64 66 72

3: 75 76

Программа 4.20 Клиентская программа, моделирующая очередь

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

РИСУНОК 4.13 МОДЕЛИРОВАНИЕ НЕУПОРЯДОЧЕННОЙ ОЧЕРЕДИ

Данный листинг представляет заключительную часть выходных данных программы 4.20 для случая, когда в командной строке вводится аргумент 80. Он отображает содержимое очередей после указанных операций, которые заключаются в следующем: случайным образом выбирается очередь и в нее заносится следующий элемент; затем еще раз выбирается очередь (также случайно) и, eaiu она не пуста, из нее извлекается элемент.

Здесь неявно предполагается, что класс QUEUE принадлежит в типу данных первого класса. Эта программа не будет корректно функционировать с реализациями, предоставленными в программах 4.14 и 4.15, по причине неправильной семантики копирования во внутреннем цикле for.

Реализация АТД Очередь в программе 4.22 имеет конструктор копирования, который исправляет этот дефект. Во внутреннем цикле for эта реализация каждый раз делает соответствующую копию для объекта q и полагается на то, мто ее деструктор позволит системе освободить память, занятую копиями.

#include <iostreain.h> #include <stdlib.h> #include QUEUE.схх static const int M = 4 ; int main(int argc, char *argv[]) { int N = atoi(argv[1]); QUEUE<int> queues[M];

for (int i = 0; i < N; i++, cout endl) { int in = randO % M, out = rand() % M; queues[in].put(i); cout i in ; if (queues[out].empty 0)

cout queues [out] .get 0 out ; cout endl;

for (int к = 0; к < M; k++, cout endl) { QUEUE<int> q = queues[k]; cout к : ; while (! q. empty 0)

cout q.getO ;

Еще хуже обстоят дела, когда объект класса QUEUE выходит за пределы видимости: система освобождает память, относящуюся к указателям, но не всю память, занимаемую собственно связным списком. Действительно, как только указатели прекращают свое существование, исчезает возможность доступа к данной области памяти. Вот вам пример утечки памяти (memory leak) - серьезной проблемы, всегда требующей особого внимания во время написании программы, которая имеет дело с распределением памяти.

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

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

Перегруженную операцию присваивания - для того чтобы объект мог присутствовать с левой стороны оператора присваивания.

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

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