私の '次のオフセット'アルゴリズムのバグ - C++

Question

アーカイブから読み込まれたファイルにファイル名を適用しようとしています。

最初のステップでは、3ビットの情報を保持する構造体の配列を作成します。ファイル名、ファイルサイズ、およびファイル内のオフセット（最初から）。ファイルサイズとオフセットは、最初に構造体に読み込まれます。次に、ファイル名をデコードしてベクトルに読み込みます。

ここでそれは難しいです。ファイル名は、オフセットの順番に適用されます。しかし、オフセットは順不同です。たとえば：3つのファイル名を持つので

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へファイル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 ...ループの外側にある "無限"に設定するか、last_offsetのテストに合格する最初のjを防ぐことができないほどの高いオフセット値を設定する必要があります。