Reversing lines & outputting to text file w/o vectors or arrays

[dakotad8218]

Really stumped here. Basically taking a multiple line text file such as this:

Mary had a little lamb
Its fleece was white as snow
And everywhere that Mary went
The lamb was sure to go.

And trying to reverse the line output, so I end up with something like this:

The lamb was sure to go.
And everywhere that Mary went
Its fleece was white as snow
Mary had a little lamb

I'm basically just trying to set the position of the stream get to the last character (in.seekg(0, ios::end);) and just iterate backwards through each character with a while loop, checking to see if any characters are newlines and if they are, grabbing the line with a getline(in_file, line). Am I missing something here? Super frustrated with random access so far.

  #include <iostream>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <string>

using namespace std;


int main()
{
    //declare and open streams
    ifstream in_file;
    in_file.open("input.txt");
    ofstream out_file;
    out_file.open("output.txt");

    //declare variable to contain individual lines
    string line;

    

    //start from the end of the file
    in_file.seekg(0, ios::end);

    //loop backwards to the beginning of the file
    char ch;

    while(in_file.get(ch))
    {
        in_file.seekg(-1, ios::cur);
        //if new line char found, move one ahead and get current line and output to file
        if(ch == '\n')
        {
            in_file.seekg(1, ios::cur);
            getline(in_file, line);
            out_file << line << endl;
        }
        
    }
    
    

    return 0;
}

[poteto]

I can see what you are trying to accomplish, which is to avoid putting the whole file into the heap, but it isn't really worth it since you are turning a 10 line solution into 100+ lines.

The problem is that windows inserts /r/n for newlines (carriage return), and this is only removed by reading the stream from left to right (by getline or >>, but seekg will not respect it), you can confirm this by loading a txt file in binary and printing the byte values out and comparing to an ascii table. And note that your optimization only applies to peak memory allocated, but if you are using getline, you are not optimizing away the total memory allocated (other than the std::deque or whatever to store the string lines).

Oh but I can spend all day explaining how you can accidentally create redundant allocations with strings very easily and std::move is required in certain cases, but I expect you already know all about that :) But something you would need to benchmark is whether it is cheaper to move the std::string into the queue, or is it faster to let getline reuse the string as a buffer and to directly copy into the queue (since std::string::clear() will not delete the memory, it will be reused).

[dakotad8218]

Please excuse my lack of knowledge, but this answer is a bit over my head. The point is to be able to use this to reverse any file, regardless of the amount of lines. I am a first semester C++ student so everything I'm working on is completely 100% new to me. To put it in perspective, only 3 months ago I was learning things like declaring variables and arrays. It's gotten advanced really quickly and I have an awful teacher who just reads the textbook word-for-word, so there is a foundation to many of these concepts I am missing, because she just skips ahead and assumes prior knowledge that I do not possess.

[mbozzi]

The solution you've presented suggests that you've thought about the problem and are trying to implement an optimization.

@poteto's trying to tell you not to bother.

Start with a vector of strings. Read all the lines in the file and put them into the vector, in order. Then print the vector's contents in reverse order.

[dakotad8218]

I've stated twice now that that is not an option. If I try to do this with say, a 2GB file and my machine only has 2GB of memory I would not be able to allocate enough. This needs to be able to scale without overwhelming the heap.

[mbozzi]

This needs to be able to scale without overwhelming the heap.

Okay, fine. So the problem's not that you aren't allowed to use std::vector.

Usually, when a new programmer posts something like this, the intent of the requirement is to dissuade the use of fixed-size arrays.

[dutch]

If you can store the starting positions:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ofstream out("output.txt", ios::binary);
    ifstream in("input.txt", ios::binary);

    vector<ios::pos_type> pos;
    pos.push_back(0);

    string line;
    while (getline(in, line))
        pos.push_back(in.tellg());

    size_t i = pos.size();
    if (i-- > 0)
        while (i-- > 0) {
            in.clear();
            in.seekg(pos[i]);
            getline(in, line);
            out << line << '\n';
        }
}

If you really need to go a character at a time, then maybe something like this:

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
    ofstream out("output.txt", ios::binary);
    ifstream in("input.txt", ios::binary);
    in.seekg(0, ios::end);

    string line;
    char ch;
    bool char_seen = false;

    in.seekg(-1, ios::cur);
    while (in.get(ch)) {
        if (ch == '\n' && char_seen) {
            auto pos = in.tellg();
            getline(in, line);
            out << line << '\n';
            in.clear();
            in.seekg(pos);
        }
        char_seen = true;
        in.seekg(-2, ios::cur);
    }
    in.clear();
    in.seekg(0);
    getline(in, line);
    out << line << '\n';
}

The best way is probably to use memory mapped files.

[dakotad8218]

No, the problem is precisely that I'm not allowed to use std::vector. I'm not allowed to use an array either. This has to use random access. I could have done it myself with an array or vector in 5 minutes.

For example, here's an implementation I found on stack overflow that uses pretty close to the same method, but only returns the last line and outputs to the terminal rather than to a text file:

#include <iostream>
#include <fstream>
#include <sstream>

using namespace std;

int main()
{
    string filename = "in.txt";
    ifstream in_file;
    in_file.open(filename);
    if(in_file.is_open()) {
        in_file.seekg(-1,ios_base::end);                // go to one spot before the EOF

        bool check = true;
        while(check) {
            char ch;
            in_file.get(ch);                            // Get current byte's data

            if((int)in_file.tellg() <= 1) {             // If the data was at or before the 0th byte
                in_file.seekg(0);                       // The first line is the last line
                check = false;                // So stop there
            }
            else if(ch == '\n') {                   // If the data was a newline
                check = false;                // Stop at the current position.
            }
            else {                                  // If the data was neither a newline nor at the 0 byte
                in_file.seekg(-2,ios_base::cur);        // Move to the front of that data, then to the front of the data before it
            }
        }

        string lastLine;
               
          getline(in_file,lastLine);
                                                   // Read the current line
        cout << "Result: " << lastLine << '\n';     // Display it

        in_file.close();
    }

    return 0;
}

I basically need to do what's been done here, just outputting each line to the .txt with a loop.

[dutch]

Did you see the second program I posted above?

[dakotad8218]

Just saw it, your edit came after mine so I didn't see it until a refresh. That was exactly what I was looking for, thank you much. Any reason you used an auto data type rather than an int?

[dutch]

tellg() returns an ios::pos_type which is "implementation defined" and may not be an int or even a basic arithmetic type at all (could be a struct/class).

[dakotad8218]

Understood. Thank you for the help! Sorry my needs were so specific. I also noticed that if I opened the file streams this way:

ifstream in_file;
in_file.open("input.txt");
ofstream out_file;
out_file.open("output.txt");

my program ended up just printing the last line continuously

The lamb was sure to go.
The lamb was sure to go.
The lamb was sure to go.
The lamb was sure to go.
The lamb was sure to go.
The lamb was sure to go.
The lamb was sure to go.
.......

But when I opened them using ios::binary the program ran correctly. Do you have a spare moment to explain why a text file stream needs to be opened in binary mode?

[dutch]

If you see a difference between text and binary modes that means you are probably on Windows where the end-of-line sequence is two chars, '\r' and '\n', whereas in *nix it is just '\n'. In text mode on Windows, the '\r' is ignored on reading (so you never see it) and automatically added before every '\n' on output.

You need to suppress this behavior in order to use the file positioning correctly. In binary mode, the '\r', if present, will simply be read in and printed out like a regular character, which is why we open the output file in binary mode, too. We don't want it to add an extra '\r'.

EDIT: I can see a bug in the code in the case where the end-of-line sequence is missing from the last line the code. It will add a '\n' without a preceding '\r'.

As for pos_type, turns out it is ultimately (most likely) an instance of the class std::fpos like std::streampos. https://en.cppreference.com/w/cpp/io/fpos

[dakotad8218]

Ah I see. My teacher and the entire school uses iMacs, no wonder it was taught that way. Looks like it's time to load up the ol' Ubuntu shell if this is an issue next semester. Thanks though, you saved my ass!

[dhayden]

I understand that you can't use vectors or arrays. Are you required to make it scale, or is that something you want to do yourself? If it doesn't need to scale, then do it recursively:

#include <iostream>
#include <string>

using std::string;
using std::cin;
using std::cout;

void reverse() {
    string line;
    if (getline(cin, line)) {
	reverse();
	cout << line << '\n';
    }
}

int main()
{
    // You can't call main recursively.
    reverse();
}