C++ Series

【C++基础】第六十八课：[动态内存]使用标准库：文本查询程序

文本查询程序

Posted by x-jeff on April 8, 2023

【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。

1.使用标准库：文本查询程序

我们将实现一个简单的文本查询程序，作为标准库相关内容学习的总结。我们的程序允许用户在一个给定文件中查询单词。查询结果是单词在文件中出现的次数及其所在行的列表。如果一个单词在一行中出现多次，此行只列出一次。行会按照升序输出——即，第7行会在第9行之前显示，依此类推。

例如，我们读入一个文件，在其中寻找单词element。输出结果的前几行应该是这样的：

1
2
3
4
5
6

element occurs 112 times
	(line 36) A set element contains only a key;
	(line 158) operator creates a new element
	(line 160) Regardless of whether the element
	(line 168) When we fetch an element from a map, we
	(line 214) If the element is not found, find returns

2.文本查询程序设计

开始一个程序的设计的一种好方法是列出程序的操作。了解需要哪些操作会帮助我们分析出需要什么样的数据结构。从需求入手，我们的文本查询程序需要完成如下任务：

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

利用很多标准库设施，我们可以很漂亮地实现这些要求：

  • 我们将使用一个vector<string>来保存整个输入文件的一份拷贝。输入文件中的每行保存为vector中的一个元素。当需要打印一行时，可以用行号作为下标来提取行文本。
  • 我们使用一个istringstream来将每行分解为单词。
  • 我们使用一个set来保存每个单词在输入文本中出现的行号。这保证了每行只出现一次且行号按升序保存。
  • 我们使用一个map来将每个单词与它出现的行号set关联起来。这样我们就可以方便地提取任意单词的set。

我们的解决方案还使用了shared_ptr。

2.1.数据结构

虽然我们可以用vector、set和map来直接编写文本查询程序，但如果定义一个更为抽象的解决方案，会更为有效。我们将从定义一个保存输入文件的类开始，这会令文件查询更为容易。我们将这个类命名为TextQuery，它包含一个vector和一个map。vector用来保存输入文件的文件，map用来关联每个单词和它出现的行号的set。这个类将会有一个用来读取给定输入文件的构造函数和一个执行查询的操作。

查询操作要完成的任务非常简单：查找map成员，检查给定单词是否出现。设计这个函数的难点是确定应该返回什么内容。一旦找到了一个单词，我们需要知道它出现了多少次、它出现的行号以及每行的文本。

返回所有这些内容的最简单的方法是定义另一个类，可以命名为QueryResult，来保存查询结果。这个类会有一个print函数，完成结果打印工作。

2.2.在类之间共享数据

我们的QueryResult类要表达查询的结果。这些结果包括与给定单词关联的行号的set和这些行对应的文本。这些数据都保存在TextQuery类型的对象中。

由于QueryResult所需要的数据都保存在一个TextQuery对象中，我们就必须确定如何访问它们。我们可以拷贝行号的set，但这样做可能很耗时。而且，我们当然不希望拷贝vector，因为这可能会引起整个文件的拷贝，而目标只不过是为了打印文件的一小部分而已（通常会是这样）。

通过返回指向TextQuery对象内部的迭代器（或指针），我们可以避免拷贝操作。但是，这种方法开启了一个陷阱：如果TextQuery对象在对应的QueryResult对象之前被销毁，会发生什么？在此情况下，QueryResult就将引用一个不再存在的对象中的数据。

对于QueryResult对象和对应的TextQuery对象的生存期应该同步这一观察结果，其实已经暗示了问题的解决方案。考虑到这两个类概念上“共享”了数据，可以使用shared_ptr来反映数据结构中的这种共享关系。

2.3.使用TextQuery类

当我们设计一个类时，在真正实现成员之前先编写程序使用这个类，是一种非常有用的方法。通过这种方法，可以看到类是否具有我们所需要的操作。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
	}
}

3.文本查询程序类的定义

我们以TextQuery类的定义开始。用户创建此类的对象时会提供一个istream，用来读取输入文件。这个类还提供一个query操作，接受一个string，返回一个QueryResult表示string出现的那些行。

设计类的数据成员时，需要考虑与QueryResult对象共享数据的需求。QueryResult类需要共享保存输入文件的vector和保存单词关联的行号的set。因此，这个类应该有两个数据成员：一个指向动态分配的vector（保存输入文件）的shared_ptr和一个string到shared_ptr<set>的map。map将文件中每个单词关联到一个动态分配的set上，而此set保存了该单词所出现的行号。

为了使代码更易读，我们还会定义一个类型成员来引用行号，即string的vector中的下标：

1
2
3
4
5
6
7
8
9
10
11
12

class QueryResult;//为了定义函数query的返回类型，这个定义是必需的
class TextQuery
{
public:
	using line_no = std::vector<std::string>::size_type;
	TextQuery(std::ifstream&);
	QueryResult query(const std::string&) const;
private:
	std::shared_ptr<std::vector<std::string>> file;//输入文件
	//每个单词到它所在的行号的集合的映射
	std::map<std::string, std::shared_ptr<std::set<line_no>>> wm;
};

3.1.TextQuery构造函数

TextQuery的构造函数接受一个ifstream，逐行读取输入文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

构造函数初始值列表。

注意，lines是一个引用，因此改变lines也会改变wm中的元素。如果一个给定单词在同一行中出现多次，对insert的调用什么都不会做。

3.2.QueryResult类

QueryResult类有三个数据成员：一个string，保存查询单词；一个shared_ptr，指向保存输入文件的vector；一个shared_ptr，指向保存单词出现行号的set。它唯一的一个成员函数是一个构造函数，初始化这三个数据成员：

1
2
3
4
5
6
7
8
9
10

class QueryResult
{
friend std::ostream& print(std::ostream&, const QueryResult&);
public:
	QueryResult(std::string s, std::shared_ptr<std::set<line_no>> p, std::shared_ptr<std::vector<std::string>> f) : sought(s), lines(p), file(f) { }
private:
	std::string sought; //查询单词
	std::shared_ptr<std::set<line_no>> lines; //出现的行号
	std::shared_ptr<std::vector<std::string>> file; //输入文件
};

构造函数的唯一工作是将参数保存在对应的数据成员中，这是在其初始化器列表中完成的。

3.3.query函数

query函数接受一个string参数，即查询单词，query用它来在map中定位对应的行号set。如果找到了这个string，query函数构造一个QueryResult，保存给定string、TextQuery的file成员以及从wm中提取的set。

唯一的问题是：如果给定string未找到，我们应该返回什么？在这种情况下，没有可返回的set。为了解决此问题，我们定义了一个局部static对象，它是一个指向空的行号set的shared_ptr。当未找到给定单词时，我们返回此对象的一个拷贝：

1
2
3
4
5
6
7
8
9
10
11

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);
}

3.4.打印结果

print函数在给定的流上打印出给定的QueryResult对象：

1
2
3
4
5
6
7
8
9
10

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

make_plural函数。

CATALOG
    FEATURED TAGS
    README Machine Learning Series Mathematics Series Image Segmentation Python Series Fundamentals of Computers OpenCV Series C++ Series Deep Learning Series Conda Tensorflow Series Algorithms Series AI Papers Object Recognition Natural Language Processing Aha! Algorithms Camera Calibration How Program Works Optical Flow Estimation How Networks Work Computer Vision