updating a file in sorted order

Question

suppose my file contains Names

         Nitish
         Prudhvi Raj Borra  
         Rajesh
         Srinath

now what the questions i want to update the file i mean i want to append some data in the file suppose i want to enter The Name "Sarath Chandra"

the file should updated in sorted order like this

         Nitish
         Prudhvi Raj Borra  
         Rajesh
         Sarath Chandra
         Srinath

so my method in at first i will store all the words in an vector

                     string line;
                    ifstream fin("somefile.txt");
                    while(!fin.eof()){
    fin>>line;//fin 
            v.push_back(line);//v some be vector name
}

i will also the entered name in vector and sort like this

                 sort(v.begin,v.end);

and after wards i will open the file in write mode and then copy back the vector contents into the file but this takes so much memory is there any method to update a file without using any extra memory

i think you mean "open the file in write mode", and i don't see how this would take "so much memory" unless you have millions of names. — Borgleader, Aug 08 '13 at 19:15
It can take as little as memory for only two names. Plus enough external memory to story a copy of the original file plus the new name. — Jongware, Aug 08 '13 at 19:22

score 0 · Answer 1 · edited May 23 '17 at 11:56

Per http://www.cplusplus.com/reference/algorithm/sort/, vector::sort performs at O(nlogn) time, though it doesn't have any information about overhead. If you would really like to save memory, you could write a function that sorts the data in place, or try to take advantage of inplace_merge (http://www.cplusplus.com/reference/algorithm/inplace_merge/). I have never used that particular function though, so I don't know whether it's exactly what you are looking for or not.

This also might be useful to you: How to sort in-place using the merge sort algorithm?

A naive solution would be to use a bubble sort, which is in place, but if you have so much data that you are worried about memory then this will be a very slow solution.

One more thing: if you know the file is already sorted, it takes no overhead (beyond storing the name to be inserted) and O(n) insertion time to simply parse the file until you find the correct insertion point.

updating a file in sorted order

1 Answers1