C++ Чтение файла в Array/List/Vector

Question

В настоящее время я работаю над небольшой программой, чтобы присоединиться к двум текстовым файлам (подобно объединению базы данных). Один файл может выглядеть следующим образом:

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

Второй похож:

    hsdf87347 
    7485C5 
    rhdff 
    23487 
    948FD4 

Оба файла имеют более 1.000.000 линий и не ограничивается определенным количеством символов. Мне бы хотелось найти все соответствующие строки в обоих файлах.

Я пробовал несколько вещей, Массивы, Векторы, Списки - но я в настоящее время борется с тем, чтобы решить, какой лучший (самый быстрый и простой в использовании).

Мой код в настоящее время выглядит следующим образом:

    #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 записей в массиве будет очень интенсивным и потребует много времени. Списки могут быстрее читать файлы, а случайный доступ дорог.

В конечном итоге я буду искать не только точные соответствия, но и первые четыре символа каждой строки.

Не могли бы вы помочь мне решить, какой самый эффективный способ? Я пробовал массивы, векторы и списки, но до сих пор не удовлетворен скоростью. Есть ли другой способ найти совпадения, которые я не рассматривал? Я очень счастлив полностью изменить код, с нетерпением жду любого предложения!

Большое спасибо!

EDIT: выход должен отображать соответствующие значения/линии. В этом примере вывод должен выглядеть так:

    7485C5 
    948FD4 

Answer 1

Если значения для этого уникальны в первом файле, это становится тривиальным при использовании характеристик набора O(nlogn). В следующем списке хранятся все строки в первом файле, переданные в качестве аргумента командной строки для набора, затем выполняет поиск O(logn) для каждой строки во втором файле.

EDIT: добавлен поиск преамбулы только с 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

ЧТЕНИЕ 2 миллиона строк не будут слишком медленно, что может быть замедление является ваше сравнение логика:

Использование: 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 и вставляя в него строки из обоих файлов, результирующий набор будет иметь только уникальные элементы.