Ошибка в алгоритме 'next offset' - C++

Question

Я пытаюсь применить имена файлов к файлам, загруженным из архива.

Для первого шага я создаю массив структур, содержащих три бита информации. Имя файла, размер файла и смещение в файле (с самого начала). Размеры и смещения файлов сначала читаются в структурах. Затем я декодирую имена файлов и читаю их в вектор.

Вот где это становится сложно. Имена файлов в порядке применяются к порядку смещений. Однако смещения не в порядке. Например:

File 1: 
Name: 
Size: 20102 
Offset: 16 

File 2: 
Name: 
Size: 23419 
Offset: 2040 

File 3: 
Name: 
Size: 145 
Offset: 350 

Так с 3-имена файлов декодируются в мой вектор, я бы применить имя файла # 1 в файл 1, файл # 2 в файл 3 (так как он имеет более низкое смещение), и, наконец, имя файла # 3 файл 2.

Теперь мой алгоритм для этого не работает правильно. Вот код:

file_names - это мой вектор со строками в нем. file_count вычитается на 1, потому что он включает файл каталога для архива, который не нужно подсчитывать. Это также самое высокое смещение и поэтому даже не рассматривается.

В основном, этот код пытается найти следующее самое высокое смещение каждый раз, а затем применить следующее имя файла в векторе.

Вот выход из моего журнала ошибок:

<-!-> File debug name: 
<-!-> File size: 17464 
<-!-> File offset: 47974 
<-!-> File debug name: 1dirt.bmp 
<-!-> File size: 17462 
<-!-> File offset: 12 
<-!-> File debug name: rrock.bmp 
<-!-> File size: 17464 
<-!-> File offset: 17011 
<-!-> File debug name: mtfloor.bmp 
<-!-> File size: 5176 
<-!-> File offset: 30725 
<-!-> File debug name: 
<-!-> File size: 17640 
<-!-> File offset: 134953 
<-!-> File debug name: 
<-!-> File size: 158 
<-!-> File offset: 140286 
<-!-> File debug name: 
<-!-> File size: 134188 
<-!-> File offset: 81658 
<-!-> File debug name: lights.wld 
<-!-> File size: 17464 
<-!-> File offset: 34273 
<-!-> File debug name: 
<-!-> File size: 1496 
<-!-> File offset: 139799 
<-!-> File debug name: 
<-!-> File size: 17464 
<-!-> File offset: 61625 

Это указывает на то, что явно не работал.

Другой вариант, который я могу сделать, это сортировать массив структур по смещениям по возрастанию,, о котором я не знаю, как это сделать, но сделало бы этот процесс намного проще, поскольку я мог бы просто применять имена по порядку.

Спасибо за ваше время и сообщите мне, если вы видите ошибку.

Answer 1

Сортировка, сортировка, сортировка! В противном случае вы получите алгоритм O (N). Нехорошо. Но вы не должны сортировать files, вместо того, чтобы построить отсортированный индекс к files массива следующим образом:

#include <algorithm> 
#include <vector> 

struct CompareOffset { 
    bool operator()(const file_type* x, const file_type* y) const { 
     return x->offset < y->offset; 
    } 
}; 

vector<file_type*> vec; 
for(size_t i = 0; i < files.size(); i++) 
    vec.push_back(&files[i]); 
std::sort(vec.begin(), vec.end(), CompareOffset()); 

for(size_t i = 0; i < file_names.size(); i++) 
    vec[i]->name = file_names[i]; 

Здесь file_type это ваш struct описания файла.

Answer 2

Вы правы, что сначала вам лучше отсортировать свои смещения, но конкретная ошибка в вашем алгоритме - это то, как вы инициализируете current_offset. Прямо за пределами цикла for (j ... вам нужно установить его в «бесконечность» или какое-то значение смещения настолько высоко, что оно не будет препятствовать первому j, который пройдет тест last_offset, чтобы стать текущим.