1
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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'. \$\endgroup\$ – Incomputable Jun 28 '18 at 10:28
  • \$\begingroup\$ It's an online compiler and it haven't shown me the error I have done. Maybe. something wrong with the compiler. \$\endgroup\$ – Aswin Jun 28 '18 at 10:35
  • \$\begingroup\$ @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. \$\endgroup\$ – Adriano Repetti Jun 28 '18 at 10:56
  • \$\begingroup\$ In short: your C++ code might be reviewed (someone already did) but to be fundamentally broken may be your algorithm... \$\endgroup\$ – Adriano Repetti Jun 28 '18 at 10:57
  • \$\begingroup\$ @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?. \$\endgroup\$ – Incomputable Jun 28 '18 at 11:07
3
\$\begingroup\$

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

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.