Использование STL для поиска необработанных байтов и замены их в файле, что является лучшим / правильным способом

Question

Я хотел бы использовать STL (C ++ 0x в vs2010), чтобы открыть файл и выполнить двоичный поиск по нему, а затем заменить при обнаружении совпадения.

Я могу использовать fstream, чтобы открытьфайл, но я немного запутался в том, как искать файл.

Чтение одного байта за раз не очень хорошо, поэтому он должен прочитать блок в буфер, а затем мы ищем в буфере, но этофункциональность уже в STL?

Я хочу, чтобы часть буферизации была автоматической, когда поиск достигнет конца буфера, он должен автоматически прочитать следующий блок из файла, как если бы он читал его напрямую (используясмещения файлов и т. д.1011 * MapViewOfFile но я хочу использовать STL, чтобы сделать мой код переносимым, а также с помощью STL, также более гибким.Используя эти функции Windows, вы можете прочитать файл, не беспокоясь о буферизации и т. Д., Они даже обновят файл при изменении данных.Это функциональность, которую я использую после использования STL.

Обновление : я изменил «бинарный поиск» на «сырой поиск байтов», чтобы устранить путаницу, извините за это.

Пример функции поиска необработанных байтов (, если вам лучше, сообщите )

// NOTE: This function doesn't support big files > 4 gb
DWORD_PTR RawByteSearch( PBYTE pBaseAddress, DWORD dwLowSize, PBYTE pSignature, DWORD sigSize )
{
 PBYTE pBasePtr = pBaseAddress;
 PBYTE pEndPtr = pBaseAddress + dwLowSize;
 DWORD_PTR i;
 while ( pBasePtr < pEndPtr )
 {
  for (i = 0; i < sigSize; ++i)
  {
   if ( pSignature[i] != pBasePtr[i] )
    break;
  }
  if ( i == sigSize ) // Found a match
  {
   return pBasePtr - pBaseAddress;
  }
  ++pBasePtr; // Next byte
 }
 return 0;
}

Answer 1

std::search уже делает то, что вам нужно.

std::search(pBasePtr, bEndPtr, pSignature, pSignature+sigSize)

Из-за полноты вам не нужно использовать отображение памяти (хотя это, вероятно, будет наиболее эффективным).

Вместо этого на 100% переносимо решение использоватьитераторы потока библиотеки:

std::ifstream file;
std::search(std::istreambuf_iterator<char>(file.rdbuf()) // search from here
          , std::istreambuf_iterator<char>()             // ... to here
          , pSignature                                   // looking for a sequence starting with this
          , pSignature+sigSize);                         // and ending with this

Answer 2

Вам следует избегать термина «бинарный поиск».Это термин, используемый для поиска в отсортированных данных в логарифмическом времени, что вы делаете, это линейный поиск (в двоичных данных).Стандартная библиотека C ++ имеет функцию для этого, это std :: search.Это будет работать примерно так:

PWORD pos = std::search(pBaseAddress, pBaseAddress+dwLowSize, pSignature, pSignature+pSigSize);

PS Венгерская нотация отстой;)

Answer 3

std :: fstream имеет функцию с именем read , которая может считывать блок в буфер. Я что-то неправильно понимаю?

Редактировать: я только что сделал быстрый поиск по реализации отображенных в память файлов. Может быть, это может быть полезно для вас: http://www.boost.org/doc/libs/1_40_0/libs/iostreams/doc/classes/mapped_file.html

Answer 4

BinarySearch на самом деле означает начинать с середины и сравнивать, чтобы разделить пространство поиска на две части, а затем перейти к средней точке нового пространства поиска, чтобы разделить его дальше. Поскольку ваше пространство поиска уменьшается вдвое с каждой итерацией, операция выполняется за O (log N), что, в общем, намного быстрее.

Вы можете сделать это здесь, создав индекс.

Многое зависит от того, как отформатирован ваш файл. Он состоит из «записей» фиксированной длины с ключом в начале записи и с этим отсортированным ключом?

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

Например, допустим, что каждая запись имеет длину 128 байт, ключ - 4 байта, а запись - 32 КБ, поэтому размер файла составляет около 4 МБ. Если вы загружаете каждую 64-ю запись, вы читаете 512 из них и сохраняете 2К данных в памяти. При поиске в локальном индексе вы затем загружаете 8К-часть в память и ищете в ней фактическую запись, которую вы хотите изменить, и соответственно изменяете ее.

Если ваши записи не имеют одинаковую длину, у вас возникнет проблема, если ваша модификация вышла за пределы следующей записи.