С++ для начинающих - Учебное пособие

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.

В нашей системе мы выбрали следующий язык запросов:

одиночное  слово,  например  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:

==> ! 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. Определение иерархии классов

В этой главе мы построим иерархию классов для представления  запроса пользователя.

Примечание [O.A.5]: Нумера ция сносок сбита.

 

 

NameQuery     // Shakespeare

NotQuery        // ! Shakespeare

OrQuery          // Shakespeare || Marlowe

Сначала реализуем каждую операцию в виде отдельного класса:

AndQuery       // William && Shakespeare

В каждом классе определим функцию-член eval(), которая выполняет соответствующую операцию.  К  примеру,  для  NameQuery она  возвращает  вектор  позиций,  содержащий координаты (номера строки и колонки) начала каждого вхождения слова (см. раздел 6.8); для OrQuery строит объединение векторов позиций обоих своих операндов и т.д.

Таким образом, запрос

untamed || fiery

состоит из объекта класса OrQuery, который содержит два объекта NameQuery в качестве операндов. Для простых запросов этого достаточно, но при обработке составных запросов типа

Alice || Emma && Weeks

1 Напомним, что для упрощения реализации необходимо, чтобы между любыми двумя словами, включая скобки и операторы запроса, был пробел. В реальной системе такое требование вряд ли разумно, но мы полагаем, что для вводного курсе, каковым является наша книга, это вполне приемлемо.

 

возникает  проблема.  Данный  запрос  состоит  из  двух  подзапросов:  объекта  OrQuery,

содержащего  объекты  NameQuery для  представления  слов  Alice и  Emma,  и  объекта

AndQuery

OrQuery

NameQuery ("Alice") NameQuery ("Emma")

AndQuery. Правым операндом AndQuery является объект NameQuery для слова Weeks.

NameQuery ("Weeks")

Но левый операнд – это объект OrQuery, предшествующий оператору &&. На его месте мог бы быть объект NotQuery или другой объект AndQuery. Как же следует представить операнд, если он может принадлежать к типу любого из четырех классов? Эта проблема имеет две стороны:

необходимо  уметь  объявлять  тип  операнда  в  классах  OrQuery,  AndQuery и NotQuery так,  чтобы  с  его  помощью  можно  было представить  тип  любого  из четырех классов запросов;

какое бы решение мы ни выбрали в предыдущем случае, мы должны иметь возможность  вызывать  соответствующий  классу  каждого операнда  вариант функции-члена 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++,  то имеем  в  виду главным  образом способность указателя или ссылки на базовый класс адресовать любой из производных от

// pquery может адресовать любой из классов, производных от Query void eval( const Query *pquery )

{

pquery->eval();

него. Если определить обычную функцию eval() следующим образом:

}

int main()

{

AndQuery aq; NotQuery notq;

OrQuery *oq = new OrQuery; NameQuery nq( "Botticelli" );

// правильно: любой производный от Query класс

// компилятор автоматически преобразует в базовый класс

eval( &aq ); eval( &notq ); eval( oq ); eval( &nq );

то мы вправе вызывать ее, передавая адрес объекта любого из четырех типов запросов:

}

В  то  же  время   попытка   передать   eval() адрес  объекта   класса,   не  являющегося

int main()

{

string name( "Scooby-Doo" );

// ошибка: тип string не является производным от Query eval( &name );

производным от Query, вызовет ошибку компиляции:

}

Внутри 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++ обеспечивает поддержку полиморфизма следующими способами:

путем неявного преобразования указателя или ссылки на производный класс к указателю или ссылке на открытый базовый:

Query *pquery = new NameQuery( "Class" );

через механизм виртуальных функций:

pquery->eval();

с помощью операторов dynamic_cast и typeid (они подробно обсуждаются в

if ( NameQuery *pnq =

разделе 19.1):

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 следует ответить на такие вопросы:

(a)                    Какие  операции   следует   предоставить   в   открытом   интерфейсе  иерархии классов Query?

(b)        Какие из них следует объявить виртуальными?

(c)        Какие дополнительные операции могут потребоваться производным классам?

(d)       Какие данные-члены  следует  объявить в нашем абстрактном  базовом классе

Query?

(e)        Какие данные-члены могут потребоваться производным классам?

К сожалению, однозначно ответить на эти вопросы невозможно. Как мы увидим, процесс объектно-ориентированного проектирования по своей природе итеративен, эволюционирующая  иерархия  классов требует и добавлений, и модификаций. В оставшейся части этого раздела мы будем постепенно уточнять иерархию классов Query.

17.2.1. Определение базового класса

Члены Query представляют:

 

множество операций, поддерживаемых всеми производными от него классами запросов.  Сюда  входят  как  виртуальные  операции,  переопределяемые  в производных классах, так и невиртуальные, разделяемые всеми производными классами (мы приведем примеры тех и других);

множество данных-членов, общих для всех производных классов. Если вынести такие члены в абстрактный базовый класс 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).

2 В объявлении унаследованной виртуальной функции, например eval(), в производном   классе   ключевое   слово   virtual необязательно.   Компилятор делает правильное заключение на основе сравнения с прототипом функции.

 

Простейший  способ  вычислить  все  это –  создать  единственный  разделяемый  всеми объектами вектор позиций, который содержит пары (строка, колонка) для каждого слова в тексте (полную реализацию мы рассмотрим в разделе 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(). Вот начальное

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;

 

 

определение OrQuery:

};

Любой  объект  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.) Итак,

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;

 

 

определим AndQuery:

};

17.2.3. Резюме

Открытый интерфейс каждого из четырех производных классов состоит из их открытых членов и унаследованных открытых членов Query. Когда мы пишем:

Query *pq = new NmaeQuery( "Monet" );

то  получить  доступ  к  открытому  интерфейсу  Query можно  только  через  pq.  А  если пишем:

pq->eval();

то  вызывается  реализация  виртуальной  eval() из  производного  класса,  на  объект которого указывает pq, в данном случае – из класса NameQuery. Строкой

pq->display();

 

всегда  вызывается  невиртуальная  функция  display() из Query.  Однако она выводит разрешающее множество строк объекта того производного класса, на который указывает pq. В этом случае мы не стали полагаться на механизм виртуализации, а вынесли разделяемую  операцию и необходимые для нее данные в общий  абстрактный  базовый класс   Query.   display() –   это   пример   полиморфного   программирования,   которое поддерживается не виртуальностью, а исключительно с помощью   наследования. Вот ее реализация  (это  пока  только  промежуточное  решение,  как  мы  увидим  в  последнем

void Query:: display()

{

if ( ! _solution->size() ) {

cout << " Извините, "

<< " подходящих строк в тексте не найдено. "

<< endl;

}

set<short>::const_iterator

it = _solution->begin(), end_it = _solution->end();

for ( ; it != end_it; ++it ) {

int line = *it;

// не будем пользоваться нумерацией строк с 0... cout << "(" << line+1 << " ) "

<< (*_text_file)[line] << ' ';

}

cout << endl;

разделе):

}

В этом разделе мы попытались определить  иерархию классов Query. Однако вопрос о том,   как   же   построить   с   ее   помощью   структуру   данных,   описывающую   запрос пользователя, остался без ответа. Когда мы приступим к реализации, это определение придется пересмотреть и расширить. Но прежде нам предстоит более детально изучить механизм наследования в языке C++.

Упражнение 17.3

Рассмотрите приведенные члены иерархии классов для поддержки библиотеки из упражнения 17.1 (раздел 17.1). Выявите возможные кандидаты на роль виртуальных функций, а также те члены, которые являются общими для всех предметов, выдаваемых библиотекой, и, следовательно, могут быть представлены в базовом классе. (Примечание: LibMember –   это   абстракция   человека,   которому   разрешено   брать   из   библиотеки различные предметы; Date – класс, представляющий календарную дату.)

 

class Library {

public:

bool check_out( LibMember* );         // выдать

bool check_in ( LibMember* );           // принять назад

bool is_late( const Date& today ); // просрочил double apply_fine();          // наложить штраф ostream& print( ostream&=cout );

Date* due_date() const;         // ожидаемая дата возврата

Date* date_borrowed() const;            // дата выдачи

string title() const;       // название

const LibMember* member() const;   // записавшийся

};

Упражнение 17.4

Идентифицируйте члены базового и производных классов для той иерархии, которую вы выбрали  в  упражнении  17.2  (раздел  17.1).  Задайте  виртуальные  функции,  а  также открытые и защищенные члены.

Упражнение 17.5

class base { ... };

(a) class Derived : public Derived { ... }; (b) class Derived : Base { ... };

(c) class Derived : private Base { ... }; (d) class Derived : public Base;

Какие из следующих объявлений неправильны:

(e) class Derived inherits Base { ... };

17.3. Доступ к членам базового класса

Объект   производного   класса   фактически   построен   из   нескольких   частей.   Каждый базовый класс вносит свою долю в виде подобъекта, составленного из нестатических данных-членов этого класса. Объект производного класса построен из подобъектов, соответствующих каждому из его базовых, а также из части, включающей нестатические члены самого производного класса. Так, наш объект NameQuery состоит из подобъекта Query, содержащего члены _loc и _solution, и части, принадлежащей NameQuery, – она содержит только член _name.

Внутри производного класса к членам, унаследованным из базового, можно обращаться напрямую,  как  к  его  собственным.  (Глубина  цепочки  наследования  не  увеличивает затраты времени и не лимитирует доступ к ним.) Например:

 

void

NameQuery::

display_partial_solution( ostream &os )

{

os << _name

<< " is found in "

<< (_solution ? _solution->size() : 0)

<< " lines of text ";

}

Это  касается   и  доступа   к  унаследованным   функциям-членам   базового  класса:  мы

NameQuery nq( "Frost" );

// вызывается NameQuery::eval()

nq.eval();

// вызывается Query::display()

вызываем их так, как если бы они были членами производного – либо через его объект:

nq.display();

void NameQuery:: match_count()

{

if ( ! _solution )

// вызывается Query::_vec2set()

_solution = _vec2set( &_loc );

return _solution->size();

либо непосредственно из тела другой (или той же самой) функции-члена:

}

Однако прямой доступ  из производного класса к членам базового запрещен,  если имя

class Diffident { public:  // ... protected:

int _mumble;

// ...

};

class Shy : public Diffident {

public: // ...

protected:

// имя Diffident::_mumble скрыто

string _mumble;

// ...

последнего скрыто в производном классе:

};

 

В   области   видимости   Shy употребление   неквалифицированного   имени   _mumble

разрешается  в  пользу  члена  _mumble класса  Shy (объекта  string),  даже  если  такое

void Shy:: turn_eyes_down()

{

// ...

_mumble = "excuse me";         // правильно

// ошибка: int Diffident::_mumble скрыто

_mumble = -1;

использование в данном контексте недопустимо:

}

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

void Shy:: turn_eyes_down()

{

// ...

_mumble = "excuse me";         // правильно

// правильно: имя члена базового класса квалифицировано

Diffident::_mumble = -1;

turn_eyes_down():

}

Функции-члены        базового         и          производного            классов           не        составляют     множество

class Diffident {

public:

void mumble( int softness );

// ...

};

class Shy : public Diffident {

public:

// скрывает видимость функции-члена Diffident::_mumble,

// а не перегружает ее

void mumble( string whatYaSay );

void print( int soft, string words );

// ...

перегруженных функций:

};

Вызов функции-члена базового класса из производного в этом случае приводит к ошибке компиляции:

 

Shy simon;

// правильно: Shy::mumble( string )

simon.mumble( "pardon me" );

// ошибка: ожидался первый аргумент типа string

// Diffident::mumble( int ) невидима

simon.mumble( 2 );

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

class Diffident {

public:

void turn_aside( );

// ...

};

class Shy : public Diffident {

public:

// скрывает видимость

// Diffident::turn_aside()

void turn_aside();

// ...

следующие два экземпляра невиртуальной функции-члена turn_aside()

};

привели бы к ошибке повторного определения, так как их сигнатуры одинаковы. Однако запись  правильна,  поскольку  каждая  функция  находится  в  области  видимости  того класса, в котором определена.

А если нам действительно нужен набор перегруженных функций-членов базового и производного классов? Написать в производном классе небольшую встроенную заглушку

class Shy : public Diffident {

public:

// один из способов реализовать множество перегруженных

// членов базового и производного классов

void mumble( string whatYaSay );

void mumble( int softness ) { Diffident::mumble( softness ); }

// ...

для вызова экземпляра из базового? Это возможно:

};

Но в стандартном C++  тот же результат достигается посредством using-объявления:

 

class Shy : public Diffident {

public:

// в стандартном C++ using-объявление

// создает множество перегруженных

// членов базового и производного классов

void mumble( string whatYaSay );

using Diffident::mumble;

// ...

};

По  сути  дела,  using-объявление  вводит  каждый  именованный  член  базового  класса  в область видимости производного. Поэтому такой член теперь входит в множество перегруженных   функций,   ассоциированных   с  именем   функции-члена   производного класса.  (В  ее  using-объявлении  нельзя  указать  список  параметров,  только  имя.  Это означает, что если некоторая функция уже перегружена в базовом классе, то в область видимости  производного  класса  попадут  все  перегруженные  экземпляры  и, следовательно, добавить только одну из них невозможно.)

Обратим внимание на степень доступности защищенных членов базового класса. Когда

class Query {

public:

const vector<location>* locations() { return &_loc; }

// ... protected:

vector<location> _loc;

// ...

мы пишем:

};

то имеем в виду, что класс, производный от Query, может напрямую обратиться к члену

_loc,  тогда  как  во  всей  остальной  программе  для  этого  необходимо  пользоваться открытой функцией доступа. Однако объект производного класса имеет доступ только к защищенному члену _loc входящего в него подобъекта, относящегося к базовому классу. Объект  производного  класса  неспособен  обратиться  к  защищенным  членам  другого

bool

NameQuery::

compare( const Query *pquery )

{

// правильно: защищенный член подобъекта Query int myMatches = _loc.size();

// ошибка: нет прав доступа к защищенному члену

// независимого объекта Query

int itsMatches = pquery->_loc.size();

return myMatches == itsMatches;

независимого объекта базового класса:

}

 

У объекта NameQuery есть доступ к защищенным членам только одного объекта Query – подобъекта самого себя. Прямое обращение к ним из производного класса осуществляется через неявный указатель this (см. раздел 13.4). Первая реакция на ошибку компиляции – переписать     функцию     compare()  с    использованием     открытой     функции-члена

bool

NameQuery::

compare( const Query *pquery )

{

// правильно: защищенный член подобъекта Query int myMatches = _loc.size();

// правильно: используется открытый метод доступа

int itsMatches = pquery->locations()->size();

return myMatches == itsMatches;

location():

}

Однако проблема  заключается  в неправильном  проектировании.  Поскольку _loc – это член   базового   класса   Query,   то   место   compare() среди   членов   базового,   а   не производного класса. Во многих случаях подобные проблемы могут быть решены путем переноса некоторой операции в тот класс, где находится недоступный член, как в приведенном примере.

Этот вид ограничения доступа не распространяется на доступ изнутри класса к другим

bool

NameQuery::

compare( const NameQuery *pname )

{

int myMatches = _loc.size();   // правильно

int itsMatches = name->_loc.size();    // тоже правильно

return myMatches == itsMatches;

объектам того же класса:

}

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

Рассмотрим инициализацию указателя на базовый Query адресом объекта производного

NameQuery:

Query *pb = new NameQuery( "sprite" );

При вызове виртуальной функции, определенной в базовом классе Query, например:

pb->eval(); // вызывается NameQuery::eval()

 

вызывается функция из NameQuery. За исключением вызова виртуальной функции, объявленной  в  Query и  переопределенной  в  NameQuery,  другого  способа  напрямую добраться до членов класса NameQuery через указатель pb не существует:

(a)        если  в  Query и  NameQuery объявлены  некоторые  невиртуальные  функции-

члены с одинаковым именем, то через pb всегда вызывается экземпляр из Query;

(b)        если  в  Query и  NameQuery объявлены  одноименные  члены,  то  через  pb

обращение происходит к члену класса Query;

(c)        если  в  NameQuery имеется  виртуальная  функция,  отсутствующая  в  Query,

скажем   suffix(),   то   попытка   вызвать   ее   через   pb приводит   к   ошибке

// ошибка: suffix() - не член класса Query

компиляции:

pb->suffix();

Обращение к члену или невиртуальной функции-члену класса NameQuery через

// ошибка: _name - не член класса Query

pb тоже вызывает ошибку компиляции:

pb->_name;

// ошибка: у класса Query нет базового класса NameQuery

Квалификация имени члена в этом случае не помогает:

pb->NameQuery::_name;

В C++ с помощью указателя на базовый класс можно работать только с данными и функциями-членами, включая виртуальные, которые объявлены (или унаследованы) в самом этом классе, независимо от того, какой фактический объект адресуется указателем. Объявление функции-члена виртуальной откладывает решение вопроса о том, какой экземпляр  функции  вызвать,  до  выяснения  (во  время  выполнения  программы) фактического типа объекта, адресуемого pb.

Такой подход может показаться недостаточно гибким, но у него есть два весомых преимущества:

поиск виртуальной функции-члена во время выполнения никогда не закончится неудачно из-за того, что фактический тип класса не существует. В таком случае программа просто не смогла бы откомпилироваться;

механизм виртуализации можно оптимизировать. Часто вызов такой функции оказывается  не дороже,  чем  косвенный  вызов  функции  по указателю  (детально этот вопрос рассмотрен в [LIPPMAN96a]).

В базовом классе Query определен статический член _text_file:

static vector<string> *_text_file;

 

Создается   ли   при   порождении   класса   NameQuery второй   экземпляр   _text_file, уникальный именно для него? Нет. Все объекты производного класса ссылаются на тот же самый,  единственный  разделяемый  статический  член.  Сколько бы  ни было производных классов, существует лишь один экземпляр _text_file. Можно обратиться к нему через объект производного класса с помощью синтаксиса доступа:

nameQueryObject._text_file;             // правильно

Наконец,  если  производный  класс  хочет  получить  доступ  к  закрытым  членам  своего

class Query {

friend class NameQuery;

public:

// ...

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

};

Теперь  объект  NameQuery может  обращаться  не  только  к  закрытым  членам  своего подобъекта, соответствующего базовому классу, но и к закрытым и защищенным членам любых объектов Query.

А  если  мы  произведем  от  NameQuery класс  StringQuery?  Он  будет  поддерживать сокращенную форму запроса AndQuery, и вместо

beautiful && fiery && bird

можно будет написать:

"beautiful fiery bird"

Унаследует  ли StringQuery от класса NameQuery дружественные отношения с Query? Нет.  Отношение  дружественности  не  наследуется.  Производный  класс  не  становится другом  класса,  который  объявил  своим  другом  один  из  базовых.  Если  производному классу требуется стать другом одного или более классов, то эти классы должны предоставить  ему соответствующие  права  явно.  Например,  у класса  StringQuery нет никаких специальных прав доступа по отношению к Query. Если расширенный доступ необходим, то Query должен разрешить его явно.

Упражнение 17.6

Даны следующие определения базового и производных классов:

 

class Base {

public:

foo( int );

// ...

protected:

int _bar;

double _foo_bar;

};

class Derived : public Base {

public:

foo( string );

bool bar( Base *pb );

void foobar();

// ... protected:

string _bar;

};

Derived d; d.foo( 1024 );

Исправьте ошибки в каждом из следующих фрагментов кода:

(c) bool Derived::bar( Base *pb )

(b) void Derived::foobar() { _bar = 1024; }

{ return _foo_bar == pb->_foo_bar; }

17.4. Конструирование базового и производного классов

Напомним, что объект производного класса состоит из одного или более подобъектов, соответствующих базовым классам, и части, относящейся к самому производному. Например,   NameQuery состоит  из  подобъекта  Query и  объекта-члена   string.  Для иллюстрации   поведения   конструктора   производного   класса  введем   еще  один   член

class NameQuery : public Query {

public:

// ... protected:

bool     _present;

string _name;

встроенного типа:

};

Если _present установлен в false, то слово _name в тексте отсутствует.

 

Рассмотрим   случай,   когда   в   NameQuery конструктор   не   определен.   Тогда   при определении объекта этого класса

NameQuery nq;

по очереди вызывается конструктор по умолчанию Query, а затем конструктор по умолчанию класса string (ассоциированный с объектом _name). Член _present остается неинициализированным, что потенциально может служить источником ошибок. Чтобы инициализировать его, можно так определить конструктор по умолчанию для класса NameQuery:

inline NameQuery::NameQuery() { _present = false; }

Теперь при определении nq вызываются три конструктора по умолчанию: для базового класса   Query,   для  класса  string при  инициализации   члена  _name и  для  класса NameQuery.

А как передать аргумент конструктору базового класса Query? Ответить на этот вопрос можно, рассуждая по аналогии.

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

inline NameQuery::

NameQuery( const string &name )

: _name( name ), _present( false )

являющимся объектами классов; подробности см. в разделе 14.5):

{}

Для передачи одного или более аргументов конструктору базового класса также разрешается использовать список инициализации членов. В следующем примере мы передаем конструктору string аргумент name, а конструктору базового класса Query –

inline NameQuery::

NameQuery( const string &name,

vector<location> *ploc )

: _name( name ), Query( *ploc ), _present( true )

объект, адресованный указателем ploc:

{}

Хотя   Query помещен   в   список   инициализации   вторым,   его   конструктор   всегда вызывается раньше конструктора для _name. Порядок их вызова следующий:

Конструктор базового класса. Если базовых классов несколько, то конструкторы вызываются в порядке их следования в списке базовых классов, а не в порядке появления в списке инициализации. (О множественном наследовании в этой связи мы поговорим в главе 18.)

Конструктор объекта-члена. Если в классе есть несколько таких членов, то конструкторы вызываются в порядке их объявления в классе, а не в порядке появления в списке инициализации (подробнее см. раздел 14.5).

 

Конструктор производного класса.

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

В  оставшейся  части  этого  раздела  мы  последовательно  изучим  конструктор  базового класса и конструкторы четырех производных от него, а после этого рассмотрим альтернативный дизайн иерархии классов Query, чтобы познакомиться с иерархиями глубиной больше двух. В конце раздела речь пойдет о деструкторах классов.

17.4.1. Конструктор базового класса

class Query {

public:

// ...

protected:

set<short> *_solution;

vector<location> _loc;

// ...

В нашем базовом классе объявлено два нестатических члена: _solution и _loc:

};

Конструктор   Query по   умолчанию   должен   явно   инициализировать   только   член

_solution.  Для  инициализации  _loc автоматически  вызывается  конструктор  класса

vector. Вот реализация нашего конструктора:

inline Query::Query(): _solution( 0 ) {}

В  Query нам  понадобится  еще  один  конструктор,  принимающий  ссылку  на  вектор

inline

Query::

Query( const vector< locaton > &loc )

: _solution( 0 ), _loc( loc )

позиций:

{}

Он  вызывается  только  из  конструктора  NameQuery,  когда  объект  этого  класса используется для представления указанного в запросе слова. В таком случае передается предварительно подготовленный для него вектор позиций. Остальные три производных класса вычисляют свои векторы позиций в соответствующей функции-члене eval(). (В следующем  подразделе  мы  покажем,  как  это  делается.  Реализации  функций-членов eval() приведены в разделе 17.5.)

Какой уровень доступа обеспечить для конструкторов? Мы не хотим объявлять их открытыми, так как предполагается, что Query будет существовать в программе только в

 

виде подобъекта в составе объектов производных от него классов. Поэтому мы объявим

class Query {

public:

// ... protected:

Query();

// ...

конструктор не открытым, а защищенным:

};

Ко второму конструктору класса Query предъявляются  еще более жесткие требования: он не только должен конструировать Query в виде подобъекта производного класса, но этот производный класс должен к тому же быть NameQuery. Можно объявить конструктор закрытым,  а  NameQuery сделать  другом  класса  Query.  (В  предыдущем  разделе  мы говорили, что производный класс может получить доступ только к открытым и защищенным членам базового. Поэтому любая попытка вызвать второй конструктор из

class Query {

public:

// ...

protected: Query();

// ... private:

explicit Query( const vector<location>& );

классов AndQuery, OrQuery или NotQuery приведет к ошибке компиляции.)

};

(Необходимость  второго конструктора  спорна;  вероятно,  правильнее  заполнить  _loc в функции  eval() класса  NameQuery.   Однако  принятый   подход  в  большей  степени отвечает нашей цели проиллюстрировать использование конструктора базового класса.)

17.4.2. Конструктор производного класса

В классе NameQuery также определены  два  конструктора.  Они объявлены  открытыми,

class NameQuery : public Query {

public:

explicit NameQuery( const string& );

NameQuery( const string&, const vector<location>* );

// ... protected:

// ...

поскольку ожидается, что в приложении будут создаваться объекты этого класса:

};

 

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

inline

NameQuery::

NameQuery( const string &name )

// Query::Query() вызывается неявно

: _name( name )

члена _name. Конструктор по умолчанию базового класса Query вызывается неявно:

{}

Конструктор с двумя параметрами также принимает строку в качестве одного из них. Второй  его  параметр –  это  указатель  на  вектор  позиций.  Он  передается  закрытому конструктору базового класса Query. (Обратите внимание, что _present нам больше не

inline

NameQuery::

NameQuery( const string &name, vector<location> *ploc )

: _name( name ), Query( *ploc )

нужен, и мы исключили его из числа членов NameQuery.)

{}

string title( "Alice" ); NameQuery *pname;

// проверим, встречается ли "Alice" в отображении слов

// если да, получить ассоциированный с ним вектор позиций

if ( vector<location> *ploc = retrieve_location( title ))

pname = new NameQuery( title, ploc );

Конструкторы можно использовать так:

else pname = new NameQuery( title );

В   каждом   из   классов   NotQuery,   OrQuery и   AndQuery определено   по   одному

inline NotQuery::

NotQuery( Query *op = 0 ) : _op( op ) {}

inline OrQuery::

OrQuery( Query *lop = 0, Query *rop = 0 )

: _lop( lop ), _rop( rop )

{}

inline AndQuery::

AndQuery( Query *lop = 0, Query *rop = 0 )

: _lop( lop ), _rop( rop )

конструктору, каждый из которых вызывает конструктор базового класса неявно:

{}

 

(В  разделе  17.7  мы  построим  объекты  каждого  из  производных  классов  для представления различных запросов пользователя.)

17.4.3. Альтернативная иерархия классов

Хотя  наша  иерархия  классов  Query представляется  вполне приемлемой,  она  вовсе не является единственно возможной. Например, AndQuery и OrQuery связаны с бинарной операцией, поэтому они в какой-то степени дублируют друг друга. Можно вынести все данные и функции-члены, общие для них, в абстрактный базовый класс BinaryQuery. Поддерево новой иерархии Query изображено на рисунке 17.2:

Query

BinaryQuery

AndQuery       OrQuery

Рис. 17.2. Альтернативная иерархия классов

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

Две функции-члена для доступа – lop() и rop(), общие для обоих классов, переносятся выше, в BinaryQuery, и определяются как нестатические встроенные. Аналогично два члена _lop и _rop, объявленные в обоих классах, также переносятся в BinaryQuery и становятся     нестатическими     и    защищенными.     Открытые     конструкторы     обоих

class BinaryQuery : public Query {

public:

const Query *lop() { return _lop; }

const Query *rop() { return _rop; }

protected:

BinaryQuery( Query *lop, Query *rop )

: _lop( lop ), _rop( rop )

{}

Query *_lop; Query *_rop;

производных классов объединяются в один защищенный конструктор BinaryQuery:

};

 

Складывается  впечатление,  что  теперь  оба  производных  класса  должны  предоставить

// увы! эти определения классов некорректны

class OrQuery : public BinaryQuery {

public:

virtual void eval();

};

class AndQuery : public BinaryQuery {

public:

virtual void eval();

лишь подходящие реализации eval():

};

Однако в том виде, в котором мы их определили, эти классы неполны. При компиляции самих   определений   ошибок   не   возникает,   но   если   мы   попытаемся   определить

// ошибка: отсутствует конструктор класса AndQuery

AndQuery proust( new NameQuery( "marcel" ),

 

 

фактический объект:

new NameQuery( "proust " ));

 

 

то  компилятор  выдаст  сообщение  об  ошибке:  в  классе  AndQuery нет  конструктора,

готового принять два аргумента.

Мы предположили, что AndQuery и OrQuery наследуют конструктор BinaryQuery точно так же, как они наследуют функции-члены lop() и rop(). Однако производный класс не наследует конструкторов базового. (Это могло бы привести к ошибкам, связанным с неинициализированными членами производного класса. Представьте, что будет, если в AndQuery добавить  пару  членов,  не являющихся  объектами  классов:  унаследованный конструктор базового класса для инициализации объекта производного AndQuery применять   уже  нельзя.   Однако   программист   может   этого  не  осознавать.   Ошибка проявится не при конструировании объекта AndQuery, а позже, при его использовании. Кстати   говоря,   перегруженные  операторы   new и  delete наследуются,   что  иногда приводит к аналогичным проблемам.)

Каждый производный класс должен предоставлять собственный набор конструкторов. В случае  классов  AndQuery и  OrQuery единственная  цель  конструкторов –  обеспечить интерфейс для передачи двух своих операндов конструктору BinaryQuery. Так выглядит исправленная реализация:

 

// правильно: эти определения классов корректны

class OrQuery : public BinaryQuery {

public:

OrQuery( Query *lop, Query *rop )

: BinaryQuery( lop, rop ) {}

virtual void eval();

};

class AndQuery : public BinaryQuery {

public:

AndQuery( Query *lop, Query *rop )

: BinaryQuery( lop, rop ) {}

virtual void eval();

};

Если мы еще раз взглянем на рис. 17.2, то увидим, что BinaryQuery – непосредственный базовый  класс  для  AndQuery и  OrQuery,  а  Query –для  BinaryQuery.  Таким  образом, Query не является непосредственным базовым классом для AndQuery и OrQuery.

Конструктору производного класса разрешается напрямую вызывать только конструктор своего   непосредственного   предшественника   в   иерархии   (виртуальное   наследование является исключением из этого правила, да и из многих других тоже: см. раздел 18.5). Например,   попытка  включить  конструктор   Query в  список  инициализации  членов объекта AndQuery приведет к ошибке.

При   определении   объектов   классов   AndQuery и   OrQuery теперь   вызываются   три конструктора: для базового Query, для непосредственного базового класса BinaryQuery и для  производного  AndQuery или  OrQuery.  (Порядок  вызова  конструкторов  базовых классов отражает обход дерева иерархии наследования в глубину.) Дополнительный уровень иерархии, связанный с BinaryQuery, практически не влияет на производительность, поскольку мы определили его конструкторы как встроенные.

Так как модифицированная иерархия сохраняет открытый интерфейс исходного проекта, то все эти изменения не сказываются на коде, который был написан в расчете на старую иерархию.  Хотя  модифицировать  пользовательский  код не нужно,  перекомпилировать его все же придется, что может отвратить некоторых пользователей от перехода на новую версию.

17.4.4. Отложенное обнаружение ошибок

Начинающие   программисты   часто   удивляются,   почему   некорректные   определения классов   AndQuery и   OrQuery (в   которых   отсутствуют   необходимые   объявления конструкторов) компилируются без ошибок. Если бы мы не попытались определить фактический объект класса AndQuery, в этой модифицированной иерархии так и осталась бы ненайденная ошибка. Дело в том, что:

если ошибка обнаруживается в точке объявления, то мы не можем продолжать компиляцию  приложения,  пока  не исправим ее. Если же конфликтующее объявление – это часть библиотеки,  для которой  у нас нет исходного текста, то разрешение конфликта может оказаться нетривиальной задачей. Более того, возможно, в нашем коде никогда и не возникнет ситуации, когда эта ошибка проявляется, так что для нас она останется лишь потенциальной угрозой;

 

с другой стороны, если ошибка не найдена вплоть до момента использования, то код может оказаться замусоренным ошибками, проявляющимися в самый неподходящий момент к удивлению программиста. При такой стратегии успешная компиляция говорит не об отсутствии семантических ошибок, а лишь о том, что программа не исполняет код, нарушающий семантические правила языка.

Выдача сообщения об ошибке в точке использования – это одна из форм отложенного вычисления,  распространенного  метода  повышения  производительности  программ.  Он часто применяется для того, чтобы отложить потенциально дорогую операцию выделения или инициализации ресурса до момента, когда в нем возникнет реальная необходимость. Если ресурс так и не понадобится, мы сэкономим на ненужных подготовительных операциях. Если же он потребуется, но не сразу, мы растянем инициализацию программы на более длительный период.

В C++ потенциальные ошибки “комбинирования”, связанные с перегруженными функциями,  шаблонами  и  наследованием  классов,  обнаруживаются  в  точке использования, а не в точке объявления. (Мы полагаем, что это правильно, поскольку необходимость выявлять все возможные ошибки, которые можно допустить в результате комбинирования многочисленных компонентов, – пустая трата времени). Следовательно, для  обнаружения  и  устранения  латентных  ошибок необходимо  тщательно  тестировать код. Подобные ошибки, возникающие при комбинировании двух или более больших компонентов, допустимы; однако в пределах одного компонента, такого, как иерархия классов Query, их быть не должно.

17.4.5. Деструкторы

Когда  заканчивается  время  жизни  объекта  производного  класса,  автоматически вызываются  деструкторы  производного  и  базового  классов  (если  они  определены),  а также деструкторы всех объектов-членов.  Например, если имеется объект класса NameQuery:

NameQuery nq( "hyperion" );

то порядок вызова деструкторов следующий: сначала деструктор NameQuery, затем деструктор  string для  члена  _name и  наконец  деструктор  базового  класса.  В общем случае эта последовательность противоположна порядку вызова конструкторов.

Вот  деструкторы  нашего  базового  Query и  производных  от  него (все  они  объявлены

inline Query::

~Query(){ delete _solution; }

inline NotQuery::

~NotQuery(){ delete _op; }

inline OrQuery::

~OrQuery(){ delete _lop; delete _rop; }

inline AndQuery::

открытыми членами соответствующих классов):

~AndQuery(){ delete _lop; delete _rop; }

Отметим два аспекта:

 

мы не предоставляем явного деструктора NameQuery, потому что никаких специальных действий по очистке его объекта предпринимать не нужно. Деструкторы  базового  класса  и  класса  string для  члена  _name вызываются автоматически;

в деструкторах производных классов оператор delete применяется к указателю типа  Query*.  Чтобы  вызвать  не  деструктор  Query,  а  деструктор  класса  того объекта, который фактически адресуется этим указателем, мы должны объявить деструктор   базового   Query виртуальным.   (Более   подробно   о   виртуальных функциях вообще и о виртуальных деструкторах в частности мы поговорим в следующем разделе.)

В нашей реализации неявно подразумевалось, что память для операндов, указатели на которые имеются в объектах классов NotQuery, OrQuery и AndQuery, выделена из хипа. Именно поэтому в деструкторах мы применяли к этим указателям оператор delete. Но язык  не  позволяет  обеспечить  истинность  такого  предположения,  так  как  в  нем  нет различий между адресами в хипе и вне его. С этой точки зрения наша реализация не застрахована от ошибок.

В  разделе  17.7  мы  инкапсулируем  выделение  памяти  и  конструирование  объектов иерархии Query в управляющий класс UserQuery. Это гарантирует выполнение нашего предположения.  На  уровне  программы  в  целом  следует  перегрузить  операторы  new и delete для   классов   иерархии.   Например,   можно  поступить   следующим   образом. Оператор new устанавливает в объекте флажок, говорящий, что память для него выделена из хипа. Перегруженный оператор delete проверяет этот флажок: если он есть, то память освобождается с помощью стандартного оператора delete.

Упражнение 17.7

Идентифицируйте конструкторы и деструкторы базового и производных классов для той иерархии, которую вы выбрали в упражнении 17.2 (раздел 17.1).

Упражнение 17.8

Измените реализацию класса OrQuery так, чтобы он был производным от BinaryQuery.

Упражнение 17.9

class Object {

public:

virtual ~Object();

virtual string isA();

protected:

string _isA;

private:

Object( string s ) : _isA( s ) {}

Найдите ошибку в следующем определении класса:

};

Упражнение 17.10

Дано определение базового класса:

 

class ConcreteBase {

public:

explicit ConcreteBase( int ); virtual ostream& print( ostream& ); virtual ~Base();

static int object_count();

protected:

int _id;

static int _object_count;

};

(a) class C1 : public ConcreteBase {

public:

C1( int val )

: _id( _object_count++ ) {}

// ...

Что неправильно в следующих фрагментах:

(b) class C2 : public C1 {

public:

C2( int val )

: ConcreteBase( val ), C1( val ) {}

// ...

};

(c) class C3 : public C2 {

public:

C3( int val )

: C2( val ), _object_count( val ) {}

// ...

};

(d) class C4 : public ConcreteBase {

public:

C4( int val )

: ConcreteBase ( _id+val ){}

// ...

};

};

Упражнение 17.11

В  первоначальном   определении  языка  C++  порядок  следования  инициализаторов  в списке  инициализации   членов  определял  порядок  вызова  конструкторов.   Принцип,

 

который  действует  сейчас,  был  принят  в  1986  году.  Как  вы  думаете,  почему  была изменена исходная спецификация?

17.5. Виртуальные функции в базовом и производном классах

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

void Query::display( Query *pb )

{

set<short> *ps = pb->solutions();

// ... display();

(или указателя, или ссылки на объект), для которого она вызвана:

}

Статический тип pb – это Query*. При обращении к невиртуальному члену solutions() вызывается функция-член класса Query. Невиртуальная функция display() вызывается через  неявный  указатель  this.  Статическим  типом  указателя  this также  является Query*, поэтому вызвана будет функция-член класса Query.

class Query {

public:

virtual ostream& print( ostream* = cout ) const;

// ...

Чтобы объявить функцию виртуальной, нужно добавить ключевое слово virtual:

};

Если  функция-член  виртуальна,  то при обращении  к ней вызывается  функция, определенная  в  динамическом  типе  объекта  класса  (или  указателя,  или  ссылки  на объект), для которого она вызвана. Однако для самих объектов класса статический и динамический  тип –  это  одно  и  то  же.  Механизм  виртуальных  функций  правильно работает только для указателей и ссылок на объекты.

Таким  образом,  полиморфизм  проявляется  только  тогда,  когда  объект  производного класса  адресуется  косвенно,  через  указатель  или  ссылку  на  базовый.  Использование самого  объекта   базового   класса   не  сохраняет   идентификацию   типа   производного.

NameQuery nq( "lilacs" );

// правильно: но nq "усечено" до подобъекта Query

Рассмотрим следующий фрагмент кода:

Query qobject = nq;

Инициализация  qobject переменной nq абсолютно законна: теперь qobject равняется подобъекту  nq,  который  соответствует  базовому  классу  Query,  однако  qobject не

 

является объектом NameQuery. Часть nq, принадлежащая NameQuery, “усечена” перед инициализацией  qobject, поскольку она не помещается в область памяти, отведенную под объект Query. Для поддержки этой парадигмы приходится использовать указатели и

void print ( Query object,

const Query *pointer,

const Query &reference )

{

// до момента выполнения невозможно определить,

// какой экземпляр print() вызывается

pointer->print();

reference.print();

// всегда вызывается Query::print()

object.print();

}

int main()

{

NameQuery firebird( "firebird" );

print( firebird, &firebird, firebird );

ссылки, но не сами объекты:

}

В  данном  примере  оба   обращения   через  указатель   pointer и  ссылку  reference разрешаются своим динамическим типом; в обоих случаях вызывается NameQuery::print().  Обращение  же  через  объект  object всегда  приводит  к  вызову Query::print(). (Пример программы, в которой используется эффект “усечения”, приведен в разделе 18.6.2.)

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

17.5.1. Виртуальный ввод/вывод

Первая виртуальная операция, которую мы хотели реализовать, – это печать запроса на стандартный вывод либо в файл:

ostream& print( ostream &os = cout ) const;

Функцию  print() следует объявить виртуальной, поскольку ее реализации зависят от типа,  но нам  нужно  вызывать  ее через указатель  типа  Query*.  Например,  для класса

ostream&

AndQuery::print( ostream &os ) const

{

_lop->print( os );

os << " && ";

_rop->print( os );

AndQuery эта функция могла бы выглядеть так:

}

 

Необходимо  объявить  print() виртуальной  функцией  в  абстрактном  базовом  Query, иначе мы не сможем вызвать ее для членов классов AndQury, OrQuery и NotQuery, являющихся указателями на операнды соответствующих запросов типа Query*. Однако для самого Query разумной реализации print() не существует. Поэтому мы определим

class Query {

public:

virtual ostream& print( ostream &os=cout ) const {}

// ...

ее как пустую функцию, а потом сделаем чисто виртуальной:

};

В базовом  классе,  где виртуальная  функция  появляется  в  первый  раз,  ее объявлению должно предшествовать ключевое слово virtual. Если же ее определение находится вне этого  класса,  повторно  употреблять  virtual не  следует.  Так,  данное  определение

// ошибка: ключевое слово virtual может появляться

//          только в определении класса

print() приведет к ошибке компиляции:

virtual ostream& Query::print( ostream& ) const { ... }

Правильный вариант не должен включать слово virtual.

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

Прежде  чем  приступать  к  рассмотрению  реализаций   print() для  наших  четырех производных классов, обратим внимание на употребление скобок в запросе. Например, с помощью

fiery && bird || shyly

пользователь ищет вхождения пары слов

fiery bird

или одного слова

shyly

С другой стороны, запрос

 

fiery && ( bird || hair )

найдет все вхождения любой из пар

fiery  bird

или

fiery hair

Если наши реализации print() не будут показывать скобки в исходном запросе, то для пользователя  они  окажутся  почти  бесполезными.  Чтобы  сохранить  эту  информацию, введем  в  наш  абстрактный  базовый  класс  Query два  нестатических  члена,  а  также функции  доступа  к ним (подобное  расширение  класса –  естественная  часть  эволюции

class Query {

public:

// ...

// установить _lparen и _rparen

void lparen( short lp ) { _lparen = lp; }

void rparen( short rp ) { _rparen = rp; }

// получить значения_lparen и _rparen short lparen() { return _lparen; } short rparen() { return _rparen; }

// напечатать левую и правую скобки

void print_lparen( short cnt, ostream& os ) const;

void print_rparen( short cnt, ostream& os ) const;

protected:

// счетчики левых и правых скобок

short _lparen;

short _rparen;

// ...

иерархии):

};

_lparen –  это  количество  левых,  а  _rparen –  правых  скобок,  которое  должно  быть выведено при распечатке объекта. (В разделе 17.7 мы покажем, как вычисляются такие величины и как происходит присваивание обоим членам.) Вот пример обработки запроса с большим числом скобок:

==> ( untamed || ( fiery || ( shyly ) ) )

evaluate word: untamed

_lparen: 1

_rparen: 0 evaluate Or

_lparen: 0

_rparen: 0

 

evaluate word: fiery

_lparen: 1

_rparen: 0

evaluate 0r

_lparen: 0

_rparen: 0

evaluate word: shyly

_lparen: 1

_rparen: 0

evaluate right parens:

_rparen: 3

( untamed ( 1 ) lines match

( fiery ( 1 ) lines match

( shyly ( 1 ) lines match

( fiery || (shyly ( 2 ) lines match3

( untamed || ( fiery || ( shyly ))) ( 3 ) lines match

Requested query: ( untamed || ( fiery || ( shyly ) ) )

( 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,"

( 6 ) Shyly, she asks, "I mean, Daddy, is there?"

ostream& NameQuery::

print( ostream &os ) const

{

if ( _lparen )

print_lparen( _lparen, os );

os << _name;

if ( _rparen )

print_rparen( _rparen, os );

return os;

Реализация print() для класса NameQuery:

}

class NameQuery : public Query {

public:

virtual ostream& print( ostream &os ) const;

// ...

А так выглядит объявление:

};

Чтобы реализация виртуальной функции в производном классе замещала реализацию из базового, прототипы функций обязаны совпадать. Например, если бы мы опустили слово const или  объявили  еще  один  параметр,  то  реализация  print() в  NameQuery не заместила  бы  реализацию  из  базового  класса.  Возвращаемые  значения  также  должны

3   Увы!   Правые   скобки   не   распознаются,   пока   OrQuery   не   выведет   все ассоциированное с ним частичное решение.

 

быть одинаковыми за одним исключением: значение, возвращенное реализацией в производном  классе,  может  принадлежать  к типу  класса,  который  открыто  наследует классу значения, возвращаемого реализацией в базовом классе. Если бы реализация из базового класса возвращала значение типа Query*, то реализация из производного могла бы возвращать NameQuery*. (Позже при работе с функцией clone() мы покажем, зачем

class NotQuery : public Query {

public:

virtual ostream& print( ostream &os ) const;

// ...

это нужно.) Вот объявление и реализация print() в NotQuery:

ostream& NotQuery::

print( ostream &os ) const

{

os << " ! ";

if ( _lparen )

print_lparen( _lparen, os );

_op->print( os );

if ( _rparen )

print_rparen( _rparen, os );

return os;

};

}

Разумеется, вызов print() через _op – виртуальный.

Объявления  и  реализации  этой  функции  в  классах  AndQuery и  OrQuery практически

class AndQuery : public Query {

public:

virtual ostream& print( ostream &os ) const;

// ...

дублируют друг друга. Поэтому приведем их только для AndQuery:

};

 

ostream& AndQuery::

print( ostream &os ) const

{

if ( _lparen )

print_lparen( _lparen, os );

_lop->print( os );

os << " && ";

_rop->print( os );

if ( _rparen )

print_rparen( _rparen, os );

return os;

}

Такая реализация виртуальной функции print() позволяет вывести любой подтип Query

cout << "Был сформулирован запрос "; Query *pq = retrieveQuery();

в поток класса ostream или любого другого, производного от него:

pq->print( cout );

Однако   такой  возможности   недостаточно.   Еще  нужно  уметь  распечатывать   любой производный  от  Query тип,  который  уже  есть  или  может  появиться  в  будущем,  с

Query *pq = retrieveQuery();

cout << "В ответ на запрос "

<< *pq

помощью оператора вывода из библиотеки iostream:

<< " получены следующие результаты: ";

Мы не можем непосредственно предоставить виртуальный  оператор вывода, поскольку они являются  членами класса ostream.  Вместо этого мы должны написать косвенную

inline ostream&

operator<<( ostream &os, const Query &q )

{

// виртуальный вызов print()

return q.print( os );

виртуальную функцию:

}

AndQuery query;

// сформулировать запрос ...

Строки

 

cout << query << endl;

вызывают наш оператор вывода в ostream, который в свою очередь вызывает

q.print( os )

где q привязано к объекту query класса AndQuery, а os – к cout. Если бы вместо этого

NameQuery query2( "Salinger" );

мы написали:

cout << query2 << endl;

Query *pquery = retrieveQuery();

то была бы вызвана реализация print() из класса NameQuery. Обращение

cout << *pquery << endl;

приводит   к   вызову   той   функции   print(),   которая   ассоциирована   с   объектом,

адресуемым указателем pquery в данной точке выполнения программы.

17.5.2. Чисто виртуальные функции

С точки зрения кодирования основная задача, стоящая перед нами в связи с поддержкой пользовательских запросов, – это реализация зависимых от типа операций для каждого из возможных операторов. Для этого мы определили четыре конкретных типа классов: AndQuery,   OrQuery и   т.д.   Однако   с   точки   зрения   проектирования   наша   цель – инкапсулировать обработку каждого вида запроса, спрятать за не зависящим от типа интерфейсом. Это позволит построить ядро приложения, которое не потребует изменений при добавлении или удалении типов.

Чтобы добиться этого, определим абстрактный тип класса Query. При этом мы не будем программировать   разные   типы   пользовательских    запросов,   а   лишь   абстрактные

void doit_and_bedone( vector< Query* > *pvec )

{

vector<Query*>::iterator

it = pvec->begin(),

end_it = pvec->end();

for ( ; it != end_it; ++it )

{

Query *pq = *it;

cout << "обрабатывается " << *pq << endl;

pq->eval();

pq->display();

delete pq;

}

операции, применимые к ним:

}

 

Такое определение позволяет добавлять неограниченное число типов запросов без необходимости изменять или даже перекомпилировать ядро системы, но при условии, что открытый   интерфейс   нашего   абстрактного   базового   класса   Query достаточен   для поддержки новых запросов.

Проектируя открытый интерфейс Query, мы определим множество операций, достаточное для поддержки  всех  существующих  и будущих  типов  запросов,  хотя на практике нам вряд ли удастся это гарантировать. Предоставление общего интерфейса для тех запросов, о которых мы уже знаем, – вполне реальная задача, но любое заявление, претендующее на более широкую поддержку, следует рассматривать с долей скептицизма.

Поскольку Query – абстрактный класс, объекты которого в приложении не создаются, то никакой разумной реализации виртуальных функций в нем самом мы предложить не можем. Это лишь названия, которые должны быть замещены в производных классах. Напрямую вызывать их мы не будем.

Язык обладает синтаксической конструкцией, обозначающей, что некоторая виртуальная функция   предоставляет   интерфейс,   который   должен  быть   замещен   в  производных подтипах, но вызываться непосредственно  не может. Это чисто виртуальные функции.

class Query {

public:

// объявляется чисто виртуальная функция

virtual ostream& print( ostream&=cout ) const = 0;

// ...

Объявляются они следующим образом:

};

Заметьте, что за объявлением функции следует присваивание нуля.

Класс, содержащий (или наследующий) одну или несколько таких функций, распознается компилятором как абстрактный базовый класс. Попытка создать независимый объект абстрактного  класса  приводит  к ошибке компиляции. (Ошибкой является также вызов

// В классе Query объявлены одна или несколько виртуальных функций,

// поэтому программист не может создавать независимые объекты

// класса Query

// правильно: подобъект Query в составе NameQuery

Query *pq = new NameQuery( "Nostromo" );

// ошибка: оператор new создает объект класса Query

чисто виртуальной функции с помощью механизма виртуализации.) Например:

Query *pq2 = new Query;

Абстрактный базовый класс может существовать только как подобъект в составе объекта некоторого производного от него класса. Это именно та семантика, которая нужна нам для базового Query.

 

17.5.3. Статический вызов виртуальной функции

Вызывая виртуальную функцию с помощью оператора разрешения области видимости класса, мы отменяем механизм виртуализации и разрешаем вызов статически, на этапе компиляции. Предположим, что мы определили виртуальную функцию isA() в базовом

Query *pquery = new NameQuery( "dumbo" );

// isA() вызывается динамически с помощью механизма виртуализации

// реально будет вызвана NameQuery::isA()

pquery->isA();

// isA вызывается статически во время компиляции

// реально будет вызвана Query::isA

и каждом из производных классов иерархии Query:

pquery->Query::isA();

Тогда явный вызов Query::isA() разрешается на этапе компиляции в пользу реализации

isA() в базовом классе Query, хотя pquery адресует объект NameQuery.

Зачем нужно отменять механизм виртуализации? Как правило, ради эффективности. В теле виртуальной функции производного класса часто необходимо вызвать реализацию из базового, чтобы завершить операцию, расщепленную между базовым и производным классами. К примеру, вполне вероятно, что виртуальная функция display() из Camera выводит  некоторую  информацию,  общую  для  всех  камер,  а  реализация  display() в классе  PerspectiveCamera сообщает  информацию,  специфичную  только  для перспективных камер. Вместо того чтобы дублировать в ней действия, общие для всех камер, можно вызвать реализацию из класса Camera. Мы точно знаем, какая именно реализация нам нужна, поэтому нет нужды прибегать к механизму виртуализации. Более того,   реализация   в   Camera объявлена   встроенной,   так  что   разрешение   во   время компиляции приводит к подстановке по месту вызова.

Приведем еще один пример, когда отмена механизма виртуализации может оказаться полезной,   а  заодно  познакомимся   с  неким  аспектом   чисто  виртуальных   функций, который начинающим программистам кажется противоречащим интуиции.

Реализации функции print() в классах AndQuery и OrQuery совпадают во всем, кроме литеральной   строки,   представляющей   название   оператора.   Реализуем   только   одну функцию, которую можно вызывать из данных классов. Для этого мы снова определим абстрактный  базовый  BinaryQuery (его  наследники –  AndQuery и  OrQuery).  В  нем определены два операнда и еще один член типа string для хранения значения оператора. Поскольку это абстрактный класс, объявим print() чисто виртуальной функцией:

 

class BinaryQuery : public Query {

public:

BinaryQuery( Query *lop, Query *rop, string oper )

: _lop(lop), _rop(rop), _oper(oper) {}

~BinaryQuery() { delete _lop; delete _rop; }

ostream &print( ostream&=cout, ) const = 0;

protected:

Query *_lop;

Query *_rop;

string _oper;

};

Вот  как  реализована  в  BinaryQuery функция  print(),  которая  будет  вызываться  из

inline ostream& BinaryQuery::

print( ostream &os ) const

{

if ( _lparen )

print_lparen( _lparen, os );

_lop->print( os );

os << ' ' << _oper << ' ';

_rop->print( os );

if ( _rparen )

print_rparen( _rparen, os );

return os;

производных классов AndQuery и OrQuery:

}

Похоже, мы попали в парадоксальную ситуацию. С одной стороны, необходимо объявить этот  экземпляр  print() как  чисто  виртуальную  функцию,  чтобы  компилятор воспринимал   BinaryQuery как   абстрактный   базовый   класс.   Тогда   в   приложении определить независимые объекты BinaryQuery будет невозможно.

С  другой  стороны,  нужно  определить  в  классе  BinaryQuery виртуальную  функцию

print() и уметь вызывать ее через объекты AndQuery и OrQuery.

Но как  часто  бывает  с кажущимися  парадоксами,  мы  не учли одного обстоятельства:

чисто виртуальную функцию нельзя вызывать с помощью механизма виртуализации, но

inline ostream& AndQuery::

print( ostream &os ) const

{

// правильно: подавить механизм виртуализации

// вызвать BinaryQuery::print статически

BinaryQuery::print( os );

можно вызывать статически:

}

 

17.5.4. Виртуальные функции и аргументы по умолчанию

#include <iostream>

class base {

public:

virtual int foo( int ival = 1024 ) {

cout << "base::foo() -- ival: " << ival << endl;

return ival;

}

// ...

};

class derived : public base {

public:

virtual int foo( int ival = 2048 ) {

cout << "derived::foo() -- ival: " << ival << endl;

return ival;

}

// ...

Рассмотрим следующую простую иерархию классов:

};

Проектировщик  класса  хотел,  чтобы  при вызове без параметров  реализации  foo() из

base b;

base *pb = &b;

// вызывается base::foo( int )

// предполагалось, что будет возвращено 1024

базового класса по умолчанию передавался аргумент 1024:

pb->foo();

Кроме того, разработчик хотел, чтобы при вызове его реализации foo() без параметров

derived d;

base *pb = &d;

// вызывается derived::foo( int )

// предполагалось, что будет возвращено 2048

использовался аргумент по умолчанию 2048:

pb->foo();

Однако  в  C++  принята  другая  семантика  механизма  виртуализации.  Вот  небольшая программа для тестирования нашей иерархии классов:

 

int main()

{

derived *pd = new derived;

base *pb = pd;

int val = pb->foo();

cout << "main() : val через base: "

<< val << endl;

val = pd->foo();

cout << "main() : val через derived: "

<< val << endl;

}

После компиляции и запуска программа выводит следующую информацию:

derived::foo() -- ival: 1024 main() : val через base: 1024 derived::foo() -- ival: 2048 main() : val через derived: 2048

При обоих обращениях реализация foo() из производного класса вызывается корректно, поскольку  фактически  вызываемый  экземпляр  определяется  во  время  выполнения  на основе  типа   класса,   адресуемого   pd и   pb.  Но  передаваемый   foo() аргумент   по умолчанию определяется не во время выполнения, а во время компиляции на основе типа объекта,  через  который  вызывается  функция.  При вызове foo() через pb аргумент  по умолчанию  извлекается  из  объявления  base::foo() и  равен  1024.  Если  же  foo() вызывается через pd, то аргумент по умолчанию извлекается из объявления derived::foo() и равен 2048.

Если  реализации  из  производного  класса  при  вызове  через  указатель  или  ссылку  на базовый класс по умолчанию передается аргумент, указанный в базовом классе, то зачем задавать аргумент по умолчанию для реализации из производного класса?

Нам могут понадобиться различные аргументы по умолчанию в зависимости не от реализации  foo() в конкретном  производном  классе, а от типа указателя или ссылки, через которые функция вызвана. Например, значения 1024 и 2048 – это размеры изображений.  Когда  нужно  получить  менее  детальное  изображение,  вызываем  foo() через класс base, а когда более детальное – через derived.

Но если мы все-таки хотим, чтобы аргумент по умолчанию, передаваемый foo(), зависел от фактически вызванного экземпляра? К сожалению, механизм виртуализации такую возможность не поддерживает. Однако разрешается задать такой аргумент по умолчанию, который  для  вызванной   функции  означает,  что  пользователь  не  передал  никакого значения.  Тогда  реальное  значение,  которое  функция  хотела  бы  видеть  в  качестве аргумента  по  умолчанию,  объявляется  локальной  переменной  и  используется,  если ничего другого не передано:

 

void base::

foo( int ival = base_default_value )

{

int real_default_value = 1024;            // настоящее значение по умолчанию

if ( ival == base_default_value )

ival = real_default_value;

// ...

}

Здесь base_default_value – значение, согласованное между всеми классами иерархии,

которое   явно   говорит   о   том,   что   пользователь   не   передал   никакого   аргумента.

void derived::

foo( int ival = base_default_value )

{

int real_default_value = 2048;

if ( ival == base_default_value )

ival = real_default_value;

// ...

Производный класс может быть реализован аналогично:

}

17.5.5. Виртуальные деструкторы

void doit_and_bedone( vector< Query* > *pvec )

{

// ...

for ( ; it != end_it; ++it )

{

Query *pq = *it;

// ... delete pq;

}

В данной функции мы применяем оператор delete:

}

Чтобы   функция   выполнялась   правильно,    применение   delete должно   вызывать деструктор того класса, на который указывает pq. Следовательно, необходимо объявить деструктор Query виртуальным:

 

class Query {

public:

virtual ~Query() { delete _solution; }

// ...

};

Деструкторы  всех  производных  от  Query классов  автоматически  считаются виртуальными. doit_and_bedone() выполняется правильно.

Поведение деструктора при наследовании таково: сначала вызывается деструктор производного  класса, в случае pq – виртуальная функция. По завершении  вызывается деструктор  непосредственного  базового класса – статически.  Если деструктор  объявлен встроенным, то в точке вызова производится подстановка. Например, если pq указывает на объект класса AndQuery, то

delete pq;

приводит  к  вызову  деструктора  класса  AndQuery за  счет  механизма  виртуализации. После   этого   статически   вызывается   деструктор   BinaryObject,   а   затем –   снова статически – деструктор Query.

class Query { public: // ... protected:

virtual ~Query();

// ...

};

class NotQuery : public Query {

public:

~NotQuery();

// ...

В следующей иерархии классов

};

уровень доступа к конструктору NotQuery открытый при вызове через объект NotQuery, но  защищенный –  при  вызове  через  указатель  или  ссылку  на  объект  Query.  Таким образом, виртуальная функция подразумевает уровень доступа того класса, через объект

int main()

{

Query *pq = new NotQuery;

// ошибка: деструктор является защищенным

delete pq;

которого вызывается:

}

 

Эвристическое правило: если в корневом базовом классе иерархии объявлены одна или несколько виртуальных функций, рекомендуем объявлять таковым и деструктор. Однако, в отличие от конструктора базового класса, его деструктор не стоит делать защищенным.

17.5.6. Виртуальная функция eval()

В основе иерархии классов Query лежит виртуальная функция eval() (но с точки зрения возможностей   языка  она  наименее  интересна).  Как  и  для  других  функций-членов, разумной реализации eval() в абстрактном классе Query нет, поэтому мы объявляем ее

class Query {

public:

virtual void eval() = 0;

// ...

чисто виртуальной:

};

Реальное разрешение имени eval() происходит  при  построении  отображения  слов  на вектор позиций. Если слово есть в тексте, то в отображении будет его вектор позиций. В нашей реализации вектор позиций, если он имеется, передается конструктору NameQuery вместе с самим словом. Поэтому в классе NameQuery функция eval() пуста.

Однако  мы  не  можем  унаследовать  чисто  виртуальную  функцию  из  Query.  Почему? Потому что NameQuery – это конкретный класс, объекты которого разрешается создавать в приложении. Если бы мы унаследовали чисто виртуальную функцию, то он стал бы абстрактным  классом,  так что создать объект такого типа не удалось бы. Поэтому мы

class NameQuery : public Query {

public:

virtual void eval() {}

// ...

объявим eval() пустой функцией:

};

Для запроса NotQuery отыскиваются все строки текста, где указанное слово отсутствует. Для таких строк в член _loc класса NotQuery помещаются все пары (строка, колонка). Наша реализация выглядит следующим образом:

 

void NotQuery::eval()

{

// вычислим операнд

_op->eval();

// _all_locs - это вектор, содержащий начальные позиции всех слов,

// он является статическим членом NotQuery:

// static const vector<locations>* _all_locs vector< location >::const_iterator

iter = _all_locs->begin(), iter_end = _all_locs->end();

// получить множество строк, в которых операнд встречается

set<short> *ps = _vec2set( _op->locations() );

// для каждой строки, где операнд не найден,

// скопировать все позиции в _loc

for ( ; iter != iter_end; ++iter )

{

if ( ! ps->count( (*iter).first )) {

_loc.push_back( *iter );

}

}

}

Ниже приводится трассировка выполнения запроса NotQuery. Операнд встречается в 0, 3 и  5  строках   текста.   (Напомним,   что  внутри  программы   строки  текста  в  векторе нумеруются  с  0;  а  когда  мы  предъявляем  строки  пользователю,  мы  нумеруем  их  с единицы.) Поэтому при вычислении ответа создается вектор, содержащий начальные позиции слов в строках 1,2 и 4. (Мы отредактировали вектор позиций, чтобы он занимал меньше места.)

==> ! daddy

daddy ( 3 ) lines match

display_location_vector:

first: 0 second: 8

first: 3 second: 3

first: 5 second: 5

! daddy ( 3 ) lines match

display_location_vector:

first: 1 second: 0

first: 1 second: 1

first: 1 second: 2

...

first: 1 second: 10

first: 2 second: 0

first: 2 second: 1

...

first: 2 second: 12

first: 4 second: 0

first: 4 second: 1

...

first: 4 second: 12

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.

При обработке запроса OrQuery векторы позиций обоих операндов объединяются. Для этого  применяется  обобщенный  алгоритм  merge().  Чтобы  merge() мог  упорядочить

 

пары   (строка,   колонка),   мы  определяем   объект-функцию   для  их  сравнения.   Ниже

class less_than_pair {

public:

bool operator()( location loc1, location loc2 )

{

return (( loc1.first < loc2.first ) ||

( loc1.first == loc2.first ) && ( loc1.second < loc2.second ));

}

};

void OrQuery::eval()

{

// вычислить левый и правый операнды

_lop->eval();

_rop->eval();

// подготовиться к объединению двух векторов позиций

vector< location, allocator >::const_iterator riter = _rop->locations()->begin(),

liter = _lop->locations()->begin(),

riter_end = _rop->locations()->end(), liter_end = _lop->locations()->end();

merge( liter, liter_end, riter, riter_end, inserter( _loc, _loc.begin() ), less_than_pair() );

приведена наша реализация:

}

А вот трассировка выполнения запроса OrQuery, в которой мы выводим вектор позиций каждого из двух операндов и результат их объединения. (Напомним еще раз, что для пользователя строки нумеруются с 1, а внутри программы – с 0.)

==> fiery || untamed fiery ( 1 ) lines match display_location vector:

first: 2          second: 2 first: 2          second: 8

untamed ( 1 ) lines match display_location vector:

first: 3          second: 2

fiery || untamed ( 2 ) lines match display_location vector:

first: 2          second: 2 first: 2          second: 8 first: 3          second: 2

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,"

При обработке запроса AndQuery мы обходим векторы позиций обоих операндов и ищем соседние слова. Каждая найденная пара вставляется в вектор _loc. Основная трудность связана с тем, что эти векторы нужно просматривать синхронно, чтобы можно было установить соседство слов.

 

void AndQuery::eval()

{

// вычислить левый и правый операнды

_lop->eval();

_rop->eval();

// установить итераторы

vector< location, allocator >::const_iterator riter = _rop->locations()->begin(),

liter = _lop->locations()->begin(), riter_end = _rop->locations()->end(), liter_end = _lop->locations()->end();

// продолжать цикл, пока есть что сравнивать

while ( liter != liter_end &&

riter != riter_end )

{

// пока номер строки в левом векторе больше, чем в правом

while ( (*liter).first > (*riter).first )

{

++riter;

if ( riter == riter_end ) return;

}

// пока номер строки в левом векторе меньше, чем в правом

while ( (*liter).first < (*riter).first )

{

// если соответствие найдено для последнего слова

// в одной строке и первого слова в следующей

// _max_col идентифицирует последнее слово в строке

if ( ((*liter).first == (*riter).first-1 ) &&

((*riter).second == 0 ) &&

((*liter).second == (*_max_col)[ (*liter).first ] ))

{

_loc.push_back( *liter );

_loc.push_back( *riter );

++riter;

if ( riter == riter_end ) return;

}

++liter;

if ( liter == liter_end ) return;

}

// пока оба в одной и той же строке

while ( (*liter).first == (*riter).first )

{

if ( (*liter).second+1 == ((*riter).second) )

{ // соседние слова

_loc.push_back( *liter ); ++liter;

_loc.push_back( *riter ); ++riter;

}

else

if ( (*liter).second <= (*riter).second )

++liter;

else ++riter;

if ( liter == liter_end || riter == riter_end )

return;

}

}

}

 

А  так  выглядит  трассировка  выполнения  запроса  AndQuery,  в  которой  мы  выводим векторы позиций обоих операндов и результирующий вектор:

==> fiery && bird

fiery ( 1 ) lines match

display_location vector:

first: 2 second: 2

first: 2 second: 8

bird ( 1 ) lines match

display_location vector:

first: 2 second: 3

first: 2 second: 9

fiery && bird ( 1 ) lines match

display_location vector:

first: 2 second: 2

first: 2 second: 3

first: 2 second: 8

first: 2 second: 9

Requested query: fiery && bird

( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,

Приведем трассировку выполнения составного запроса, включающего как И, так и ИЛИ.

Показаны векторы позиций каждого операнда, а также результирующий вектор:

==> fiery && ( bird || untamed ) fiery ( 1 ) lines match display_location vector:

first: 2           second: 3 first: 2           second: 8

bird ( 1 ) lines match

display_location vector:

first: 2           second: 3

first: 2           second: 9

untamed ( 1 ) lines match

display_location vector:

first: 3          second: 2

( bird || untamed ) ( 2 ) lines match display_location vector:

first: 2           second: 3 first: 2           second: 9 first: 3           second: 2

fiery && ( bird || untamed ) ( 1 ) lines match display_location vector:

first: 2           second: 2 first: 2           second: 3

first: 2           second: 8 first: 2           second: 9

Requested query: fiery && ( bird || untamed )

( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,

17.5.7. Почти виртуальный оператор new

Если  дан  указатель  на  один  из  конкретных  подтипов  запроса,  то  разместить  в  хипе

NotQuery *pnq;

// установить pnq ...

// оператор new вызывает

// копирующий конструктор NotQuery ...

дубликат объекта несложно:

NotQuery *pnq2 = new NotQuery( *pnq );

 

Если  же у нас есть только указатель на абстрактный класс Query, то задача  создания

const Query *pq = pnq->op();

дубликата становится куда менее тривиальной:

// как получить дубликат pq?

Если бы позволялось объявить виртуальный экземпляр оператора new, то проблема была бы решена,  поскольку автоматически  вызывался  бы нужный экземпляр. К сожалению, это  невозможно:  new –  статическая  функция-член,  которая  применяется  к неструктурированной памяти еще до конструирования объекта класса (см. раздел 15.8).

Но хотя оператор  new нельзя сделать  виртуальным,  разрешается  создать  его суррогат,

class Query {

public:

virtual Query *clone() = 0;

// ...

который будет выделять память из хипа и копировать туда объекты, – clone():

};

class NameQuery : public Query {

public:

virtual Query *clone()

// вызывается копирующий конструктор класса NameQuery

{ return new NameQuery( *this ); }

// ...

Вот как он может быть реализован в классе NameQuery:

};

Query *pq = new NameQuery( "valery" );

Это работает правильно, если тип целевого указателя Query*:

Query *pq2 = pq->clone();

Если  же  его  тип  равен  NameQuery*,  нужно  привести  возвращенный  указатель  типа

NameQuery *pnq = new NameQuery( "Rilke" ); NameQuery *pnq2 =

Query* назад к типу NameQuery*:

static_cast<NameQuery*>( pnq->clone() );

(Причина, по которой необходимо преобразование типа, объясняется в разделе 19.1.1.)

 

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

class NameQuery : public Query {

public:

virtual NameQuery *clone()

{ return new NameQuery( *this ); }

// ...

открытым типом наследования (то же относится к ссылкам и указателям):

};

// Query *pq = new NameQuery( "Broch" ); Query *pq2 = pq->clone();       // правильно

// NameQuery *pnq = new NameQuery( "Rilke" );

Теперь pq2 и pnq2 можно инициализировать без явного приведения типов:

NameQuery *pnq2 = pnq->clone();    // правильно

class NotQuery : public Query {

public:

virtual NotQuery *clone()

{ return new NotQuery( *this ); }

// ...

Так выглядит реализация clone() в классе NotQuery:

};

Реализации в AndQuery и OrQuery аналогичны. Чтобы эти реализации clone() работали правильно,  в  классах  NotQuery,  AndQuery и  OrQuery должны  быть  явно  определены копирующие конструкторы. (Мы займемся этим в разделе 17.6.)

17.5.8. Виртуальные функции, конструкторы и деструкторы

Как мы видели в разделе 17.4, для объекта производного класса сначала вызывается конструктор базового, а затем производного класса. Например, при таком определении объекта NameQuery

NameQuery poet( "Orlen" );

сначала будет вызван конструктор Query, а потом NameQuery.

 

При выполнении  конструктора  базового класса Query часть объекта,  соответствующая классу  NameQuery,  остается  неинициализированной.  По  существу,  poet –  это  еще  не объект NameQuery, сконструирован лишь его подобъект.

Что должно происходить, если внутри конструктора базового класса вызывается виртуальная  функция,  реализации  которой  существуют как в базовом, так и в производном классах? Какая из них должна быть вызвана? Результат вызова реализации из производного класса в случае, когда необходим доступ к его членам, оказался бы неопределенным. Вероятно, выполнение программы закончилось бы крахом.

Чтобы этого не случилось, в конструкторе базового класса всегда вызывается реализация виртуальной функции, определенная именно в базовом. Иными словами, внутри такого конструктора объект производного класса рассматривается как имеющий тип базового.

То же самое справедливо и внутри деструктора базового класса, вызываемого для объекта производного. И в этом случае часть объекта, относящаяся к производному классу, не определена: не потому, что еще не сконструирована, а потому, что уже уничтожена.

Упражнение 17.12

Внутри объекта NameQuery естественное внутреннее представление вектора позиций – это указатель, который инициализируется указателем, хранящимся в отображении слов. Оно же является и наиболее эффективным, так как нам нужно скопировать лишь один адрес, а не  каждую  пару  координат.  Классы  AndQuery,  OrQuery и  NotQuery должны конструировать собственные векторы позиций на основе вычисления своих операндов. Когда время жизни объекта любого из этих классов завершается, ассоциированный с ним вектор позиций необходимо удалить. Когда же заканчивается время жизни объекта NameQuery, вектор позиций удалять не следует. Как сделать так, чтобы вектор позиций был  представлен  указателем  в  базовом  классе  Query и  при  этом  его экземпляры  для объектов AndQuery, OrQuery и NotQuery удалялись,  а для объектов NameQuery – нет? (Заметим,  что  нам  не  разрешается  добавить  в  класс  Query признак,  показывающий, нужно ли применять оператор delete к вектору позиций!)

Упражнение 17.13

class AbstractObject {

public:

~AbstractObject();

virtual void doit() = 0;

// ...

Что неправильно в приведенном определении класса:

};

Упражнение 17.14

NameQuery nq( "Sneezy" ); Query q( nq );

Даны такие определения:

Query *pq = &nq;

Почему в инструкции

 

pq->eval();

вызывается экземпляр eval() из класса NameQuery, а в инструкции

q.eval();

экземпляр из Query?

Упражнение 17.15

(a) Base* Base::copy( Base* );

Какие из повторных объявлений виртуальных функций в классе Derived неправильны:

(b) Base* Base::copy( Base* );

Base* Derived::copy( Derived* );

(c) ostream& Base::print( int, ostream&=cout );

Derived* Derived::copy( Vase* );

(d) void Base::eval() const;

ostream& Derived::print( int, ostream& );

void Derived::eval();

Упражнение 17.16

Маловероятно, что наша программа заработает при первом же запуске и в первый раз, когда  прогоняется  с реальными  данными.  Средства  отладки  полезно включать уже на этапе проектирования классов. Реализуйте в нашей иерархии классов Query виртуальную функцию  debug(),  которая  будет  отображать  члены  соответствующих  классов. Поддержите управление уровнем детализации двумя способами: с помощью аргумента, передаваемого функции debug(), и с помощью члена класса. (Последнее позволяет включать или отключать выдачу отладочной информации в отдельных объектах.)

Упражнение 17.17

Найдите ошибку в следующей иерархии классов:

 

class Object {

public:

virtual void doit() = 0;

// ...

protected:

virtual ~Object();

};

class MyObject : public Object {

public:

MyObject( string isA );

string isA() const;

protected:

string _isA;

};

17.6. Почленная инициализация и присваивание  A

При проектировании класса мы должны позаботиться о том, чтобы почленная инициализация (см. раздел 14.6) и почленное присваивание (см. раздел 14.7) были реализованы  правильно  и  эффективно.  Рассмотрим  связь  этих  операций  с наследованием.

До сих пор мы не занимались явной обработкой почленной инициализации. Посмотрим,

что происходит в нашей иерархии классов Query по умолчанию.

class Query { public: // ... protected:

int _paren;

set<short> *_solition;

vector<location> _loc;

// ...

В абстрактном базовом классе Query определены три нестатических члена:

};

Член _solution, если он установлен, адресует множество, память для которого выделена в   хипе  функцией-членом   _vec2set().   Деструктор   Query применяет   к  _solution оператор delete.

Класс Query должен  предоставлять  как явный копирующий  конструктор, так и явный копирующий  оператор  присваивания.  (Если  вам  это    непонятно,  перечитайте  раздел

14.6.) Но сначала посмотрим, как почленное копирование по умолчанию происходит без них.

Производный класс NameQuery содержит объект-член типа string и подобъект базового

Query. Если есть объект folk класса NameQuery:

NameQuery folk( "folk" );

то инициализация music с помощью folk

 

NameQuery music = folk;

осуществляется так:

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

2.   Далее компилятор  проверяет,  содержит  ли объект  NameQuery подобъекты  базового класса. (Да, в нем имеется подобъект Query.)

3.  Компилятор  проверяет,  определен  ли  в  классе  Query явный  копирующий конструктор. (Нет, поэтому компилятор применит почленную инициализацию по умолчанию.)

4.   Компилятор проверяет, содержит ли объект Query подобъекты базового класса. (Нет.)

5.   Компилятор просматривает все нестатические члены Query в порядке их объявления. (Если  некоторый   член  не  является  объектом  класса,  как,  например,  _paren и

_solution,  то  в  объекте  music он  инициализируется  соответствующим  членом объекта   folk.   Если   же   является,   как,   скажем,   _loc,   то   к   нему   рекурсивно применяется шаг 1. В классе vector определен копирующий конструктор, который вызывается для инициализации music._loc с помощью folk._loc.)

6.   Далее  компилятор  рассматривает  нестатические  члены  NameQuery в  порядке  их объявления  и  находит  объект  класса  string,  где есть  явный  копирующий конструктор.   Он   и   вызывается   для   инициализации   music._name с   помощью folk._name.

Инициализация по умолчанию music с помощью folk завершена. Она хороша во всех отношениях, кроме одного: если разрешить копирование по умолчанию члена _solution, то программа, скорее всего, завершится аварийно. Поэтому вместо такой обработки мы предоставим   явный   копирующий    конструктор   класса   Query.   Можно,   например,

Query::Query( const Query &rhs )

: _loc( rhs._loc ), _paren(rhs._paren)

{

if ( rhs._solution )

{

_solution = new set<short>;

set<short>::iterator

it = rhs._solution->begin(),

end_it = rhs._solution->end();

for ( ; _ir != end_it; ++it )

_solution->insert( *it );

}

else _solution = 0;

скопировать все разрешающее множество:

}

Однако, поскольку в нашей реализации разрешающее множество вычисляется по мере необходимости, копировать его сразу нет нужды. Назначение нашего копирующего конструктора –   предотвратить   копирование   по   умолчанию.   Для   этого   достаточно инициализировать _solution нулем:

 

Query::Query( const Query &rhs )

: _loc( rhs._loc ),

_paren(rhs._paren), _solution( 0 )

{}

Шаги 1 и 2 инициализации musiс c помощью folk те же, что и раньше. Но на шаге 3 компилятор обнаруживает,  что в классе Query есть явный копирующий  конструктор и вызывает его. Шаги 4 и 5 пропускаются, а шаг 6 выполняется, как и прежде.

На этот раз почленная инициализация music с помощью folk корректна. Реализовывать явный копирующий конструктор в NameQuery нет необходимости.

Объект производного класса NotQuery содержит подобъект базового Query и член _op типа Query*, который указывает на операнд, размещенный в хипе. Деструктор NotQuery применяет к этому операнду оператор delete.

Для класса NotQuery почленная инициализация по умолчанию члена _op небезопасна,

поэтому  необходим  явный  копирующий  конструктор.  В  его  реализации  используется

inline NotQuery::

NotQuery( const NotQuery &rhs )

// вызывается Query::Query( const Query &rhs )

: Query( rhs )

виртуальная функция clone(), которую мы определили в предыдущем разделе.

{ _op = rhs._op->clone(); }

При почленной  инициализации  одного объекта  класса  NotQuery другим выполняются два шага:

1.   Компилятор  проверяет,  определен ли в NotQuery явный копирующий  конструктор.

Да, определен.

2.   Этот конструктор вызывается для почленной инициализации.

Вот и все. Ответственность за правильную инициализацию подобъекта базового класса и нестатических членов возлагается на копирующий конструктор NotQuery. (Классы AndQuery и   OrQuery сходны   с   NotQuery,   поэтому   мы  оставляем   их   в   качестве упражнения для читателей.)

Почленное присваивание аналогично почленной инициализации. Если имеется явный копирующий оператор присваивания, то он вызывается для выполнения присваивания одного  объекта  класса  другому.  В  противном  случае  применяется  почленное присваивание по умолчанию.

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

Просматриваются  все  нестатические  члены  в  порядке  их  объявления.  Если  член  не является  объектом  класса,  то  его  значение  справа  от  знака  равенства  копируется  в значение  соответствующего  члена  слева  от  знака  равенства.  Если  же  член  является объектом класса, в котором определен явный копирующий оператор присваивания, то он и   вызывается.   В   противном   случае   к   базовым   классам   и   членам   объекта-члена применяется почленное присваивание по умолчанию.

 

Вот как выглядит копирующий оператор присваивания для нашего объекта Query. Еще раз  отметим,  что  в  этом  месте  необязательно  копировать  разрешающее  множество,

Query& Query::

operator=( const Query &rhs )

{

// предотвратить присваивание самому себе

if ( &rhs != this )

{

_paren = rhs._paren;

_loc = rhs._loc;

delete _solution;

_solution = 0;

}

return *this;

достаточно предотвратить копирование по умолчанию:

};

В классе NameQuery явный копирующий оператор присваивания не нужен. Присваивание одного объекта NameQuery другому выполняется в два шага:

1.   Для присваивания  подобъектов  Query двух объектов NameQuery вызывается явный копирующий оператор присваивания класса Query.

2.   Для   присваивания   членов   string вызывается   явный   копирующий   оператор присваивания этого класса.

Для объектов NameQuery вполне достаточно почленного присваивания по умолчанию.

В  каждом  из  классов  NotQuery,  AndQuery и  OrQuery для  безопасного  копирования операндов требуется явный копирующий оператор присваивания. Вот его реализация для

inline NotQuery& NotQuery::

operator=( const NotQuery &rhs )

{

// предотвратить присваивание самому себе

if ( &rhs != this )

{

// вызвать копирующий оператор присваивания Query this->Query::operator=( rhs );

// скопировать операнд

_op = rhs._op->clone();

}

return *this;

NotQuery:

}

В отличие от копирующего конструктора, в копирующем операторе присваивания нет специальной  части,  через  которую  вызывается  аналогичный  оператор базового класса. Для этого используются две синтаксических конструкции: явный вызов, продемонстрированный выше, и явное приведение типа, как в следующем примере:

 

(*static_cast<Query*>(this)) = rhs;

(Реализация  копирующих  операторов  присваивания  в  классах  AndQuery и  OrQuery

выглядит так же, поэтому мы оставим ее в качестве упражнения.)

Ниже  предложена  небольшая  программа  для  тестирования  данной  реализации.  Мы

#include "Query.h"

int main()

{

NameQuery nm( "alice" ); NameQuery nm( "emma" );

NotQuery nq1( &nm );

cout << "notQuery 1: " << nq1 << endl;

NotQuery nq2( nq1 );

cout << "notQuery 2: " << nq2 << endl;

NotQuery nq3( &nm2 );

cout << "notQuery 3: " << nq3 << endl;

nq3 = nq2;

cout << "notQuery 3 присвоено значение nq2: " << nq3 << endl;

AndQuery aq( &nq1, &nm2 );

cout << "AndQuery : " << aq << endl;

AndQuery aq2( aq );

cout << "AndQuery 2: " << aq2 << endl;

AndQuery aq3( &nm, &nm2 );

cout << "AndQuery 3: " << aq3 << endl;

aq2 = aq3;

cout << "AndQuery 2 после присваивания: " << aq2 << endl;

создаем или копируем объект, а затем распечатываем его.

}

После компиляции и запуска программа печатает следующее:

notQuery 1:  ! alice notQuery 2:  ! alice notQuery 3:  ! emma

notQuery 3 присвоено значение nq2:  ! alice

AndQuery :  ! alice && emma

AndQuery 2:  ! alice && emma

AndQuery 3:  alice && emma

AndQuery 2 после присваивания:  alice && emma

Упражнение 17.18

Реализуйте копирующие конструкторы в классах AndQuery и OrQuery.

Упражнение 17.19

Реализуйте копирующие операторы присваивания в классах AndQuery и OrQuery.

Упражнение 17.20

 

Что   указывает   на   необходимость   реализации   явных   копирующего   конструктора   и копирующего оператора присваивания?

17.7. Управляющий класс UserQuery

Если имеется запрос такого типа:

fiery && ( bird || potato )

AndQuery

NameQuery( "fiery" )

OrQuery

NameQuery( "bird" )

то в нашу задачу входит построение эквивалентной иерархии классов:

NameQuery( "potato" )

Как лучше всего это сделать? Процедура вычисления ответа на запрос напоминает функционирование   конечного  автомата.   Мы  начинаем  с  пустого  состояния  и  при обработке каждого элемента запроса переходим в новое состояние, пока весь запрос не будет  разобран.  В  основе  нашей  реализации  лежит  одна  инструкция  switch внутри операции,  которую  мы  назвали  eval_query().  Слова  запроса  считываются  одно  за другим из вектора строк и сравниваются с каждым из возможных значений:

 

vector<string>::iterator

it          = _query->begin(),

end_it = _query->end();

for ( ; it != end_it; ++it )

switch( evalQueryString( *it ))

{

case WORD:

evalWord( *it );

break;

case AND: evalAnd(); break;

case OR: evalOr(); break;

case NOT: evalNot(); break;

case LPAREN:

++_paren;

++_lparenOn;

break;

case RPAREN:

--_paren;

++_rparenOn;

evalRParen();

break;

}

Пять операций eval: evalWord(), evalAnd(), evalOr(), evalNot и evalRParen() – как раз и строят иерархию классов Query. Прежде чем обратиться к деталям их реализации, рассмотрим общую организацию программы.

Нам  нужно  определить  каждую  операцию  в  виде  отдельной  функции,  как  это  было сделано в главе 6 при построении процедур обработки запроса. Пользовательский запрос и   производные   от   Query классы   представляют   независимые   данные,   которыми оперируют  эти  функции.  От  такой  модели  программирования  (она  называется процедурной) мы предпочли отказаться.

В разделе 6.14 мы ввели класс TextQuery, где инкапсулировали операции и данные, изучавшиеся в главе 6. Здесь нам потребуется класс UserQuery, решающий аналогичные задачи.

Одним из членов этого класса должен быть вектор строк, содержащий сам запрос пользователя. Другой член – это указатель типа Query* на иерархическое представление запроса, построенное в eval_query(). Еще три члена служат для обработки скобок:

_paren помогает изменить подразумеваемый  порядок вычисления операторов  (чуть позже мы продемонстрируем это на примере);

_lparenOn и  _rparenOn содержат  счетчики  левых  и  правых  скобок, ассоциированные с текущим узлом дерева разбора запроса (мы показывали, как они используются, при обсуждении виртуальной функции print() в разделе 17.5.1).

 

Помимо этих пяти членов, нам понадобятся еще два. Рассмотрим следующий запрос:

fiery || untamed

OrQuery

NameQuery( "fiery" )

Наша цель – представить его в виде следующего объекта OrQuery:

NameQuery( "untamed" )

Однако порядок обработки такого запроса вызывает некоторые проблемы. Когда мы определяем объект NameQuery, объект OrQuery , к которому его надо добавить, еще не определен.  Поэтому  необходимо  место,  где  можно  временно  сохранить  объект NameQuery.

Чтобы сохранить что-либо для последующего использования, традиционно применяется стек.  Поместим  туда  наш  объект  NameQuery.  А  когда  позже  встретим  оператор  ИЛИ (объект  OrQuery),  то  достанем  NameQuery из  стека  и  присоединим  его  к  OrQuery в качестве левого операнда.

Объект  OrQuery неполон:  в  нем  не хватает  правого  операнда.  До тех  пор  пока  этот операнд не будет построен, работу с данным объектом придется прекратить.

Его  можно  поместить   в  тот  же  самый   стек,  что  и  NameQuery.   Однако   OrQuery представляет другое состояние обработки запроса: это неполный оператор. Поэтому мы определим  два  стека:  _query_stack для  хранения  объектов,  представляющих сконструированные операнды составного запроса (туда мы помещаем объект NameQuery), а  второй  для  хранения  неполных  операторов  с  отсутствующим  правым  операндом. Второй стек можно трактовать как место для хранения текущей операции, подлежащей завершению, поэтому назовем его _current_op. Сюда мы и поместим объект OrQuery. После того как второй объект NameQuery будет определен, мы достанем объект OrQuery из стека _current_op и добавим к нему NameQuery в качестве правого операнда. Теперь объект OrQuery завершен и мы можем поместить его в стек _query_stack.

Если  обработка  запроса  завершилась  нормально,  то стек _current_op пуст, а в стеке

_query_stack содержится  единственный  объект,  который  и  представляет  весь пользовательский запрос. В нашем случае это объект класса OrQuery.

Рассмотрим несколько примеров. Первый из них – простой запрос типа NotQuery:

! daddy

Ниже показана трассировка его обработки. Финальным объектом в стеке _query_stack

является объект класса NotQuery:

 

evalNot() : incomplete!

push on _current_op ( size == 1 )

evalWord() : daddy

pop _current_op : NotQuery

add operand: WordQuery : NotQuery complete!

push NotQuery on _query_stack

Текст, расположенный  с отступом  под функциями  eval, показывает,  как выполняется операция.

Во втором примере – составном запросе типа OrQuery – встречаются оба случая. Здесь же иллюстрируется помещение полного оператора в стек _query_stack:

==> fiery || untamed || shyly

evalWord() : fiery

push word on _query_stack

evalOr() : incomplete!

pop _query_stack : fiery

add operand : WordQuery : OrQuery incomplete!

push OrQuery on _current_op ( size == 1 )

evalWord() : untamed

pop _current_op : OrQuery

add operand : WordQuery : OrQuery complete!

push OrQuery on _query_stack evalOr() : incomplete!

pop _query_stack : OrQuery

add operand : OrQuery : OrQuery incomplete!

push OrQuery on _current_op ( size == 1 )

evalWord() : shyly

pop _current_op : OrQuery

add operand : WordQuery : OrQuery complete!

push OrQuery on _query_stack

В  последнем  примере  рассматривается   составной  запрос  и  применение  скобок  для изменения порядка вычислений:

==> fiery && ( bird || untamed )

evalWord() : fiery

push word on _query_stack

evalAnd() : incomplete!

pop _query_stack : fiery

add operand : WordQuery : AndQuery incomplete!

push AndQuery on _current_op ( size == 1 )

evalWord() : bird

_paren is set to 1

push word on _query_stack

evalOr() : incomplete!

pop _query_stack : bird

add operand : WordQuery : OrQuery incomplete!

push OrQuery on _current_op ( size == 2 )

evalWord() : untamed

pop _current_op : OrQuery

add operand : WordQuery : OrQuery complete!

push OrQuery on _query_stack

evalRParen() :

_paren: 0 _current_op.size(): 1

pop _query_stack : OrQuery

pop _current_op : AndQuery

add operand : OrQuery : AndQuery complete!

push AndQuery on _query_stack

Реализация системы текстового поиска состоит из трех компонентов:

 

класс TextQuery, где производится обработка текста (подробно он рассматривался в разделе 16.4). Для него нет производных классов;

объектно-ориентированная   иерархия  Query для  представления  и  обработки различных типов запросов;

класс  UserQuery,  с  помощью  которого  представлен  конечный  автомат  для построения иерархии Query.

До настоящего момента мы реализовали эти три компонента практически независимо  друг  от  друга  и  без  каких  бы  то  ни  было  конфликтов.  Но,  к сожалению,  иерархия  классов  Query не  поддерживает  требований  к конструированию объектов, предъявляемых реализацией UserQuery:

классы  AndQuery,  OrQuery и  NotQuery требуют,  чтобы  каждый  операнд присутствовал   в   момент   определения   объекта.   Однако   принятая   нами   схема обработки подразумевает наличие неполных объектов;

наша схема предполагает отложенное добавление операнда к объектам AndQuery, OrQuery и NotQuery. Более того, такая операция должна быть виртуальной. Операнд приходится    добавлять    через    указатель    типа    Query*,    находящийся    в    стеке

_current_op. Однако способ добавления операнда зависит от типа: для унарных (NotQuery) и бинарных (AndQuery и OrQuery) операций он различен. Наша иерархия классов Query подобные операции не поддерживает.

Оказалось,  что  анализ  предметной  области  был  неполон,  в  результате  чего разработанный интерфейс не согласуется с конкретной реализацией проекта. Нельзя сказать, что анализ был неправильным, он просто неполон. Эта проблема связана с тем, что этапы анализа, проектирования и реализации отделены друг от друга и не допускают обратной связи и пересмотра. Но хотя мы не можем все продумать и все предвидеть, необходимо отличать неизбежные неправильные шаги от ошибок, обусловленных собственной невнимательностью или нехваткой времени.

В таком случае мы должны либо сами модифицировать иерархию классов Query, либо договориться, чтобы это сделали за нас. В данной ситуации мы, как авторы всей системы, сами изменим код, модифицировав конструкторы подтипов и включив виртуальную функцию-член  add_op() для  добавления  операндов  после определения  оператора  (мы покажем, как она применяется, чуть ниже, при рассмотрении функций evalRParen() и evalWord()).

17.7.1. Определение класса UserQuery

Объект   класса   UserQuery можно   инициализировать   указателем   на   вектор   строк, представляющий запрос пользователя, или передать ему адрес этого вектора позже, с помощью   функции-члена   query().   Это   позволяет   использовать   один   объект   для нескольких  запросов.  Фактическое  построение  иерархии  классов  Query выполняется функцией eval_query():

 

// определить объект, не имея запроса пользователя

UserQuery user_query;

string text;

vector<string> query_text;

// обработать запросы пользователя

do {

while( cin >> text )

query_text.push_back( text );

// передать запрос объекту UserQuery user_query.query( &query_text );

// вычислить результат запроса и вернуть

// корень иерархии Query*

Query *query = user_query.eval_query();

}

while ( /* пользователь продолжает формулировать запросы */ );

Вот определение нашего класса UserQuery:

 

#ifndef USER_QUERY_H

#define USER_QUERY_H

#include <string>

#include <vector>

#include <map>

#include <stack>

typedef pair<short,short>       location;

typedef vector<location,allocator>  loc;

#include "Query.h" class UserQuery {

public:

UserQuery( vector< string,allocator > *pquery = 0 )

: _query( pquery ), _eval( 0 ), _paren( 0 ) {}

Query *eval_query();  // строит иерархию void       query( vector< string,allocator > *pq ); void  displayQuery();

static void word_map( map<string,loc*,less<string>,allocator>

*pwm ) {

if ( !_word_map ) _word_map = pwm;

}

 

 

private:

 

enum QueryType { WORD = 1, AND, OR, NOT, RPAREN, LPAREN }; QueryType evalQueryString( const string &query );

void     evalWord( const string &query );

void      evalAnd();

void      evalOr();

void      evalNot();

void      evalRParen();

bool      integrity_check();

int            _paren; Query *_eval; vector<string> *_query;

 

 

stack<Query*, vector<Query*> > _query_stack;

stack<Query*, vector<Query*> > _current_op;

static short _lparenOn, _rparenOn;

static map<string,loc*,less<string>,allocator> *_word_map;

};

#endif

Обратите внимание,  что два  объявленных  нами  стека  содержат  указатели  на  объекты типа Query, а не сами объекты. Хотя правильное поведение обеспечивается обеими реализациями, хранение объектов значительно менее эффективно, поскольку каждый объект  (и  его  операнды)  должен  быть  почленно  скопирован  в  стек  (напомним,  что операнды  копируются  виртуальной  функцией  clone())  только для того, чтобы вскоре быть уничтоженным. Если мы не собираемся модифицировать объекты, помещаемые в контейнер, то хранение указателей на них намного эффективнее.

Ниже показаны реализации различных встроенных операций eval. Операции evalAnd()

и   evalOr() выполняют   следующие   шаги.   Сначала   объект   извлекается   из   стека

 

_query_stack (напомним,   что   для   класса   stack,   определенного   в   стандартной библиотеке,  это  требует  двух  операций:  top() для  получения  элемента  и  pop() для удаления его из стека). Затем из хипа выделяется память для объекта класса AndQuery или OrQuery, и указатель на него передается объекту, извлеченному из стека. Каждая операция передает объекту AndQuery или OrQuery счетчики левых или правых скобок, необходимые  ему  для  вывода  своего  содержимого.   И  наконец  неполный   оператор

inline void UserQuery:: evalAnd()

{

Query *pop = _query_stack.top(); _query_stack.pop(); AndQuery *pq = new AndQuery( pop );

if ( _lparenOn )

{ pq->lparen( _lparenOn ); _lparenOn = 0; }

if ( _rparenOn )

{ pq->rparen( _rparenOn ); _rparenOn = 0; }

_current_op.push( pq );

}

inline void UserQuery:: evalOr()

{

Query *pop = _query_stack.top(); _query_stack.pop(); OrQuery *pq = new OrQuery( pop );

if ( _lparenOn )

{ pq->lparen( _lparenOn ); _lparenOn = 0; }

if ( _rparenOn )

{ pq->rparen( _rparenOn ); _rparenOn = 0; }

_current_op.push( pq );

помещается в стек _current_op:

}

Операция  evalNot() работает  следующим  образом.  В  хипе  создается  новый  объект класса NotQuery, которому передаются счетчики левых и правых скобок для правильного

inline void UserQuery:: evalNot()

{

NotQuery *pq = new NotQuery;

if ( _lparenOn )

{ pq->lparen( _lparenOn ); _lparenOn = 0; }

if ( _rparenOn )

{ pq->rparen( _rparenOn ); _rparenOn = 0; }

_current_op.push( pq );

отображения содержимого. Затем неполный оператор помещается в стек _current_op:

}

 

При обнаружении закрывающей скобки вызывается операция evalRParen(). Если число активных левых скобок больше числа элементов в стеке _current_op, то ничего не происходит.    В   противном   случае   выполняются   следующие   действия.   Из   стека

_query_stack извлекается текущий еще не присоединенный к оператору операнд, а из стека  _current_op –  текущий  неполный  оператор.  Вызывается  виртуальная  функция add_op() класса Query, которая их объединяет. И наконец полный оператор помещается

inline void UserQuery:: evalRParen()

{

if ( _paren < _current_op.size() )

{

Query *poperand = _query_stack.top();

_query_stack.pop();

Query *pop = _current_op.top();

_current_op.pop();

pop->add_op( poperand );

_query_stack.push( pop );

}

в стек _query_stack:

}

Операция  evalWord() выполняет  следующие  действия.  Она  ищет  указанное  слово  в отображении _word_map взятых из файла слов на векторы позиций. Если слово найдено, берется его вектор позиций и в хипе посредством конструктора с двумя параметрами создается новый объект NameQuery. В противном случае объект порождается с помощью конструктора с одним параметром. Если число элементов в стеке _current_op меньше либо равно числу встреченных ранее скобок, то нет неполного оператора, ожидающего операнда  типа  NameQuery,  поэтому  новый  объект  помещается  в  стек  _query_stack. Иначе из  стека  _current_op извлекается  неполный  оператор,  к которому с помощью виртуальной функции add_op() присоединяется операнд NameQuery, после чего ставший полным оператор помещается в стек _query_stack:

 

inline void

UserQuery::

evalWord( const string &query )

{

NameQuery *pq;

loc       *ploc;

if ( ! _word_map->count( query ))

pq = new NameQuery( query );

else {

ploc = ( *_word_map )[ query ];

pq = new NameQuery( query, *ploc );

}

if ( _current_op.size() <= _paren )

_query_stack.push( pq );

else {

Query *pop = _current_op.top();

_current_op.pop();

pop->add_op( pq );

_query_stack.push( pop );

}

}

Упражнение 17.21

Напишите деструктор, копирующий конструктор и копирующий оператор присваивания для класса UserQuery.

Упражнение 17.22

Напишите функции print() для класса UserQuery. Обоснуйте свой выбор того, что она выводит.

17.8. Соберем все вместе

Функция  main() для  нашего  приложения   текстового  поиска   выглядит  следующим

#include "TextQuery.h"

int main()

{

TextQuery tq;

tq.build_up_text();

tq.query_text();

образом:

}

Функция-член  build_text_map() –  это  не  что  иное,  как  переименованная  функция

doit() из раздела 6.14:

 

inline void TextQuery:: build_text_map()

{

retrieve_text(); separate_words(); filter_text(); suffix_text(); strip_caps(); build_word_map();

}

Функция-член   query_text() заменяет   одноименную   функцию   из   раздела   6.14.   В первоначальной реализации в ее обязанности входили прием запроса от пользователя и вывод ответа. Мы решили сохранить за query_text() эти задачи, но реализовать ее по- другому19:

19 Полный текст программы можно найти на FTP-сайте издательства Addison- Wesley по адресу, указанному на задней стороне обложки.

void

TextQuery::query_text()

{

С++ для/*налчоикнаалюьщныиех объекты:

*

* text: содержит все слова запроса

* query_text: вектор для хранения пользовательского запроса

* caps: фильтр для поддержки преобразования

* прописных букв в строчные

*

* user_query: объект UserQuery, в котором инкапсулировано

*          собственно вычисление ответа на запрос

*/

921

 

string text;

string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ"  ); vector<string, allocator> query_text; UserQuery user_query;

// инициализировать статические члены UserQuery NotQuery::all_locs( text_locations->second ); AndQuery::max_col( &line_cnt ); UserQuery::word_map( word_map );

do {

// удалить предыдущий запрос, если он был

query_text.clear();

cout << "Введите запрос. Пожалуйста, разделяйте все его "

<< "элементы пробелами. "

<< "Запрос (или весь сеанс) завершается точкой ( . ). "

<< "==> ";

/*

* прочитать запрос из стандартного ввода,

* преобразовать все заглавные буквы, после чего

* упаковать его в query_text ...

*

* примечание: здесь производятся все действия по

* обработке запроса, связанные собственно с текстом ...

*/

while( cin >> text )

{

if ( text == "." )

break;

string::size_type pos = 0;

while (( pos = text.find_first_of( caps, pos ))

!= string::npos )

text[pos] = tolower( text[pos] );

query_text.push_back( text );

}

// теперь у нас есть внутреннее представление запроса

// обработаем его ...

if ( ! query_text.empty() )

{

// передать запрос объекту UserQuery user_query.query( &query_text );

// вычислить ответ на запрос

// вернуть иерархию Query*

// подробности см. в разделе 17.7

// query - это член класса TextQuery типа Query*

query = user_query.eval_query();

// вычислить иерархию Query,

// реализация описана в разделе 17.7

query->eval();

// вывести ответ с помощью

// функции-члена класса TextQuery

display_solution();

// вывести на терминал пользователя дополнительную

// пустую строку

cout << endl;

 

}

Тестируя программу, мы применили ее к нескольким текстам. Первым стал короткий рассказ Германа Мелвилла “Bartleby”. Здесь иллюстрируется составной запрос AndQuery, для которого подходящие слова расположены в соседних строках. (Отметим, что слова, заключенные между символами косой черты, предполагаются набранными курсивом.)

Введите запрос. Пожалуйста, разделяйте все его элементы пробелами.

Запрос (или весь сеанс) завершается точкой ( . ).

==> John && Jacob && Astor

john ( 3 ) lines match jacob ( 3 ) lines match

john && jacob ( 3 ) lines match astor ( 3 ) lines match

john && jacob && astor ( 5 ) lines match

Requested query: john && jacob && astor

( 34 ) All who know me consider me an eminently /safe/ man. The late

John Jacob

( 35 ) Astor, a personage little given to poethic enthusiasm, had no

hesitation in

( 38 ) my profession by the late John Jacob Astor, a name which, I admit

I love to

( 40 ) bullion. I will freely add that I was not insensible to the late

John Jacob

( 41 ) Astor's good opinion.

Следующий  запрос, в котором тестируются скобки  и составные операторы,  обращен  к тексту новеллы “Heart of Darkness” Джозефа Конрада:

==> horror || ( absurd && mystery ) || ( North && Pole )

horror ( 5 ) lines match absurd ( 8 ) lines match mystery ( 12 ) lines match

( absurd && mystery ) ( 1 ) lines match

horror || ( absurd && mystery ) ( 6 ) lines match

north ( 2 ) lines match

pole ( 7 ) lines match

( north && pole ) ( 1 ) lines match

horror || ( absurd && mystery ) || ( north && pole )

( 7 ) lines match

Requested query: horror || ( absurd && mystery ) || ( north && pole ) ( 257 ) up I will go there.' The North Pole was one of these

( 952 ) horros. The heavy pole had skinned his poor nose

( 3055 ) some lightless region of subtle horrors, where pure,

( 3673 ) " 'The horror! The horror!'

( 3913 ) the whispered cry, 'The horror! The horror! '

( 3957 ) absurd mysteries not fit for a human being to behold.

( 4088 ) wind. 'The horror! The horror!'

Последний запрос был обращен к отрывку из романа Генри Джеймса “Portrait of a Lady”.

В нем иллюстрируется составной запрос в применении к большому текстовому файлу:

==> clever && trick || devious

clever ( 46 ) lines match trick ( 12 ) lines match

clever && trick ( 2 ) lines match devious ( 1 ) lines match

clever && trick || devious ( 3 ) lines match

Requested query: clever && trick || devious

( 13914 ) clever trick she had guessed. Isabel, as she herself grew older

 

( 13935 ) lost the desire to know this lady's clever trick. If she had ( 14974 ) desultory, so devious, so much the reverse of processional. There were

Упражнение 17.23

Реализованная нами обработка запроса пользователя обладает одним недостатком: она не применяет к каждому слову те же предварительные фильтры, что и программа, строящая вектор позиций (см. разделы 6.9 и 6.10). Например, пользователь, который хочет найти слово “maps”, обнаружит, что в нашем представлении текста распознается только “map”, поскольку  существительные  во  множественном  числе  приводятся  к  форме  в единственном числе. Модифицируйте функцию query_text() так, чтобы она применяла эквивалентные фильтры к словам запроса.

Упражнение 17.24

Поисковую систему можно было бы усовершенствовать, добавив еще одну разновидность запроса “И”, которую мы назовем InclusiveAndQuery и будем обозначать символом &. Строка  текста  удовлетворяет  условиям  запроса,  если  в  ней  находятся  оба  указанных слова, пусть даже не рядом. Например, строка

We were her pride of ten, she named us

удовлетворяет запросу:

pride & ten

но не:

pride && ten

Поддержите запрос InclusiveAndQuery.

Упражнение 17.25

Представленная ниже реализация функции display_solution() может выводить только в  стандартный   вывод.  Более  правильно  было  бы  позволить   пользователю   самому задавать поток ostream, в который надо направить вывод. Модифицируйте display_solution() так, чтобы ostream можно было задавать. Какие еще изменения необходимо внести в определение класса UserQuery?

 

void TextQuery::

display_solution()

{

cout << " "

<< "Requested query: "

<< *query << " ";

const set<short,less<short>,allocator> *solution = query-

>solution();

if ( ! solution->size() ) {

cout << " "

<< "Sorry, no matching lines were found in text. "

<< endl;

}

set<short>::const_iterator it = solution->begin(), end_it = solution->end();

for ( ; it != end_it; ++it ) {

int line = *it;

// пронумеруем строки с 1 ... cout << "( " << line+1 << " ) "

<< (*lines_of_text)[line] << ' ';

}

cout << endl;

}

Упражнение 17.26

Нашему  классу  TextQuery не  хватает  возможности  принимать  аргументы,  заданные пользователем в командной строке.

(a)  Предложите синтаксис командной строки для нашей поисковой системы. (b)  Добавьте в класс необходимые данные и функции-члены.

(c)  Предложите средства для работы с командной строкой (см. пример в разделе 7.8).

Упражнение 17.27

В  качестве  темы  для  рабочего  проекта  рассмотрите  следующие  усовершенствования нашей поисковой системы:

(a)  Реализуйте  поддержку,  необходимую  для  представления  запроса  AndQuery в  виде одной строки, например “Motion Picture Screen Cartoonists”.

(b)  Реализуйте поддержку для ответа на запрос на основе вхождения слов не в строку, а в предложение.

(c) Реализуйте подсистему хранения истории, с помощью которой пользователь мог бы ссылаться на предыдущий запрос по номеру, возможно, комбинируя его с новым запросом.

(d)  Вместо   того   чтобы   показывать   счетчик   найденных   и   все   найденные   строки, реализуйте возможность задать диапазон выводимых строк для промежуточных вычислений и для окончательного ответа:

==> John && Jacob && Astor

(1)        john ( 3 ) lines match

(2)        jacob ( 3 ) lines match

(3)        john && jacob ( 3 ) lines match

(4)        astor ( 3 ) lines match

(5)        john && jacob && astor ( 5 ) lines match

// Новая возможность: пусть пользователь укажет, какой запрос выводить

// пользователь вводит число

==> вывести? 3

// Затем система спрашивает, сколько строк выводить

// при нажатии клавиши Enter выводятся все строки,

// но пользователь может также ввести номер одной строки или диапазон

            сколько (Enter выводит все, иначе введите номер строки или диапазон)

1-3

 

18