CODEWITHSUNDEEP
c++stringrecursionspace-complexity
Dominic Farolino
Dominic Farolino

Reputation: 1383

String Reversal Memory Consumption Differences

Suppose I implement the following two string reversal algorithms:

void reverse(string &s) {
  if(s.size() == 1) return;
  string restOfS = s.substr(1);
  reverse(restOfS);
  s = restOfS + s.at(0);
}

string reverseString(string s) {
    if(s.size() == 1) return s;
    return reverseString(s.substr(1)) + s.at(0);
}

int main() {
    string name = "Dominic Farolino";
    reverse(name);
    cout << name << endl;
    name = reverseString(name);
    cout << name << endl;
    return 0;
}

One of these obviously modifies the string given to it, and one of returns a new string. Since the first one modifies the given string and uses a reference parameter as its mode of communication to the next recursive stack frame, I at first assumed this would be more efficient since using a reference parameter may help us not duplicate things in memory down the line, however I don't believe that's the case. Obviously we have to use a reference parameter with this void function, but it seems that we are undoing any memory efficiency using a reference parameter may give us since we since we are just declaring a new variable on the stack every time.

In short, it seems that the first one is making a copy of the reference every call, and the second one is making a copy of the value each call and just returning its result, making them of equal memory consumption.

To make the first one more memory efficient I feel like you'd have to do something like this:

void reverse(string &s) {
  if(s.size() == 1) return;
  reverse(s.substr(1));
  s = s.substr(1) + s.at(0);
}

however the compiler won't let me:

error: invalid initialization of non-const reference of type 'std::string& {aka std::basic_string<char>&}' from an rvalue of type 'std::basic_string<char>' 6:6: note: in passing argument 1 of 'void reverse(std::string&)'

Is this analysis correct?

Upvotes: 1

Views: 78

Answers (1)

Barry
Barry

Reputation: 303537

substr() returns a new string every time, complete with all the memory use that goes with that. So if you're going to do N-1 calls to substr(), that's O(N^2) extra memory you're using for no reason.

With std::string though, you can modify it in place, just by iterating over it with a simple for loop. Or just using std::reverse:

void reverseString(string &s) {
    std::reverse(s.begin(), s.end());
}

Either way (for loop or algorithm) takes O(1) extra memory instead - it effectively is just a series of swaps, so you just need one extra char as the temporary. Much better.

Upvotes: 3

Related Questions