Ошибка в моем алгоритме «следующего смещения» - 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.

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

// Keep track of the last offset we used
    int last_offset = 0;
    int current_offset = 0;
    int index = 0;

    // Finally, apply the correct filenames to the correct files
    for(int i = 0; i < file_names.size(); i++)
    {
        for(int j = 0; j < file_count - 1; j++)
        {
            if(j == 0)
            {
                current_offset = files[j].offset;
            }

            if(files[j].offset > last_offset && files[j].offset < current_offset)
            {
                index = j;
                current_offset = files[j].offset;
            }
        }
        files[index].name = file_names[i];
        last_offset = current_offset;
    }

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, стать текущим.