c++ - 如何随机访问 C/C++ 中的文本文件？

Question

我有一个很大的日志文件，其中的记录按时间排序。每行都有一个时间。我需要找到时间 T1 和时间 T2 之间的所有记录(T1 <= T2)。我可以逐行扫描整个文件并找到带有 T1 的起始行，将其复制到缓冲区中，然后扫描下一行直到我到达结束时间 T2。这会起作用，但效率不高。

我想知道我是否可以使用二进制搜索来定位时间为 T1 和 T2 的行。但我不确定如何确定以下内容:

1. 文件的中间行
2. 如何确定我们应该传递给 lseek() 的偏移量？

是否可以对文件使用二进制搜索？

Answer 1

让我们假设，您的行在平均长度附近都是合理的(这意味着没有行会占据日志的一半左右)，这将使二进制搜索可行。

接下来我也假设你会有以下功能:

//find the first start of a new log line after (or including) position start
//return the last position of the file if no start could be found
streampos findNextLineStart(ifstream &file, streampos start);
//extract the data as a timestamp from a line
int extractDate(ifstream &file, streampos lineStart);

通过这些函数我们可以实现以下功能:

//find the position of the first line whose date is bigger than the given
streampos lower_bound(ifstream &file, int date)
{
  file.seekg(0, ios::end);
  streampos begin = 0, 
            end = file.tellg();
  while(begin < end)
  {
     streampos cur = (begin + end) / 2;
     streampos start = findNextLineStart(file, cur);
     //was a line start found?
     if(start < end)
     {
        int lineDate = extractDate(file, start);
        if(lineDate < date)
          begin = start;
        else
          end = start;
     }
     else
       //narrow the bound as no line was found
       end = cur;
  }
  return begin;
}

我不保证这会起作用(在所有极端情况下)，但它勾画了整体实现情况。一个人会使用另一个函数 upper_bound 并且使用那些你可以得到你范围内的行的开始和结束。