Cpp Get File Line by Index

Question

I have a C++ program which reads a specific line from a file based on the index of that line. The index is calculated elsewhere in the program. My question is: can I open a file (i.e., a .txt) and read a line specified by its index?

So far, I have the following code:

#include <iostream>
#include <fstream>
std::string getLineByIndex(int index, std::fstream file)
{
 int file_index = 0;
 std::string found_line;
 for( std::string line; std::getline(file, line); )
 {
 if (index == file_index)
 {
 found_line = line;
 break;
 }
 file_index++;
 }
 return found_line;
}

This linear search will of course become less efficient as the number of lines in the file scales. Therefore, is there a more efficient way to read a line from a file using its index? Does the answer change if each line in the file is the exact same length?

• molbdnilo: A file doesn't have "lines" - that's just a convention. If you want indexing, you need to make every line the same length (some text file formats in the 1960s did exactly that).
• molbdnilo: It will be slightly more efficient to ignore every line before the one you need.
• Some programmer dude: How large is the file? Can you load it all into a vector, with each line is an element in the vector? Then it becomes trivial to get a specific line by "index".
• abcdefg: If the lines have the same length, it is possible to directly access the corresponding part in the file. Otherwise, in case getLineByIndex is called very often, you could iterate once the file and remember the offset in the file of each line beginning, which will allow you to access to it directly after.

Answer 1

Files have no indexes. There are offsets though. They can be thought of as indexes, but they "index" not the lines, but certain bytes. If the line length is known and fixed, you can calculate the offset at which the searched line is located, move the "cursor" at this offset, and read it with one operation. I do not know how this works in C++, but in C you will use lseek for file descriptors, and fseek for FILE structures. I'd suggest reading on file offset manipulation in iostreams, or use stdio.h.

Basically, if the line length is 10 and you need 3rd line you will move offset at 10 * 3 and read 10 bytes. You should also factor in the file contents. If there are cyrillic letters, for example, then offset might point at the certain bytes in one letter, which makes the task more difficult.

If line length is not fixed:

If you do this fetching of lines from one particular file often, I suggest reading file in it's entirety into the memory, provided the file is not too big, placing the lines into the vector. Or you can mmap the file - this is pretty much the same.

Or, if the file is big, and you need to access it's lines often, I'd suggest caching each fetch operation. Basically - read a file, got a line - place it's somewhere if you will need it later.

Overall, the best solution depends on what exactly you want to achieve. Is the file big? How often will the file be read? Is there only one file, or several files? Is the line length fixed?

But I think that your current solution is probably the most sane. Not too difficult, just read the lines in the loop.

Answer 2

Here a solution that will keep track of the lines offsets in the file. This makes it possible to go directly at the good position in the file in case we already asked for an index.

#include <fstream>
#include <iostream>
#include <map>
class GetLineByIndex
{
public:
 GetLineByIndex (std::fstream& file) : file_(file) {}
 
 std::string operator() (std::size_t index)
 {
 // We check whether this index has already been used
 auto lookup = offsets_.find(index);
 if (lookup == offsets_.end())
 {
 // We retrieve the line and its offset in the file.
 std::pair<std::string,std::fstream::pos_type> info = getLineByIndex (index);
 // We remember the offset for further calls. 
 offsets_[index] = info.second;
 
 // We return the line
 return info.first;
 }
 else
 {
 // The index has already been seen, we can get the associated offset in the file.
 std::fstream::pos_type offset = lookup->second;
 
 // We get the line and return it.
 return getLineByOffset (offset);
 }
 }
 
private:
 std::fstream& file_;
 std::map<std::size_t, std::fstream::pos_type> offsets_;
 
 // Return the line and its offset in the file.
 std::pair<std::string,std::fstream::pos_type> getLineByIndex (std::size_t index)
 {
 std::size_t file_index = 0;
 std::string found_line;
 std::fstream::pos_type pos=0;
 
 file_.seekp(0); 
 
 for( std::string line; std::getline(file_, line); )
 {
 if (index == file_index)
 {
 found_line = line;
 break;
 }
 file_index++;
 pos = file_.tellp();
 }
 return std::make_pair (found_line, pos);
 }
 
 // We get the line that begins at the provided offset.
 std::string getLineByOffset (std::fstream::pos_type offset)
 {
 // We go to the provided offset. 
 file_.seekp (offset);
 
 // We get the line.
 std::string line;
 std::getline(file_, line);
 
 return line;
 }
};
int main (int argc, char* argv[])
{
 std::fstream file (argv[1]);
 
 // We instantiate our struct.
 GetLineByIndex getter (file);
 
 // We test some indexes.
 for (std::size_t idx : {0,1,2,2,5,2})
 {
 // We get the line for the given index.
 std::cout << getter(idx) << "\n"; 
 }
}

Note that this is just the main idea and is not fully tested; some checks should also be done.

Note also that in case of a new index, we could first find the nearest lowest index in the map, which would allow to speed up the lookup for the required line.