Question

I need help making a more efficient method of searching through a text file in a C++ program.

The project specifies that we need to create text file of names, addresses, and account numbers.

For example:


Frank

1990 Mosley Avenue

Panama City, FL, 32444

CHL10910454


This would be the structure of each block of data written to the text file. The user of the program needs to have the ability to search for a specific person in the data file and make edits to their information.

I know usually I would read each line into an array, sort through the array to find the persons data in question, make the correction to the array and the rewrite the entire text file. However, i was wondering if there is a more efficient way of doing so?

Mainly, I was wondering if it was possible to search through the text file without writing the entire text file to an array, finding just the block of information in question and writing that to an array for edit. After editing just the block in question, you will reinsert the data over the where it was previously OR If I can insert it at the very end and erase the old version of the data from the text file.

Any help would be great! I do want you to keep in mind that as of yet we do not use the prefix std::. We use the "using namespace std" at the very beginning. However, I do understand the use of std:: for the most part.

Thanks for all your help!

No correct solution

OTHER TIPS

It's good that you're thinking about this, but:

  • in most operating systems and filesystem types, you can overwrite specific bytes in the file content, but there's no way to insert or erase data part way through the file such that later data is moved to create or fill a gap: this means that if you want to replace "Sonya" with "Susan" it can be done in-place, but if you change "Sonya" to "Sue" then all the rest of the file must be read and written 2 bytes further forward in the file (unless you decide it's ok to fill in the 2 unneeded characters with say spaces, but then you're still stuck if e.g. "Tom" is changed to "Thomas").

  • if you're determined to pursue this, you first need to know if the file is sorted on the key you need to search by:

    • if not then you'll have to read through the file at least until you find the data to be changed, and if the length of the new data doesn't perfectly match the length of the old data then you'll need to read and write out the updated content thereafter anyway

    • if so, then you could do a binary search through the file to find the record to be updated, but as the lines are of variable length you'd need a heuristic approach to recognising which line was name, which addresses, which bank account. That's probably possible if the accounts are all single "words" comprised of uppercase letters and numbers. It's a fairly tricky undertaking for a learner though - easier to do a binary search like that on a memory mapped file so you don't have to worry about data overlapping the edges of a fixed-sized buffer into which you're reading parts of the file.

  • for many small programs, it's perfectly fine and practical to do it the "dumb" way - load the data in to memory then operate on it there, just writing it out to avoid losing work if there's a crash, and before exiting if there's unwritten changes

  • for larger programs, you could move to a database

The fastest method to search through a file is to read the entire file into memory and search memory.

If the records in the file are of fixed size, you could use file positioning to mark where records start. This could be used in an index table, such as std::map<key, file_position>. You would search the container using the key, get the file position and read the record from the file position.

If your record quantity is small, you may want to read the records into a std::vector. Create index tables using std::map<key, vector_index> for each key you want to search with. This is similar to how databases create search indices to speed up searches.

Anything more complex than this, I suggest using a database.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top