文本单词查询复合表达式求值的实现案例分析

????????本文讨论的“文本单词查询复合表达式求值的实现”案例，来自C++ primer第四版，该案例面向对象编程和泛型编程，涉及类的继承、抽象、多态、句柄、标准IO库、容器、算法库，是综合性很强的程序

????????该程序实现文本中查找单个单词，“非”查询（使用~操作符），“或”查询（使用|操作符），“与”查询（使用&操作符），组合查询（如fiery & bird | wind），查询表达式求值 并 打印输出查询结果：符合查询条件的文本共多少行、在查询本文的第几行、以及文本内容，查询使用文本如下：

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

? ? ? ?一、程序架构

? ? ? ? 创建标准IO库的ifstream对象infile，定义的辅助函数openfile在命令行模式下，用对象infile打开文本文件，具体操作是：在命令行下输入程序名字及文本文件所在目录

????????TextQuery类实现文本的读取存储，容器vector按行存储文本，容器map存储所有单词所在的行的set容器，接口函数run_query返回一个单词所在的行的set容器，text_line返回具体行的文本，size返回存储的文本共多少行

? ? ? ? 句柄类Query，包装类型为查询基类Query_base的模板句柄Handle实例对象h，该句柄实例包装查询基类指针，Query类对象由查询基类指针构造 或 string字符串（由字符串构造的对象返回的是基类指针）构造，Query类对象的构造，最终初始化查询基类指针，注意：查询基类指针指向具体的查询对象：继承自查询基类Query_base的子类WordQuery、NotQuery、BinaryQuery（BinaryQuery的子类AndQuery、OrQuery）的对象

????????句柄类的友元函数，是重载 |、&、~操作符的函数，返回句柄类对象（动态构造的具体查询对象返回的是查询基类指针，查询基类指针可以隐式转换为句柄类对象），用以实现查询表达式

????????句柄类Query的接口函数display显式具体查询表达式，接口函数eval返回符合查询条件的set容器（存储所有符合查询条件的文本行号）

? ? ? ? 程序几个版本的演变及完整代码，请点击这里（本文讨论的是第六版）

? ? ? ?主函数代码：

int main(int argc, char**argv )
{
    std::ifstream infile;
    if(argc<2 ||!open_file(infile,argv[1] ) ) {
        std::cerr << "No input file!" << std::endl;
        return EXIT_FAILURE;
    }
    TextQuery tq;
    tq.read_file(infile );
    
    Query q = Query("fiery") & Query("bird") | Query("wind");
    std::set<TextQuery::line_no> qset = q.eval(tq );
    q.display(std::cout ); // ((fiery & bird) | wind)
    print_results(qset,"",tq );
          
    return 0;
}

? ? ? ? Query q = Query("fiery") & Query("bird") | Query("wind");? Query对象q的构造过程：字符串"fiery"构造Query临时对象（包含查询基类Query_base的子类WordQuery类的对象），字符串"bird"构造Query临时对象（包含查询基类Query_base的子类WordQuery类的对象），Query类的友元函数重载 & 操作符，构造左操作数Query("fiery")，右操作数Query("bird")的Query临时对象（包含查询基类Query_base的子类BinaryQuery类的子类AndQuery类的对象），Query类的友元函数重载 | 操作符，构造左操作数为Query临时对象（包含查询基类Query_base的子类BinaryQuery类的子类AndQuery类的对象），右操作数Query("wind")的Query临时对象（包含查询基类Query_base的子类BinaryQuery类的子类OrQuery类的对象），表达式求值的Query临时对象复制构造Query类对象q

????????std::set<TextQuery::line_no> qset = q.eval(tq );Query类对象q，调用eval函数，把存储文本的TextQuery类对象的引用传递到函数，实现表达式查询，Query类对象q包含的Handle句柄对象（包含查询基类Query_base指针），利用重载的操作符-> 以及利用查询类的多态性将函数调用分发到基类Query_base指针指向的各个具体的派生类的eval函数，最终返回符合条件的set容器

UML类设计图??

?????????二、查询基类Query_base及其子类WordQuery、NotQuery、BinaryQuery（BinaryQuery的子类AndQuery、OrQuery）

? ? ? ? 查询基类Query_base代码：

class Query_base{
    friend class Query; //句柄Query
    friend class Handle<Query_base >;//类型为Query_base的句柄模板实例
protected://派生类访问
    typedef TextQuery::line_no line_no;
    virtual ~Query_base() {  }
private:   //两个接口，用户和Query_base类的派生类只通过句柄Query使用Query_base类
    virtual std::set<line_no> eval(const TextQuery&) const = 0;
    virtual std::ostream& display(std::ostream& = std::cout) const = 0;
};

????????查询基类Query_base的子类WordQuery类的代码：

class WordQuery: public Query_base{
    friend class Query;//句柄Query友元//调用构造函数需要
    WordQuery(const std::string &s ):query_word(s ) {  }
    std::set<line_no > eval(const TextQuery &t)const{  //实现基类纯虚函数eval
        return t.run_query(query_word ); //用到了TextQuery类的成员函数run_query
    }
    std::ostream& display(std::ostream &os)const{      //实现基类纯虚函数display
        return os << query_word;
    }
    std::string query_word;  //数据成员query_word
};

????????查询基类Query_base的子类NotQuery类的代码：

class NotQuery: public Query_base{
    friend Query operator~(const Query & );//调用构造函数需要
    NotQuery(Query q ):query(q ) {  } //构造
    std::set<line_no > eval(const TextQuery & )const;
    std::ostream& display(std::ostream &os )const{
        return os << "~(" << query << ")"; //输出操作符的使用最终是对Query_base对象的虚函数的调用
    }
    const Query query;  //数据成员Query句柄对象
};
std::set<TextQuery::line_no > NotQuery::eval(const TextQuery &file) const{
    std::set<TextQuery::line_no > has_val = query.eval(file );
    std::set<line_no > 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;
}    

????????查询基类Query_base的子类BinaryQuery类的代码：

class BinaryQuery: public Query_base{
protected:
    BinaryQuery(Query left, Query right, std::string op ):lhs(left),rhs(right),oper(op) {  }
    std::ostream& display(std::ostream &os)const{
        return os << "(" << lhs << " " << oper << " "
                        << rhs << ")"; //输出操作符的使用最终是对Query_base对象的虚函数的调用
    }
    const Query lhs, rhs;
    const std::string oper;
};
 

????????查询基类Query_base的子类BinaryQuery类的子类AndQuery类的代码：

class AndQuery: public BinaryQuery{
    friend Query operator&(const Query &, const Query & );//调用构造函数需要
    AndQuery(Query left, Query right ):BinaryQuery(left, right, "&" ) {  }
    std::set<line_no > eval(const TextQuery & )const;
};
std::set<TextQuery::line_no > AndQuery::eval(const TextQuery &file) const{
    std::set<line_no > left = lhs.eval(file ),
                    right = rhs.eval(file );
    std::set<line_no > ret_lines;
    set_intersection(left.begin(), left.end(),
                    right.begin(),right.end(),
                    inserter(ret_lines, ret_lines.begin()) );
    return ret_lines;
}

? ? ? ? 算法std::set_intersection，构造一个排序范围，它是两个排序范围的集合交集，实现&运算

????????查询基类Query_base的子类BinaryQuery类的子类OrQuery类的代码：

class OrQuery: public BinaryQuery{
    friend Query operator|(const Query &, const Query & );//调用构造函数需要
    OrQuery(Query left, Query right ):BinaryQuery(left, right, "|" ) {  }
    std::set<line_no > eval(const TextQuery & )const;
};
std::set<TextQuery::line_no > OrQuery::eval(const TextQuery &file) const{
    std::set<line_no > right = rhs.eval(file ),
                    ret_lines = lhs.eval(file );    //返回的set对象ret_lines初始化为lhs的结果
    ret_lines.insert(right.begin(), right.end() );
    return ret_lines;
}

? ? ? ? 三、句柄模板

? ? ? ? 句柄简单的来讲，它是一个类，包装了一种基类指针的一个类，该指针指向动态创建的有继承关系的对象，句柄确保指针指向的对象在有指针指向的时候不会释放，在没有指针指向的时候释放，句柄避免了对象的重复创建，句柄在C++沉思录一书中有详细的描述，可以点击这里查看

? ? ? ?本人认为，句柄，这个包含一个基类指针的类，真的是为实现面向对象编程的多态性而生，安全、方便，句柄对象的构造、复制、赋值、析构轻松、简单，当你真正理解本文论述的程序，你会发现，句柄是这个程序的灵魂

????????句柄模板类Handle代码：

template<class T> class Handle{
private:
    T* ptr;          //指向基础对象的指针
    size_t *use;     //指针计数 //即多少个指针指向同一个基础对象
    void rem_ref(){  //删除基础对象(根据计数判断是否删除)
        if(--*use == 0){
            delete ptr; //删除基础对象
            delete use; //删除计数
        }
    }
public:
    Handle(T *p = 0 ):ptr(p ),use(new size_t(1) ){ } //指针ptr指向动态分配的基础对象的地址
    //复制控制
    Handle(const Handle& h):ptr(h.ptr ), use(h.use) { ++*use; } //复制，++*use
    Handle& operator=(const Handle& rhs );
    ~Handle() { rem_ref(); }   //Handle对象析构 // 删除基础对象(根据计数判断是否删除)
    //用于访问基础对象
    const T& operator*()const; //解引用操作符
    const T* operator->()const; //成员操作符            
};
 
template<class T>
inline Handle<T>& Handle<T>:: operator=(const Handle& rhs)
{
    ++*rhs.use;     //protect against self-assignment //防止自我复制
    rem_ref();    //decrement use count and delete pointers if needed
    ptr = rhs.ptr;
    use = rhs.use;
    
    return *this;
}
 
template<class T>//const Handle对象可以调用，返回类型是const T&不可以修改基础对象
inline const T& Handle<T>::operator*()const   
{
    if(ptr)
        return *ptr;
    throw std::runtime_error("dereference of unbound Handle");
}
 
template<class T>
inline  const T* Handle<T>::operator->()const
{
    if(ptr)
        return ptr;
    throw std::runtime_error("dereference of unbound Handle");
} 

? ? ? ? 四、句柄类Query（包装句柄模板实例对象 Handle<Query_base > h）的代码

class Query{  //使用Query友元的类，增加句柄模板实例为友元
    friend Query operator~(const Query &);
    friend Query operator|(const Query &, const Query &);
    friend Query operator&(const Query &, const Query &);
public:
    Query(const std::string &); //!!!  
    std::set<TextQuery::line_no> eval(const TextQuery &t)const {return h->eval(t); } //!!!
    std::ostream &display(std::ostream &os = std::cout) const {return h->display(os); }//!!!
private:
    Query(Query_base *query):h(query) {  } //!!!操作符创建Query对象调用
    Handle<Query_base > h; //!!!
};
Query::Query(const std::string &s ):h(new WordQuery(s ) ) {   }    ; //!!!创建WordQuery对象
inline std::ostream& operator << (std::ostream &os, const Query &q){
    return q.display(os ); //参数q是const，调用的display函数也必须是const
}

//return语句隐式调用接受Query_base指针的Query构造函数//隐式类型转换
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 );
}      

? ? ? ? 五、查询结果打印函数

void print_results(const std::set<TextQuery::line_no > &locs, 
                   const std::string &sought,
                   const TextQuery &file  )
{
    typedef std::set<TextQuery::line_no > line_nums;
    line_nums::size_type size = locs.size();
    std::cout << "\n" << sought << " occurs "
            << size << " "
            << make_plural(size, "time", "s" ) << std::endl;
    line_nums::const_iterator it = locs.begin();
    for( ; it != locs.end(); ++it ){
        std::cout << "\t(line "
            << (*it) + 1 << ")"
            << file.text_line(*it ) << std::endl;
    }
}
 
std::string make_plural(std::size_t ctr, 
                            const std::string &word,
                            const std::string &ending )    //make_plural //单词复数形式
{
    return (ctr == 1 ) ? word : word + ending;
}

? ? ? ? 六、文件打开函数open_file

std::ifstream& open_file(std::ifstream &in, const std::string &file )
{
    in.close(); //如果已经打开
    in.clear();
    in.open(file.c_str() ); //打开文件
    return in;
}

? ? ? ? 七、文本存储TextQuery类

class TextQuery{
public:
    typedef std::vector<std::string>::size_type line_no;
    void read_file(std::ifstream &is){  //std::ifstream &
        store_file(is);
        build_map();
    }
    std::set<line_no> run_query(const std::string & )const;
    std::string text_line(line_no )const;
    line_no size() const{ return lines_of_text.size(); } //!!!const函数
private:
    void store_file(std::ifstream & );  //std::ifstream & //保存文件
    void build_map();                   //从文件提取单词(去除标点符号)并记录单词所在文件的行号   
    std::vector<std::string> lines_of_text;  
    std::map< std::string, std::set<line_no> > word_map;//
};
 
void TextQuery::store_file(std::ifstream &is )
{
    std::string textline;
    while(getline(is,textline) ){
        lines_of_text.push_back(textline );
    }
}
 
void TextQuery::build_map()
{
    for( line_no line_num = 0; 
         line_num != lines_of_text.size();
         ++line_num )
    {
        std::istringstream line(lines_of_text[line_num] );//从std::vector读到 std::istringstream
        std::string word;        
        while(line >> word ){
            word.std::string::erase( std::remove_if(word.begin(),word.end(), static_cast<int(*)(int) >(&ispunct)), word.end() );//!!!去除标点符号
            word_map[word].insert(line_num );
        }
    }    
}
 
std::set<TextQuery::line_no> TextQuery::run_query(const std::string &query_word )const
{
    std::map<std::string,std::set<line_no> > ::const_iterator loc = word_map.find(query_word ); //std::map里查找行std::set
    if(loc == word_map.end() )
        return std::set<line_no>();  //没找到返回set空对象
    else
        return loc->second;
}
 
std::string TextQuery::text_line(line_no line ) const
{
    if(line <lines_of_text.size() )
        return lines_of_text[line ];
    throw std::out_of_range("line number out of range");
}