18.6.2. Порождение класса отсортированного массива.

Вторая наша специализация класса Array – отсортированный подтип Array_Sort. Мы поместим его определение в заголовочный файл Array_S.h:

#ifndef ARRAY_S_H_

#define ARRAY_S_H_

#include "Array.h".

Template class Type.

Class Array_Sort : public virtual Array Type {

Protected:

Void set_bit() { dirty_bit = true; }.

Void clear_bit() { dirty_bit = false; }.

Void check_bit() {

If ( dirty_bit ) {

Sort( 0, Array Type::_size-1 );

Clear_bit();

}

}

Public:

Array_Sort( const Array_Sort& );

Array_Sort( int sz = Array Type::ArraySize ).

: Array Type( sz ).

{ clear_bit(); }.

Array_Sort( const Type* arr, int sz ).

: Array Type( arr, sz ).

{ sort( 0,Array Type::_size-1 ); clear_bit(); }.

Type& operator[]( int ix ).

{ set_bit(); return ia[ ix ]; }.

Void print( ostream& os = cout ) const.

{ check_bit(); Array Type::print( os ); }.

Type min() { check_bit(); return ia[ 0 ]; }.

Type max() { check_bit(); return ia[ Array Type::_size-1 ]; }.

Bool is_dirty() const { return dirty_bit; }.

Int find( Type );

Void grow();

Protected:

Bool dirty_bit;

};

#endif.

Array_Sort включает дополнительный член – dirty_bit. Если он установлен в true, то не гарантируется, что массив по-прежнему отсортирован. Предоставляется также ряд вспомогательных функций доступа: is_dirty() возвращает значение dirty_bit; set_bit() устанавливает dirty_bit в true; clear_bit() сбрасывает dirty_bit в false; check_bit() пересортировывает массив, если dirty_bit равно true, после чего сбрасывает его в false. Все операции, которые потенциально могут перевести массив в неотсортированное состояние, вызывают set_bit().

При каждом обращении к шаблону Array необходимо указывать полный список параметров.

ArrayType::print( os );

Вызывает функцию-член print() базового класса Array, конкретизированного одновременно с Array_Sort. Например:

Array_Sortstring sas;

Конкретизирует типом string оба шаблона: Array_Sort и Array.

Cout sas;

Конкретизирует оператор вывода из класса Array, конкретизированного типом string, затем этому оператору передается строка sas. Внутри оператора вывода инструкция.

Ar.print( os );

Приводит к вызову виртуального экземпляра print() класса Array_Sort, конкретизированного типом string. Сначала вызывается check_bit(), а затем статически вызывается функция-член print() класса Array, конкретизированного тем же типом. (Напомним, что под статическим вызовом понимается разрешение функции на этапе компиляции и – при необходимости – ее подстановка в место вызова.) Виртуальная функция обычно вызывается динамически в зависимости от фактического типа объекта, адресуемого ar. Механизм виртуализации подавляется, если она вызывается явно с помощью оператора разрешения области видимости, как в Array::print(). Это повышает эффективность в случае, когда мы явно вызываем экземпляр виртуальной функции базового класса из экземпляра той же функции в производном, например в print() из класса Array_Sort (см. раздел 17.5).

Функции-члены, определенные вне тела класса, помещены в файл Array_S.C. Объявление может показаться слишком сложным из-за синтаксиса шаблона. Но, если не считать списков параметров, оно такое же, как и для обычных классов:

Template class Type.

Array_SortType::

Array_Sort( const Array_SortType &as ).

: ArrayType( as ).

{

// замечание: as.check_bit() не работает!

// ---- объяснение см. ниже ...

If ( as.is_dirty() ).

Sort( 0, ArrayType::_size-1 );

Clear_bit();

}

Каждое использование имени шаблона в качестве спецификатора типа должно быть квалифицировано полным списком параметров. Следует писать:

Template class Type.

Array_SortType::

Array_Sort( const Array_SortType &as ).

А не.

Template class Type.

Array_SortType::

Array_SortType( // ошибка: это не спецификатор типа.

Поскольку второе вхождение Array_Sort синтаксически является именем функции, а не спецификатором типа.

Есть две причины, по которым правильна такая запись:

If ( as.is_dirty() ).

Sort( 0, _size );

А не просто.

As.check_bit();

Первая причина связана с типизацией: check_bit() – это неконстантная функция-член, которая модифицирует объект класса. В качестве аргумента передается ссылка на константный объект. Применение check_bit() к аргументу as нарушает его константность и потому воспринимается компилятором как ошибка.

Вторая причина: копирующий конструктор рассматривает массив, ассоциированный с as, только для того, чтобы выяснить, нуждается ли вновь созданный объект класса Array_Sort в сортировке. Напомним, однако, что член dirty_bit нового объекта еще не инициализирован. К началу выполнения тела конструктора Array_Sort инициализированы только члены ia и _size, унаследованные от класса Array. Этот конструктор должен с помощью clear_bit() задать начальные значения дополнительных членов и, вызвав sort(), обеспечить специальное поведение подтипа. Конструктор Array_Sort можно было бы инициализировать и по-другому:

// альтернативная реализация.

Template class Type.

Array_SortType::

Array_Sort( const Array_SortType &as ).

: ArrayType( as ).

{

Dirty_bit = as.dirty_bit;

Clear_bit();

}

Ниже приведена реализация функции-члена grow().1 Наша стратегия состоит в том, чтобы воспользоваться имеющейся в базовом классе Array реализацией для выделения дополнительной памяти, а затем пересортировать элементы и сбросить dirty_bit:

Template class Type.

Void Array_SortType::grow().

{

ArrayType::grow();

Sort( 0, ArrayType::_size-1 );

Clear_bit();

}

Так выглядит реализация двоичного поиска в функции-члене find() класса Array_Sort:

Template class Type.

Int Array_SortType::find( const Type &val ).

{

Int low = 0;

Int high = ArrayType::_size-1;

Check_bit();

While ( low = high ) {

Int mid = ( low + high )/2;

If ( val == ia[ mid ] ).

Return mid;

If ( val ia[ mid ] ).

High = mid-1;

Else low = mid+1;

}

Return -1;

}

Протестируем нашу реализацию класса Array_Sort с помощью функции try_array(). Показанная ниже программа тестирует шаблон этого класса для конкретизаций типами int и string:

#include "Array_S.C".

#include "try_array.C".

#include string.

Main().

{

Static int ia[ 10 ] = { 12,7,14,9,128,17,6,3,27,5 };

Static string sa[ 7 ] = {

"Eeyore", "Pooh", "Tigger",

"Piglet", "Owl", "Gopher", "Heffalump".

};

Array_Sortint iA( ia,10 );

Array_Sortstring SA( sa,7 );

Cout "eiie?aoecaoey eeanna Array_Sortint".

Endl;

Try_array( iA );

Cout "eiie?aoecaoey eeanna Array_Sortstring".

Endl;

Try_array( SA );

Return 0;

}

При конкретизации типом string после компиляции и запуска программа печатает следующий текст (обратите внимание, что попытка вывести элемент с индексом -1 заканчивается крахом):

Конкретизация класса Array_Sortstring.

Try_array: начальные значения массива.

( 7 ) Eeyore, Gopher, Heffalump, Owl, Piglet, Pooh.

Tigger.

Try_array: после присваиваний.

( 7 ) Eeyore, Gopher, Owl, Piglet, Pooh, Pooh.

Pooh.

Try_array: почленная инициализация.

( 7 ) Eeyore, Gopher, Owl, Piglet, Pooh, Pooh.

Pooh.

Try_array: после почленного копирования.

( 7 ) Eeyore, Piglet, Owl, Piglet, Pooh, Pooh.

Pooh.

Try_array: после вызова grow.

( 7 ) empty, empty, empty, empty, Eeyore, Owl.

Piglet, Piglet, Pooh, Pooh, Pooh.

Искомое значение: Tigger возвращенный индекс: -1.

Memory fault (coredump).

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