C++ Primer文本查询程序

​ 此为C++ Primer中第十二章中的一个文本查询程序，我想通过自己的分析来更加透彻的理解整个程序的设计，于是将此节单独作为一章重点去看：

文本查询程序

设计思路

需求

• 当程序读取输入文件时，它必须记住单词出现的每一行。因此，程序需要逐行读取输入文件，并将每一行分解为独立的单词
• 当程序生成输出时，
  • 它必须能提取每个单词所关联的行号
  • 行号必须按升序出现且无重复
  • 它必须能打印给定行号中的文本。

例子

当输入element时，得到的是：

分析

​ 首先看这里我认为最重要一个对应关系，单词→行号。每一个单词都有n行与之对应，那么容易想到的方法是用容器将每个单词的行号记录下来，由于每个行号只出现一次且需要升序排列，所以最优解就是使用set容器，接着如何实现通过行号找到那一行文字呢？我们可以想到使用vector<string>按行号保存文本。此外使用一个map可以将单词与它对应的set容器绑定起来，就可以实现，单词对应行号，行号对应文本。

​ 还有一个问题是：如何建立起这个map和set，我们定义一个函数，命名为istringstream，思路大致是从vector读取每个元素（每行文本），访问每个单词前首先判断map中没有这个单词，如果有：就将对应的set中加入这一次遍历的下标（即行号），如果没有：就创建一个set，并将单词与set加入map中。

大致的类

​ 我们需要将这些结构与操作串联起来，从定义一个保存输入文件的类开始，将类命名为TextQuery，它包含一个vector和一个map。我们用这个类来构造vector和map，并且执行查询操作。

​ 之后如果我们查到了到底要返回什么呢？返回那么一大串的东西最好的方法就是定义另一个类，这个类内应该有一个打印操作。我们将它命名为QueryResult。

类之间的数据共享

​ 再仔细看一下这个QueryResult类，由于我们必须要返回文本，所以要用到提到过的保存整个文本的vector，然而它是第一类的成员，我们拷贝一份貌似没有必要，因为我们只需要调用其中很小的一部分，这样会造成大量的浪费，那么使用一个类内的迭代器（或指针）可以嘛？答案也是不行，因为如果第一个类在第二个类之前销毁，那么打印操作就会访问一个不存在的对象中的数据。最好的办法就是使用我们“最牛逼”的shared_ptr来反映数据结构中的共享关系。

设计类之前先使用类

​ 当我们设计一个类时，在真正实现成员之前先编写程序使用这个类，是一种非常有用的方法。通过这种方法，可以看到类是否具有我们所需要的操作。例如，下面的程序使用了TextQuery和 QueryResult类。这个函数接受一个指向要处理的文件的ifstream，并与用户交互，打印给定单词的查询结果

void runQueries(ifstream &infile)
{
	//infile是一个ifstream，指向我们要处理的文件
	TextQuery tq(infile); 	//保存文件并建立查询map
	//与用户交互:提示用户输入要查询的单词，完成查询并打印结果
	while (true){
		cout << "enter word to look for, or q to quit: ";
		string s;
		//若遇到文件尾或用户输入了'q'时循环终止
		if(!(cin >> s) || s == "q") break;
		//指向查询并打印结果
		print(cout, tq.query(s)) << endl;
	}
}

类的定义

TextQuery框架

​ 首先是TextQuery，用用户提供的一个istream读取文件，类中应该还有query操作，接受string，返回QueryResult表示string出现的行。我们创建一个头文件命名为textquery，在其中输入：

#ifndef TEXTQUERY_H
#define TEXTQUERY_H

#include <vector>
#include <string>
#include <memory>
#include <map>
#include <set>
using std::vector;
using std::string;
using std::shared_ptr;

class QueryResult;// 为了定义函数query的返回类型，这个定义是必需的
class TextQuery {
public:
	//简化行下标
	using line_no = vector<string>::size_type;
	//通过用户提供的文本的构造函数
	TextQuery(std::ifstream&);
	//返回查询结果的函数，由于只是查询所以应该加上const
	QueryResult query(const string&) const;
private:
	//输入的文件
	shared_ptr<vector<string>> file;
	//每个单词到它所在的行号的集合的映射
	std::map<string, shared_ptr<std::set<line_no>>> wm;
};

#endif

​ 至于这里为什么出现这么多的std，而不是直接引入整个命名空间：在头文件这样做是非常危险的，由于C++头文件通常与源文件分开存放，对于不知道这个头文件里有什么的用户来说，使用这个头文件就有可能会导致很多的命名冲突。这里建议在任何文件中都不要这样做。

QueryResult框架

​ QueryResult类有三个数据成员：一个string，保存查询单词：一个shared_ptr，指向保存输入文件的vector；一个shared ptr，指向保存单词出现行号的set。它唯一的一个成员函数是一个构造函数，初始化这三个数据成员。在刚才的类之后，紧接着写入以下代码：

class QueryResult {
    //将ostream声明为友元函数，之后用来打印结果
	friend std::ostream& print(std::ostream&, const QueryResult&);
public:
    //构造函数
	QueryResult(string s,
		shared_ptr<set<TextQuery::line_no>> p,
		shared_ptr<vector<string>> f) :
		sought(s), lines(p), file(f) {}
private:
    // 查询单词
	string sought; 							
    //出现的行号
	shared_ptr<set<TextQuery::line_no>> lines;
    //输入文件
	shared_ptr<vector<string>> file;		 
};

这里为什么不在TextQuery类之前那里写呢？因为这个类中我们用到了TextQuery中的line_no，这两个类其实是你中有我，我中有你的关系，所以我们在开头需要一个声明，在之后去定义他。

类的实现

TextQuery构造函数

接下来是类的实现，我们创建一个源文件，取名为textquery.cpp，首先是构造函数，直接写入代码：

//读取输入文件并建立单词到行号的映射
TextQuery::TextQuery(std::ifstream& is) : file(new vector<string>)
{
	string text;
	//对文件中每一行
	while (getline(is, text)) {
		//保存此行文本
		file->push_back(text);
		//当前行号
		int n = file->size() - 1;
		//将行文本分解为单词
		std::istringstream line(text);
		string word;
		//对行中每个单词
		while (line >> word) {
			//如果单词不在 wm 中，以之为下标在wm中添加一项
			// lines是一个shared_ptr
			auto& lines = wm[word];
			if (!lines)
				//分配一个新的set
				lines.reset(new set<line_no>);
			lines->insert(n);//将此行号插入set中
		}
	}
}

这里可以看到在函数体之前就已经为file分配了动态内存，同时由于file是指针类型这里需要使用->来使用push函数，之后使用istringstream处理当前这一行的字符，按空格存入word内，在第二个while循环中，首先定义lines获取在map中的这个单词的set容器，注意这里line是一个只能指针类型，由于有可能是第一次录入改单词，则需要对line进行判断，若不存在则需要新分配一个set，这里同样需要动态的分配内存。最后不论一定要将则一行的行号传入这个set容器中。

query函数

它接受一个string参数，用它在map中对应行号，如果找到就构造一个QueryResult返回。这里有一个问题是如果没有找到返回什么呢？我们可以定义一个局部的static对象，它指向空的行号set的shared_ptr，没有找到就返回它：

QueryResult TextQuery::query(const string& sought) const {
	//如果未找到sought，我们将返回一个指向此set的指针
	static shared_ptr<set<line_no>> nodata(new set<line_no>);
	//使用find而不是下标运算符来查找单词，避免将单词添加到wm中!
	auto loc = wm.find(sought);
	if (loc == wm.end())
		return QueryResult(sought, nodata, file);//未找到
	else
		return QueryResult(sought, loc->second, file);
}

print函数

//如果ctr的值大于1，返回word的复数形式
string make_plural(size_t ctr, const string &word, const string &ending)
{
	return (ctr > 1) ? word + ending : word;
}

std::ostream& print(std::ostream& os, const QueryResult& qr) {
	//如果找到了单词，打印出现次数和所有出现的位置
	os << qr.sought << " occurs " << qr.lines->size() << " "
		<< make_plural(qr.lines->size(), "time", "s") << std::endl;
	for (auto num : *qr.lines)
		//避免行号从0开始给用户带来的困惑
		os << "\t (line " << num + 1 << ")"
		//使用标准库:文本查询程序
		<< *(qr.file->begin() + num) << std::endl;
	return os;
}

文本查询程序2.0

利用C++继承与多态的性质改进该类， 以实现更多功能。

新的需求

• 单词查询，用于得到匹配某个给定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 l 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 f1owing red hair.

• 此外，我们还希望能够混合使用这些运算符，比如:fiery & bird l wind

  Executing Query for: ((fiery & bird)l wind) ( (fiery & bird) l 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 ,

解决方案

我们可以将集中不同的查询建模成相互独立的类，它们共享一个公共基类：

wordQuery		// Daddy
NotQuery		// ~Alice
orQuery			// hair l Alice
AndQuery		// hair & Alice

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

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

关键概念:继承与组合

继承体系的设计本身是一个非常复杂的问题,已经超出了本书的范围。然而,有一条设计准则非常重要也非常基础，每个程序员都应该熟悉它。

当我们令一个类公有地继承另一个类时，派生类应当反映与基类的“是一种(IsA)”关系。在设计良好的类体系当中，公有派生类的对象应该可以用在任何需要基类对象的地方。

类型之间的另一种常见关系是“有一个(Has A)”关系，具有这种关系的类暗含成员的意思。

在我们的书店示例中，基类表示的是按规定价格销售的书籍的报价。Bulk_quote“是一种”报价结果，只不过它使用的价格策略不同。我们的书店类都“有一个”价格成员和ISBN成员。

抽象基类

由于这四种查询并不存在继承关系，从概念上来说互为熊底，它们都共享同一个接口，我们定义一个抽象基类Query_base，并把eval和rep定义为纯虚函数。

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

我们的程序将致力于计算查询结果，而非仅仅构建查询的体系。为了使程序能正常运行，我们必须首先创建查询命令，最简单的办法是编写C++表达式。例如，可以编写下面的代码来生成之前描述的复合查询:

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

用户不会直接使用这些类，而是使用Query保存一个Query_base指针，用户将通过 Query 对象的操作间接地创建并处理Query _base对象。我们定义Query对象的三个重载运算符以及一个接受string参数的Query构造函数，这些函数动态分配一个新的Query base派生类的对象:

• &运算符生成一个绑定到新的AndQuery对象上的Query对象;
• |运算符生成一个绑定到新的orQuery对象上的Query对象;
• ~运算符生成一个绑定到新的NotQuery对象上的Query对象;
• 接受string 参数的Query构造函数生成一个新的wordQuery对象。

Query_base类和Query类

首先定义Query_base类

//这是一个抽象基类，具体的查询类型从中派生，所有成员都是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;
};

把所有操作都纯虚函数，因此Query_base是一个抽象基类，因为不直接使用它，所有没有public成员。

Query类

它负责提供外界的接口，并隐藏继承体系。每个Query对象都含有一个指向Query_base对象的智能指针。

接受一个string参数的Query构造函数将创建一个新的wordQuery对象，然后将它的 shared_ prt成员绑定到这个新创建的对象上。&、|和~运算符分别创建AndQuery、OrQuery和 NotQuery对象，这些运算符将返回一个绑定到新创建的对象上的Query对象。

//这是一个管理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&);															
	//构建一个新的wordouery
	//接口函数:调用对应的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;
};

Query 的输出运算符

输出运算符可以很好地解释我们的整个查询系统是如何工作的:std: :ostream &
operator<<(std: :ostream &os,const Query &query)
/ / Query: :rep通过它的Query base指针对rep ()进行了虚调用return os<<query.rep (;
当我们打印一个 Query时，输出运算符调用Query类的公有rep成员。运算符函数通过指针成员虚调用当前Query所指对象的rep成员。也就是说，当我们编写如下代码时:
Query andq = Query (sought1) &Query (sought2 );
cout << andq << endl;
输出运算符将调用andq 的 Query: :rep,而 Query: :rep通过它的Query base指针虚调用Query _base版本的rep函数。因为andq指向的是一个AndQuery对象，所以本次的函数调用将运行AndQuery: : rep。