# Reverse words in a string without affecting space

I came across a problem that needs to reverse each word in a string without affecting space in it. For example, if a string has two spaces between the word, the answer needs to have space between two words. These are example test cases, I have been given
/This is a sentence/
/ This is a Sentence /
My approach is:

string oreverse(string s){
for(int i=0,n=s.size();i<n/2;++i)
swap(s[i],s[n-i-1]);
return s;
}
string reverseWords(string s) {
string re;
for(auto i=0;i<s.size();){
if(s[i]!=' '||s[i]=='/0'){
int _t = s.find_first_of(' ',i);
re+=oreverse(s.substr(i,_t-i));
i=_t;
}else{
re+=s[i];
i++;
}
}
return re;
}


I like to know, is there any further optimisation can be done or any other approaches with increased efficiency.

• Welcome to Code Review! Could you please provide an example main and provide all of the includes? Also, did you test this? The compiler should complain about '/0', as it should be '\0'. – Incomputable Jun 28 '18 at 10:28
• It's an online compiler and it haven't shown me the error I have done. Maybe. something wrong with the compiler. – Aswin Jun 28 '18 at 10:35
• @Aswin we need some more context (and example of the expected input/output). About context: which locales you need to support? To reverse an ASCII7 string is trivial, to reverse a string with modifiers, Unicode surrogate pairs, multi-byte UTF8 encoded code-points and other Unicode sequences (and, in general, grapheme clusters) is more complex. To handle tailored grapheme clusters is MORE complex. To reverse a string according to character directionality (to support RTL language) is MUCH MUCH more complex. To do it in a performance critical snippet is even worse. – Adriano Repetti Jun 28 '18 at 10:56
• In short: your C++ code might be reviewed (someone already did) but to be fundamentally broken may be your algorithm... – Adriano Repetti Jun 28 '18 at 10:57
• @Aswin, please do not update code after receiving an answer, as it invalidates the answer. Please read What should I do when someone answers my question?. – Incomputable Jun 28 '18 at 11:07

# Use compiler warnings

You should always enable compilers warning in c++. For your code, clang & g++ gives the following warnings (live demo):

prog.cc:14:29: warning: multi-character character constant [-Wmultichar]
if(s[i]!=' '||s[i]=='/0'){
^
prog.cc:13:19: warning: comparison of integers of different signs: 'int' and '...' (aka 'unsigned long') [-Wsign-compare]
for(auto i=0;i<s.size();){
~^~~~~~~~~
prog.cc:14:27: warning: result of comparison of constant 12080 with expression of type '...' (aka 'char') is always false [-Wtautological-constant-out-of-range-compare]
if(s[i]!=' '||s[i]=='/0'){
~~~~^ ~~~~


The ones about s[i]=='/0' are especially concerning. You probably meant s[i]=='\0'. I don't know if you want to handle other possible separators of a string (like tabs, line feeds). If it's the case, you should have a look at std::isspace or std::isblank.

The one about the for suggests that the type int (deduced for auto) might not be the most suited as a string/vector index. According to this post, the most portable index type to use would be std::string::size_type.

# Avoid std::string copy

Your code is performing a lot of string construction / copy / concatenation. They all can cause memory allocation/deallocation, which can be quite costly compared to the rest of your code. You should be able to avoid most of them.

## Output: generate the result directly in a single std::string

• You know exactly the size of the output string re (same size as input). You can preallocate it with std::string::reserve.
• Pass a reference to re to void oreverse(std::string& output,/*InputType*/ input), and directly push_back the characters of the input in reverse order.

## Input: work directly on the input string

• pass your input string by (const) references in both functions: const std::string&.
• avoid std::string::substr:
• C++17: you can use std::string_view instead of std::string. It's substr method won't do any copy.
• Pre-C++17: pass iterators to the input string to oreverse. Or a (const) reference to the input string, with start/end indices.

# Use "static" for global functions when applicable

Declaring a global function as "static" indicates to your compiler that your function is used only in the current translation unit (current *.cpp file). The compiler can use this information to do better inlining decisions (see for example gcc/g++: -finline-functions-called-once option).

• Thanks @vincent-saulue-laborde. I'll consider your points and learn through it. – Aswin Jun 28 '18 at 10:36

Well, Vincent covered almost everything as I was writing up alternative implementation... I'll just cover the rest then:

## Do not make unqualified calls

Unqualified call is a non-member function call which doesn't have :: in front of to-be-called function name. Example:

std::sort(numbers.begin(), numbers.end()); //qualified
sort(numbers.begin(), numbers.end()); //unqualified


The latter can do something abysmally evil. If you don't know what ADL is, do not make unqualified calls.

## Use iterators, possibly templated

Templates are not always a good thing, but using iterators is mostly a good thing. If one is tired of writing begin()/end() pair, one can just provide adapter interface for it.

## Alternative implementation

When creating non-trivial algorithm, it is better to get a pen and something to write on. One can observe that there are only two parts to this algorithm:

1) Copy into result until non-space is found

2) Anchor on current position, find first space occurrence from anchor, then reverse copy into the result

The whole algorithm then looks like this:

while didn't reach end:
execute 1)
if reached end, break
execute 2)


One can extract 1) and 2) into their own functions, but since they're trivial I didn't do so.

## Code

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

namespace rev {
using iterator = std::string::const_iterator;

std::string reverse_words(iterator first, iterator last) {
std::string reversed_words(std::distance(first, last), '\0');
auto d_first = reversed_words.begin();

while (first != last) {
while (first != last and *first ==' ')
*d_first++ = *first++;
if (first == last) break;

auto word_anchor = first;
while (first != last and *first != ' ')
++first;

std::reverse_copy(word_anchor, first, d_first);
d_first += std::distance(word_anchor, first);
}
return reversed_words;
}
}

int main() {
std::string words = "This is a bunch of words";
auto reversed = rev::reverse_words(words.begin(), words.end());

std::cout << reversed << '\n';
}


Demo.