类设计者的工具(五)：面向对象程序设计示例

本文为《C++ Primer》的读书笔记

文本查询程序再探

接下来， 我们扩展之前的文本查询程序，用它作为说明继承的最后一个例子。在上一版的程序中， 我们可以查询在文件中某个指定单词的出现情况。我们将在本节扩展该程序使其支持更多更复杂的查询操作。在后面的例子中， 我们将针对下面这个小故事展开查询：

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

我们的系统将支持如下查询形式。

• 单词查询， 用于得到匹配某个给定string 的所有行：

Executing Query for: Daddy
Daddy 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?"

• 逻辑非查询， 得到不匹配查询条件的所有行：

Executing Query for: ~(Alice)
~(Alice) 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．

• 逻辑或查询， 返回匹配两个条件中任意一个的行：

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

• 逻辑与查询， 返回匹配全部两个条件的行：

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

此外， 我们还希望能够混合使用这些运算符， 比如：

fiery & bird | wind

在类似这样的例子中， 我们将使用C++通用的优先级规则对复杂表达式求值。因此， 这条查询语句所得行应该是如下二者之一：在该行中或者fiery 和bird 同时出现，或者出现了wind:

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

在输出内容中首先是那条查询语句， 我们使用圆括号来表示查询被解释和执行的次序。与之前实现的版本一样，接下来系统将按照查询结果中行号的升序显示结果并且每一行只显示一次

面向对象的解决方案

我们可能会认为使用之前的TextQuery 类来表示单词查询， 然后从该类中派生出其他查询是一种可行的方案

然而，这样的设计实际上存在缺陷。为了理解其中的原因，我们不妨考虑逻辑非查询：单词查询查找一个指定的单词， 为了让逻辑非查询按照单词查询的方式执行， 我们将不得不定义逻辑非查询所要查找的单词。但是在一般情况下，我们无法得到这样的单词。相反，一个逻辑非查询中含有一个结果值需要取反的查询语句；类似的， 一个逻辑与查询和一个逻辑或查询各包含两个结果值需要合并的查询语句

由上述观察结果可知， 我们应该将几种不同的查询建模成相互独立的类， 这些类共享一个公共基类：

WordQuery		// Daddy
NotQuery		// ~Alice
OrQuery			// hair | Alice
AndQuery		// hair & Alice

这些类将只包含两个操作：

• eval, 接受一个TextQuery对象并返回一个QueryResult, eval 函数使用给定的TextQuery对象查找与之匹配的行
• rep, 返回基础查询的string表示形式，eval函数使用rep创建一个表示匹配结果的QueryResult, 输出运算符使用rep打印查询表达式

关键概念：继承与组合
当我们令一个类公有地继承另一个类时，派生类应当反映与基类的”是一种(Is A)"关系。在设计良好的类体系当中， 公有派生类的对象应该可以用在任何需要基类对象的地方。类型之间的另一种常见关系是“有一个(Has A)"关系， 具有这种关系的类暗含成员的意思

抽象基类

我们需要定义一个抽象基类Query_base来表示上述四个类的公共接口。它将把eval和rep定义成纯虚函数。我们将从Query_base直接派生出WordQuery和NotQuery

AndQuery和OrQuery 都各自包含两个运算对象。为了对这种属性建模， 我们定义另外一个名为BinaryQuery 的抽象基类。AndQuery和OrQuery继承自BinaryQuery, 而BinaryQuery继承自Query_base

将层次关系隐藏于接口类中

为了使程序能正常运行， 我们必须首先创建查询命令，最简单的办法是编写C++表达式。例如， 可以编写下面的代码来生成之前描述的复合查询：

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

如上所述， 其隐含的意思是用户层代码将不会直接使用这些继承的类； 相反， 我们将定义一个名为Query的接口类， 由它负责隐藏整个继承体系：

• Query类将保存一个指向Query_base对象的shared_ptr，该指针绑定到Query_base的派生类对象上。Query类与Query_base类提供的操作是相同的： eval用于求查询的结果， rep用于生成查询的string版本， 同时Query也会定义一个重载的输出运算符用于显示查询

我们定义Query对象的三个重载运算符以及一个接受string参数的Query构造函数， 这些函数动态分配一个新的Query_base派生类的对象：

• &运算符生成一个绑定到新的AndQuery对象上的Query对象；
• |运算符生成一个绑定到新的OrQuery对象上的Query对象；
• ~运算符生成一个绑定到新的NotQuery对象上的Query对象
• 接受string参数的Query构造函数生成—个新的WordQuery对象， 然后将它的shared_prt 成员绑定到这个新创建的对象上

例如，如果我们对q(即树的根节点）调用eval函数，则该调用语句将令q所指的OrQuery对象调用eval，而这实际上是对它的两个运算对象执行eval操作：一个运算对象是AndQuery,另一个是查找单词wind 的WordQuery…

Query_base类和Query类

下面我们开始程序的实现过程， 首先定义Query_base类：

class Query_base {
friend class Query;
protected:using line_no = TextQuery::line_no; //用于eval函数virtual ~Query_base() = default; //析构函数也是受保护的，因为它将（隐式地） 在派生类析构函数中使用
private://eval返回与当前Query匹配的QueryResultvirtual QueryResult eval(const TextQuery&) const = 0;//rep是表示查询的一个stringvirtual std::string rep() const = 0;
};

因为我们不希望用户或者派生类直接使用Query_base, 所以它没有public成员。所有对Query_base的使用都需要通过Query对象，因为Query需要调用Query_base的虚函数， 所以我们将Query声明成Query_base的友元。

为了支持&, |, ~ 运算符， Query还需要另外一个构造函数， 它接受指向Query_base的shared_ptr并且存储给定的指针。我们将这个构造函数声明为私有的，原因是我们不希望一般的用户代码能随便定义Query_base 对象。因为这个构造函数是私有的， 所以我们需要将三个运算符声明为友元：

class Query (
// 这些运算符需要访问接受shared_ptr的构造函数， 而该函数是私有的
friend Query operator~(const Query &);
friend Query operator|(const Query&, const Query&);
friend Query operator&(const Query&, const Query&);
public:Query(const std::string&); //构建一个新的WordQueryQueryResult eval(const TextQuery &t) const{ return q->eval(t); } // 调用虚函数std::string rep() const { return q->rep(); } // 调用虚函数
private:Query(std::shared_ptr<Query_base> query): q(query) {}std::shared_ptr<Query_base> q;
};

Query的输出运算符：

std::ostream &
operator<<(std::ostream &os, const Query &query)
{// Query::rep通过它的Query_base指针对rep()进行了虚调用return os << query.rep();
}

派生类

WordQuery类

一个WordQuery查找一个给定的string, 它是在给定的TextQuery对象上实际执行查询的唯一一个操作：

class WordQuery : public Query_base {friend class Query; 	// Query使用WordQuery 构造函数WordQuery(const std::string &s): query_word(s) { }// 具体的类： WordQuery将定义所有继承而来的纯虚函数QueryResult eval(const TextQuery &t) const{ return t.query(query_word); }		//调用其TextQuery参数的query成员，由query成员在文件中实际进行查找std::string rep() const { return query_word; }std::string query_word; //要查找的单词
} ;

定义了WordQuery类之后， 我们就能定义接受string的Query构造函数了：

inline
Query::Query(const std::string &s): q(new WordQuery(s)) { }

NotQuery 类及~ 运算符

运算符生成一个NotQuery, 其中保存着一个需要对其取反的Query:

class NotQuery: public Query_base {friend Query operator~(const Query &);NotQuery(const Query &q): query(q) { }// 具体的类： NotQuery将定义所有继承而来的纯虚函数// rep 的调用最终执行的是一个虚调用： // query.rep()是对Query 类rep 成员的非虚调用， 接着Query::rep 将调用q->rep (), 这是一个通过Query_base 指针进行的虚调用std::string rep() const {return "~(" + query.rep() + "}";}QueryResult eval(const TextQuery&) const;Query query;
};inline Query operator~(const Query &operand}
{return std::shared_ptr<Query_base>(new NotQuery(operand));
}

BinaryQuery类

class BinaryQuery: public Query_base {
protected:BinaryQuery(const Query &l, const Query &r, std::string s):lhs(l), rhs(r), opSym(s) { }// 抽象类： BinaryQuery不定义evalstd::string rep() const {return "(" + lhs.rep() + " "+ opSym + " "+ rhs.rep() + ")"; }Query lhs, rhs; 		// 左侧和右侧运算对象std::string opSym; 		// 运算符的名字
};

BinaryQuery继承了eval纯虚函数。因此， BinaryQuery也是一个抽象基类

AndQuery 类、OrQuery 类及相应的运算符

class AndQuery: public BinaryQuery {friend Query operator&(const Query&, const Query&);AndQuery(const Query &left, const Query &right):BinaryQuery(left, right, "&") { }// 具体的类： AndQuery继承了rep并且定义了其他纯虚函数QueryResult eval(const TextQuery&) const;
};inline Query operator&(const Query &lhs, const Query &rhs)
{return std::shared_ptr<Query_base>(new AndQuery(lhs, rhs));
}class OrQuery: public BinaryQuery {friend Query operator | (const Query&, const Query&);OrQuery(const Query &left, const Query &right):BinaryQuery(left, right, "|") { }QueryResult eval{const TextQuery&) const;
};inline Query operator | (const Query &lhs, const Query &rhs)
{return std::shared_ptr<Query_base>(new OrQuery(lhs, rhs));
}

eval函数

为了支持eval函数的处理， 我们需要使用QueryResult。假设QueryResult包含begin和end成员，它们允许我们在QueryResult保存的行号set中进行迭代； 另外假设QueryResult还包含一个名为get_file的成员， 它返回一个指向待查询文件的shared_ptr

OrQuery::eval

一个OrQuery表示的是它的两个运算对象结果的并集， 对每个运算对象来说， 我们通过调用eval得到它的查询结果。因为这些运算对象的类型是Query, 所以调用eval也就是调用Query::eval, 而后者实际上是对潜在的Query_base对象的eval进行虚调用。每次调用完成后，得到的结果是一个QueryResult, 它表示运算对象出现的行号。我们把这些行号组织在一个新set中：

// 返回运算对象查询结果set的并集
QueryResult
OrQuery::eval(const TextQuery& text) const
{// 通过Query成员lhs和rhs进行的虚调用// 调用eval返回每个运算对象的QueryResultauto right = rhs.eval(text), left = lhs.eval(text);// 将左侧运算对象的行号拷贝到结果set中auto ret_lines = make_shared<set<line_no>>(left.begin(), left.end());// 插入右侧运算对象所得的行号ret_lines->insert(right.begin(), right.end());// 返回一个新的QueryResult, 它表示lhs和rhs的升集return QueryResult(rep(), ret_lines, left.get_file());
}

AndQuery::eval

AndQuery的eval和OrQuery很类似， 唯一的区别是它调用了一个标准库算法来求得两个查询结果中共有的行：

// 返回运算对象查询结果set的交集
QueryResult
AndQuery::eval(const TextQuery& text) const
{// 通过Query运算对象进行的虚调用， 以获得运算对象的查询结果setauto left = lhs.eval(text), right= rhs.eval(text);// 保存left和right 交集的setauto ret_lines = make_shared<set<line_no>>();// 将两个范围的交集写入一个目的迭代器中// 本次调用的目的迭代器向ret添加元素set_intersection(left.begin(), left.end(), right.begin(), right.end(),inserter(*ret_lines, ret_lines->begin())); // 最后一个实参表示目的位置，在上述调用中我们传入一个插入迭代器作为目的位置，当set_intersection向这个迭代器写入内容时，实际上是向ret_lines插入一个新元素return QueryResult(rep(), ret_lines, left.get_file());
}

NotQuery::eval

QueryResult
NotQuery::eval(const TextQuery& text) const
{// 通过Query运算对象对eval 进行虚调用auto result = query.eval(text);// 开始时结果set为空auto ret_lines = make_shared<set<line_no>>();// 我们必须在运算对象出现的所有行中进行迭代auto beg = result.begin(), end= result.end();// 对于输入文件的每一行， 如果该行不在result当中， 则将其添加到ret_linesauto sz = result.get_file()->size();for (size_t n= 0; n != sz; ++n) {if (beg == end || *beg != n)ret_lines->insert(n); //如果不在result当中， 添加这一行else if (beg != end)++beg; // 否则继续获取result的下一行（如果有的话）}return QueryResult(rep(), ret_lines, result.get_file());
}