Team LiB
Previous Section Next Section

15.9. Text Queries Revisited

15.9. 再谈文本查询示例

As a final example of inheritance, we'll extend our text query application from Section 10.6 (p. 379). The class we developed there let us look for occurrences of a given word in a text file. We'd like to extend the system to support more complex queries.

作为继承的最后一个例子,我们来扩展第 10.6 节的文本查询应用程序。使用在第 10.6 节开发的类,已经能够在文本文件中查找给定单词的出现,但我们想扩展系统以支持更复杂的查询。

For illustration purposes, we'll run queries against the following simple story:

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

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

Our system should support:

系统应该支持:

  1. Word queries that find a single word. All lines in which the word appears should be displayed in ascending order:

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

         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. Not queries, using the ~ operator. All lines that do not match the query are displayed:

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

         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. Or queries, using the | operator. All lines in which either of two queries match are displayed:

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

         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. And queries, using the & operator. All lines in which both queries match are displayed.

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

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

Moreover, these elements can be combined, as in

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

     fiery & bird | wind

Our system will not be sophisticated enough to read these expressions. Instead, we'll build them up inside a C++ program. Hence, we'll evaluate compound expressions such as this example using normal C++ precedence rules. The evaluation of this query will match a line in which fiery and bird appear or one in which wind appears. It will not match a line on which fiery or bird appears alone:

我们的系统没有复杂到能够读这些表达式。我们将在 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,

Our output will print the query, using parentheses to indicate the way in which the query was interpreted. As with our original implementation, our system must be smart enough not to display the same line more than once.

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

15.9.1. An Object-Oriented Solution

15.9.1. 面向对象的解决方案

We might think that we could use the TextQuery class from page 382 to represent our word queries. We might then derive our other queries from that class.

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

However, this design would be flawed. Conceptually, a "not" query is not a kind of word query. Instead, a not query "has a" query (word query or any other kind of query) whose value it negates.

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

This observation suggests that we model our different kinds of queries as independent classes that share a common base class:

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

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

Instead of inheriting from TextQuery, we will use that class to hold the file and build the associated word_map. We'll use the query classes to build up expressions that will ultimately run queries against the file in a TextQuery object.

我们不继承 TextQuery,而是使用 TextQuery 类保存文件并建立相关的 word_map,使用查询类建立表达式,这些表达式最终对 TextQuery 对象中的文件运行查询。

Abstract Interface Class
抽象接口类

We have identified four kinds of query classes. These classes are conceptually siblings. Each class shares the same abstract interface, which suggests that we'll need to define an abstract base class (Section 15.6, p. 595) to represent the operations performed by a query. We'll name our abstract class Query_base, indicating that its role is to serve as the root of our query hierarchy.

已经识别出四各查询类,这些类在概念上是兄弟类。它们共享相同的抽象接口,这暗示我们定义一个抽象基类(第 15.6 节)以表示由查询执行的操作。将该抽象基类命名为 Query_base,以指出它的作用是作为查询继承层次的根。

We'll derive WordQuery and NotQuery directly from our abstract base. The AndQuery and OrQuery classes share one property that the other classes in our system do not: They each have two operands. To model this fact, we'll add another abstract class, named BinaryQuery, to our hierarchy to represent queries with two operands. The AndQuery and OrQuery classes will inherit from the BinaryQuery class, which in turn will inherit from Query_base. These decisions give us the class design represented in Figure 15.3 on the next page.

直接从抽象基类派生 WordQueryNotQuery 类,WordQueryNotQuery 类具有系统中其他类所没有的一个性质:它们都有两个操作数。要为此建立模型,将在继承层次中增加另一个名为 BinaryQuery 的抽象类,表示带两个操作数的查询。WordQueryNotQuery 类将继承 BinaryQuery 类,BinaryQuery 类继承 Query_base 类。这些决定得出了图 15.3 所示的类设计。

Figure 15.3. Query_base Inheritance Hierarchy
图 15.3. Query_base 继承层次


Operations
操作

Our Query_base classes exist mostly to represent kinds of queries; they do little actual work. We'll reuse our TextQuery class to store the file, build the query map, and search for each word. Our query types need only two operations:

Query_base 类的存在主要是为了表示查询类型,不做实际工作。我们将重用 TextQuery 类以存储文件、建立查询以及查找每个单词。查询类型只需要两个操作:

  1. An eval operation to return the set of matching line numbers. This operation takes a TextQuery object on which to execute the query.

    eval 操作,返回匹配行号编号的集合。该操作接受 TextQuery 对象,在 TextQuery 对象上执行查询。

  2. A display operation that takes a reference to an ostream and prints the query that a given object performs on that stream.

    display 操作,接受 ostream 引用并打印给定对象在该 ostream 上执行的查询。

We'll define each of these operations as pure virtual functions (Section 15.6, p. 595) in the Query_base class. Each of our derived classes will have to define its own version of these functions.

我们将这些操作定义为 Query_base 中的纯虚函数(第 15.6 节),每个派生类都必须对这些函数定义自己的版本。

15.9.2. A Valuelike Handle

15.9.2. 值型句柄

Our program will deal with evaluating queries, not with building them. However, we need to be able to create queries in order to run our program. The simplest way to do so is to write C++ expressions to create queries directly. For example, we'd like to be able to write code such as

程序将处理计算查询,而不建立查询,但是,需要能够创建查询以便运行程序。最简单的办法是编写 C++ 表达式直接创建查询,例如,可以编写这样的代码:

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

to generate the compound query previously described.

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

This problem description implicitly suggests that user-level code won't use our inherited classes directly. Instead, we'll define a handle class named Query, which will hide the hierarchy. User code will execute in terms of the handle; user code will only indirectly manipulate Query_base objects.

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

As with our Sales_item handle, our Query handle will hold a pointer to an object of a type in an inheritance hierarchy. The Query class will also point to a use count, which we'll use to manage the object to which the handle points.

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

In this case, our handle will completely hide the underlying inheritance hierarchy. Users will create and manipulate Query_base objects only indirectly through operations on Query objects. We'll define three overloaded operators on Query objects and a Query constructor that will dynamically allocate a new Query_base object. Each operator will bind the generated Query_base object to a Query handle: The & operator will generate a Query bound to a new AndQuery; the | operator will generate a Query bound to a new OrQuery; and the ~ operator will generate a Query bound to a new NotQuery. We'll give Query a constructor that takes a string. This constructor will generate a new WordQuery.

在这种情况下,句柄将完全屏蔽基础继承层次,用户将只能间接地通过 Query 对象的操作创建和操纵 Query_base 对象。我们将定义 Query 对象的三个重载操作符以及 Query构造函数,Query 构造函数将动态分配新的 Query_base 对象。每个操作符将生成的对象绑定到 Query 句柄:& 操作符将生成绑定到新的 AndQuery 对象的 Query 对象;| 操作符将生成绑定到新的 OrQuery 对象的 Query 对象;~ 操作符将生成绑定到新的 NotQuery 对象的 Query 对象。给 Query 定义一个参数为 string 对象的构造函数,该构造函数将生成新的 WordQuery

The Query class will provide the same operations as the Query_base classes: eval to evaluate the associated query, and display to print the query. It will define an overloaded output operator to display the associated query.

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

Table 15.1. Query Program Design: A Recap
表 15.1. 查询程序设计:扼要重述

TextQuery

Class that reads a specified file and builds an associated lookup map. That class provides a query_text operation that takes a string argument and returns a set of line numbers on which the argument appears.

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

Query_base

Abstract base class for the query classes.

查询类的抽象基类。

Query

Use-counted handle class, which points to an object of a type derived from Query_base.

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

WordQuery

Class derived from Query_base that looks for a given word.

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

NotQuery

Class derived from Query_base that returns the set of lines in which its Query operand does not appear.

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

BinaryQuery

Abstract base type derived from Query_base that represents queries with two Query operands.

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

OrQuery

Class derived from BinaryQuery that returns the union of the line numbers in which its two operands appear.

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

AndQuery

Class derived from BinaryQuery that returns the intersection of the line numbers in which its two operands appear.

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

q1 & q2

Returns a Query bound to a new AndQuery object that holds q1 and q2.

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

q1 | q2

Returns a Query bound to a new OrQuery object that holds q1 and q2.

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

~q

Returns a Query bound to a new NotQuery object that holds q.

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

Query q(s)

Binds the Query q to a new WordQuery that holds the string s.

Query q 绑定到保存 string s 的新 WordQuery 对象。


Our Design: A Recap
我们的设计:扼要重述

It is often the case, especially when new to designing object-oriented systems, that understanding the design is the hardest part. Once we're comfortable with the design, the implementation flows naturally.

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



It is important to realize that much of the work in this application consists of building objects to represent the user's query. As illustrated in Figure 15.4 on the following page, an expression such as

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

Figure 15.4. Objects Created by Query Expressions
图 15.4. Query 表达式创建的对象


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

generates ten objects: five Query_base objects and their associated handles. The five Query_base objects are three WordQuerys, an OrQuery, and an AndQuery.

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

Once the tree of objects is built up, evaluating (or displaying) a given query is basically a process (managed for us by the compiler) of following these links, asking each object in the tree to evaluate (or display) itself. For example, if we call eval on q (i.e., on the root of this tree), then eval will ask the OrQuery to which it points to eval itself. Evaluating this OrQuery calls eval on its two operands, which in turn calls eval on the AndQuery and WordQuery that looks for the word wind, and so on.

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

     Objects Created by the Expression
     Query("fiery") & Query("bird") | Query("wind");

Exercises Section 15.9.2

Exercise 15.39:

Given that s1, s2, s3 and s4 are all strings, determine what objects are created in the following uses of the Query class:

给定 s1s2s3s4 均为 string 对象,确定下述 Query 类的使用创建什么对象:

     (a) Query(s1) | Query(s2) & ~ Query(s3);
     (b) Query(s1) | (Query(s2) & ~ Query(s3));
     (c) (Query(s1) & (Query(s2)) | (Query(s3) & Query(s4)));


15.9.3. The Query_base Class

15.9.3. Query_base

Now that we've explained our design, we'll start our implementation by defining the Query_base class:

现在我们的设计已经解释清楚,该开始实现了。首先来定义 Query_base 类:

     // private, abstract class acts as a base class for concrete query types
     class Query_base {
         friend class Query;
     protected:
         typedef TextQuery::line_no line_no;
         virtual ~Query_base() { }
     private:
         // eval returns the |set| of lines that this Query matches
         virtual std::set<line_no>
             eval(const TextQuery&) const = 0;
         // display prints the query
         virtual std::ostream&
             display(std::ostream& = std::cout) const = 0;
     };

The class defines two interface members: eval and display. Both are pure virtual functions (Section 15.6, p. 595), which makes this class abstract. There will be no objects of type Query_base in our applications.

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

Users and the derived classes will use the Query_base class only through the Query handle. Therefore, we made our Query_base interface private. The (virtual) destructor (Section 15.4.4, p. 587) and the typedef are protected so that the derived types can access these members. The destructor is used (implicitly) by the derived-class destructors and so must be accessible to them.

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

We grant friendship to the Query handle class. Members of that class will call the virtuals in Query_base and so must have access to them.

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

15.9.4. The Query Handle Class

15.9.4. Query 句柄类

Our Query handle will be similar to the Sales_item class in that it will hold a pointer to the Query_base and a pointer to a use count. As in the Sales_item class, the copy-control members of Query will manage the use count and the Query_base pointer.

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

Unlike the Sales_item class, Query will provide the only interface to the Query_base hierarchy. Users will not directly access any of the members of Query_base or its derived classes. This design decision leads to two differences between Query and Sales_item. The first is that the Query class won't define overloaded versions of dereference and arrow operators. The Query_base class has no public members. If the Query handle defined the dereference or arrow operators, they would be of no use! Any attempt to use those operators to access a Query_base member would fail. Instead, Query must define its own versions of the Query_base interface functions eval and display.

Sales_item 类不同的是,Query 类将只为 Query_base 继承层次提供接口。用户将不能直接访问 Query 或其派生类的任意成员,这一设计决定导致 QuerySales_item 之间存在两个区别。第一个区别是,Query 类将不定义解引用操作符和箭头操作符的重载版本。Query_base 类没有 public 成员,如果 Query 句柄定义了解引用操作符和箭头操作符,它们将没有用处!使用那些操作符访问成员的任何尝试都将失败,相反,Query 类必须定义接口函数 evaldisplay 的自身版本。

The other difference results from how we intend objects of the hierarchy to be created. Our design says that objects derived from Query_base will be created only through operations on the Query handle. This difference results in different constructors being required for the Query class than were used in the Sales_item handle.

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

The Query Class
Query

Given the preceeding design, the Query class itself is quite simple:

按照前面的的设计,Query 类本身相当简单:

     // handle class to manage the Query_base inheritance hierarchy
     class Query {
         // these operators need access to the Query_base* constructor
         friend Query operator~(const Query &);
         friend Query operator|(const Query&, const Query&);
         friend Query operator&(const Query&, const Query&);
     public:
         Query(const std::string&); // builds a new WordQuery
         // copy control to manage pointers and use counting
         Query(const Query &c): q(c.q), use(c.use) { ++*use; }
         ~Query() { decr_use(); }
         Query& operator=(const Query&);
     // interface functions: will call corresponding Query_base operations
     std::set<TextQuery::line_no>
       eval(const TextQuery &t) const { return q->eval(t); }
     std::ostream &display(std::ostream &os) const
                             { 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 decr_use()
         { if (--*use == 0) { delete q; delete use; } }
     };

We start by naming as friends the operators that create Query objects. We'll see shortly why these operators need to be friends.

首先指定创建 Query 对象的操作符为友元,我们将很快看快看到为什么需要将这些操作符设为友元。

In the public interface for Query, we declare, but cannot yet define, the constructor that takes a string. That constructor creates a WordQuery object, so we cannot define the constructor until we have defined the WordQuery class.

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

The next three members handle copy control and are the same as the corresponding members of the Sales_item class.

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

The last two public members represent the interface for Query_base. In each case, the Query operation uses its Query_base pointer to call the respective Query_base operation. These operations are virtual. The actual version that is called is determined at run time and will depend on the type of the object to which q points.

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

The private implementation of Query includes a constructor that takes a pointer to a Query_base object. This constructor stores in q the pointer it is given and allocates a new use counter, which it initializes to one. This constructor is private because we don't intend general user code to define Query_base objects. Instead, the constructor is needed for the operators that create Query objects. Because the constructor is private, the operators had to be made friends.

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

The Query Overloaded Operators
Query 重载操作符

The |, & and ~ operators create OrQuery, AndQuery, and NotQuery objects, respectively:

|&~ 操作符分别创建 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);
     }

Each of these operations dynamically allocates a new object of a type derived from Query_base. The return (implicitly) uses the Query constructor that takes a pointer to a Query_base to create the Query object from the Query_base pointer that the operation allocates. For example the return statement in the ~ operator is equivalent to

每个操作符动态分配 Query_base 派生类型的新对象,return 语句(隐式)使用接受 Query_base 指针的 Query 构造函数,用操作分配的 Query_base 指针创建 Query 对象。例如,~ 操作符中的 return 语句等价于:

     // allocate a new Not Query object
     // convert the resulting pointer to NotQuery to a pointer to Query_base
     Query_base *tmp = new NotQuery(expr);

     return Query(tmp); // use Query constructor that takes a pointer to Query_base

There is no operator to create a WordQuery. Instead, we gave our Query class a constructor that takes a string. That constructor generates a WordQuery to look for the given string.

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

The Query Output Operator
Query 输出操作符

We'd like users to be able to print Querys using the normal (overloaded) output operator. However, we also need the print operation to be virtualprinting a Query should print the Query_base object to which the Query points. There's only one problem: only member functions can be virtual, but the output operator cannot be a member of the Query_base classes (Section 14.2.1, p. 514).

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

To obtain the necessary virtual behavior, our Query_base classes defined a virtual display member, which the Query output operator will use:

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

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

When we write

如果编写

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

the Query output operator is invoked. That operator calls

将调用 Query 输出操作符,该操作符调用

     q.display(os)

with q referring to the Query object that points to this AndQuery, an dos bound to cout. When we write

其中,q 引用指向该 AndQuery 对象的 Query 对象,os 绑定到 cout。如果编写

     Query name(sought);
     cout << "\nExecuted Query for: " << name << endl;

the WordQuery instance of display is called. More generally, a call

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

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

invokes the instance of display associated with the object that query addresses at that point in the execution of our program.

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

15.9.5. The Derived Classes

15.9.5. 派生类

We next need to implement our concrete query classes. The one interesting part about these classes is how they are represented. The WordQuery class is most straightforward. Its job is to hold the search word.

下面要实现具体的查询类。关于这些类,一个有趣的部分是如何表示它们。WordQuery 类最直接,它的工作是保存要查找的单词。

The other classes operate on one or two Query operands. A NotQuery negates the result of another Query. Both AndQuery and OrQuery have two operands, which are actually stored in their common base class, BinaryQuery.

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

In each of these classes, the operand(s) could be an object of any of the concrete Query_base classes: A NotQuery could be applied to a WordQuery, an AndQuery, an OrQuery, or another NotQuery. To allow this flexibility, the operands must be stored as pointers to Query_base that might point to any one of the concrete Query_base classes.

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

However, rather than storing a Query_base pointer, our classes will themselves use the Query handle. Just as user code is simplified by using a handle, we can simplify our own class code by using the same handle class. We'll make the Query operand const because once a given Query_base object is built, there are no operations that can change the operand(s).

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

Now that we know the design for these classes, we can implement them.

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

The WordQuery Class
WordQuery

A WordQuery is a kind of Query_base that looks for a specified word in a given query map:

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

     class WordQuery: public Query_base {
         friend class Query; // Query uses the WordQuery constructor
         WordQuery(const std::string &s): query_word(s) { }
         // concrete class: WordQuery defines all inherited pure virtual functions
         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; // word for which to search
      };

Like Query_base, WordQuery has no public members; WordQuery must make Query a friend to allow Query to access the WordQuery constructor.

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

Each of the concrete query classes must define the inherited pure virtual functions. The WordQuery operations are simple enough to define in the class body. The eval member calls the query_text member of its TextQuery parameter passing it the string that was used to create this WordQuery. To display a WordQuery, we print the query_word.

每个具体的查询类必须定义继承的纯虚函数。WordQuery 类的操作足够简单,可以定义在类定义中。eval 成员调用其 TextQuery 形参的 query_word 成员,将用于创建该 WordQuery 对象的 string 对象传给它。要 display 一个 WordQuery 对象,就打印 query_word 对象。

The NotQuery Class
NotQuery

A NotQuery holds a const Query, which it negates:

NotQuery 对象保存一个 const Query 对象,对它求反:

     class NotQuery: public Query_base {
         friend Query operator~(const Query &);
         NotQuery(Query q): query(q) { }
          // concrete class: NotQuery defines all inherited pure virtual functions
          std::set<line_no> eval(const TextQuery&) const;
          std::ostream& display(std::ostream &os) const
                { return os << "~(" << query << ")"; }
          const Query query;
     };

The Query overloaded ~ operator is made a friend to allow that operator to create a new NotQuery object. To display a NotQuery, we print the ~ symbol followed by the underlying Query. We parenthesize the output to ensure that precedence is clear to the reader.

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

The use of the output operator in the display operation is ultimately a virtual call to a Query_base object:

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


     // uses the Query output operator, which calls Query::display
     // that funtion makes a virtual call to Query_base::display
     { return os << "~(" << query << ")"


The eval member is complicated enough that we will implement it outside the class body. The eval function appears in Section 15.9.6 (p. 620).

eval 成员比较复杂,我们将在类定义体之外实现它,eval 函数见第 15.9.6 节

The BinaryQuery Class
BinaryQuery

The BinaryQuery class is an abstract class that holds the data needed by the two query types, AndQuery and OrQuery, that operate on two operands:

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

     class BinaryQuery: public Query_base {
     protected:
         BinaryQuery(Query left, Query right, std::string op):
               lhs(left), rhs(right), oper(op) { }
         // abstract class: BinaryQuery doesn't define eval
         std::ostream& display(std::ostream &os) const
         { return os << "(" << lhs << " " << oper << " "
                                  << rhs << ")"; }
         const Query lhs, rhs; // right- and left-hand operands
         const std::string oper; // name of the operator
      };

The data in a BinaryQuery are the two Query operands and the operator symbol to use when displaying the query. These data are all declared const, because the contents of a query should not change once it has been constructed. The constructor takes the two operands and the operator symbol, which it stores in the appropriate data members.

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

To display a BinaryOperator, we print the parenthesized expression consisting of the left-hand operand, followed by the operator, followed by the right-hand operand. As when we displayed a NotQuery, the overloaded << operator that is used to print left and right ultimately makes a virtual call to the underlying Query_base display.

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

The BinaryQuery class does not define the eval function and so inherits a pure virtual. As such, BinaryQuery is also an abstract class, and we cannot create objects of BinaryQuery type.

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



The AndQuery and OrQuery Classes
AndQueryOrQuery

The AndQuery and OrQuery classes are nearly identical:

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

     class AndQuery: public BinaryQuery {
         friend Query operator&(const Query&, const Query&);
         AndQuery (Query left, Query right):
                               BinaryQuery(left, right, "&") { }
         // concrete class: And Query inherits display and defines remaining pure virtual
         std::set<line_no> eval(const TextQuery&) const;
     };
         class OrQuery: public BinaryQuery {
             friend Query operator|(const Query&, const Query&);
             OrQuery(Query left, Query right):
                         BinaryQuery(left, right, "|") { }
             // concrete class: OrQuery inherits display and defines remaining pure virtual
             std::set<line_no> eval(const TextQuery&) const;
     };

These classes make the respective operator a friend and define a constructor to create their BinaryQuery base part with the appropriate operator. They inherit the BinaryQuery definition of display, but each defines its own version of the eval function.

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

Exercises Section 15.9.5

Exercise 15.40:

For the expression built in Figure 15.4 (p. 612)

图 15.4 中建立的表达式:

  1. List the constructors executed in processing this expression.

    列出处理这个表达式所执行的构造函数。

  2. List the calls to display and to the overloaded << operator that are made in executing cout << q.

    列出执行 cout << q 所调用的 display 函数和重载的 << 操作符。

  3. List the calls to eval made when evaluating q.eval.

    列出计算 q.eval 时所调用的 eval 函数。


15.9.6. The eval Functions

15.9.6. eval 函数

The heart of the query class hierarchy are the eval virtual functions. Each of these functions calls eval on its operand(s) and then applies its own logic: The AndQuery eval operation returns the union of the results of its two operands; OrQuery returns the intersection. The NotQuery is more complicated: It must return the line numbers not in its operand's set.

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

OrQuery::eval

An OrQuery merges the set of line numbers returned by its two operandsits result is the union of the results for its two operands:

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

     // returns union of its operands' result sets
     set<TextQuery::line_no>
     OrQuery::eval(const TextQuery& file) const
     {
             // virtual calls through the Query handle to get result sets for the operands
             set<line_no> right = rhs.eval(file),
                         ret_lines = lhs.eval(file); // destination to hold results
             // inserts the lines from right that aren't already in ret_lines
             ret_lines.insert(right.begin(), right.end());

             return ret_lines;
     }

The eval function starts by calling eval on each of its Query operands. Those calls call Query::eval, which in turn makes a virtual call to eval on the underlying Query_base object. Each of these calls yields a set of line numbers in which its operand appears. We then call insert on ret_lines, passing a pair of iterators denoting the set returned from evaluating the right-hand operand. Because ret_lines is a set, this call adds the elements from right that are not also in left into ret_lines. After the call to insert, ret_lines contains each line number that was in either of the left or right sets. We complete the function by returning ret_lines.

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

AndQuery::eval

The AndQuery version of eval uses one of the library algorithms that performs setlike operations. These algorithms are described in the Library Appendix, in Section A.2.8 (p. 821):

AndQueryeval 版本使用了完成集合式操作的一个标准库算法。标准库附录中说明了这些算法,见 A.2.8 节

     // returns intersection of its operands' result sets
     set<TextQuery::line_no>
     AndQuery::eval(const TextQuery& file) const
     {
          // virtual calls through the Query handle to get result sets for the operands
          set<line_no> left = lhs.eval(file),
                             right = rhs.eval(file);
          set<line_no> ret_lines; // destination to hold results
          // writes intersection of two ranges to a destination iterator
          // destination iterator in this call adds elements to ret
          set_intersection(left.begin(), left.end(),
                        right.begin(), right.end(),
                        inserter(ret_lines, ret_lines.begin()));
          return ret_lines;
     }

This version of eval uses the set_intersection algorithm to find the lines in common to both queries: That algorithm takes five iterators: The first four denote two input ranges, and the last denotes a destination. The algorithm writes each element that is in both of the two input ranges into the destination. The destination in this call is an insert iterator (Section 11.3.1, p. 406) which inserts new elements into ret_lines.

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

NotQuery::eval

NotQuery finds each line of the text within which the operand is not found. To support this function, we need the TextQuery class to add a member to return the size of the file, so that we can know what line numbers exist.

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

     // returns lines not in its operand's result set
     set<TextQuery::line_no>
     NotQuery::eval(const TextQuery& file) const
     {
          // virtual call through the Query handle to eval
          set<TextQuery::line_no> has_val = query.eval(file);
          set<line_no> ret_lines;
          // for each line in the input file, check whether that line is in has_val
         // if not, add that line number to 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;
     }

As in the other eval functions, we start by calling eval on this object's operand. That call returns the set of line numbers on which the operand appears. What we want is the set of line numbers on which the operand does not appear. We obtain that set by looking at each line number in the input file. We use the size member that must be added to TextQuery to control the for loop. That loop adds each line number to ret_lines that does not appear in has_val. Once we've processed all the line numbers, we return ret_lines.

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

Exercises Section 15.9.6

Exercise 15.41:

Implement the Query and Query_base classes, and add the needed size operation to the TextQuery class from Chapter 10. Test your application by evaluating and printing a query such as the one in Figure 15.4 (p. 612).

实现 Query 类和 Query_base 类,并为第十章TextQuery 类增加需要的 size 操作。通过计算和打印如图 15.4 所示的查询,测试你的应用程序。

Exercise 15.42:

Design and implement one of the following enhancements:

设计并实现下述增强中的一个:

  1. Introduce support for evaluating words based on their presence within the same sentence rather than the same line.

    引入基于同一句子而不是同一行计算单词的支持。

  2. Introduce a history system in which the user can refer to a previous query by number, possibly adding to it or combining it with another.

    引入历史系统,用户可以用编号查阅前面的查询,并可以在其中增加内容或与其他查询组合。

  3. Rather than displaying the count of matches and all the matching lines, allow the user to indicate a range of lines to display, both for intermediate query evaluation and the final query.

    除了显示匹配数目和所有匹配行之外,允许用户对中间查询计算和最终查询指出要显示的行的范围。


Team LiB
Previous Section Next Section