Visit the reverse-string exercise on Exercism to read the full instructions and download the exercise files.
Dig Deeper
Iterative
Approach: Iterative
reverse_string.h
#pragma once
#include <string>
namespace reverse_string
{
std::string reverse_string(const std::string& str);
}
reverse_string.cpp
#include "reverse_string.h"
namespace reverse_string
{
// (1) the function takes its argument "by reference to const"
std::string reverse_string(const std::string& original)
{
// (2) start with an empty string
std::string result;
// (3) loop over the original string
for (std::size_t i = 0; i < size(original); ++i)
{
std::size_t rindex = size(original) - i - 1;
// (4) append each character (starting from the end)
result.append(original[rindex]);
}
// result now contains a reversed version of the string
return result;
}
} // namespace reverse_string;
The type of the parameter
The function takes its argument “by reference to const” (const std::string&).
That avoids creating an unnecessary copy which can be comparatively expensive for a std::string.
This is a best practice and widely recommended if a copy is expensive and the function does not need a “working copy” that it can modify (see the C++ Core Guidelines.)
Alternatively you could use a std::string_view.
That type was added to C++17, it is an immutable view of a string, it is cheap to construct and to copy (see cppreference.com.)
Constructing an empty std::string
There are several equivalent ways to construct an empty std::string, for example:
std::string result;
std::string result{};
std::string result{""};
std::string result = "";
auto result = std::string{};
None of them is significantly better than the others, choosing one is mostly a matter of personal preferences.
Looping over the original string from back to front
In the implementation above i is a loop variable that goes from 0 to size(original) (exclusive).
Inside the loop i is used to to calulate rindex, an index that goes from size(original) - 1 to 0 (inclusive).
There are other ways to write that loop, for example like this:
for (std::size_t rindex = size(original) - 1; rindex < size(original); --rindex)
That uses the fact that std::size_t is an unsigned integer type that “wraps around”, std::size_t{0} - 1 is a large positive number.
Or with reverse iterators which many experienced C++ programmers would prefer:
for (auto rit = rbegin(original); rit != rend(original); ++rit)
{
// *rit is the current character
}
Appending to the result
The solution above uses the member function append (see cppreference.com.)
There are other equivalent member function like push_back() (see cppreference.com) or the operator += (see cppreference.com.)
Either one is fine, chosing one is a matter of personal preferences.
Variation: With assignments
Instead of starting with an empty std::string and appending each character we could start with a string that has the correct length, and then assign each character to its correct position.
// start with a string of the correct length
std::string result(size(original), '_');
// loop over the original string
for (std::size_t i = 0; i < size(original); ++i)
{
std::size_t rindex = size(original) - i - 1;
// assign each character to its new place
result[rindex] = original[i];
}
The assignment (result[rindex] = original[i]) needs two indexes, so we have to write the loop in a way that we get both.
Either by computing the other index like in the snippet (std::size_t rindex = ...), or by using two loop variables:
for (std::size_t i = 0, rindex = size(original) - 1; i < size(original); ++i, --rindex)
Conclusion
This is a valid approach, it produces a correct result and is reasonably efficient.
But most experts recommend not doing things “manually” if there are better alternatives.
You could consider using the std::string class to construct the reversed string directly.
That would shorten the code, would be concise, easy to read, idiomatic, and very efficient.
Check out the Direct Construction approach.
Swapping characters
Approach: Swapping characters
reverse_string.h
#pragma once
#include <string>
namespace reverse_string
{
std::string reverse_string(std::string str);
}
reverse_string.cpp
#include "reverse_string.h"
namespace reverse_string
{
// (1) the function takes its argument "by value"
std::string reverse_string(std::string str)
{
// (2) handle an empty string as a special case
if (str.empty())
return str;
// (3) use two indexes,
// a starts a the beginning and gets incremented
// b starts at the end and gets decremented
std::size_t a = 0;
std::size_t b = size(str) - 1;
// (4) swap characters until the two indexes meet
while (a < b)
{
std::swap(str[a], str[b]);
++a;
--b;
}
// str is now reversed
return str;
}
} // namespace reverse_string;
The type of the parameter
The function takes its argument “by value” (std::string).
That means the parameter str gets constructed from the argument that the caller passes to the function, and it gets destructed at the end of the function.
Any modifications of the parameter will not be visible outside of the function and will not affect the argument of the caller.
We do that because the function needs a “working copy” of the string, it will reverse and return that parameter without creating an additional instance of std::string.
Handling an empty string as a special case
The rest of the function would have problems with an empty string because in that case size(empty_string) - 1 is a large positive number, and the first iteration of the loop tries to access str[b] which would be out of bounds.
Therefore we handle the empty string as a special case with an “early return”.
Using two indexes
This solution swaps characters, the first character with the last one, the second character with the second to last, etc.
It therefore uses two variables for the indexes: a starts at 0 and gets incremented, b starts at size(str) - 1 and gets decremented.
The general category of this algorithm is sometimes called “Two pointers technique” (pointers and indexes are closely related.)
Swapping characters
The standard library provides a function std::swap for swapping two variables (see cppreference.com.)
We could do that manually with a temporary third variable:
char temp = str[a];
str[a] = str[b];
str[b] = temp;
But calling std::swap is shorter, expresses the intent more clearly, and through the optimizations that all modern compilers perform it is just as efficient.
Conclusion
This is a valid approach, it produces a correct result and is reasonably efficient.
But most experts recommend not doing things “manually” if there are better alternatives.
You could consider calling a function from the standard library that performs the reversal for you.
That would shorten the code, would be concise, easy to read, idiomatic, and very efficient.
Check out the Using the standard library approach.
Using the standard library
Approach: Using the standard library
reverse_string.h
#pragma once
#include <string>
namespace reverse_string
{
std::string reverse_string(std::string str);
}
reverse_string.cpp
#include "reverse_string.h"
#include <algorithm> // (1) for std::reverse()
namespace reverse_string
{
// (2) the function takes its argument "by value"
std::string reverse_string(std::string str)
{
// (3) call a function from the standard library that performs the reversal
std::reverse(begin(str), end(str));
// str is now reversed
return str;
}
} // namespace reverse_string;
The header <algorithm> is part of the standard library, it contains lots of useful functions (see cppreference.com).
After including this header we can call the function std::reverse later in the file.
The type of the parameter
The function takes its argument “by value” (std::string).
That means the parameter str gets constructed from the argument that the caller passes to the function, and it gets destructed at the end of the function.
Any modifications of the parameter will not be visible outside of the function and will not affect the argument of the caller.
We do that because the function needs a “working copy” of the string, it will reverse and return that parameter without creating an additional instance of std::string.
Calling std::reverse().
std::reverse() is a function template (in other languages known as “generics”) that takes two “bidirectional iterators”.
These two iterators define a half-open interval [begin, end).
std::reverse() reverses the order of the elements in the interval by swapping (see cppreference.com.)
Conclusion
This is a great approach; it is concise, easy to read, idiomatic, and very efficient.
Source: Exercism cpp/reverse-string