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.

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

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.