Reverse words and trim

Why it matters

Text from people is messy. Someone types two spaces after a word, or pastes a line with a space at the start. A program that compares "blue " with "blue" sees two different values, so a search for the word fails. Removing the extra spaces is a common first step in any text task.

Reversing the order of words is a good exercise because it needs two skills at once. You must move through a string by index, and you must change characters inside the string without losing any of them. The same skills appear in palindrome checks, string reversal and parsing.

The CSV lesson in this module split a line on commas. This lesson splits on spaces, and the rule is different. A run of several spaces counts as one separator, and spaces at the start or end never create an empty word.

Words, spaces and indexes

A word here is one or more characters in a row that are not spaces. A space is the character ' ', written in single quotes. A single character has type char. Text in double quotes has type std::string.

A std::string is a row of characters. Each character has a position called an index. The first character is at index 0. The last character is at index s.size() - 1. The expression s[3] means the character at index 3.

Trim means remove the spaces at both ends of the text. Collapse means turn a run of spaces into one space. Take this input:

"  hello   world  "

It has two spaces at the start, three spaces between the words, and two spaces at the end. After trimming and collapsing, the text is hello world. After reversing the word order, it is world hello.

std::string has no built-in trim or split method. You write these with loops. A stream such as std::istringstream can split words for you, but then the work happens inside the stream and the string itself is never examined. This lesson writes the loops by hand.

Method 1: collect the words, then join them backwards

The first method works in two stages. It walks through the text once and collects each word into a list. Then it walks through the list from the last word to the first and joins the words with one space between each pair.

A std::vector is a list that holds values of one type and grows as you add values. A std::vector<std::string> is a list of strings.

#include <iostream>
#include <string>
#include <vector>
 
std::vector<std::string> split_words(const std::string& text) {
    std::vector<std::string> words;
    std::string current;
    for (char c : text) {
        if (c == ' ') {
            if (!current.empty()) {
                words.push_back(current);
                current.clear();
            }
        } else {
            current.push_back(c);
        }
    }
    if (!current.empty()) {
        words.push_back(current);
    }
    return words;
}
 
std::string reverse_words_with_list(const std::string& text) {
    std::vector<std::string> words = split_words(text);
    std::string result;
    for (std::size_t i = words.size(); i > 0; --i) {
        result += words[i - 1];
        if (i > 1) {
            result += ' ';
        }
    }
    return result;
}

The loop in split_words reads one character at a time into current. When it reads a space, it saves current into the list, if current is not empty, and then empties it. Here is what happens to "the sky is blue".

1. Read t, h, e. current becomes the.
2. Read a space. the goes into the list. current is empty again.
3. Read s, k, y. current becomes sky.
4. Read a space. sky goes into the list. current is empty again.
5. Read i, s, then a space. is goes into the list.
6. Read b, l, u, e. The text ends. The word blue is still in current, so the last if saves it.

The list now holds ["the", "sky", "is", "blue"].

The loop in reverse_words_with_list counts i down from the number of words to 1. It reads words[i - 1], so the index never goes below 0. It adds a space only when i > 1. The first word in the list is the last one written, so no space follows it, and the result has no space at the end.

Why the loop counts down this way

A common first attempt is for (std::size_t i = words.size() - 1; i >= 0; --i). That loop has a hidden problem. words.size() returns an unsigned number, of type std::size_t. An unsigned number cannot be negative. Here i is unsigned too, so when i reaches 0, --i does not give -1. It would give a very large number, and the loop would not stop. Counting i from the size down to 1, and reading words[i - 1], avoids this.

What this method costs

Each word is copied twice: once into the list and once into result. The memory used is about the size of the text, because the list and the result both hold the same letters. The time grows in step with the number of characters. Computer scientists write this as O(n), read as "order n". The letter n stands for the length of the text, so doubling the text roughly doubles the work.

Method 2: change the text in place

"In place" means the characters are changed inside the same string. This method does not build a list of words. It works in three steps.

1. Remove the extra spaces, so the text has single spaces between words and no spaces at the ends.
2. Reverse all the characters in the string. The words are now in reverse order, but each word is spelled backwards.
3. Reverse each word again, so the spelling is normal.

For "the sky is blue", step 2 gives "eulb si yks eht" and step 3 gives "blue is sky the".

Step 1: remove the extra spaces

The code uses two index positions. in reads the input from left to right. out is where the next kept character is written. out is never larger than in, so every write goes to a position that has already been read. No character that is still waiting to be read gets overwritten.

std::size_t out = 0;
std::size_t in = 0;
while (in < s.size()) {
    while (in < s.size() && s[in] == ' ') {
        ++in;
    }
    if (in == s.size()) {
        break;
    }
    if (out > 0) {
        s[out++] = ' ';
    }
    while (in < s.size() && s[in] != ' ') {
        s[out++] = s[in++];
    }
}
s.resize(out);

The outer loop does one word per round. The first inner loop skips all spaces. The break ends the loop when only spaces are left, which handles trailing spaces. The if (out > 0) check writes one space before every word except the first, which handles the leading spaces. The second inner loop copies one word.

The last line, s.resize(out), cuts the string down to the cleaned length. Without it, leftover characters from the old text stay at the end. Common mistakes shows what this looks like.

Here is the trace for " a b ", which is six characters long: space, a, space, space, b, space.

1. in moves past the first space to index 1. out is 0, so no space is written. The letter a is copied to index 0. Now out is 1 and in is 2.
2. The skip loop moves in past two spaces to index 4. out is 1, so a space is written at index 1. The letter b is copied to index 2. Now out is 3 and in is 5.
3. The skip loop moves in past the last space to index 6, which is the end of the string. The break runs.
4. s.resize(3) keeps indexes 0 to 2, so the string is a b.

Step 2: reverse the whole string

To reverse a range, swap the two characters at the ends, move both positions one step toward the middle, and repeat. The loop stops when the two positions meet or cross.

void reverse_range(std::string& s, std::size_t left, std::size_t right) {
    while (left < right) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
        ++left;
        --right;
    }
}

The parameters left and right are both indexes, and both ends are included in the range. A range with one character has left equal to right, so nothing is swapped. Reversing "a b" from index 0 to index 2 swaps a and b, which gives "b a".

Step 3: reverse each word

This step finds each word by its start and end. The variable start marks the first character of the current word. The loop checks each position i. When i reaches a space or the end of the string, the word runs from start to i - 1. The code reverses that part. Then start moves to i + 1, the character after the space.

std::size_t start = 0;
for (std::size_t i = 0; i <= s.size(); ++i) {
    if (i == s.size() || s[i] == ' ') {
        if (i > start) {
            reverse_range(s, start, i - 1);
        }
        start = i + 1;
    }
}

The check if (i > start) skips an empty word. After step 1, an empty word can only appear when the whole text is empty. The check keeps the loop safe in that case too.

The full in-place function

Put this function after reverse_range in the same file as the list method.

std::string reverse_words_in_place(std::string s) {
    std::size_t out = 0;
    std::size_t in = 0;
    while (in < s.size()) {
        while (in < s.size() && s[in] == ' ') {
            ++in;
        }
        if (in == s.size()) {
            break;
        }
        if (out > 0) {
            s[out++] = ' ';
        }
        while (in < s.size() && s[in] != ' ') {
            s[out++] = s[in++];
        }
    }
    s.resize(out);
 
    if (s.empty()) {
        return s;
    }
 
    reverse_range(s, 0, s.size() - 1);
 
    std::size_t start = 0;
    for (std::size_t i = 0; i <= s.size(); ++i) {
        if (i == s.size() || s[i] == ' ') {
            if (i > start) {
                reverse_range(s, start, i - 1);
            }
            start = i + 1;
        }
    }
    return s;
}

The parameter is a copy of the text, because the function changes it and the caller keeps the original. The if (s.empty()) check comes before step 2 and is explained in Common mistakes.

Worked examples

Example 1: a plain sentence

The input "the sky is blue" has one space between each pair of words and no spaces at the ends. Step 1 leaves the text unchanged. Step 2 turns it into eulb si yks eht, which is the same letters in reverse order. Step 3 reverses each run of letters that is between spaces. The runs are eulb (indexes 0 to 3), si (5 to 6), yks (8 to 10) and eht (12 to 14). They become blue, is, sky and the. The result is blue is sky the.

Example 2: extra spaces

The input " hello world " has spaces at both ends and three spaces between the words. Step 1 removes the spaces at the ends and reduces the three spaces to one, so the text becomes hello world. Step 2 turns it into dlrow olleh. Step 3 turns the two words back into world and hello. The result is world hello.

The list method reaches the same result. Its split_words never stores an empty word, so the repeated spaces disappear there as well.

Example 3: short and empty input

Three inputs have no normal sentence in them.

• "a" has one word. Step 2 reverses one letter, which changes nothing. The result is a.
• " " is only spaces. Step 1 skips all of them, so out stays 0 and resize(0) empties the string. The function returns early, and the result is the empty string.
• "" is already empty. The early return handles it.

Both methods give the same results for all five inputs in the run below. The list method needs no special case for empty input, because split_words finds no words and the result stays empty.

Run it

Put the split_words and reverse_words_with_list functions from Method 1, reverse_range and reverse_words_in_place from Method 2, and this main function in one file named reverse_words.cpp.

int main() {
    const std::string inputs[] = {
        "the sky is blue",
        "  hello   world  ",
        "a",
        "     ",
        "",
    };
    for (const std::string& text : inputs) {
        std::cout << '"' << text << "\" -> list: \"" << reverse_words_with_list(text)
                  << "\" in place: \"" << reverse_words_in_place(text) << "\"\n";
    }
}

Compile and run it with:

g++ -std=c++20 -Wall -o reverse_words reverse_words.cpp
./reverse_words

The output on g++ 15.2.0 is:

"the sky is blue" -> list: "blue is sky the" in place: "blue is sky the"
"  hello   world  " -> list: "world hello" in place: "world hello"
"a" -> list: "a" in place: "a"
"     " -> list: "" in place: ""
"" -> list: "" in place: ""

The compile step prints no warnings with -Wall.

Common mistakes

Calling at or indexing an empty string

The last index of an empty string is s.size() - 1. Because size() is unsigned, 0 - 1 does not give -1. It gives the largest value an unsigned number can hold. Here is a small program that reads the last character of an empty string.

#include <iostream>
#include <string>
 
int main() {
    std::string empty;
    char last = empty.at(empty.size() - 1);
    std::cout << last << std::endl;
}

It stops with this message on g++ 15.2.0 (libstdc++):

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 18446744073709551615) >= this->size() (which is 0)

The number 18446744073709551615 is the wrapped value of 0 - 1. The at function checks the index and throws an error. Plain empty[empty.size() - 1] does not check. Reading past the end of a string is undefined behaviour, which means the C++ rules do not say what happens. The program may crash later or keep running with wrong data. The if (s.empty()) check in reverse_words_in_place prevents both problems.

Forgetting to shrink the string

Step 1 writes the cleaned text over the start of the string, but it does not remove the old characters at the end. The original "a b" has four characters. The cleaning loop writes a, a space and b into the first three positions, and the fourth position still holds the old b. Here is the result when resize is left out. The program was run with that line removed.

without resize: [a bb] size 4

The string has an extra b at the end. Calling s.resize(out) after the loop removes it.

Using an unsigned index with a signed limit

This loop looks reasonable, but it does not compile cleanly.

#include <cstdio>
#include <vector>
 
int main() {
    std::vector<int> words = {1, 2, 3};
    for (int i = 0; i < words.size(); ++i) {
        std::printf("%d\n", words[i]);
    }
}

With -Wall, g++ 15.2.0 reports this warning. It prints a long message, and the important part is the first line.

warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

The warning is correct. The comparison converts i to an unsigned number, so a negative i would look huge. Use std::size_t for the index, as the lesson does, or compare with a cast.

Treating tabs as part of a word

The code above only treats the space character as a separator. A tab character is different, so "a\tb" is counted as one word. Exercise 4 shows the fix.

Practice

Exercise 1: trace the in-place method

Work out the value of s after each of the three steps of reverse_words_in_place for the input " a good example ". Write the three values.

Show the answer

After step 1: a good example. After step 2: elpmaxe doog a. After step 3: example good a. The run of reverse_words_in_place on this input gives example good a.

Exercise 2: count the words in one pass

Write a function count_words that returns the number of words in a std::string. Do not build a list. Use a bool that says whether the current position is inside a word.

Show the answer

std::size_t count_words(const std::string& text) {
    std::size_t count = 0;
    bool in_word = false;
    for (char c : text) {
        if (c == ' ') {
            in_word = false;
        } else if (!in_word) {
            in_word = true;
            ++count;
        }
    }
    return count;
}

The function returns 3 for " a good example ", 0 for "", and 1 for "one". Each word is counted once, on the first character that starts it.

Exercise 3: why the empty check comes first

Explain why reverse_words_in_place returns early when s.empty() is true, before it calls reverse_range(s, 0, s.size() - 1).

Show the answer

When the string is empty, s.size() - 1 wraps to the largest unsigned value. Passing that as right would make reverse_range read and write far outside the string. The early return skips step 2 and step 3 for empty input, so the wrapped value is never used.

Exercise 4: treat tabs as spaces

The function count_words from Exercise 2 counts "a\tb" as one word. Change it so that a tab, a newline or any other whitespace character ends a word. Use std::isspace from the <cctype> header.

Show the answer

Replace the test c == ' ' with a call to std::isspace. The cast to unsigned char avoids undefined behaviour for characters outside the normal range.

if (std::isspace(static_cast<unsigned char>(c))) {
    in_word = false;
} else if (!in_word) {
    in_word = true;
    ++count;
}

With this change, "a\tb" returns 2, and " x y\t" returns 2.

Exercise 5: why the list method adds spaces the way it does

In reverse_words_with_list, the space is added only when i > 1. Explain what would happen to the output if the check were removed.

Show the answer

The loop adds the word first and then the space. The last word that the loop writes is words[0], the first word of the sentence, and it is written when i is 1. Without the check, a space would also follow that word, and the result would end with one extra space, such as blue is sky the . The check stops the space after the final word.

Summary

• Trimming removes spaces at the ends. Collapsing turns a run of spaces into one space.
• std::string has no built-in trim or split function, so the code walks through the characters with index positions.
• The list method collects words into a std::vector and joins them from the back. It uses extra memory about the size of the text.
• The in-place method cleans the text, reverses the whole string, and then reverses each word. It keeps only one string.
• Always handle empty input before subtracting 1 from size(), because the unsigned result wraps to a huge value.
• After removing characters in place, call resize to drop the old characters at the end.