Return to Answer

Finally, with a few modifications, you can make this algorithm truly generic, so that it will work on not only std::string, but also std::wstring, char[N] (though not string literals due to the null termination), std::vector<int>, etc.

template <typename T>
bool is_palindrome(const T& in) {
    using std::begin;
    using std::end;
    using std::rbegin;

    auto it1 = begin(in);
    auto it2 = it1 + (std::distance(it1, end(in)) / 2);
    return std::equal(it1, it2, rbegin(in));
}

All other factors being equal, the best solution to a problem is the one that's easiest for someone else to understand. You mention that you don't want to use anything but "basic loops and mathematical operations," but code that is easiest to understand usually does not contain raw, explicit loops. Therefore I suggest the best solution is simply:

bool is_palindrome = std::equal(in.begin(), in.end(), in.rbegin());

Of course, this does roughly twice as much work as is necessary, reading each character twice. Unless you have extremely long strings, this is unlikely to matter at all, but if you want to reduce that linear-time coefficient in half anyway, you can do so without losing much readability:

bool is_palindrome = std::equal(in.begin(), in.begin() + (in.size() / 2), in.rbegin());

All the edge cases here just do the right thing, but I'll go over them anyway, just for laughs and kicks.

In the case of an empty string, in.begin() == in.end(), and std::equal returns true for empty ranges, so it is correctly considered a palindrome. In the optimized version, in.begin() + 0 == in.begin() so we get the same thing.

In the case of a single character input, the first version compares it with itself, and (surprise!) finds that it's equal. In the optimized version in.size() / 2 becomes 1 / 2, which when doing integer division, ends up as 0, so we're back to comparing an empty range, and it's considered a palindrome.

In the case of an input with odd length, the first version compares the character in the middle with itself, which is unnecessary but doesn't change the result. In the optimized version, again n / 2 truncates towards 0, so the middle character is ignored, and that's okay.

Since we know that the length counting from the beginning of the string is always going to be equal to the length if we start counting from the end of the string, we never need to worry about using the std::equal overload that takes an end iterator for the second range or checking sizes explicitly.

All other factors being equal, the best solution to a problem is the one that's easiest for someone else to understand. You mention that you don't want to use anything but "basic loops and mathematical operations," but code that is easiest to understand usually does not contain raw, explicit loops. Therefore I suggest the best solution is simply:

bool is_palindrome = std::equal(in.begin(), in.end(), in.rbegin());

Having a healthy understanding of iterators is essential to writing concise algorithms using the standard library, so you owe it to yourself to make sure you're comfortable with them. std::equal compares the elements of two ranges and returns true if the first element of each is equal, the second element of each is equal, etc. until the end is reached. The rbegin() and rend() functions of standard-library containers return reverse iterators over the container. That is, iterators which traverse the container from the last element to the first instead of first to last. So essentially what we're doing is checking if a reversed view of the string is equal to the string itself.

Of course, this does roughly twice as much work as is necessary, reading each character twice. Unless you have extremely long strings, this is unlikely to matter at all, but if you want to reduce that linear-time coefficient in half anyway, you can do so without losing much readability:

bool is_palindrome = std::equal(in.begin(), in.begin() + (in.size() / 2), in.rbegin());

All the edge cases here just do the right thing, but I'll go over them anyway, just for laughs and kicks.

In the case of an empty string, in.begin() == in.end(), and std::equal returns true for empty ranges, so it is correctly considered a palindrome. In the optimized version, in.begin() + 0 == in.begin() so we get the same thing.

In the case of a single character input, the first version compares it with itself, and (surprise!) finds that it's equal. In the optimized version in.size() / 2 becomes 1 / 2, which when doing integer division, ends up as 0, so we're back to comparing an empty range, and it's considered a palindrome.

In the case of an input with odd length, the first version compares the character in the middle with itself, which is unnecessary but doesn't change the result. In the optimized version, again n / 2 truncates towards 0, so the middle character is ignored, and that's okay.

Since we know that the length counting from the beginning of the string is always going to be equal to the length if we start counting from the end of the string, we never need to worry about checking sizes explicitly or using the std::equal overload that takes an end iterator for the second range.

All other factors being equal, the best solution to a problem is the one that's easiest for someone else to understand. You mention that you don't want to use anything but "basic loops and mathematical operations," but code that is easiest to understand usually does not contain raw, explicit loops. Therefore I suggest the best solution is simply:

bool is_palindrome = std::equal(in.begin(), in.end(), in.rbegin());

Of course, this does roughly twice as much work as is necessary, reading each character twice. Unless you have extremely long strings, this is unlikely to matter at all, but if you want to reduce that linear-time coefficient in half anyway, you can do so without losing much readability:

bool is_palindrome = std::equal(in.begin(), in.begin() + (in.size() / 2), in.rbegin());

All other factors being equal, the best solution to a problem is the one that's easiest for someone else to understand. You mention that you don't want to use anything but "basic loops and mathematical operations," but code that is easiest to understand usually does not contain raw, explicit loops. Therefore I suggest the best solution is simply:

bool is_palindrome = std::equal(in.begin(), in.end(), in.rbegin());

Of course, this does roughly twice as much work as is necessary, reading each character twice. Unless you have extremely long strings, this is unlikely to matter at all, but if you want to reduce that linear-time coefficient in half anyway, you can do so without losing much readability:

bool is_palindrome = std::equal(in.begin(), in.begin() + (in.size() / 2), in.rbegin());

All the edge cases here just do the right thing, but I'll go over them anyway, just for laughs and kicks.

In the case of an empty string, in.begin() == in.end(), and std::equal returns true for empty ranges, so it is correctly considered a palindrome. In the optimized version, in.begin() + 0 == in.begin() so we get the same thing.

In the case of a single character input, the first version compares it with itself, and (surprise!) finds that it's equal. In the optimized version in.size() / 2 becomes 1 / 2, which when doing integer division, ends up as 0, so we're back to comparing an empty range, and it's considered a palindrome.

In the case of an input with odd length, the first version compares the character in the middle with itself, which is unnecessary but doesn't change the result. In the optimized version, again n / 2 truncates towards 0, so the middle character is ignored, and that's okay.

Since we know that the length counting from the beginning of the string is always going to be equal to the length if we start counting from the end of the string, we never need to worry about using the std::equal overload that takes an end iterator for the second range or checking sizes explicitly.