Reverse the word order in string, without reversing the words

I was tasked with using C++ to turn this

"Hello Jarryd, do you like socks?"

into:

"socks? like you do Jarryd, Hello";

Edit: The condition was to reverse this in place.

Here's what I came up with, knocked up in Visual Studio using the TestExplorer to run it. Criticism is much appreciated!

.h

namespace SentenceFlipNamespace
{
class SentenceFlip
{
public:
SentenceFlip();
~SentenceFlip();

int FlipSentenceInPlace(char* in_Sentence);
void SentenceFlip::Move(int in_StartIndex, char in_String[]);

};
}


.cpp

namespace SentenceFlipNamespace
{
SentenceFlip::SentenceFlip()
{
}

SentenceFlip::~SentenceFlip()
{
}

int SentenceFlip::FlipSentenceInPlace(char in_Sentence[])
{
int index = 0;
int length = strlen(in_Sentence);

while (index < length)
{
int dist = 0;
int wordSize = 0;

//Get the characters to the first word
for (int i = length - 1; i > 0; i--)
{
if (in_Sentence[i] == ' ' && i != length - 1)
{
dist = i - index;
wordSize = length - i - 1; //exclude the space
break;
}
}

//Push everything forwards
for (int i = 0; i <= dist; i++)
Move(index, in_Sentence);

//This leaves a space at the end, push it forward
if (index + wordSize >= length)
return 0;

for (size_t i = 0; i < length - wordSize - index - 1; i++)
Move(index + wordSize, in_Sentence);

index += wordSize + 1; //include the space
}

return -1;
}

void SentenceFlip::Move(int in_StartIndex, char in_String[])
{
char temp = in_String[in_StartIndex];
int length = strlen(in_String);
for (int j = length - 1; j >= in_StartIndex; j--)
{
char temp2 = in_String[j];
in_String[j] = temp;
temp = temp2;
}
}
}


Test Method, since I don't invoke it in main.

namespace CodeChallengesTests
{
TEST_CLASS(TextFlip)
{
public:
TEST_METHOD(SentenceFlipInPlace)
{
SentenceFlipNamespace::SentenceFlip *testFlip = new SentenceFlipNamespace::SentenceFlip();
char input[] = "Hello Jarryd, do you like socks?";
char expectedResult[] = "socks? like you do Jarryd, Hello";
testFlip->FlipSentenceInPlace(input);

Assert::AreEqual(expectedResult, input, "Results do not match");
}
};

}

• Welcome to code review. We can do a better job of reviewing your code if you provide the entire SentenceFlip class and the main program. Jul 12 '19 at 14:24
• I've added the .h, .cpp and my test method. Thank you, and I'll add these to future questions. Jul 15 '19 at 4:20

Your algorithm is supremely inefficient. Moving a word to the front moves all the other characters to the back, resulting in a quadratic algorithm. In addition to that, you repeatedly recalculate the length of the null terminated string.

As an aside, the standard library provides std::rotate() for moving part of a sequence from the end to the beginning, no need to write your own.

There is an alternative in-place algorithm which swaps every character at most twice, and traverses three times. Thus it is trivially proven linear:

1. Reverse every word in isolation. Remember the end if needed.
2. Reverse everything.

The standard library features std::reverse() for implementing this.

• Oh damn, I am completely out of touch with the standard library, which I need to remedy. And what a great idea, to reverse the words like that. Thanks for taking the time to provide such a great answer, I've learned a lot! Jul 15 '19 at 4:08

I would probably do this by reading the words into a vector of strings, then rather than reversing the order, just traverse the vector in reverse order:

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>

int main() {
std::vector<std::string> words { std::istream_iterator<std::string>(std::cin), {} };

std::copy(words.rbegin(), words.rend(),
std::ostream_iterator<std::string>(std::cout, " "));
std::cout << '\n';
}


So a couple obvious points:

1. Avoiding work is good.
2. Letting your code avoid work is good too.
3. The standard library has lots of stuff that can make programming a lot easier.
• Love that. Now if only if we had reverse ranges so we could use the range based for. Jul 12 '19 at 23:56
• @MartinYork: Soon (C++20). Probably available already, if you use a reasonably new compiler. Jul 13 '19 at 0:51

Just find words in reverse order and put them in new string.

Code should be quite simple:

std::string reverse_words(std::string_view s)
{
std::string result;
result.reserve(s.size());
while(!s.empty()) {
auto i = s.rfind(' ');
result.append(s.begin() + i + 1, s.end());
if (i == std::string_view::npos) break;
result += ' ';
s = s.substr(0, i);
}
return result;
}


This code is fast since it does minimum allocations and minimum amount of coping.

• Welcome to code review. We do things a little differently than stack overflow, good answers actually comment on the users code rather than provide alternate solutions. Jul 13 '19 at 3:39

If it is important to execute the reversing in place, here is an example code (which implements the algorithm mentioned in https://codereview.stackexchange.com/a/224037):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

static void reverse_chars(char *s, int n)
{
int n2 = n / 2;
for (int i = 0; i < n2; i++)
{
char tmp = s[i];
s[i] = s[n - i - 1];
s[n - i - 1] = tmp;
}
}

static char *get_next_word(char *s, int *wlen)
{
while (*s && isspace(*s))
s++;
if (*s == '\0')
return nullptr;
char *p = s;
while (*p && !isspace(*p))
p++;
*wlen = (p - s);
return s;
}

static void reverse_words(char *s, int n)
{
reverse_chars(s, n);
int wlen;
char *w;
while ((w = get_next_word(s, &wlen)) != nullptr)
{
reverse_chars(w, wlen);
s += wlen;
}
}

int main(int argc, char **argv)
{
if (argc < 2)
{