Reverse words in a string without affecting space

Question

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.

• Incomputable: 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円'.
• Aswin: It's an online compiler and it haven't shown me the error I have done. Maybe. something wrong with the compiler.
• Adriano Repetti: @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: In short: your C++ code might be reviewed (someone already did) but to be fundamentally broken may be your algorithm...
• Incomputable: @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?.

Answer 1

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).

• Aswin: Thanks @vincent-saulue-laborde. I'll consider your points and learn through it.

Answer 2

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.