Порождение класса отсортированного массива
Вторая наша специализация класса 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 необходимо указывать полный список параметров.
Array_Sort( const Array_Sort<Type> &as )
а не
template <class Type>
Array_Sort<Type>::
Array_Sort<Type>( // ошибка: это не спецификатор типа
поскольку второе вхождение 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_Sort<Type>::
Array_Sort( const Array_Sort<Type> &as )
: Array<Type>( as )
{
dirty_bit = as.dirty_bit;
clear_bit();
}
Ниже приведена реализация функции-члена grow().1 Наша стратегия состоит в том, чтобы воспользоваться имеющейся в базовом классе Array реализацией для выделения дополнительной памяти, а затем пересортировать элементы и сбросить dirty_bit:
template <class Type>
void Array_Sort<Type>::grow()
{
Array<Type>::grow();
sort( 0, Array<Type>::_size-1 );
clear_bit();
}
Так выглядит реализация двоичного поиска в функции-члене find() класса Array_Sort:
template <class Type>
int Array_Sort<Type>::find( const Type &val )
{
int low = 0;
int high = Array<Type>::_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_Sort<int> iA( ia,10 );
Array_Sort<string> SA( sa,7 );
cout << "конкретизация класса Array_Sort<int>"
<< endl;
try_array( iA );
cout << "конкретизация класса Array_Sort<string>"
<< endl;
try_array( SA );
return 0;
}
При конкретизации типом string после компиляции и запуска программа печатает следующий текст (обратите внимание, что попытка вывести элемент с индексом -1 заканчивается крахом):
конкретизация класса Array_Sort<string>
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. (Разумеется, мы реализовали такое поведение только в целях демонстрации.)
