面向对象编程

--再谈文本查询示例

引言：

扩展第10.6节的文本查询应用程序，使我们的系统可以支持更复杂的查询。

为了说明问题,将用下面的简单小说来运行查询:

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

系统应该支持:

1）查找单个单词的查询。按升序显示所有包含该单词的行:

	Executed Query for: 
	Daddy match occurs 3 times: 
	(line 2) Her Daddy says when the wind blows 
	(line 7) "Daddy, shush, there is no such thing," 
	(line 10) Shyly, she asks, "I mean, Daddy, is there?"

2）“非”查询,使用~操作符。显示所有不匹配的行:

	Executed Query for: ~(Alice) 
	match occurs 9 times: 
	(line 2) Her Daddy says when the wind blows 
	(line 3) through her hair, it looks almost alive, 
	(line 4) like a fiery bird in flight. ... 

3）“或”查询,使用|操作符。显示与两个查询条件中任意一个匹配的所有行:

	Executing Query for: (hair | Alice) 
	match occurs 2 times: 
	(line 1) Alice Emma has long flowing red hair. 
	(line 3) through her hair, it looks almost alive,

4）“与”查询,使用&操作符。显示与两个查询条件都匹配的所有行:

	Executed query: (hair & Alice) 
	match occurs 1 time: 
	(line 1) Alice Emma has long flowing red hair. 

而且,可以组合这些元素,如

	fiery & bird | wind

我们将在 C++程序中创建这些表达式,因此,将用常规C++优先级规则对诸如此类的复合表达式求值。这个查询的求值结果将与出现的fiery和 bird的行或者出现wind的行相匹配,而不会与fiery或 bird单独出现的行相匹配:

	Executing Query for: ((fiery & bird) | wind) 
	match occurs 3 times: 
	(line 2) Her Daddy says when the wind blows 
	(line 4) like a fiery bird in flight. 
	(line 5) A beautiful fiery bird, he tells her, 

输出将打印查询,并使用圆括号指出解释该查询的方法。像原来的实现一样,系统必须足够聪明,不会重复显示相同行。

一、面向对象的解决方案

可以考虑使用10.6.2节的TextQuery表示单词查询，然后从TextQuery类派生其他类。

但是，这个设计可能有缺陷。概念上，“非”查询不是一种单词查询，相反，非查询“有一个”查询（单词查询或其他任意种类的查询），非查询对该查询的值求反。

注意到这一点,我们将不同种类的查询建模为独立的类,它们共享一个公共基类:

	WordQuery 		//Shakespeare 
	NotQuery 		//~Shakespeare 
	OrQuery 		//Shakespeare | Marlowe 
	AndQuery 		//William & Shakespeare

	Query q = Query("fiery") & Query("bird") | Query("wind");

以产生前面描述的复合查询。

这个问题描述暗示我们：用于级代码将不能直接使用我们的继承层次，相反，我们将定义一个名为Query的句柄类，用它隐藏继承层次。用户代码将根据句柄执行，用户代码只能间接操纵Query_base对象[以及Query_base的派生对象]。

像Sales_item句柄一样,Query句柄将保存指向继承层次中一个类型的对象的指针,Query类还指向一个使用计数,我们用这个使用计数管理句柄指向的对象。

在这种情况下,句柄将完全屏蔽基础继承层次,用户将只能间接地通过Query对象的操作创建和操纵Query_base对象。我们将定义Query对象的三个重载操作符以及Query构造函数，Query构造函数将动态分配新的Query_base对象。每个操作符将生成的对象绑定到Query句柄：

1)&操作符将生成绑定到新的AndQuery对象的 Query对象;

2)|操作符将生成绑定到新的OrQuery对象的 Query对象;

3)~操作符将生成绑定到新的NotQuery对象的 Query对象。

4)给Query定义一个参数为string对象的构造函数,该构造函数将生成新的WordQuery。

Query类将提供与Query_base类同样的操作:eval 对相关查询进行计算,display 打印查询。它将定义重载输出操作符显示相关查询。

我们的设计：扼要重述

【小心地雷】

理解设计经常是最困难的部分，尤其是刚开始设计面向对象系统时。一旦熟悉了设计，实现就是顺理成章的了！

这个应用程序的主要工作由建立对象表示用户的查询构成，认识到这一点很重要。如下图所示，表达式：

	Query q = Query("fiery") & Query("bird") | Query("wind");

一旦建立了对象树，计算(或显示)给定查询基本上就是沿着这些链接，要求树中每个对象计算(或显示)自己的过程，该过程由编译器管理。
例如,如果调用 q (即,在这棵树的树根)的eval,则 eval 将要求 q 指向的 OrQuery 对 象调用 eval 来计算自己,计算这个 OrQuery对象用两个操作数调用 eval,这个依次调用 AndQuery 对象和 WordQuery 对象的 eval,查找单词 wind,依此 类推。


三、Query_base类
首先定义Query_base类：

class Query_base
{
    friend class Query;
protected:
    typedef TextQuery::line_no line_no;
    virtual ~Query_base() {}

private:
    virtual std::set<line_no>
    eval(const TextQuery &) const = 0;

    virtual std::ostream &
    display(std::ostream & = std::cout) const = 0;
};

这个类定义了两个接口成员:eval和display。两个成员都是纯虚函数,因此该类为抽象类,应用程序中将没有Query_base类型的对象。

用户和派生类将只通过Query句柄使用Query_base类,因此,将Query_base接口设为private。(虚)析构函数和类型别名为 protected,这些派生类型就能够访问这些成员,构造函数由派生类构造函数(隐式)使用,因此派生类必须能够访问构造函数。

给Query句柄类授予友元关系,该类的成员将调用Query_base中的虚函数因此必须能够访问它们。

四、Query句柄类

Query句柄将类似于Sales_item类，因为它将保存Query_base指针和使用计数指针。像Sales_item类一样，Query的复制控制成员将管理使用计数和Query_base指针。

与Sales_item不同的是，Query类将只为Query_base继承层次提供接口。用户将不能直接访问Query或其派生类的任意成员。这一设计决定导致Query和 Sales_item之间存在两个区别：

第一个区别是,Query类将不定义解引用操作符和箭头操作符的重载版本。Query_base类没有 public成员,如果Query句柄定义了解引用操作符和箭头操作符,它们将没有用处!使用那些操作符访问成员的任何尝试都将失败,相反,Query类必须定义接口函数eval和display的自身版本。

另一个区别来自于我们打算怎样创建继承层次的对象。我们的设计指出将只通过 Query句柄的操作创建Query_base的派生类对象,这个区别导致Query类需要与Sales_item句柄中所用的构造函数不同的构造函数。

1、Query类

class Query
{
    friend Query operator~(const Query &);
    friend Query operator|(const Query &,const Query &);
    friend Query operator&(const Query &,const Query &);
public:
    Query(const std::string &);
    Query(const Query &c):q(c.q),use(c.use)
    {
        ++ *use;
    }

    ~Query()
    {
        desr_use();
    }

    Query &operator=(const Query &);

    std::set<TextQuery::line_no> eval(const TextQuery &t) const
    {
        return q -> eval(t);
    }

    std::ostream &display(std::ostream &os = std::cout)
    {
        return q -> display(os);
    }

private:
    Query(Query_base *query):q(query),use(new std::size_t(1)) {}

    Query_base *q;
    std::size_t *use;

    void desr_use()
    {
        if (-- *use == 0)
        {
            delete q;
            delete use;
        }
    }
};

首先指定创建Query对象的操作符为友元。

在Query类的 public接口中,声明了但没有定义接受string对象的构造函数,该构造函数创建WordQuery对象,因此在定义WordQuery类之前不能定义它。

后面三个成员处理复制控制,与Sales_item类中的对应成员相同。

最后两个public成员表示对Query_base类的接口。每种情况下,Query操作都使用它的Query_base指针调用相应Query_base操作。这些操作是虚函数,在运行时根据q指向的对象的类型确定调用的实际版本。

Query类实现的private部分包括一个接受Query_base对象指针的构造函数,该构造函数将获得的指针存储在q中并分配新的使用计数,将使用计数初始化为1。该构造函数为private,是因为我们不希望普通用户代码定义Query_base对象,相反,创建Query对象的操作符需要这个构造函数。构造函数为private,所以必须将操作符设为友元。

2、Query重载操作符

|、&和 ~操作符分别创建OrQuery、AndQuery和 NotQuery对象:

inline
Query operator&(const Query &lhs,const Query &rhs)
{
    return new AndQuery(lhs,rhs);
}

inline
Query operator|(const Query &lhs,const Query &rhs)
{
    return new OrQuery(lhs,rhs);
}

inline
Query operator~(const Query &oper)
{
    return new NotQuery(oper);
}

每个操作动态分配Query_base派生类型的新对象，return语句（隐式）使用接受Query_base指针的Query构造函数：

    Query(Query_base*query):q(query),use(new std::size_t(1)) {}

用操作分配的Query_base指针创建Query对象。例如，~操作符中的return语句等价于：

    Query_base *tmp = new NotQuery(oper);
    return Query(tmp);

没有操作符创建WordQuery对象,相反,为Query类定义一个接受string对象的构造函数,该构造函数生成WordQuery对象查找给定string。

3、Query输出操作符

我们希望用户可以用标准(重载的)输出操作符打印Query对象,但是,也需要打印操作是虚函数——打印 Query对象应打印Query对象指向的Query_base对象。这里存在一个问题:只有成员函数可以为虚函数,但输出操作符不能是Query_base类的成员。

要获得必要的虚函数行为,Query_base类定义了一个虚函数成员display,Query 输出操作符将使用它:

inline std::ostream &
operator<<(std::ostream &os,const Query &q)
{
    return q.display(os);
}

如果编写：

    Query andq = Query(sought1) & Query(sought2);
    cout << "\nExecuted query: " << andq << endl;

将调用display的WordQuery实例。更一般的，以下代码：

    Query query = some_query;
    cout << query << endl;

将调用程序运行到此时与query所指对象相关联的display实例。

五、派生类

下面要实现具体的查询类:

WordQuery类最直接,它的工作是保存要查找的单词。

其他类操作一个或两个Query操作数。NotQuery对象对别的Query对象的结果求反，AndQuery类和 OrQuery类都有两个操作数,操作数实际存储在它们的公共基类BinaryQuery中。

在这些类当中,操作数都可以是任意具体Query_base类的对象:NotQuery 对象可以应用于WordQuery对象、AndQuery对象、OrQuery对象或其他NotQuery对象。要允许这种灵活性,操作数必须存储为Query_base指针,它可以指向任意具体的Query_base类。

但是,我们的类不存储Query_base指针,而是使用自己的Query句柄。正如使用句柄可以简化用户代码,也可以使用同样的句柄类简化类代码。将Query操作数设为const,因为一旦创立了Query_base对象,就没有操作可以改变操作数了。

了解了这些类的设计之后,就可以实现它们了。

1、WordQuery类

WordQuery是一种Query_base，它在给定的查询映射中查找指定的单词：

class WordQuery : public Query_base
{
    friend class Query; //只有Query句柄能够创建WordQuery对象
    WordQuery(const std::string &s):query_word(s){}

    std::set<line_no> eval(const TextQuery &t) const
    {
        return t.run_query(query_word);
    }

    std::ostream &display(std::ostream &os) const
    {
        return os << query_word;
    }

    std::string query_word;
};

像Query_base类一样,WordQuery类没有 public成员,WordQuery必须将Query类设为友元以允许Query访问WordQuery构造函数。

每个具体的查询类必须定义继承的纯虚函数。WordQuery类的操作足够简单,可以定义在类定义中。eval成员调用其TextQuery形参的run_query成员[此处原书与翻译有误，英文原版为query_text，第四版翻译为query_word，特注于此！],将用于创建该WordQuery对象的 string对象传给它。要display一个 WordQuery对象,就打印query_word对象。

2、NotQuery类

class NotQuery  : public Query_base
{
    friend Query operator~(const Query &);
    NotQuery(Query q):query(q){}

    std::set<line_no> eval(const TextQuery &) const;
    std::ostream &display(std::ostream &os) const
    {
        return os << "~(" << query << ")";
    }
    const Query query;
};

将Query的重载 ~操作符设为友元,从而允许该操作符创建新的NotQuery对象。为了display一个 NotQuery对象,打印~对象,将输出用圆括号括住以保证读者清楚优先级。

【注解】

display操作中输出操作符的使用最终是对Query_base对象的虚函数调用:

    std::ostream &display(std::ostream &os) const
    {
        return os << "~(" << query << ")";
    }

  eval成员比较复杂,我们将在类定义体之外实现它,eval函数将在后面介绍。

3、BinaryQuery类

BinaryQuery类是一个抽象类，保存AndQuery和OrQuery两个查询类型所需的数据，AndQuery和OrQuery有两个操作数：

class BinaryQuery : public Query_base
{
protected:
    BinaryQuery(Query left,Query right,std::string &op):
        lhs(left),rhs(right),oper(op) {}

    std::ostream &
    display(std::ostream &os) const
    {
        return os << "(" << lhs << " " << oper
               << " " << rhs << ")";
    }

    const Query lhs,rhs;
    const std::string oper;
};

BinaryQuery中的数据是两个Query操作数,以及显示查询时使用的操作符符号。这些数据均声明为const,因为一旦建立了查询的内容就不应该再改变。构造函数接受两个操作数以及操作符符号,将它们存储在适当的数据成员中。

要显示一个BinaryOperator对象,打印由圆括号括住的表达式、该表达式由左操作数后接操作、再接右操作数构成。像显示NotQuery对象一样,用于打印left和 right的重载 <<操作符最终对基础Query_base对象的display进行虚函数调用。

【注解】

BinaryQuery类没有定义eval函数,因此继承了一个纯虚函数。这样,BinaryQuery也是一个抽象类,不能创建BinaryQuery类型的对象。

4、AndQuery和OrQuery类

AndQuery类和 OrQuery类几乎完全相同:

class AndQuery : public BinaryQuery
{
    friend Query operator&(const Query &,const Query &);

    AndQuery(const Query left,const Query right):
        BinaryQuery(left,right,"&") {}

    std::set<line_no> eval(const TextQuery &) const;
};
class OrQuery : public BinaryQuery
{
    friend Query operator|(const Query &,const Query &);

    OrQuery(const Query left,const Query right):
        BinaryQuery(left,right,"|"){}

    std::set<line_no> eval(const TextQuery &) const;
};

这两个类将各自的操作符设为友元,并定义了构造函数用适当的操作符创建它们的BinaryQuery基类部分。它们继承BinaryQuery类的display函数定义,但各自定义了自己的eval函数版本。

六、eval函数

查询类层次的中心是虚函数eval。每个eval函数调用其操作数的eval函数,然后应用自己的逻辑:AndQuery的 eval操作返回两个操作数的结果的并集,OrQuery的 eval操作返回交集,NotQuery的 eval操作比较复杂:它必须返回不在其操作数的集合中的行编号。

1、OrQuery::eval

OrQuery对象合并由它的两个操作数返回的行号编号集合—— 其结果是它的两个操作数的结果的并集:

set<TextQuery::line_no>
OrQuery::eval(const TextQuery &file) const
{
    set<line_no> right = rhs.eval(file),
                 ret_lines = lhs.eval(file);

    ret_lines.insert(right.begin(),right.end());

    return ret_lines;
}

  eval函数首先调用每个操作数的eval函数,操作数的eval函数调用Query::eval，Query::eval再调用基础Query_base对象的虚函数eval,每个调用获得其操作数出现在其中表示对右操作数求值所返回的set。因为ret_lines是一个 set对象,这个调用将right中未在left中出现的元素加到ret_lines中。调用insert函数之后，ret_lines包含在 left集或在right集的每个行编号。返回ret_lines而结束OrQuery::eval函数。

2、AndQuery::eval

set<TextQuery::line_no>
AndQuery::eval(const TextQuery &file) const
{
    set<line_no> left = lhs.eval(file),
                 right = rhs.eval(file);
    set<line_no> ret_linies;

    //该标准库算法的简单介绍可以在附录A.2.8节找到
    set_intersection(left.begin(),left.end(),
                     right.begin(),right.end(),
                     inserter(ret_linies,ret_linies.begin()));

    return ret_linies;
}

 eval函数这个版本使用set_intersection算法查找两个查询中的公共行:该算法接受5个迭代器,前4个表示两个输入范围,最后一个表示目的地。算法将同时在两个输入范围中存在的每个元素写到目的地。该调用的目的地是一个迭代器,它将新元素插入到ret_lines中。

3、NotQuery::eval

NotQuery查找未出现操作数的每个文本行。要支持这个函数,需要TextQuery类增加一个成员返回文件的大小size,以便了解存在什么样的行编号。

set<TextQuery::line_no>
NotQuery::eval(const TextQuery &file) const
{
    set<TextQuery::line_no> has_val = query.eval(file);
    set<line_no> ret_lines;

    for (TextQuery::line_no n = 0;n != file.size(); ++n)
    {
        if (has_val.find(n) == has_val.end())
        {
            ret_lines.insert(n);
        }
    }

    return ret_lines;
}

像其他eval函数一样,首先调用该对象的操作数的eval函数。该调用返回操作数所出现的行编号的set,而我们想要的是不出现操作数的行编号的set,通过查找输入文件的每个行编号获得该set。使用必须加到TextQuery的size成员控制 for循环,该循环将没有在has_val中出现的每个行编号加到ret_lines中,一旦处理完所有的行编号,就返回ret_lines。