【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.文本查询程序再探
接下来，我们扩展【C++基础】第六十八课：[动态内存]使用标准库：文本查询程序中的文本查询程序，用它作为说明继承的最后一个例子。我们将针对下面这个小故事展开查询：
1
2
3
4
5
6
7
8
9
10
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的所有行：
1 2 3 4 5
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?"
-
逻辑非查询，使用
~运算符得到不匹配查询条件的所有行：1 2 3 4 5 6
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. ...
-
逻辑或查询，使用
|运算符返回匹配两个条件中任意一个的行：1 2 3 4
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,
-
逻辑与查询，使用
&运算符返回匹配全部两个条件的行：1 2 3
Executing query for: (hair & Alice) (hair & Alice) occurs 1 time (line 1) Alice Emma has long flowing red hair
此外，我们还希望能够混合使用这些运算符，比如：
1
fiery & bird | wind
在类似这样的例子中，我们将使用C++通用的优先级规则对复杂表达式求值。因此，这条查询语句所得行应该是如下二者之一：在该行中或者fiery和bird同时出现，或者出现了wind：
1
2
3
4
5
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 beautiful fiery bird, he tells her,
系统将按照查询结果中行号的升序显示结果并且每一行只显示一次。
2.面向对象的解决方案
我们应该将几种不同的查询建模成相互独立的类，这些类共享一个公共基类：
1
2
3
4
WordQuery //Daddy
NotQuery //~Alice
OrQuery //hair | Alice
AndQuery //hair & Alice
这些类将只包含两个操作：
- eval，接受一个TextQuery对象并返回一个QueryResult，eval函数使用给定的TextQuery对象查找与之匹配的行。
- rep，返回基础查询的string表示形式，eval函数使用rep创建一个表示匹配结果的QueryResult，输出运算符使用rep打印查询表达式。
2.1.抽象基类
我们将所需的抽象基类命名为Query_base。我们的Query_base类将把eval和rep定义成纯虚函数，其他代表某种特定查询类型的类必须覆盖这两个函数。
2.2.将层次关系隐藏于接口类中
我们的程序将致力于计算查询结果，而非仅仅构建查询的体系。为了使程序能正常运行，我们必须首先创建查询命令，最简单的办法是编写C++表达式。例如，可以编写下面的代码来生成之前描述的复合查询：
1
Query q = Query("fiery") & Query("bird") | Query("wind");
如上所述，其隐含的意思是用户层代码将不会直接使用这些继承的类；相反，我们将定义一个名为Query的接口类，由它负责隐藏整个继承体系。Query类将保存一个Query_base指针，该指针绑定到Query_base的派生类对象上。Query类与Query_base类提供的操作是相同的：eval用于求查询的结果，rep用于生成查询的string版本，同时Query也会定义一个重载的输出运算符用于显示查询。
用户将通过Query对象的操作间接地创建并处理Query_base对象。我们定义Query对象的三个重载运算符以及一个接受string参数的Query构造函数，这些函数动态分配一个新的Query_base派生类的对象：
&运算符生成一个绑定到新的AndQuery对象上的Query对象；|运算符生成一个绑定到新的OrQuery对象上的Query对象；~运算符生成一个绑定到新的NotQuery对象上的Query对象；- 接受string参数的Query构造函数生成一个新的WordQuery对象。
2.3.理解这些类的工作机理
3.Query_base类和Query类
下面我们开始程序的实现过程，首先定义Query_base类：
1
2
3
4
5
6
7
8
9
10
11
12
//这是一个抽象基类，具体的查询类型从中派生，所有成员都是private的
class Query_base {
friend class Query;
protected:
using line_no = TextQuery::line_no; //用于eval函数
virtual ~Query_base() = default;
private:
//eval返回与当前Query匹配的QueryResult
virtual QueryResult eval(const TextQuery&) const = 0;
//rep是表示查询的一个string
virtual std::string rep() const = 0;
};
3.1.Query类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//这是一个管理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&); //构建一个新的WordQuery
//接口函数：调用对应的Query_base操作
QueryResult 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;
};
3.2.Query的输出运算符
输出运算符可以很好地解释我们的整个查询系统是如何工作的：
1
2
3
4
5
6
std::ostream &
operator<<(std::ostream &os, const Query &query)
{
//Query::rep通过它的Query_base指针对rep()进行了虚调用
return os << query.rep();
}
当我们打印一个Query时，输出运算符调用Query类的公有rep成员。运算符函数通过指针成员虚调用当前Query所指对象的rep成员。也就是说，当我们编写如下代码时：
1
2
Query andq = Query(sought1) & Query(sought2);
cout << andq << endl;
输出运算符将调用andq的Query::rep，而Query::rep通过它的Query_base指针虚调用Query_base版本的rep函数。因为andq指向的是一个AndQuery对象，所以本次的函数调用将运行AndQuery::rep。
4.派生类
对于Query_base的派生类来说，最有趣的部分是这些派生类如何表示一个真实的查询。其中WordQuery类最直接，它的任务就是保存要查找的单词。
其他类分别操作一个或两个运算对象。NotQuery有一个运算对象，AndQuery和OrQuery有两个。在这些类当中，运算对象可以是Query_base的任意一个派生类的对象：一个NotQuery对象可以被用在WordQuery、AndQuery、OrQuery或另一个NotQuery中。为了支持这种灵活性，运算对象必须以Query_base指针的形式存储，这样我们就能把该指针绑定到任何我们需要的具体类上。
然而，实际上我们的类并不存储Query_base指针，而是直接使用一个Query对象。就像用户代码可以通过接口类得到简化一样，我们也可以使用接口类来简化我们自己的类。
4.1.WordQuery类
一个WordQuery查找一个给定的string，它是在给定的TextQuery对象上实际执行查询的唯一一个操作：
1
2
3
4
5
6
7
8
9
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); }
std::string rep() const { return query_word; }
std::string query_word; //要查找的单词
};
Query必须作为WordQuery的友元，这样Query才能访问WordQuery的构造函数。定义了WordQuery类之后，我们就能定义接受string的Query构造函数了：
1
2
inline
Query::Query(const std::string &s): q(new WordQuery(s)) { }
4.2.NotQuery类及~运算符
~运算符生成一个NotQuery，其中保存着一个需要对其取反的Query：
1
2
3
4
5
6
7
8
9
10
11
12
class NotQuery: public Query_base {
friend Query operator~(const Query &);
NotQuery(const Query &q): query(q) { }
//具体的类：NotQuery将定义所有继承而来的纯虚函数
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));
}
~运算符动态分配一个新的NotQuery对象，其return语句隐式地使用接受一个shared_ptr<Query_base>的Query构造函数。也就是说，return语句等价于：
1
2
3
4
//分配一个新的NotQuery对象
//将所得的NotQuery指针绑定到一个shared_ptr<Query_base>
shared_ptr<Query_base> tmp(new NotQuery(expr));
return Query(tmp); //使用接受一个shared_ptr的Query构造函数
4.3.BinaryQuery类
1
2
3
4
5
6
7
8
9
class BinaryQuery: public Query_base {
protected:
BinaryQuery(const Query &l, const Query &r, std::string s):
lhs(l), rhs(r), opSym(s) { }
//抽象类：BinaryQuery不定义eval
std::string rep() const { return "(" + lhs.rep() + " " + opSym + " " + rhs.rep() + ")"; }
Query lhs, rhs; //左侧和右侧运算对象
std::string opSym; //运算符的名字
};
BinaryQuery不定义eval，而是继承了该纯虚函数。因此，BinaryQuery也是一个抽象基类，我们不能创建BinaryQuery类型的对象。
4.4.AndQuery类、OrQuery类及相应的运算符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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));
}
5.eval函数
eval函数是我们这个查询系统的核心。每个eval函数作用于各自的运算对象，同时遵循的内在逻辑也有所区别：OrQuery的eval操作返回两个运算对象查询结果的并集，而AndQuery返回交集。与它们相比，NotQuery的eval函数更加复杂一些：它需要返回运算对象没有出现的文本行。
为了支持上述eval函数的处理，我们需要使用QueryResult。假设QueryResult包含begin和end成员，它们允许我们在QueryResult保存的行号set中进行迭代；另外假设QueryResult还包含一个名为get_file的成员，它返回一个指向待查询文件的shared_ptr。
5.1.OrQuery::eval
1
2
3
4
5
6
7
8
9
10
11
12
13
//返回运算对象查询结果set的并集
QueryResult OrQuery::eval(const TextQuery& text) const
{
//通过Query成员lhs和rhs进行的虚调用
//调用eval返回每个运算对象的QueryResult
auto 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());
}
我们使用接受一对迭代器的set构造函数初始化ret_lines。一个QueryResult的begin和end成员返回行号set的迭代器，因此，创建ret_lines的过程实际上是拷贝了left集合的元素。接下来对ret_lines调用insert，并将right的元素插入进来。调用结束后，ret_lines将包含在left或right中出现过的所有行号。
5.2.AndQuery::eval
1
2
3
4
5
6
7
8
9
10
11
12
//返回运算对象查询结果set的交集
QueryResult AndQuery::eval(const TextQuery& text) const
{
//通过Query运算对象进行的虚调用，以获得运算对象的查询结果set
auto left = lhs.eval(text), right = rhs.eval(text);
//保存left和right交集的set
auto ret_lines = make_shared<set<line_no>>();
//将两个范围的交集写入一个目的迭代器中
//本次调用的目的迭代器向ret添加元素
set_intersection(left.begin(), left.end(), right.begin(), right.end(), inserter(*ret_lines, ret_lines->begin()));
return QueryResult(rep(), ret_lines, left.get_file());
}
其中我们使用标准库算法set_intersection来合并两个set。set_intersection算法接受五个迭代器。它使用前四个迭代器表示两个输入序列，最后一个实参表示目的位置。该算法将两个输入序列中共同出现的元素写入到目的位置中。在上述调用中我们传入一个插入迭代器作为目的位置。当set_intersection向这个迭代器写入内容时，实际上是向ret_lines插入一个新元素。
5.3.NotQuery::eval
NotQuery查找运算对象没有出现的文本行：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//返回运算对象的结果set中不存在的行
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_lines
auto sz = result.get_file()->size();
for(size_t n = 0; n != sz; ++n) {
//如果我们还没有处理完result的所有行
//检查当前行是否存在
if(beg == end || *beg != n)
ret_lines->insert(n); //如果不在result当中，添加这一行
else if(beg != end)
++beg; //否则继续获取result的下一行（如果有的话）
}
return QueryResult(rep(), ret_lines, result.get_file());
}
