本文共 2737 字，大约阅读时间需要 9 分钟。

找出3000000条字符串中使用频率最高的10条

要求:高效

目的:锻炼STL的用法，涉及到STL各大类组件使用，包括自定义hash索引类，自定义hash函数，STL堆算法，C++类的设计方法等

主要用到hash_map和heap

生成原始数据脚本(matlab文件)：

base = 97;alpha = 26;total = 3000000;max_len = 4;min_len = 1;filename = 'data.txt';fid = fopen(filename,'w+');for n=1:total    seed=mod(floor(rand()*100),max_len)+min_len;    for m=min_len:seed        fprintf(fid,char(mod(floor(rand()*100),alpha)+base));    end    fprintf(fid,'\n');endfclose(fid);

生成的数据文件大致为data.txt：

zcvyhkfpjohrdrcukvba

...

STL C++求解实现：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;using namespace stdext;class Node{public: Node(){_str="";}; Node(const Node &n){_str = n.getv();}; Node(const std::string & str):_str(str){}; Node(const char * pstr):_str(pstr){}; ~Node(){}; std::string getv() const { return _str; } void setv(const std::string & str) { _str = str; } Node & operator = (const Node & m) { _str = m.getv(); return *this; } friend bool operator < (const Node &n,const Node &m) { return n._str < m._str; } friend bool operator == (const Node &n,const Node &m) { return n._str == m._str; } friend ostream & operator << (ostream& o,const Node&n) { o<
         
          { size_t operator ()(const Node &n)const { return node_hash_value(n); } bool operator () (const Node & n, const Node &m)const { return n.getv() < m.getv(); }};ostream & operator << (std::ostream& o,const pair< Node,int> &n ){ o<
          
           <<":"<
           
             &m,const pair
            
              &n) { return m.second > n.second; }};const char *filename = "data.txt";const int find_num = 10;int main(){ ifstream out; hash_map
             
               nodes; out.open(filename, ios::in); std::string line; while(!out.eof()) { std::getline(out,line); if (line.size() == 0) { continue; } Node n(line); if (nodes.count(n) > 0) { nodes[n] = nodes[n] + 1; } else { nodes[n] = 1; } } //copy(nodes.begin(),nodes.end(),std::ostream_iterator< std::pair< Node, int> >(cout,"\n")); out.close(); pair
              
                A[find_num+1]; if (nodes.size() < find_num) { copy(nodes.begin(),nodes.end(),std::ostream_iterator< std::pair< Node, int> >(cout,"\n")); return 0; } hash_map
               
                ::iterator it = nodes.begin(); int s=0; for (;s
                
                 first; A[s].second = it->second; } make_heap(A, A + find_num,node_hash_greater()); cout<<"\nheap start:\n"; copy(A, A + find_num,std::ostream_iterator< std::pair< Node, int> >(cout,"\n")); for (;it != nodes.end();it++) { if (it->second > A[0].second) { A[find_num].first = it->first; A[find_num].second = it->second; push_heap(A,A+find_num+1,node_hash_greater()); pop_heap(A,A+find_num+1,node_hash_greater()); } } sort_heap(A, A + find_num,node_hash_greater()); cout<<"\nresult:\n"; copy(A, A + find_num,std::ostream_iterator< std::pair< Node, int> >(cout,"\n")); return 0; }
                
               
              
             
            
           
          
         
        
       
      
     
    
   

结果：

转载地址：https://blog.csdn.net/thq0201/article/details/8675590 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！