Reversing a string? a more optimal way

Question

#include<iostream>
#include<string.h>
using namespace std;
int main ()
{
    char str[50], temp;
    int i, j;
    cout << "Enter a string : ";
    gets(str);
    j = strlen(str) - 1;
    for (i = 0; i < j; i++,j--)
    {
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
    cout << "\nReverse string : " << str;
    return 0;
}

Is there any more optimal way without using this function to reverse a string ? The function will start from the last position of S and will continue to be copied the string reversed. Instead of using the tmp variable.

string reverse(string s)
{
    string reversed ;
    for(int is.length();int i >0;--)
    {
        reversed +=s[i];
    }
return reversed;
    }

The original method loops over half the string and swaps each char with the char on the other side. Yours copies the entire string, so assuming that copying one char over is half as expensive as doing a swap, the result is the same. But then we didn't consider all the overhead in your new method yet that happens behind the scenes, such as allocating the new string, deleting the old string and resizing it multiple times (though that's amortized O(n)). Both methods are O(n), but the second one will hardly be any faster. But why not just time it and see for yourself? — Blaze, Mar 15 '19 at 10:27
I think there are a couple of characters missing in your snippet, but no, it's not a better method. First, you are creating a new string, instead of reversing in place, so it's more memory. Second, you are appending to a `std::string` character-wise, which (potentially) means continuous resizing of its internal buffer. Third, the number of iterations in the first string is just half the size of the string, whereas your second algorithm has to iterate it entirely. — jdehesa, Mar 15 '19 at 10:29
[Why is the gets function so dangerous that it should not be used?](https://stackoverflow.com/q/1694036/995714) — phuclv, Mar 15 '19 at 13:27
efficiency depends on the architecture, so there's no definitive single answer to that. And on modern systems reversing with SIMD is probably the fastest way. But it might even be faster to change the procedure that receives your reversed string to just iterate the string in reverse with [`std::string::rbegin()`](https://en.cppreference.com/w/cpp/string/basic_string/rbegin) — phuclv, Mar 15 '19 at 13:31
Are you aware that `strlen` is also O(n) ? Using the string class (which tracks length in a variable) can give some efficiencies in that regard. — Brannon, Mar 15 '19 at 15:09

score 1 · Answer 1 · answered Mar 15 '19 at 15:06

You can use std::reverse to reverse the string in place, with complexity being (last - first)/2 swaps, which is exactly the complexity of the first function, but is cleaner.

The second method has an overhead of extra allocation which will probably end up being slower.

score 0 · Accepted Answer · answered Mar 15 '19 at 15:22

I have tested the two option with quite large files.

The std::reverse(ss.begin(), ss.end()); corresponds to the first option (no copy)
The ss_r = new std::string(ss.rbegin(), ss.rend()); corresponds to the second option (copy)

#include <iostream>
#include <fstream>
#include <chrono>
#include <string>
#include <algorithm>
//Just for reading the file
std::string read_file(char * file_name)
{
      std::ifstream file(file_name);

      std::string ss;
      file.seekg(0, std::ios::end);
      std::cout << file.tellg() <<std::endl;
      ss.resize(file.tellg());
      file.seekg(0, std::ios::beg);
      file.read(&ss[0], ss.size());
      file.close();

      return ss;
}
//The real test
int main(int arg, char ** args)
{
      std::string ss = read_file(args[1]);
      std::string * ss_r=NULL;

      std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
      start = std::chrono::high_resolution_clock::now();

      if(args[2]==std::string("copy"))
      {
            //Second option
            ss_r = new std::string(ss.rbegin(), ss.rend());
      }
      else
      {
            //First option
            std::reverse(ss.begin(), ss.end());
      }
      end = std::chrono::high_resolution_clock::now();
      int elapsed_nano_seconds = std::chrono::duration_cast<std::chrono::nanoseconds>
                             (end-start).count();
      if(ss_r!=NULL)
      {
            std::cout<<*ss_r<<std::endl;
      }
      else
      {
            std::cout<<ss<<std::endl;
      }
      std::cout << elapsed_nano_seconds<<std::endl;
}

Testing with icpc test.cpp -O3 --std=c++11

a.out Test_file no_copy runs in 160 microseconds
a.out Test_file copy runs in 320 microseconds

On the other hand with the first option you lost the original string...

So in summary if you don't care about loosing the original string go with std::reverse if you want to keep it go with std::string(ss.rbegin(), ss.rend());

Reversing a string? a more optimal way

2 Answers2