| Меню сайта |
|
 |
| Категория |
|
|
| Развлечение |
|
|
| ON - LINE |
|
|
| Опрос |
|
|
| Оbserver Ward |
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
|
| Друзья сайта |
|
|
| Hаша кнопка |
Для обмена банерами , наша кнопка для размещения у вас на сайте
|
|
|
17. Наследование и подтипизация классов (1)
V. Объектно-ориентированное программирование
Объектно-ориентированное программирование расширяет объектное программирование, вводя отношения тип-подтип с помощью механизма, именуемого наследованием. Вместо того чтобы заново реализовывать общие свойства, класс наследует данные-члены и функции-члены родительского класса. В языке C++ наследование осуществляется посредством так называемого порождения производных классов. Класс, свойства которого наследуются, называется базовым, а новый класс - производным. Все множество базовых и производных классов образует иерархию наследования.
Например, в трехмерной компьютерной графике классы OrthographicCamera и PerspectiveCamera обычно являются производными от базового Camera. Множество операций и данных, общее для всех камер, определено в абстрактном классе Camera. Каждый производный от него класс реализует лишь отличия от абстрактной камеры, предоставляя альтернативный код для унаследованных функций-членов либо вводя дополнительные члены.
Если базовый и производный классы имеют общий открытый интерфейс, то производный называется подтипом базового. Так, PerspectiveCamera является подтипом класса Camera. В C++ существует специальное отношение между типом и подтипом, позволяющее указателю или ссылке на базовый класс адресовать любой из производных от него подтипов без вмешательства программиста. (Такая возможность манипулировать несколькими типами с помощью указателя или ссылки на базовый класс называется полиморфизмом.) Если дана функция:
void lookAt( const Camera *pCamera );
то мы реализуем lookAt(), программируя интерфейс базового класса Camera и не заботясь о том, на что указывает pCamera: на объект класса PerspectiveCamera, на объект класса OrthographicCamera или на объект, описывающий еще какой-то вид камеры, который мы пока не определили.
При каждом вызове lookAt() ей передается адрес объекта, принадлежащего к одному из подтипов Camera. Компилятор автоматически преобразует его в указатель на подходящий базовый класс:
// правильно: автоматически преобразуется в Camera*
OrthographicCamera ocam;
lookAt( &ocam );
// ...
// правильно: автоматически преобразуется в Camera*
PerspectiveCamera *pcam = new PerspectiveCamera;
lookAt( pcam );
Наша реализация lookAt() не зависит от набора подтипов класса Camera, реально существующих в приложении. Если впоследствии потребуется добавить новый подтип или исключить существующий, то изменять реализацию lookAt() не придется.
Полиморфизм подтипов позволяет написать ядро приложения так, что оно не будет зависеть от конкретных типов, которыми мы манипулируем. Мы программируем открытый интерфейс базового класса придуманной нами абстракции, пользуясь только ссылками и указателями на него. При работе программы будет определен фактический тип адресуемого объекта и вызвана подходящая реализация открытого интерфейса.
Нахождение (или разрешение) нужной функции во время выполнения называется динамическим связыванием (dynamic binding) (по умолчанию функции разрешаются статически во время компиляции). В C++ динамическое связывание поддерживается с помощью механизма виртуальных функций класса. Полиморфизм подтипов и динамическое связывание формируют основу объектно-ориентированного программирования, которому посвящены следующие главы.
В главе 17 рассматриваются имеющиеся в C++ средства поддержки объектно-ориентированного программирования и изучается влияние наследование на такие механизмы, как конструкторы, деструкторы, почленная инициализация и присваивание; для примера разрабатывается иерархия классов Query, поддерживающая систему текстового поиска, введенную в главе 6.
Темой главы 18 является изучение более сложных иерархий, возможных за счет использования множественного и виртуального наследования. С его помощью мы развернем шаблон класса из главы 16 в трехуровневую иерархию.
В главе 19 обсуждается идентификация типов во время выполнения (RTTI), а также изучается вопрос о влиянии наследования на разрешение перегруженных функций. Здесь мы снова обратимся к средствам обработки исключений, чтобы разобраться в иерархии классов исключений, которую предлагает стандартная библиотека. Мы покажем также, как написать собственные такие классы.
Глава 20 посвящена углубленному рассмотрению библиотеки потокового ввода/вывода iostream. Эта библиотека представляет собой иерархию классов, поддерживающую как виртуальное, так и множественное наследование.
17. Наследование и подтипизация классов
В главе 6 для иллюстрации обсуждения абстрактных контейнерных типов мы частично реализовали систему текстового поиска и инкапсулировали ее в класс TextQuery. Однако мы не написали к ней никакой вызывающей программы, отложив реализацию поддержки формулирования запросов со стороны пользователя до рассмотрения объектно-ориентированного программирования. В этой главе язык запросов будет реализован в виде иерархии классов Query с одиночным наследованием. Кроме того, мы модифицируем и расширим класс TextQuery из главы 6 для получения полностью интегрированной системы текстового поиска.
Программа для запуска нашей системы текстового поиска будет выглядеть следующим образом:
#include "TextQuery.h"
int main()
{
TextQuery tq;
tq.build_up_text();
tq.query_text();
}
build_text_map() - это слегка видоизмененная функция-член doit() из главы 6. Ее основная задача - построить отображение для хранения позиций всех значимых слов текста. (Если помните, мы не храним семантически нейтральные слова типа союзов if, and, but и т.д. Кроме того, мы заменяем заглавные буквы на строчные и устраняем суффиксы, обозначающие множественное число: например, testifies преобразуется в testify, а marches в march.) С каждым словом ассоциируется вектор позиций, в котором хранятся номера строки и колонки каждого вхождения слова в текст.
query_text() принимает запросы пользователя и преобразует их во внутреннюю форму на основе иерархии классов Query с одиночным наследованием и динамическим связыванием. Внутреннее представление запроса применяется к отображению слов на вектор позиций, построенному в build_text_map(). Ответом на запрос будет множество строк текстового файла, удовлетворяющих заданному критерию:
Enter a query - please separate each item by a space.
Terminate query (or session) with a dot( . ).
==> fiery && ( bird || shyly )
fiery ( 1 ) lines match
bird ( 1 ) lines match
shyly ( 1 ) lines match
( bird || shyly ) ( 2 ) lines match
fiery && ( bird || shyly ) ( 1 ) lines match
Requested query: fiery && ( bird || shyly )
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her.
В нашей системе мы выбрали следующий язык запросов:
1. одиночное слово, например Alice или untamed. Выводятся все строки, в которых оно встречается, причем каждой строке предшествует ее номер, заключенный в скобки. (Строки печатаются в порядке возрастания номеров). Например:
==> daddy
daddy ( 3 ) lines match
Requested query: daddy
( 1 ) Alice Emma has long flowing red hair. Her Daddy says
( 4 ) magical but untamed. "Daddy, shush, there is no such thing,"
( 6 ) Shyly, she asks, "I mean, Daddy, is there?"
1. запрос "НЕ", формулируемый с помощью оператора !. Выводятся все строки, где не встречается указанное слово. Например, так формулируется отрицание запроса 1:
==> ! daddy
daddy ( 3 ) lines match
! daddy ( 3 ) lines match
Requested query: ! daddy
( 2 ) when the wind blows through her hair, it looks almost alive,
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,
( 5 ) she tells him, at the same time wanting him to tell her more.
запрос "ИЛИ", формулируемый с помощью оператора ||. Выводятся все строки, в которых встречается хотя бы одно из двух указанных слов:
==> fiery || untamed
fiery ( 1 ) lines match
untamed ( 1 ) lines match
fiery || untamed ( 2 ) lines match
Requested query: fiery || untamed
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,
( 4 ) magical but untamed. "Daddy, shush, there is no such thing,"
запрос "И", формулируемый с помощью оператора &&. Выводятся все строки, где оба указанных слова встречаются, причем располагаются рядом. Сюда входит и случай, когда одно слово является последним в строке, а другое - первым в следующей:
==> untamed && Daddy
untamed ( 1 ) lines match
daddy ( 3 ) lines match
untamed && daddy ( 1 ) lines match
Requested query: untamed && daddy
( 4 ) magical but untamed. "Daddy, shush, there is no such thing,"
Эти элементы можно комбинировать:
fiery && bird || shyly
Однако обработка производится слева направо, и все элементы имеют одинаковые приоритеты. Поэтому наш составной запрос интерпретируется как fiery bird ИЛИ shyly, а не как fiery bird ИЛИ fiery shyly:
==> fiery && bird || shyly
fiery ( 1 ) lines match
bird ( 1 ) lines match
fiery && bird ( 1 ) lines match
shyly ( 1 ) lines match
fiery && bird || shyly ( 2 ) lines match
Requested query: fiery && bird || shyly
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,
( 6 ) Shyly, she asks, "I mean, Daddy, is there?"
Чтобы можно было группировать части запроса, наша система должна поддерживать скобки. Например:
fiery && (bird || shyly)
выдает все вхождения fiery bird или fiery shyly1. Результат исполнения этого запроса приведен в начале данного раздела. Кроме того, система не должна многократно отображать одну и ту же строку.
17.1. Определение иерархии классов
В этой главе мы построим иерархию классов для представления запроса пользователя. Сначала реализуем каждую операцию в виде отдельного класса:
NameQuery // Shakespeare
NotQuery // ! Shakespeare
OrQuery // Shakespeare || Marlowe
AndQuery // William && Shakespeare
В каждом классе определим функцию-член eval(), которая выполняет соответствующую операцию. К примеру, для NameQuery она возвращает вектор позиций, содержащий координаты (номера строки и колонки) начала каждого вхождения слова (см. раздел 6.8); для OrQuery строит объединение векторов позиций обоих своих операндов и т.д.
Таким образом, запрос
untamed || fiery
состоит из объекта класса OrQuery, который содержит два объекта NameQuery в качестве операндов. Для простых запросов этого достаточно, но при обработке составных запросов типа
Alice || Emma && Weeks
возникает проблема. Данный запрос состоит из двух подзапросов: объекта OrQuery, содержащего объекты NameQuery для представления слов Alice и Emma, и объекта AndQuery. Правым операндом AndQuery является объект NameQuery для слова Weeks.
AndQuery
OrQuery
NameQuery ("Alice")
NameQuery ("Emma")
NameQuery ("Weeks")
Но левый операнд - это объект OrQuery, предшествующий оператору &&. На его месте мог бы быть объект NotQuery или другой объект AndQuery. Как же следует представить операнд, если он может принадлежать к типу любого из четырех классов? Эта проблема имеет две стороны:
1. необходимо уметь объявлять тип операнда в классах OrQuery, AndQuery и NotQuery так, чтобы с его помощью можно было представить тип любого из четырех классов запросов;
2. какое бы решение мы ни выбрали в предыдущем случае, мы должны иметь возможность вызывать соответствующий классу каждого операнда вариант функции-члена eval().
Решение, не согласующееся с объектной ориентированностью, состоит в том, чтобы определить тип операнда как объединение и включить дискриминант, показывающий текущий тип операнда:
// не объектно-ориентированное решение
union op_type {
// объединение не может содержать объекты классов с
// ассоциированными конструкторами
NotQuery *nq;
OrQuery *oq;
AndQuery *aq;
string *word;
};
enum opTypes {
Not_query=1, O_query, And_query, Name_query
};
class AndQuery {
public:
// ...
private:
/*
* opTypes хранит информацию о фактических типах операндов запроса
* op_type - это сами операнды
*/
op_type _lop, _rop;
opTypes _lop_type, _rop_type;
};
Хранить указатели на объекты можно и с помощью типа void*:
class AndQuery {
public:
// ...
private:
void * _lop, _rop;
opTypes _lop_type, _rop_type;
};
Нам все равно нужен дискриминант, поскольку напрямую использовать объект, адресуемый указателем типа void*, нельзя, равно как невозможно определить тип такого объекта по указателю. (Мы не рекомендуем применять описанное решение в C++, хотя в языке C это весьма распространенный подход.)
Основной недостаток рассмотренных решений состоит в том, что ответственность за определение типа возлагается на программиста. Например, в случае решения, основанного на void*-указателях, операцию eval() для объекта AndQuery можно реализовать так:
void
AndQuery::
eval()
{
// не объектно-ориентированный подход
// ответственность за разрешение типа ложится на программиста
// определить фактический тип левого операнда
switch( _lop_type ) {
case And_query:
AndQuery *paq = static_cast<AndQuery*>(_lop);
paq->eval();
break;
case Or_query:
OrQuery *pqq = static_cast<OrQuery*>(_lop);
poq->eval();
break;
case Not_query:
NotQuery *pnotq = static_cast<NotQuery*>(_lop);
pnotq->eval();
break;
case Name_query:
AndQuery *pnmq = static_cast<NameQuery*>(_lop);
pnmq->eval();
break;
}
// то же для правого операнда
}
В результате явного управления разрешением типов увеличивается размер и сложность кода и добавление нового типа или исключение существующего при сохранении работоспособности программы затрудняется.
Объектно-ориентированное программирование предлагает альтернативное решение, в котором работа по разрешению типов перекладывается с программиста на компилятор. Например, так выглядит код операции eval() для класса AndQuery в случае применения объектно-ориентированного подхода (eval() объявлена виртуальной):
// объектно-ориентированное решение
// ответственность за разрешение типов перекладывается на компилятор
// примечание: теперь _lop и _rop - объекты типа класса
// их определения будут приведены ниже
void
AndQuery::
eval()
{
_lop->eval();
_rop->eval();
}
Если потребуется добавить или исключить какие-либо типы, эту часть программы не придется ни переписывать, ни перекомпилировать.
17.1.1. Объектно-ориентированное проектирование
Из чего складывается объектно-ориентированное проектирование четырех рассмотренных выше видов запросов? Как решаются проблемы их внутреннего представления?
С помощью наследования можно определить взаимосвязи между независимыми классами запросов. Для этого мы вводим в рассмотрение абстрактный класс Query, который будет служить для них базовым (соответственно сами эти классы будут считаться производными). Абстрактный класс можно представить себе как неполный, который становится более или менее завершенным, когда из него порождаются производные классы, - в нашем случае AndQuery, OrQuery, NotQuery и NameQuery.
В нашем абстрактном классе Query определены данные и функции-члены, общие для всех четырех типов запроса. При порождении из Query производного класса, скажем AndQuery, мы выделяем уникальные характеристики каждого вида запроса. К примеру, NameQuery - это специальный вид Query, в котором операндом всегда является строка. Мы будем называть NameQuery производным и говорить, что Query является его базовым классом. (То же самое относится и к классам, представляющим другие типы запросов.) Производный класс наследует данные и функции-члены базового и может обращаться к ним непосредственно, как к собственным членам.
Основное преимущество иерархии наследования в том, что мы программируем открытый интерфейс абстрактного базового класса, а не отдельных производных от него специализированных типов, что позволяет защитить наш код от последующих изменений иерархии. Например, мы определяем eval() как открытую виртуальную функцию абстрактного базового класса Query. Пользовательский код, записанный в виде:
_rop->eval();
экранирован от любых изменений в языке запросов. Это не только позволяет добавлять, модифицировать и удалять типы, не изменяя программы пользователя, но и освобождает автора нового вида запроса от необходимости заново реализовывать поведение или действия, общие для всех типов в иерархии. Такая гибкость достигается за счет двух характеристик механизма наследования: полиморфизма и динамического связывания.
Когда мы говорим о полиморфизме в языке C++, то имеем в виду главным образом способность указателя или ссылки на базовый класс адресовать любой из производных от него. Если определить обычную функцию eval() следующим образом:
// pquery может адресовать любой из классов, производных от Query
void eval( const Query *pquery )
{
pquery->eval();
}
то мы вправе вызывать ее, передавая адрес объекта любого из четырех типов запросов:
int main()
{
AndQuery aq;
NotQuery notq;
OrQuery *oq = new OrQuery;
NameQuery nq( "Botticelli" );
// правильно: любой производный от Query класс
// компилятор автоматически преобразует в базовый класс
eval( &aq );
eval( ¬q );
eval( oq );
eval( &nq );
}
В то же время попытка передать eval() адрес объекта класса, не являющегося производным от Query, вызовет ошибку компиляции:
int main()
{
string name( " Scooby-Doo" );
// ошибка: тип string не является производным от Query
eval( &name );
}
Внутри eval() выполнение инструкции вида
pquery->eval();
должно вызывать нужную виртуальную функцию-член eval() в зависимости от фактического класса объекта, адресуемого указателем pquery. В примере выше pquery последовательно адресует объекты AndQuery, NotQuery, OrQuery и NameQuery. В каждой точке вызова определяется фактический тип класса объекта и вызывается подходящий экземпляр eval().
Механизм, с помощью которого это достигается, называется динамическим связыванием. (Мы вернемся к проектированию и использованию виртуальных функций в разделе 17.5.)
В объектно-ориентированной парадигме программист манипулирует неизвестным экземпляром, принадлежащим к одному из ограниченного, но потенциально бесконечного множества различных типов. (Ограничено оно иерархией наследования. Теоретически, однако, ни на глубину, ни на ширину такой иерархии не накладывается никаких ограничений.) В C++ это достигается путем манипулирования объектами исключительно через указатели и ссылки на базовый класс. В объектной (не объектно-ориентированной) парадигме программист работает с экземпляром фиксированного типа, который полностью определен на этапе компиляции.
Хотя для полиморфной манипуляции объектом требуется, чтобы доступ к нему осуществлялся с помощью указателя или ссылки, сам по себе факт их использования не обязательно приводит к полиморфизму. Рассмотрим такие объявления:
// полиморфизма нет
int *pi;
// нет поддержанного языком полиморфизма
void *pvi;
// pquery может адресовать объект любого производного от Query класса
Query *pquery;
В C++ полиморфизм существует только в пределах отдельных иерархий классов. Указатели типа void* можно назвать полиморфными, но в языке их поддержка не предусмотрена. Такими указателями программист должен управлять самостоятельно, с помощью явных приведений типов и той или иной формы дискриминанта, показывающего, объект какого типа в данный момент адресуется. (Можно сказать, что это "второсортные" полиморфные объекты.)
Язык C++ обеспечивает поддержку полиморфизма следующими способами:
1. путем неявного преобразования указателя или ссылки на производный класс к указателю или ссылке на открытый базовый:
Query *pquery = new NameQuery( " Class" );
1. через механизм виртуальных функций:
pquery->eval();
с помощью операторов dynamic_cast и typeid (они подробно обсуждаются в разделе 19.1):
if ( NameQuery *pnq =
dynamic_cast> NameQuery* >( pquery )) ...
Проблему представления запроса мы решим, определив каждый операнд в классах AndQuery, NotQuery и OrQuery как указатель на тип Query*. Например:
class AndQuery {
public:
// ...
private:
Query *_lop;
Query *_rop;
};
Теперь оба операнда могут адресовать объект любого класса, производного от абстрактного базового класса Query, без учета того, определен он уже сейчас или появится в будущем. Благодаря механизму виртуальных функций, вычисление операнда, происходящее во время выполнения программы, не зависит от фактического типа:
_rop->eval();
На рис. 17.1 показана иерархия наследования, состоящая из абстрактного класса Query и четырех производных от него классов. Как этот рисунок транслируется в код программы на C++?
Query AndQuery OrQuery NotQuery NameQuery
Рис. 17.1. Иерархия классов Query
В разделе 2.4 мы рассматривали реализацию иерархии классов IntArray. Синтаксическая структура определения иерархии, изображенной на рис. 17.1, аналогична:
class Query { ... };
class AndQuery : public Query { ... };
class OrQuery : public Query { ... };
class NotQuery : public Query { ... };
class NameQuery : public Query { ... };
Наследование задается с помощью списка базовых классов. В случае одиночного наследования этот список имеет вид:
: уровень-доступа базовый-класс
где уровень-доступа - это одно из ключевых слов public, protected, private (смысл защищенного и закрытого наследования мы обсудим в разделе 18.3), а базовый-класс - имя ранее определенного класса. Например, Query является открытым базовым классом для любого из четырех классов запросов.
Класс, встречающийся в списке базовых, должен быть предварительно определен. Следующего опережающего объявления Query недостаточно для того, чтобы он мог выступать в роли базового:
// ошибка: Query должен быть определен
class Query;
class NameQuery : piblic Query { ... };
Опережающее объявление производного класса должно включать только его имя, но не список базовых классов. Поэтому следующее опережающее объявление класса NameQuery приводит к ошибке компиляции:
// ошибка: опережающее объявление не должно
// включать списка базовых классов
class NameQuery : public Query;
Правильный вариант в данном случае выглядит так:
// опережающее объявление как производного,
// так и обычного класса содержит только имя класса
class Query;
class NameQuery;
Главное различие между базовыми классами Query и IntArray (см. раздел 2.4) состоит в том, что Query не представляет никакого реального объекта в нашем приложении. Пользователи класса IntArray вполне могут определять и использовать объекты этого типа непосредственно. Что же касается Query, то разрешается определять лишь указатели и ссылки на него, используя их для косвенного манипулирования объектами производных классов. О Query говорят, что это абстрактный базовый класс. В противоположность этому IntArray является конкретным базовым классом. Преобладающей формой в объектно-ориентированном проектировании является определение абстрактного базового класса типа Query и одиночное открытое наследование ему.
Упражнение 17.1
Библиотека может выдавать на руки предметы, для каждого из которых определены специальные правила выдачи и возврата. Организуйте их в иерархию наследования:
книга аудио-книга
аудиокассета детская кукла
видеокассета видеоигра для приставки SEGA
книга с подневной оплатой видеоигра для приставки SONY
книга на компакт-диске видеоигра для приставки Nintendo
Упражнение 17.2
Выберите или придумайте собственную абстракцию, содержащую семейство типов. Организуйте типы в иерархию наследования:
(a) Форматы графических файлов (gif, tiff, jpeg, bmp и т.д.)
(b) Геометрические примитивы (прямоугольник, круг, сфера, конус и т.д.)
(c) Типы языка C++ (класс, функция, функция-член и т.д.)
17.2. Идентификация членов иерархии
В разделе 2.4 мы уже упоминали о том, что в объектном проектировании обычно есть один разработчик, который конструирует и реализует класс, и много пользователей, применяющих предоставленный открытый интерфейс. Это разделение ответственности отразилось в концепции открытого и закрытого доступа к членам класса.
Когда используется наследование, у класса оказывается множество разработчиков. Во-первых, тот, кто предоставил реализацию базового класса (и, возможно, некоторых производных от него), а во-вторых, те, кто разрабатывал производные классы на различных уровнях иерархии. Этот род деятельности тоже относится к проектированию. Разработчик подтипа часто (хотя и не всегда) должен иметь доступ к реализации базового класса. Чтобы разрешить такой вид доступа, но все же предотвратить неограниченный доступ к деталям реализации класса, вводится дополнительный уровень доступа - protected (защищенный). Данные и функции-члены, помещенные в секцию protected некоторого класса, остаются недоступными вызывающей программе, но обращение к ним из производных классов разрешено. (Все находящееся в секции private базового класса доступно только ему, но не производным.)
Критерии помещения того или иного члена в секцию public одинаковы как для объектного, так и для объектно-ориентированного проектирования. Меняется только точка зрения на то, следует ли объявлять член закрытым или защищенным. Член базового класса объявляется закрытым, если мы не хотим, чтобы производные классы имели к нему прямой доступ; и защищенным, если его семантика такова, что для эффективной реализации производного класса может потребоваться прямой доступ к нему. При проектировании класса, который предполагается использовать в качестве базового, надо также принимать во внимание особенности функций, зависящих от типа, - виртуальных функций в иерархии классов.
На следующем шаге проектирования иерархии классов Query следует ответить на такие вопросы:
Какие операции следует предоставить в открытом интерфейсе иерархии классов Query?
Какие из них следует объявить виртуальными?
Какие дополнительные операции могут потребоваться производным классам?
Какие данные-члены следует объявить в нашем абстрактном базовом классе Query?
Какие данные-члены могут потребоваться производным классам?
К сожалению, однозначно ответить на эти вопросы невозможно. Как мы увидим, процесс объектно-ориентированного проектирования по своей природе итеративен, эволюционирующая иерархия классов требует и добавлений, и модификаций. В оставшейся части этого раздела мы будем постепенно уточнять иерархию классов Query.
17.2.1. Определение базового класса
Члены Query представляют:
1. множество операций, поддерживаемых всеми производными от него классами запросов. Сюда входят как виртуальные операции, переопределяемые в производных классах, так и невиртуальные, разделяемые всеми производными классами (мы приведем примеры тех и других);
2. множество данных-членов, общих для всех производных классов. Если вынести такие члены в абстрактный базовый класс Query, мы сможем обращаться к ним вне зависимости от того, с объектом какого производного класса мы работаем.
Если имеется запрос вида:
fiery || untamed
то двумя основными операциями для него будут: нахождение строк текста, удовлетворяющих условиям запроса, и представление найденных строк пользователю. Назовем эти операции соответственно eval() и display().
Алгоритм работы eval() свой для каждого производного класса, поэтому эту функцию следует объявить виртуальной в определении Query. Всякий производный класс должен предоставить собственную реализацию для нее. Сам же Query лишь включает ее в свой открытый интерфейс.
Алгоритм работы функции display(), выводящей найденные строки текста, не зависит от типа производного класса. Нам необходимо лишь иметь доступ к представлению самого текста и списку строк, удовлетворяющих запросу. Вместо того чтобы дублировать реализацию алгоритма и необходимые для него данные в каждом производном классе, определим единственный наследуемый экземпляр в Query.
Такое проектное решение позволит нам вызывать любую операцию, не зная фактического типа объекта, которым мы манипулируем:
void
doit( Query *pq )
{
// виртуальный вызов
pq->eval();
// статический вызов Query::display()
pq->display();
}
Как следует представить найденные строки текста? Каждому упомянутому в запросе слову будет соответствовать вектор позиций, построенный во время поиска. Позиция - это пара (строка, колонка), в которой каждый член - это значение типа short int. Отображение слов на векторы позиций, построенное функцией build_text_map(), содержит такие векторы для каждого встречающегося в тексте слова, распознанного нашей системой. Ключами для этого отображения служат значения типа string, представляющие слова. Например, для текста
Alice Emma has long flowing red hair. Her Daddy says
when the wind blows through her hair, it looks almost alive,
like a fiery bird in flight. A beautiful fiery bird, he tells her,
magical but untamed. "Daddy, shush, there is no such thing,"
she tells him, at the same time wanting him to tell her more.
Shyly, she asks, "I mean, Daddy, is there?"
приведена часть отображения для некоторых слов, встречающихся неоднократно (слово - это ключ отображения; пары значений в скобках - элементы вектора позиций; отметим, что нумерация строк и колонок начинается с нуля):
bird ((2,3),(2,9))
daddy ((0,8),(3,3),(5,5))
fiery ((2,2),(2,8))
hair ((0,6),(1,6))
her ((0,7),(1,5),(2,12),(4,11))
him ((4,2),(4,8))
she ((4,0),(5,1))
tell ((2,11),(4,1),(4,10))
Однако такой вектор - это еще ответ на запрос. К примеру, слово fiery представлено двумя позициями, причем обе находятся в одной и той же строке.
Нам нужно вычислить множество неповторяющихся строк, соответствующих вектору позиций. Для этого можно, например, создать вектор, в который помещаются все номера строк, представленные в векторе позиций, а затем передать его обобщенному алгоритму unique(), который удалит все дубликаты (см. алгоритм unique() в Приложении). Оставшиеся строки должны быть расположены в порядке возрастания номеров. Чтобы не оставалось никаких сомнений, к вектору строк можно применить обобщенный алгоритм sort().
Мы выбрали другой подход - построить множество (объект set) из номеров строк в векторе позиций. Такое множество содержит по одному экземпляру каждого элемента, причем хранит их в отсортированном виде. Нам потребуется функция для преобразования вектора позиций в множество неповторяющихся номеров строк:
set< short>* Query::_vec2set( const vector< location >* );
Объявим _vec2set() защищенной функцией-членом Query. Она не является открытой, поскольку не принадлежит к числу операций, которые могут вызывать пользователи данной иерархии. Но она и не закрыта, поскольку это вспомогательная функция, которая должна быть доступна производным классам. (Подчерк в имени функции призван обратить внимание на то, что это не часть открытого интерфейса иерархии Query.)
Например, вектор позиций для слова bird содержит два вхождения в одной и той же строке, поэтому его разрешающее множество будет состоять из одного элемента: (2). Вектор позиций для слова tell содержит три вхождения, из них два относятся к одной и той же строке; следовательно, в его разрешающем множестве будет два элемента: (2,4). Вот как выглядят результаты для всех представленных выше векторов позиций:
bird (2)
daddy (0,3,5)
fiery (2)
hair (0,1)
her (0,1,2,4)
him (4)
she (4,5)
tell (2,4)
Чтобы вычислить результат запроса NameQuery, достаточно получить вектор позиций для указанного слова, преобразовать его в множество неповторяющихся номеров строк и вывести соответствующие строки текста.
Ответом на NotQuery служит множество строк, в которых не встречается указанное слово. Так, результатом запроса
! daddy
служит множество (1,2,4). Для вычисления результата надо знать, сколько всего строк содержится в тексте. (Мы не сохраняли эту информацию, поскольку не были уверены, что она потребуется; к сожалению, недостаточно и этого.) Чтобы упростить обработку NotQuery, полезно сгенерировать множество всех номеров строк текста (0,1,2,3,4,5): теперь для получения результата достаточно с помощью алгоритма set_difference() вычислить разность двух множеств. (Ответом на показанный выше запрос будет множество (0,3,5).)
Результатом OrQuery является объединение номеров строк, где встречается левый или правый операнд. Например, если дан запрос:
fiery || her
то результирующим множеством будет (0,1,2,4), которое получается объединением множества (2) для слова fiery и множества (0,1,2,4) для слова her. Такое множество должно быть упорядочено по возрастанию номеров строк и не содержать дубликатов.
До сих пор нам удавалось вычислять результат запроса, работая только с множествами неповторяющихся номеров строк. Однако для обработки AndQuery надо принимать во внимание как номер строки, так и номер колонки в каждой паре. Так, указанные в запросе
her && hair
слова встречаются в четырех разных строках. Определенная нами семантика AndQuery говорит, что строка является подходящей, если содержит точную последовательность her hair. Вхождения слов в первую строку не удовлетворяют этому условию, хотя они стоят рядом:
Alice Emma has long flowing red hair. Her Daddy says
а вот во второй строке слова расположены так, как нужно:
when the wind blows through her hair, it looks almost alive,
Для оставшихся двух вхождений слова her слово hair не является соседним. Таким образом, ответом на запрос является вторая строка текста: (1).
Если бы не операция AndQuery, нам не пришлось бы вычислять вектор позиций для каждой операции. Но, поскольку операндом AndQuery может быть результат любого запроса, то для каждого приходится вычислять и сохранять не только множество неповторяющихся строк, но и пары (строка, колонка). Рассмотрим следующие запросы:
fiery && ( hair || bird || potato )
fiery && ( ! burr )
NotQuery может быть операндом AndQuery, следовательно, мы должны создать не просто вектор, содержащий по одному элементу для каждой подходящей строки, но и вектор, в котором хранятся позиции. (Мы еще вернемся к этому при рассмотрении функции eval() для класса NotQuery в разделе 17.5.)
Таким образом, идентифицирован еще один необходимый член - вектор позиций, ассоциированный с вычислением каждой операции. У нас есть выбор: объявить его членом каждого производного класса или членом абстрактного базового класса Query, наследуемым всеми производными. Объем памяти для хранения этого члена в обоих случаях одинаков. Мы поместим его в базовый класс, локализовав поддержку инициализации и доступа к члену.
Решение о том, представлять ли множество неповторяющихся номеров строк (мы называем его разрешающим множеством) в виде члена класса или каждый раз вычислять его, принимает разработчик. Мы предпочли вычислять его по мере необходимости, а затем сохранять адрес для последующего доступа, объявляя этот адрес членом абстрактного базового класса Query.
Для вывода найденных строк нам необходимо как разрешающее множество, так и фактический текст, из которого взяты строки. Причем вектор позиций у каждой операции должен быть свой, а экземпляр текста нужен только один. Поэтому мы определим его статическим членом класса Query. (Реализация функции display() опирается только на эти два члена.)
Вот результат первой попытки создать абстрактный базовый класс Query (конструкторы, деструктор и копирующий оператор присваивания еще не объявлены: этим мы займемся в разделах 17.4 и 17.6):
#include <vector>
#include <set>
#include <string>
#include <utility>
typedef pair< short, short > location;
class Query {
public:
// конструкторы и деструктор обсуждаются в разделе 17.4
// копирующий конструктор и копирующий оператор присваивания
// обсуждаются в разделе 17.6
// операции для поддержки открытого интерфейса
virtual void eval() = 0;
virtual void display () const;
// функции доступа для чтения
const set<short> *solution() const;
const vector<location> *locations() const { return &_loc; }
static const vector<string> *text_file() {return _text_file;}
protected:
set<short>* _vec2set( const vector<location>* );
static vector<string> *_text_file;
set<short> *_solution;
vector<location> _loc;
};
inline const set<short>
Query::
solution()
{
return _solution
? _solution
: _solution = _vec2set( &_loc );
}
Странный синтаксис
virtual void eval() = 0;
говорит о том, что для виртуальной функции eval() в абстрактном базовом классе Query нет определения: это чисто виртуальная функция, "удерживающая место" в открытом интерфейсе иерархии классов и не предназначенная для непосредственного вызова из программы. Вместо нее каждый производный класс должен предоставить настоящую реализацию. (Подробно виртуальные функции будут рассматриваться в разделе 17.5.)
17.2.2. Определение производных классов
Каждый производный класс наследует данные и функции-члены своего базового класса, и программировать приходится лишь те аспекты, которые изменяют или расширяют его поведение. К примеру, в классе NameQuery необходимо определить реализацию eval(). Кроме того, нужна поддержка для хранения слова-операнда, представленного объектом класса типа string.
Наконец, для получения ассоциированного вектора позиций должно быть доступно отображение слов на векторы. Поскольку один такой объект разделяется всеми объектами класса NameQuery, мы объявляем его статическим членом. Первая попытка определения NameQuery (рассмотрение конструкторов, деструктора и копирующего оператора присваивания мы снова отложим) выглядит так:
typedef vector<location> loc;
class NameQuery : public Query {
public:
// ...
// переопределяет виртуальную функцию Query::eval()2
virtual void eval();
// функция чтения
string name() const { return _name; }
static const map<string,loc*> *word_map() { return _word_map; }
protected:
string _name;
static map<string,loc*> *_word_map;
};
Класс NotQuery в дополнение к предоставлению реализации виртуальной функции eval() должен обеспечить поддержку своего единственного операнда. Поскольку им может быть объект любого из производных классов, определим его как указатель на тип Query. Результат запроса NotQuery, напомним, обязан содержать не только строки текста, где нет указанного слова, но также и номера колонок внутри каждой строки. Например, если есть запрос:
! daddy
то операнд запроса NotQuery включает следующий вектор позиций:
daddy ((0,8),(3,3),(5,5))
Вектор позиций, возвращаемый в ответ на исходный запрос, должен включать все номера колонок в строках (1,2,4). Кроме того, он должен включать все номера колонок в строке (0), кроме колонки (8), все номера колонок в строке (3), кроме колонки (3), и все номера колонок в строке (5), кроме колонки (5).
Простейший способ вычислить все это - создать единственный разделяемый всеми объектами вектор позиций, который содержит пары (строка, колонка) для каждого слова в тексте (полную реализацию мы рассмотрим в разделе 17.5, когда будем обсуждать функцию eval() класса NotQuery). Так или иначе, этот член мы объявим статическим для NotQuery.
Вот определение класса NotQuery (и снова рассмотрение конструкторов, деструктора и копирующего оператора присваивания отложено):
class NotQuery : public Query {
public:
// ...
// альтернативный синтаксис: явно употреблено ключевое слово virtual
// переопределение Query::eval()
virtual void eval();
// функция доступа для чтения
const Query *op() const { return _op; }
static const vector< location > * all_locs() {
return _all_locs; }
protected:
Query *_op;
static const vector< location > *_all_locs;
};
Классы AndQuery и OrQuery представляют бинарные операции, у которых есть левый и правый операнды. Оба операнда могут быть объектами любого из производных классов, поэтому мы определим соответствующие члены как указатели на тип Query. Кроме того, в каждом классе нужно переопределить виртуальную функцию eval(). Вот начальное определение OrQuery:
class OrQuery : public Query {
public:
// ...
virtual void eval();
const Query *rop() const { return _rop; }
const Query *lop() const { return _lop; }
protected:
Query *_lop;
Query *_rop;
};
Любой объект AndQuery должен иметь доступ к числу слов в каждой строке. В противном случае при обработке запроса AndQuery мы не сможем найти соседние слова, расположенные в двух смежных строках. Например, если есть запрос:
tell && her && magical
то нужная последовательность находится в третьей и четвертой строках:
like a fiery bird in flight. A beautiful fiery bird, he tells her,
magical but untamed. "Daddy, shush, there is no such thing, "
Векторы позиций, ассоциированные с каждым из трех слов, следующие:
her ((0,7),(1,5),(2,12),(4,11))
magical ((3,0))
tell ((2,11),(4,1),(4,10))
Если функция eval() класса AndQuery "не знает ", сколько слов содержится в строке (2), то она не сможет определить, что слова magical и her соседствуют. Мы создадим единственный экземпляр вектора, разделяемый всеми объектами класса, и объявим его статическим членом. (Реализацию eval() мы детально рассмотрим в разделе 17.5.) Итак, определим AndQuery:
class AndQuery : public Query {
public:
// конструкторы обсуждаются в разделе 17.4
virtual void eval();
const Query *rop() const { return _rop; }
const Query *lop() const { return _lop; }
static void max_col( const vector< int > *pcol )
{ if ( !_max_col ) _max_col = pcol; }
protected:
Query *_lop;
Query *_rop;
static const vector<int > *_max_col;
};
|
| Категория: С++ | Добавил: r2d2 (29.09.2011)
|
| Просмотров: 995
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Born in Ussr |
|
|
| Залогиниться |
|
|
|
| Турниры |
|
|
|
