| Меню сайта |
|
 |
| Категория |
|
|
| Развлечение |
|
|
| ON - LINE |
|
|
| Опрос |
|
|
| Оbserver Ward |
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
|
| Друзья сайта |
|
|
| Hаша кнопка |
Для обмена банерами , наша кнопка для размещения у вас на сайте
|
|
|
18. Множественное и виртуальное наследование (3)
18.6. Пример множественного виртуального наследования A
Мы продемонстрируем определение и использование множественного виртуального наследования, реализовав иерархию шаблонов классов Array (см. раздел 2.4) на основе шаблона Array (см. главу 16), модифицированного так, чтобы он стал конкретным базовым классом. Перед тем как приступать к реализации, поговорим о взаимосвязях между шаблонами классов и наследованием.
Конкретизированный экземпляр такого шаблона может выступать в роли явного базового класса:
class IntStack : private Array<int> {};
Разрешается также произвести его от не шаблонного базового класса:
class Base {};
template <class Type>
class Derived : public Base {};
Шаблон может выступать одновременно в роли базового и производного классов:
template <class Type>
class Array_RC : public virtual Array<Type> {};
В первом примере конкретизированный типом int шаблон Array служит закрытым базовым классом для не шаблонного IntStack. Во втором примере не шаблонный Base служит базовым для любого класса, конкретизированного из шаблона Derived. В третьем примере любой конкретизированный из шаблона Array_RC класс является производным от класса, конкретизированного из шаблона Array. Так, инструкция
Array_RC<int> ia;
конкретизирует экземпляры шаблонов Array и Array_RC.
Кроме того, сам параметр-шаблон может служить базовым классом [MURRAY93]:
template < typename Type >
class Persistent : public Type { ... };
в данном примере определяется производный устойчивый (persistent) подтип для любого конкретизированного типа. Как отмечает Мюррей (Murray), на Type налагается неявное ограничение: он должен быть типом класса. Например, инструкция
Persistent< int> pi; // ошибка
приводит к ошибке компиляции, поскольку встроенный тип не может быть объектом наследования.
Шаблон, выступающий в роли базового класса, должен квалифицироваться полным списком параметров. Если имеется определение:
template <class T> class Base {};
то необходимо писать:
template < class Type >
class Derived : public Base<Type> {};
Такая запись неправильна:
// ошибка: Base - это шаблон,
// так что должны быть заданы его аргументы
template < class Type >
class Derived : public Base {};
В следующем разделе шаблон Array, определенный в главе 16, выступает в роли виртуального базового класса для подтипа Array, контролирующего выход за границы массива; для отсортированного подтипа Array; для подтипа Array, который обладает обоими указанными свойствами. Однако первоначальное определение шаблона класса Array для наследования не подходит:
* все его члены и вспомогательные функции объявлены закрытыми, а не защищенными;
* ни одна из зависящих от типа функций-членов, скажем оператор взятия индекса, не объявлена виртуальной.
Означает ли это, что наша первоначальная реализация была неправильной? Нет. Она была верной на том уровне понимания, которым мы тогда обладали. При реализации шаблона класса Array мы еще не осознали необходимость специализированных подтипов. Теперь, однако, определение шаблона придется изменить так (реализации функций-членов при этом останутся теми же):
#ifndef ARRAY_H
#define ARRAY_H
#include <iostream>
// необходимо для опережающего объявления operator<<
template <class Type> class Array;
template <class Type> ostream&
operator<<( ostream &, Array<Type> & );
template <class Type>
class Array {
static const int ArraySize = 12;
public:
explicit Array( int sz = ArraySize ) { init( 0, sz ); }
Array( const Type *ar, int sz ) { init( ar, sz ); }
Array( const Array &iA ) { init( iA.ia, iA.size()); }
virtual ~Array() { delete[] ia; }
Array& operator=( const Array & );
int size() const { return _size; }
virtual void grow();
virtual void print( ostream& = cout );
Type at( int ix ) const { return ia[ ix ]; }
virtual Type& operator[]( int ix ) { return ia[ix]; }
virtual void sort( int,int );
virtual int find( Type );
virtual Type min();
virtual Type max();
protected:
void swap( int, int );
void init( const Type*, int );
int _size;
Type *ia;
};
#endif
Одна из проблем, связанных с таким переходом к полиморфизму, заключается в том, что реализация оператора взятия индекса перестала быть встроенной и сводится теперь к значительно более дорогому вызову виртуальной функции. Так, в следующей функции, на какой бы тип она ни ссылалась, было бы достаточно встроенного чтения элемента:
int find( const Array< int > &ia, int value )
{
for ( int ix = 0; ix <ia.size(); ++ix )
// а теперь вызов виртуальной функции
if ( ia[ ix ] == value )
return ix;
return -1;
}
Для повышения производительности мы включили встроенную функцию-член at(),обеспечивающую прямое чтение элемента.
18.6.1. Порождение класса, контролирующего выход за границы массива
В функции try_array() из раздела 16.13, предназначенной для тестирования нашей предыдущей реализации шаблона класса Array, есть две инструкции:
int index = iA.find( find_val );
Type value = iA[ index ];
find() возвращает индекс первого вхождения значения find_val или -1, если значение в массиве не найдено. Этот код некорректен, поскольку в нем не проверяется, что не была возвращена -1. Поскольку -1 находится за границей массива, то каждая инициализация value может привести к ошибке. Поэтому мы создадим подтип Array, который будет контролировать выход за границы массива, – Array_RC и поместим его определение в заголовочный файл Array_RC.h:
#ifndef ARRAY_RC_H
#define ARRAY_RC_H
#include "Array.h"
template <class Type>
class Array_RC : public virtual Array<Type> {
public:
Array_RC( int sz = ArraySize )
: Array <Type>( sz ) {}
Array_RC( const Array_RC& r );
Array_RC( const Type *ar, int sz );
Type& operator[]( int ix );
};
#endif
Внутри определения производного класса каждая ссылка на спецификатор типа шаблона базового должна быть квалифицирована списком формальных параметров:
Array_RC( int sz = ArraySize )
: Array<Type>( sz ) {}
Такая запись неправильна:
// ошибка: Array - это не спецификатор типа
Array_RC( int sz = ArraySize ) : Array( sz ) {}
Единственное отличие поведения класса Array_RC от базового состоит в том, что оператор взятия индекса контролирует выход за границы массива. Во всех остальных отношениях можно воспользоваться уже имеющейся реализацией шаблона класса Array. Напомним, однако, что конструкторы не наследуются, поэтому в Array_RC определен собственный набор из трех конструкторов. Мы сделали класс Array_RC виртуальным наследником класса Array, поскольку предвидели необходимость множественного наследования.
Вот полная реализация функций-членов Array_RC, находящаяся в файле Array_RC.C (определения функций класса Array помещены в заголовочный файл Array.C, поскольку мы пользуемся моделью конкретизации шаблонов с включением, описанной в разделе 16.18):
#include "Array_RC.h"
#include "Array.C"
#include <assert.h>
template <class Type>
Array_RC <Type >::Array_RC( const Array_RC<Type> &r )
: Array <Type>( r ) {}
template <class Type>
Array_RC <Type >::Array_RC( const Type *ar, int sz )
: Array <Type>( ar, sz ) {}
template <class Type>
Type &Array_RC <Type>::operator[]( int ix ) {
assert( ix >= 0 && ix < Array <Type>::_size );
return ia[ ix ];
}
Мы квалифицировали обращения к членам базового класса Array, например к _size, чтобы предотвратить просмотр Array до момента конкретизации шаблона:
Array <Type>::_size;
Мы достигаем этого, включая в обращение параметр шаблона. Таким образом, имена в определении Array_RC разрешаются тогда, когда определяется шаблон (за исключением имен, явно зависящих от его параметра). Если встречается неквалифицированное имя _size, то компилятор должен найти его определение, если только это имя не зависит явно от параметра шаблона. Мы сделали имя _size зависящим от параметра шаблона, предварив его именем базового класса Array. Теперь компилятор не будет пытаться разрешить имя _size до момента конкретизации шаблона. (В определении класса Array_Sort мы приведем другие примеры использования подобных приемов.)
Каждая конкретизация Array_RC порождает экземпляр класса Array. Например:
Array_RC<string> sa;
конкретизирует параметром string как шаблон Array_RC, так и шаблон Array. Приведенная ниже программа вызывает try_array() (реализацию см. в разделе 16.13), передавая ей объекты подтипа Array_RC. Если все сделано правильно, то выходы за границы массивы будут замечены:
#include "Array_RC.C"
#include "try_array.C"
int main()
{
static int ia[] = { 12,7,14,9,128,17,6,3,27,5 };
cout < < "конкретизация шаблона класса Array_RC <int>\n";
try_array( iA );
return 0;
}
После компиляции и запуска программа печатает следующее:
конкретизация шаблона класса Array_RC<int>
try_array: начальные значения массива
( 10 ) < 12, 7, 14, 9, 128, 17
6, 3, 27, 5 >
try_array: после присваиваний
( 10 ) < 128, 7, 14, 9, 128, 128
6, 3, 27, 3 >
try_array: почленная инициализация
( 10 ) < 12, 7, 14, 9, 128, 128
6, 3, 27, 3 >
try_array: после почленного копирования
( 10 ) < 12, 7, 128, 9, 128, 128
6, 3, 27, 3 >
try_array: после вызова grow
( 10 ) < 12, 7, 128, 9, 128, 128
6, 3, 27, 3, 0, 0
0, 0, 0, 0 >
искомое значение: 5 возвращенный индекс: -1
Assertion failed: ix >= 0 && ix < _size
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 необходимо указывать полный список параметров.
Array<Type>::print( os );
вызывает функцию-член print() базового класса Array, конкретизированного одновременно с Array_Sort. Например:
Array_Sort<string> 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_Sort<Type>::
Array_Sort( const Array_Sort<Type> &as )
: Array<Type>( as )
{
// замечание: as.check_bit() не работает!
// ---- объяснение см. ниже ...
if ( as.is_dirty() )
sort( 0, Array<Type>::_size-1 );
clear_bit();
}
Каждое использование имени шаблона в качестве спецификатора типа должно быть квалифицировано полным списком параметров. Следует писать:
template <class Type>
Array_Sort<Type>::
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 << "eiie?aoecaoey eeanna Array_Sort<int>"
<< endl;
try_array( iA );
cout << "eiie?aoecaoey eeanna 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. (Разумеется, мы реализовали такое поведение только в целях демонстрации.)
18.6.3. Класс массива с множественным наследованием
Определим отсортированный массив с контролем выхода за границы. Для этого можно применить множественное наследование от Array_RC и Array_Sort. Вот как выглядит наша реализация (напомним еще раз, что мы ограничились тремя конструкторами и оператором взятия индекса). Определение находится в заголовочном файле Array_RC_S.h:
#ifndef ARRAY_RC_S_H
#define ARRAY_RC_S_H
#include "Array_S.C"
#include "Array_RC.C"
template <class Type>
class Array_RC_S : public Array_RC<Type>,
public Array_Sort<Type>
{
public:
Array_RC_S( int sz = Array<Type>::ArraySize )
: Array<Type>( sz )
{ clear_bit(); }
Array_RC_S( const Array_RC_S &rca )
: Array<Type>( rca )
{ sort( 0,Array<Type>::_size-1 ); clear_bit(); }
Array_RC_S( const Type* arr, int sz )
: Array<Type>( arr, sz )
{ sort( 0,Array<Type>::_size-1 ); clear_bit(); }
Type& operator[]( int index )
{
set_bit();
return Array_RC<Type>::operator[]( index );
}
};
#endif
Этот класс наследует две реализации каждой интерфейсной функции Array: из Array_Sort и из виртуального базового класса Array через Array_RC (за исключением оператора взятия индекса, для которого из обоих базовых классов наследуется замещенный экземпляр). При невиртуальном наследовании вызов find() был бы помечен компилятором как неоднозначный, поскольку он не знает, какой из унаследованных экземпляров мы имели в виду. В нашем случае замещенным в Array_Sort экземплярам отдается предпочтение по сравнению с экземплярами, унаследованными из виртуального базового класса через Array_RC (см. раздел 18.5.4). Таким образом, при виртуальном наследовании неквалифицированный вызов find() разрешается в пользу экземпляра, унаследованного из класса Array_Sort.
Оператор взятия индекса переопределен в классах Array_RC и Array_Sort, и обе реализации имеют равный приоритет. Поэтому внутри Array_RC_S неквалифицированное обращение к оператору взятия индекса неоднозначно. Класс Array_RC_S должен предоставить собственную реализацию, иначе пользователи не смогут напрямую применять такой оператор к объектам этого класса. Но какова семантика его вызова в Array_RC_S? При учете отсортированности массива он должен установить в true унаследованный член dirty_bit. А чтобы учесть наследование от класса с контролем выхода за границы массива – проверить указанный индекс. После этого можно возвращать элемент массива с данным индексом. Последние два шага выполняет унаследованный из Array_RC оператор взятия индекса. При обращении
return Array_RC<Type>::operator[]( index );
он вызывается явно, и механизм виртуализации не применяется. Поскольку это встроенная функция, то при статическом вызове компилятор подставляет ее код в место вызова.
Теперь протестируем нашу реализацию с помощью функции try_array(), передавая ей по очереди классы, конкретизированные из шаблона Array_RC_S типами int и string:
#include "Array_RC_S.h"
#include "try_array.C"
#include <string>
int 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_RC_S<int> iA( ia,10 );
Array_RC_S<string> SA( sa,7 );
cout << "eiie?aoecaoey eeanna Array_RC_S<int>"
<< endl;
try_array( iA );
cout << "eiie?aoecaoey eeanna Array_RC_S"string>"
<< endl;
try_array( SA );
return 0;
}
Вот что печатает программа для класса, конкретизированного типом string (теперь ошибка выхода за границы массива перехватывается):
конкретизация класса 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
Assertion failed: ix >= 0 && ix < size
Представленная в этой главе реализация иерархии класса Array иллюстрирует применение множественного и виртуального наследования. Детально проектирование класса массива описано в [NACKMAN94]. Однако, как правило, достаточно класса vector из стандартной библиотеки.
Упражнение 18.16
Добавьте в Array функцию-член spy(). Она запоминает операции, примененные к объекту класса: число доступов по индексу; количество вызовов каждого члена; какой элемент искали с помощью find() и сколько было успешных поисков. Поясните свои проектные решения. Модифицируйте все подтипы Array так, чтобы spy() можно было использовать и для них тоже.
Упражнение 18.17
Стандартный библиотечный класс map (отображение) называют еще ассоциативным массивом, поскольку он поддерживает индексирование значением ключа. Как вы думаете, является ли ассоциативный массив кандидатом на роль подтипа нашего класса Array? Почему?
Упражнение 18.18
Перепишите иерархию Array, пользуясь контейнерными классами из стандартной библиотеки и применяя обобщенные алгоритмы.
|
| Категория: С++ | Добавил: r2d2 (29.09.2011)
|
| Просмотров: 789
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Born in Ussr |
|
|
| Залогиниться |
|
|
|
| Турниры |
|
|
|
