c++ - 我的 'next offset' 算法中的错误 - C++

Question

我正在尝试将文件名应用于从存档加载的文件。

第一步，我创建了一个包含三位信息的结构体数组。文件名、文件大小和文件中的偏移量(从头开始)。文件大小和偏移量最初被读入结构。然后，我解码文件名并将它们读入 vector 。

这就是它变得棘手的地方。文件名顺序适用于偏移量的顺序。然而，偏移量不按顺序排列。例如:

File 1:
Name:
Size: 20102
Offset: 16

File 2:
Name:
Size: 23419
Offset: 2040

File 3:
Name:
Size: 145
Offset: 350

因此，将 3 个文件名解码到我的 vector 中后，我会将文件名 #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 是我的 vector ，其中包含字符串。 file_count 减 1，因为它包括不需要计数的存档目录文件。它也是最高的偏移量，因此甚至没有被处理。

基本上，此代码每次都会尝试找到下一个最高偏移量，然后应用 vector 中的下一个文件名。

这是我的错误日志的输出:

<-!-> 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。