C++将文件读入Array/List/Vector

Question

我目前正在研究一个加入两个文本文件（类似于数据库连接）的小程序。一个文件可能看起来像：

    269ED3 
    86356D 
    818858 
    5C8ABB 
    531810 
    38066C 
    7485C5 
    948FD4 

第二个是类似的：

    hsdf87347 
    7485C5 
    rhdff 
    23487 
    948FD4 

两个文件都超过000000线，不限于字符的具体数量。我想要做的是在两个文件中找到所有匹配的行。

我已经尝试了一些东西，数组，矢量，列表 - 但我目前正在努力决定什么是最好的（最快和内存容易）的方式。

我的代码目前的样子：

    #include iostream> 
    #include fstream> 
    #include string> 
    #include ctime> 
    #include list> 
    #include algorithm> 
    #include iterator> 
    using namespace std; 


    int main() 
    { 

     string line; 

     clock_t startTime = clock(); 

     list data; 
     //read first file 
     ifstream myfile ("test.txt"); 
     if (myfile.is_open()) 
     { 
      for(line; getline(myfile, line);/**/){ 
       data.push_back(line); 
      } 

      myfile.close(); 
     } 

     list data2; 
     //read second file 
     ifstream myfile2 ("test2.txt"); 
     if (myfile2.is_open()) 
     { 
      for(line; getline(myfile2, line);/**/){ 
       data2.push_back(line); 
      } 

      myfile2.close(); 
     } 
     else cout data2[k], k++ 
     //if data[j] > a; 

     return 0; 


    } 

我的思路是：用一个载体，在元素随机访问是非常困难和跳跃到下一个元素是不是最佳的（而不是在代码中，但我希望你明白了）。通过使用push_back并逐一添加行，也需要很长时间才能将文件读入矢量。随着数组的随机访问更容易，但阅读> 1.000.000记录到数组中会非常强烈，并且需要很长时间。列表可以更快地读取文件，随机访问又是昂贵的。

最终，我不仅会寻找完全匹配，而且还会查找每行的前4个字符。

你能帮我决定，最有效的方法是什么？我已经尝试过数组，向量和列表，但对目前的速度并不满意。有没有其他的方式来找到匹配，我没有考虑过？我很高兴完全更改代码，期待任何建议！

非常感谢！

编辑：输出应列出匹配的值/行。在这个例子中，输出应该看起来像：

    7485C5 
    948FD4 

Answer 1

如果这个值在第一个文件中是唯一的，那么在利用集合的O(nlogn)特性时，这将变得微不足道。以下内容将第一个文件中的所有行作为命令行参数传递给一个集合，然后执行O(logn)搜索第二个文件中的每一行。

编辑：增加了4个字符的前导码搜索。为此，该集只包含每行的前四个字符，而从第二个字符开始的搜索只查找每个搜索行的前四个字符。如果匹配，则第二个文件行将完整打印。完整地打印第一个文件将会更具挑战性。

#include <iostream> 
#include <fstream> 
#include <string> 
#include <set> 

int main(int argc, char *argv[]) 
{ 
    if (argc < 3) 
     return EXIT_FAILURE; 

    // load set with first file 
    std::ifstream inf(argv[1]); 
    std::set<std::string> lines; 
    std::string line; 
    for (unsigned int i=1; std::getline(inf,line); ++i) 
     lines.insert(line.substr(0,4)); 

    // load second file, identifying all entries. 
    std::ifstream inf2(argv[2]); 
    while (std::getline(inf2, line)) 
    { 
     if (lines.find(line.substr(0,4)) != lines.end()) 
      std::cout << line << std::endl; 
    } 

    return 0; 
} 

Answer 2

一个解决方案是一次读取整个文件。

使用istream :: seekg和istream :: tellg来计算两个文件的大小。分配一个足够大的字符数组来存储它们。使用istream :: read在适当的位置将这两个文件读入数组中。

Here is an example of the above functions.

Answer 3

读一两百万行不会过多慢，什么可能会减慢你的比较逻辑：

用途：std::intersection

data1.sort(data1.begin(), data1.end()); // N1log(N1) 
data2.sort(data2.begin(), data2.end()); // N2log(N2) 

std::vector<int> v; //Gives the matching elements 

std::set_intersection(data1.begin(), data1.end(), 
         data2.begin(), data2.end(), 
         std::back_inserter(v)); 

// Does 2(N1+N2-1) comparisons (worst case) 

你也可以尝试使用std::set并从两个文件中插入行，结果集只有唯一的元素。