[数据结构与算法]C++Primer 15.9文本查询程序再探

这个程序还是比较复杂的，把这句话作为文章的开头可以看出它的真实性.....

15.9的文本查询程序是对12.3节的文本查询程序的扩展，而使用的主要知识也是15章的核心：继承和多态，即面向对象程序设计。

恩，这一节看的过程中，会有很多不理解。特别是在没有把整个程序都看完之前，会有很多疑惑，而看完之后，再思考思考，回头再看本节的前面所写的程序介绍，会有一些感悟。更加清楚这个程序的原理。

TextQuery.h

#ifndef QUERY_TEXTQUERY_H
#define QUERY_TEXTQUERY_H

#include<iostream>
#include<vector>
#include<string>
#include<memory>
#include<map>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<sstream>
#include<algorithm>
#include<fstream>
#include<stack>
using namespace std;
class QueryResult;

// ??????????????????????
class TextQuery
{
public:
    using line_no = vector<string>::size_type;
    TextQuery(ifstream&); // ?????????????????????????????в????????
    QueryResult query(const string&) const;  // ???????string???????string???в????
private:
    shared_ptr<vector<string>> file;  // ???????
    map<string, shared_ptr<set<line_no>>> wm;  // ???????????????????????к?set??
};

inline TextQuery::TextQuery(ifstream &is): file(new vector<string>) {
    string text;
    while (getline(is, text)) {   // ??????е?????
        file->push_back(text);    // ????????е????
        int n = file->size() - 1;  // ???浱????к???????·?????????????shared_ptr<set<line_no>> ?????????к?
        istringstream line(text);
        string word;
        while(line >> word){
            auto &lines = wm[word];  // lines?????shared_ptr
            if(!lines)   // ??????±??????????map?д????????word?????word????????shared_ptr??????shared_ptr???????nullptr;
                lines.reset(new set<line_no>);
            lines->insert(n);
        }
    }
}

class QueryResult{
    friend ostream& print(ostream& os, const QueryResult& qr);
public:
    QueryResult(string s, shared_ptr<set<TextQuery::line_no>> p, shared_ptr<vector<string>> f)
            : sought(s), lines(p), file(f) {}
    auto begin()const {return lines->begin();}
    auto end()const{return lines->end();}
    shared_ptr<vector<string>> get_file()const {return file;}
private:
    string sought; // ????????
    shared_ptr<set<TextQuery::line_no>> lines;  // ??????к?
    shared_ptr<vector<string>> file;  // ???????
};

inline QueryResult TextQuery::query(const string& s)const {
    static shared_ptr<set<line_no>> nodata(new set<line_no>()); // ?????????????к?set??shared_ptr
    auto loc = wm.find(s);
    if(loc == wm.cend())
        return QueryResult(s, nodata, file);
    else
        return QueryResult(s, loc->second, file);
}

inline ostream& print(ostream& os, const QueryResult& qr)
{
    os<<qr.sought<<" occurs "<<qr.lines->size()<<" "<<((qr.lines->size()>1)?"times":"time")<<endl;
    for(const auto& num: *(qr.lines)){
        os << "\t(lines "<<num+1<<") "<<(*(qr.file))[num]<<endl;
    }
    return os;
}

inline void runQueries(ifstream& infile)
{
    // infile?????ifstream??????????????????
    TextQuery  tq(infile);
    // ????????????????????????????????????????????
    while(true)
    {
        cout<<"enter word to look for, or q to quit: "<<endl;
        string s;
        // ?????????????s=='q'?????
        if(!(cin>>s) || s == "q")  break;
        print(cout, tq.query(s)) << endl;
    }
}

inline void independent_word_query(ifstream& ifile){
    vector<string> file;
    map<string,set<int>> word_map;
    string text;
    while(getline(ifile, text)){
        file.push_back(text);
        int n = (int)file.size()-1;  // ???push_back?????е??±?
        istringstream line(text);   // ???string text???????????
        string word;
        while(line >> word){
            word_map[word].insert(n);
        }
    }
    while(true){
        cout << "Enter word to look for, or q to quit: "<<endl;
        string s;
        if(!(cin>>s) || s=="q")  break;
        const auto& lines = word_map.find(s); // ?????????????????????pair<string,set<int>>
        cout<<s<<" occurs "<<(*lines).second.size()<<(lines->second.size()>1?" times":" time")<<endl;
        for(const auto& i:lines->second){
            cout<<"\t(lines "<<i+1<<") "<<file[i]<<endl;
        }
    }
}
#endif

Query.h

#ifndef QUERY_QUERY_H
#define QUERY_QUERY_H

#include"TextQuery.h"

class Query_base
{
    friend class Query;
protected:
    using line_no = TextQuery::line_no;   // �����������eval������?�?�������?protected��
    virtual ~Query_base() = default;
private:
    // eval���������??Query?���QueryResult
    virtual QueryResult eval(const TextQuery&) const = 0;
    // rep��?��?��?��string
    virtual string rep() const = 0;
};

class Query
{
    friend Query operator|(const Query&, const Query&);
    friend Query operator&(const Query&, const Query&);
    friend Query operator~(const Query&);
public:
    Query(const string&);    // ����?���μ�WordQuery
public:
    QueryResult eval(const TextQuery& t)const { return q->eval(t); }
    string rep()const { return q->rep(); }
private:
    Query(shared_ptr<Query_base> query) :q(query){}
    shared_ptr<Query_base> q;
};

//ostream& operator<<(ostream& os, const Query& q)
//{
//    // Query::rep?������Query_base?���rep�����������
//    return os<<q.rep();
//}

class WordQuery: public Query_base
{
    friend Query;
private:
    WordQuery(const string& s): query_word(s) {}
    virtual QueryResult eval(const TextQuery& t)const override
            { return t.query(query_word); }
    virtual string rep() const override
            { return query_word; }
    string query_word;
};
inline Query::Query(const string& s): q(new WordQuery(s)) {}  // ��Query���?���??���·���?���

// Query q = ~Query("dog");
class NotQuery: public Query_base
{
    friend Query operator~(const Query&);
private:
    NotQuery(const Query& q): query(q) {}
    virtual QueryResult eval(const TextQuery&) const override;
    virtual string rep() const override
    { return "~("+query.rep()+")"; }
    Query query;
};

inline Query operator~(const Query &operand)
{
    return Query(shared_ptr<Query_base>(new NotQuery(operand)));
}

class BinaryQuery: public Query_base
{
protected:
    BinaryQuery(const Query& l, const Query &r, string s):
    lhs(l), rhs(r), opSym(s) {}
    // ������?BinaryQuery������eval;
    virtual string rep()const override { return "(" + lhs.rep() + " " + opSym + + " " + rhs.rep() + ")"; }  // �������rep����������

    Query lhs, rhs;
    string opSym;
};

class AndQuery: public BinaryQuery
{
    friend Query operator&(const Query&, const Query&);
private:
    AndQuery(const Query& left, const Query& right): BinaryQuery(left,right,"&") {}
    // �?���rep��������eval
    QueryResult eval(const TextQuery&) const override;
};

inline Query operator&(const Query &lhs, const Query &rhs)
{
    return Query (shared_ptr<Query_base>(new AndQuery(lhs,rhs)));
}

class OrQuery: public BinaryQuery
{
    friend Query operator|(const Query&, const Query&);
private:
    OrQuery(const Query& left, const Query &right): BinaryQuery(left,right,"|") {}
    QueryResult eval(const TextQuery&)const override;
};

inline Query operator|(const Query &lhs, const Query &rhs)
{
    return Query(shared_ptr<Query_base>(new OrQuery(lhs,rhs)));
}

#endif //QUERY_QUERY_H

?

?Query.cpp

#include "Query.h"

// Query q = Query("dog") | Query("cat");
QueryResult OrQuery::eval(const TextQuery& t) const
{
    auto left = lhs.eval(t), right = rhs.eval(t);
    shared_ptr<set<line_no>> ret_lines(new set<line_no>(left.begin(),left.end()));
    ret_lines->insert(right.begin(),right.end());
    return QueryResult(rep(),ret_lines,lhs.eval(t).get_file());
}

QueryResult AndQuery::eval(const TextQuery& text) const
{
    auto left = lhs.eval(text), right = rhs.eval(text);
    auto ret_lines = make_shared<set<line_no>>();  // ����set���?�?��?������?�?�?��
    set_intersection(left.begin(),left.end(),right.begin(),right.end(),inserter(*ret_lines,ret_lines->begin()));
    return QueryResult(rep(),ret_lines,left.get_file());
}

QueryResult NotQuery::eval(const TextQuery& text) const
{
    auto result = query.eval(text);
    auto ret_lines = make_shared<set<line_no>>();
    auto beg = result.begin(), end = result.end();
    auto sz = result.get_file()->size();
    for(size_t n = 0; n != sz; ++n){
        if(beg == end || *beg != n)
            ret_lines->insert(n);
        else
            ++beg;
    }
    return QueryResult(rep(), ret_lines, result.get_file());
}

main.cpp

void read_file(ifstream &f){
    TextQuery textquery(f);
    Query q ( Query("dog") & Query("cat"));
    print(cout,q.eval(textquery))<<endl;
    Query q2 = Query("bbb");
    print(cout, q2.eval(textquery))<<endl;
    Query q3 = ~Query("dog");
    print(cout, q3.eval(textquery))<<endl;
    system("pause");
}

int main(){
    string filename;
    cout<<"Please enter filename"<<endl;
    cin >> filename;
    ifstream file(filename);
    if(!file){
        cout<<"Filename error"<<endl;
        return -1;
    }
    read_file(file);
    return 0;
}

出现了一些意外，代码中中文注释都是乱码。

针对程序所涉及的几个类的介绍和理解：
TextQuery类：

可以把每个TextQuery类对象看作一个文本文件，这个类将某个文本文件的内容保存在一个vector<string>中，并保存了每个单词对应的行号，而query函数就是接收一个string，然后查找这个单词。而这里的返回结果是一个QueryResult类对象。这个类只是用来保存一个查询结果，其实后续的& | ~的结果也都是这个QueryResult类对象

在12章时，我想过，为什么要设计这么一个类呢？如果直接在query函数中实现查找并打印不可以吗？其实这样是不太合适的，一个最直接的原因就是，在后方进行word1 & word2操作时，不方便，封装一个查询结果类更容易处理。这样，也可以支持更多的操作，而不仅仅是打印。

QueryResult类：

表示一个查询结果，通常与print函数联系起来使用，print用于打印这个查询结果。

后续的就是一些新的继承方面的类了，也就是为了支持word1 & word2 或者 word1 | word2 或者 ~word操作。而这些查询都建模成了相互独立的类，即AndQuery OrQuery NotQuery 而最基本的还有一个WordQuery，这些类都继承自一个抽象基类Query_base。

Query_base类：
最主要的就是两个成员函数：eval 和 rep，说真的，我觉得这两个名字起的并不好，当然受限于我的英文水平，其实eval就相当于TextQuery类的query函数，参数是TextQuery，即一个文本文件，然后在这个文本文件中执行查询操作，返回一个查询结果QueryResult。rep函数用于返回查询的string表示形式，比如~(word1 & word2)。

Query类：
这个类是很重要的，当然这句话是句废话.... 这个类的数据成员是一个基类的指针，而这也是这个程序支持面向对象编程和多态的根本原因。

这是一个接口类，它的成员函数仍然是eval和rep，调用的是基类指针所指向对象的eval和rep，基类指针或引用调用虚函数发生动态绑定。所以，Query类基类指针指向的对象，可能是继承体系中任何一种类型的对象。比如： Query q = Query("dog") & Query("cat"); 而这里的q的基类指针指向的就是一个AndQuery类的对象，调用的eval和rep也都是AndQuery类版本的eval和rep，而这个AndQuery类的数据成员就包括着右边&运算符左右两边的两个WordQuery类的对象，这里是使用了&运算符重载。operator& 返回的就是一个基类指针绑定到AndQuery类对象的Query类对象。返回值用于初始化q。这里调用的应该是Query类的拷贝构造函数吧

WordQuery类：

Query_base类的派生类，表示对于某个单词最直接的查询，覆盖了eval和rep，为什么说eval相当于query呢？这里的eval就是最明显的证明：这里的eval直接返回参数TextQuery类的query结果，就是对某个单词的查询结果。而后方的Not And Or，都没有调用这个query操作，他们操作的是Query类对象的查询结果。

NotQuery类：

这个类也是Query_base的派生类，表示~查询方式。~运算符重载之后，返回的就是一个绑定到NotQuery类对象上的Query类对象，而~作用的就是另一个Query类对象的eval查询结果。

AndQuery OrQuery类：
因为这两个类都操作两个Query类对象，所以又实现了一个BinaryQuery抽象基类，这个基类继承自Query_base，多了两个Query类对象的成员，以及一个操作符成员，用于表示& 还是 |。

这两个类所关联的是& |运算符，operator& 返回的分别是是基类指针绑定到AndQuery类对象上的Query类对象 。?operator | 返回的是?基类指针绑定到OrQuery类对象上的Query类对象，而这两个类的rep函数很简单，对于两个成员的rep函数进行一些简单加工即可，而eval函数，参数仍然是一个TextQuery类，在两个Query成员返回的QueryResult上进行处理，然后返回一个新的QueryResult对象。代表着一种& 或者 |操作之后的查询结果。

还有一个比较有趣的是：

如下代码： Query q = Query("Dog") & Query("Cat") | Query("Bird");

Print( cout, q.eval(textquery) );

一共创建了三个WordQuery，一个AndQuery，一个OrQuery。先后顺序不太清楚。。。但是其实创建好q对象之后，这里面并没有什么查询结果，保存的只是这些单词，还有一些没有调用的成员函数eval和rep。

根据运算符优先级规则，q是一个基类指针指向OrQuery类对象的Query对象，而如果想打印出这个查询结果，必然是要调用eval函数的，参数表示，在这个文件里查找这三个单词。在OrQuery的eval调用的最开始，两个Query类对象数据成员的查询结果还没有出来，而在eval函数内部，计算了两个查询结果，一个是rhs数据成员的对Bird单词的查询，查询的位置就是那个textquery保存的文件内容。另一个是AndQuery的eval函数的返回结果，这个结果是对两个WordQuery类对象查询结果的&操作之后的结果。最后才对这两个QueryResult结果进行合并处理。然后返回一个新的查询结果。

现在看来，只有WordQuery类对象调用了TextQuery的query操作。而其余的Or Not And都是对其他的Query对象的查询结果进行加工。当然这些eval函数的参数都是同一个TextQuery。并且都是返回的QueryResult。

说真的，之前比较疑惑的是，我感觉这些eval函数的TextQuery参数的传递有些奇怪。对比之前12章的文本查询程序，最后封装的对文件的查询的函数，看上去就舒服多了，它是把ifstream类对象传递给TextQuery类的构造函数的参数，然后后面调用query函数进行查询，返回一个QueryResult对象。调用print函数打印。

但是这里再探的程序就有点不一样和奇怪了，你也可以封装一个完整的查询函数，但是如果不那样做的话，进行的操作就是。

Query q = Query("Dog") & Query("Cat") | Query("Bird");

Print( cout, q.eval(textquery) );

这种操作，相比于? TextQuery tq(ifile);? print(cout, tq.query("Dog"));? 就有点奇怪了。

上方的main.cpp主函数，并没有实现完善的查询函数，即实时查询操作，如输入Dog & Cat | Bird。然后打印查询结果，之后有能力实现的话可能会补上。

就以这篇文章作为大一学习生活的结束吧。