首页 > 代码库 > C++ Primer 学习笔记_73_面向对象编程 --再谈文本查询示例

C++ Primer 学习笔记_73_面向对象编程 --再谈文本查询示例

面向对象编程

--再谈文本查询示例



引言:

扩展第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++优先级规则对诸如此类的复合表达式求值。这个查询的求值结果将与出现的fierybird的行或者出现wind的行相匹配,而不会与fierybird单独出现的行相匹配:

	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
因此,我们不继承TextQuery,而是使用TextQuery类保存文件并建立相关的word_map,使用查询类建立表达式,这些表达式对TextQuery对象中的文件运行查询。


1、抽象接口类
已经识别出四种查询类,这些类在概念上是兄弟类。它们共享相同的抽象接口,这暗示我们定义一个抽象基类以表示由查询执行的操作。将该抽象基类命名为 Query_base,以指出它的作用是作为查询继承层次的根。 
直接从抽象基类派生 WordQuery 和 NotQuery 类,但是AndQuery 和 OrQuery 类具有系统中其他类所没有的一个性质:它们都有两个操作数。要为此建立模型, 将在继承层次中增加另一个名为 BinaryQuery 的抽象类,表示带两个操作数的查询。WordQuery 和 NotQuery 类将继承 BinaryQuery 类,BinaryQuery 类继承 Query_base 类。因此类的设计如图所示:


2、操作
Query_base类的存在主要是为了表示查询类型,不做实际工作。我们将重用TextQuery类以存储文件、建立查询以及查找每个单词。查询类型只需要两个操作:
1)eval操作:返回匹配行编号的集合。该操作接受TextQuery对象,在TextQuery对象上执行查询。
2)display操作:接受ostream引用并打印给定对象在该ostream上执行的查询。
我们将这些操作定义为Query_base中的虚函数,每个派生类都必须对这些函数定义自己的版本[不然...就没法用O(∩_∩)O~]。


二、值型句柄
程序将处理计算查询,而不建立查询,但是,需要能够创建查询以便运行程序。最简单的办法是编写C++表达式直接创建查询,例如:
	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 打印查询。它将定义重载输出操作符显示相关查询。

查询程序设计:扼要重述

操作或表达式

功能

TextQuery

读指定文件创建相关查找映射的类。该类提供query_text操作,该操作接受string实参并返回一个set保存出现实参的行的编号

Query_base

查询类的抽象基类

Query

用于计数的句柄类,它指向Query_base派生类的对象

WordQuery

Query_base派生的类,查找给定单词

NotQuery

Query_base派生的类,返回操作数不出现的行的编号的集合

BinaryQuery

Query_base派生的抽象基类类型,表示带两个Query操作数的查询

OrQuery

BinaryQuery派生的类,返回两个操作数出现的行编号集的并集

AndQuery

BinaryQuery派生的类,返回两个操作数出现的行编号集的交集

q1& q2

返回Query对象,该Query对象绑定到保存q1q2的新AndQuery对象

q1| q2

返回Query对象,该Query对象绑定到保存q1q2的新OrQuery

~q

返回Query对象,该Query对象绑定到保存q的新NotQuery对象

Queryq(s)

Queryq绑定到保存strings的新的WordQuery对象



我们的设计:扼要重述

【小心地雷】

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

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

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

生成10个对象:5个Query_base对象及其相关联的句柄。5个Query_base对象分别为:3个WordQuery对象,一个OrQuery对象和AndQuery对象。


一旦建立了对象树,计算(或显示)给定查询基本上就是沿着这些链接,要求树中每个对象计算(或显示)自己的过程,该过程由编译器管理。
例如,如果调用 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;
};


这个类定义了两个接口成员:evaldisplay。两个成员都是纯虚函数,因此该类为抽象类,应用程序中将没有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或其派生类的任意成员。这一设计决定导致QuerySales_item之间存在两个区别:

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

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



1Query

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,所以必须将操作符设为友元。



2Query重载操作符

|&~操作符分别创建OrQueryAndQueryNotQuery对象:

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



3Query输出操作符

我们希望用户可以用标准(重载的)输出操作符打印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;

将调用displayWordQuery实例。更一般的,以下代码:

    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对象,就没有操作可以改变操作数了。

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



1WordQuery

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对象。



2NotQuery

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函数将在后面介绍。



3BinaryQuery

BinaryQuery类是一个抽象类,保存AndQueryOrQuery两个查询类型所需的数据,AndQueryOrQuery有两个操作数:

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对象一样,用于打印leftright的重载 <<操作符最终对基础Query_base对象的display进行虚函数调用

【注解】

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



4AndQueryOrQuery

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函数,然后应用自己的逻辑:AndQueryeval操作返回两个操作数的结果的并集,OrQueryeval操作返回交集,NotQueryeval操作比较复杂:必须返回不在其操作数的集合中的行编号



1OrQuery::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::evalQuery::eval再调用基础Query_base对象的虚函数eval,每个调用获得其操作数出现在其中表示对右操作数求值所返回的set。因为ret_lines是一个 set对象,这个调用right中未在left中出现的元素加到ret_lines。调用insert函数之后,ret_lines包含在 leftright集的每个行编号。返回ret_lines而结束OrQuery::eval函数。



2AndQuery::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



3NotQuery::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。使用必须加到TextQuerysize成员控制 for循环,该循环将没有在has_val中出现的每个行编号加到ret_lines,一旦处理完所有的行编号,就返回ret_lines。