STL实践与分析
--容器的综合应用：文本查询程序
引言：
本章中最重点的实例。由于不须要用到multiset与multimap的内容。于是将这一小节提到了前面。通过这个实例程序，大师分析问题的智慧，大师的编程风格。大师对程序的控制能力，由此可见一斑。因此。我对这一小节的内容差点儿不做改动。或仅仅做非常小的更改（由于有些东西不同人有不同的理解）。搬出来。以供大家细致品读。
要求：
我们的程序将读取用户指定的随意文本文件,然后同意用户从该文件里查找单词。查询的结果是该单词出现的次数,并列出每次出现所在的行。假设某单词在同一行中多次出现,程序将仅仅显示该行一次。
行号按升序显示。
例子：
以本章的内容作为文件输入,然后查找单词“element”。输出的前几行应为:
element occurs 125 times (line 62) element with a given key. (line 64) second element with the same key. (line 153) element |==| operator. (line 250) the element type. (line 398) corresponding element. …
一、查询程序的设计
设计程序的一个良好习惯是首先将程序所涉及的操作先列出来，明白须要提供的操作有助于建立须要的数据结构和实现这些行为。
从需求出发，我们的程序须要支持下面任务：
1）它必须同意用户指明要处理的文件名称字。
程序将存储该文件的内容,以便输出每一个单词所在的原始行。
2）它必须将每一行分解为各个单词,并记录每一个单词所在的全部行。在输出行号时,应保证以升序输出,而且不反复。
3）对特定单词的查询将返回出现该单词的全部行的行号。
4）输出某单词所在的行文本时,程序必须能依据给定的行号从输入文件里获取对应的行。
1、数据结构
设计一个简单的TextQuery类来实现这个程序：
1）使用一个vector<string>对象来存储整个输入文件。输入文件的每一行是该 vector对象的一个元素。
因而,在希望输出某一行时,仅仅需以行号为下标获取该行所在的元素就可以。
2）将每一个单词所在的行号存储在一个set容器对象中。使用set就可确保每行仅仅有一个条目,并且行号将自己主动按升序排列。
3）使用一个map容器将每一个单词与一个set容器对象关联起来,该set容器对象记录此单词所在的行号。
2、操作
对于类还要求有良好的接口。然而,一个重要的设计策略首先要确定:查询函数需返回存储一组行号的set对象。这个返回类型应该怎样设计呢?
其实,查询的过程相当简单:使用下标訪问map对象获取关联的set对象就可以。唯一的问题是怎样返回所找到的set对象。安全的设计方案是返回该set对象的副本。但如此一来,就意味着要复制set中的每一个元素。假设处理的是一个相当庞大的文件,则复制set对象的代价会很昂贵。其它可行的方法包含:返回一个pair对象,存储一对指向set中元素的迭代器;或者返回set对象的 const引用。为简单起见,我们在这里採用返回副本的方法,但注意:假设在实际应用中复制代价太大,须要新考虑事实上现方法。
第一、第三和第四个任务是使用这个类的程序猿将运行的动作。第二个任务则是类的内部任务。将这四任务映射为类的成员函数,则类的接口需提供下列三个public函数:
1）read_file成员函数,其形參为一个ifstream& 类型对象。
该函数每次从文件里读入一行,并将它保存在vector容器中。
输入完成后,read_file 将创建关联每一个单词及其所在行号的map容器。
2）run_query成员函数,其形參为一个string类型对象,返回一个set对 象,该set对象包括出现该string对象的全部行的行号。
3）text_line成员函数,其形參为一个行号,返回输入文本中该行号相应的文本行。
不管 run_query还是 text_line都不会改动调用此函数的对象,因此,可将这两个操作定义为const成员函数。
为实现read_file功能,还需定义两个private函数来读取输入文本和创建map容器:
1）store_file函数读入文件,并将文件内容存储在vector容器对象中。
2）build_map函数将每一行分解为各个单词,创建map容器对象,同一时候记录每一个单词出现行号。
二、TextQuery类
//in TextQuery.h
class TextQuery
{
public:
typedef std::vector<std::string>::size_type line_no;
void read_file(std::ifstream &is)
{
store_file(is);
build_map();
}
std::set<line_no> run_query(const std::string &) const;
std::string text_line(line_no) const;
private:
void store_file(std::ifstream &);
void build_map();
std::vector<std::string> line_of_text;
std::map< std::string,std::set<line_no> > word_map;
};
三、TextQuery类的使用
1、主程序
//in main.cpp
/**记得加入
*#include "TextQuery.h" 类的定义
*#include "other.h" 其它函数的声明
*/
int main(int argc,char **argv)
{
ifstream inFile;
if (argc != 2 || !open_file(inFile,argv[1]))
{
cerr << "No input file!" << endl;
return EXIT_FAILURE;
}
TextQuery tq;
tq.read_file(inFile);
while (true)
{
cout << "enter word to look for,or q/Q to quit: ";
string s;
cin >> s;
if (!cin || s == "q" || s == "Q")
break;
set<TextQuery::line_no> locs = tq.run_query(s);
print_results(locs,s,tq);
}
return 0;
}
2、辅助函数
print_results函数、make_plural函数、open_file函数的定义:
//in other.cpp
/**记得加入
*#include "TextQuery.h" 类的定义
*#include "other.h" 其它函数的声明
*/
string make_plural(set<TextQuery::line_no size,const string &begin,const string &ends);
ifstream &open_file(ifstream &in,const string &file)
{
in.close();
in.clear();
in.open(file.c_str());
return in;
}
void print_results(set<TextQuery::line_no> &locs,
const string &sought,
const TextQuery &file)
{
typedef set<TextQuery::line_no> line_nums;
line_nums::size_type size = locs.size();
cout << "
" << sought << " occurs "
<< size << " "
<< make_plural(size,"time","s") << endl;
line_nums::iterator iter = locs.begin();
while (iter != locs.end())
{
cout << " (line "
<< (*iter) + 1 << ")"
<< file.text_line(*iter) << endl;
}
}
string make_plural(set<TextQuery::line_no size,
const string &begin,
const string &ends)
{
return (size <= 1 ? begin : begin + ends);
}
四、编写成员函数[inTextQuery.h]
1、存储输入文件
void TextQuery::store_file(ifstream &is)
{
string textline;
while (getline(is,textline))
{
line_of_text.push_back(textline);
}
}
2、建立单词map容器
void TextQuery::build_map()
{
for (line_no line_num = 0;
line_num != line_of_text.size();
++line_num)
{
istringstream line(line_of_text[line_num]);
string word;
while (line >> word)
{
word_map[word].insert(line_num);
}
}
}
【分析：】
word_map[word].insert(line_num);
将word用做 map容器的下标。假设word在 word_map容器对象中不存在,那么下标操作符将该word加入到此容器中,并将其关联的值初始化为空的set。
无论是否加入了word,下标运算都返回一个set对象,然后调用insert函数在该 set对象中加入当前行号。假设某个单词在同一行中反复出现,那么insert函数的调用将不做不论什么操作。
3、支持查询
set<TextQuery::line_no>
TextQuery::run_query(const std::string &query_word) const
{
map<string,set<line_no> >::const_iterator
loc = word_map.find(query_word);
if (loc == word_map.end())
{
return set<TextQuery::line_no>();
}
else
{
return loc -> second;
}
}
run_query函数带有指向conststring 类型对象的引用參数,并以这个參数作为下标来訪问word_map对象。
如果成功找到这个string,那么该函数返回关联此string的 set对象,否则返回一个空的set对象。
4、run_query返回值的使用
string TextQuery::text_line(line_no line) const
{
if (line < line_of_text.size())
{
return line_of_text[line];
}
throw out_of_range("line number out of range");
}版权声明：本文博客原创文章，博客，未经同意，不得转载。