Palindrome predicate

Question

A standard beginner problem is to determine whether a particular input is palindromic, i.e. reads the same in reverse as it does forwards.

I thought it might be fun to provide a distinctly non-beginner solution to this problem, so here's a version that is hugely over-engineered for a homework answer.

#include <algorithm>
#include <concepts>
#include <ranges>
#include <string_view>

// Integer version - use decimal representation
template<std::unsigned_integral Number>
constexpr bool is_palindrome(Number n) noexcept
{
    // a trailing zero disqualifies, as we ignore leading zeros
    if (n == 0) { return true; }
    if (n % 10 == 0) { return false; }

    Number r = 0;
    while (r < n) {
        r = 10 * r + n % 10;
        if (r == n) { return true; }
        n /= 10;
    }
    return r == n;
}

// Range version (matches strings and string-views)
constexpr bool is_palindrome(std::ranges::bidirectional_range auto&& s) noexcept
{
    // We round down, because we can ignore a middle char (it will always match itself)
    auto const half_size = std::ranges::distance(s) / 2;
    auto rev_right = s | std::views::reverse | std::views::take(half_size);

#if __cpp_lib_ranges_starts_ends_with >= 202106L
    return std::ranges::starts_with(s, rev_right);
#else
    auto left = s | std::views::take(half_size);
    return std::ranges::equal(left, rev_right);
#endif
}

// Adaptor overload for string literals
template<typename Char, std::size_t N>
constexpr bool is_palindrome(Char const (&s)[N]) noexcept
{
    return is_palindrome(std::basic_string_view{s, N-1});
}

// Adaptor overload for null-terminated strings
template<typename Char>
constexpr bool is_palindrome(Char const *const &s) noexcept
{
    return is_palindrome(std::basic_string_view{s});
}

Of course, like all good homework, it's properly tested:

#include <cctype>
#include <string>
#include <gtest/gtest.h>

using namespace std::literals;

TEST(is_palindrome_string, yes)
{
    EXPECT_TRUE(is_palindrome(""));
    EXPECT_TRUE(is_palindrome(L""s));
    EXPECT_TRUE(is_palindrome(L""sv));
    EXPECT_TRUE(is_palindrome("a"sv));
    EXPECT_TRUE(is_palindrome("aa"));
    EXPECT_TRUE(is_palindrome("aba"sv));
    EXPECT_TRUE(is_palindrome(L"abcba"sv));
    EXPECT_TRUE(is_palindrome("ab\0ba"));
    EXPECT_TRUE(is_palindrome("ab\0ba"sv));
    EXPECT_TRUE(is_palindrome(L"ab\0ba"s));
    {
        const char *s = "aa\0bb"; // \0 terminates this one
        EXPECT_TRUE(is_palindrome(s));
    }
}

TEST(is_palindrome_string, no)
{
    EXPECT_FALSE(is_palindrome("ab"));
    EXPECT_FALSE(is_palindrome(L"ab"sv));
    EXPECT_FALSE(is_palindrome("abc"));
    EXPECT_FALSE(is_palindrome("abca"));
    EXPECT_FALSE(is_palindrome("aab"));
    EXPECT_FALSE(is_palindrome("aa\0"));
    EXPECT_FALSE(is_palindrome(u8"abcab"sv));
    {
        const char *s = "ab\0ba"; // \0 terminates this one
        EXPECT_FALSE(is_palindrome(s));
    }
}

TEST(is_palindrome_int, yes)
{
    EXPECT_TRUE(is_palindrome(0ul));
    EXPECT_TRUE(is_palindrome(1u));
    EXPECT_TRUE(is_palindrome(11u));
    EXPECT_TRUE(is_palindrome(101u));
    EXPECT_TRUE(is_palindrome(1001u));
    EXPECT_TRUE(is_palindrome(121u));
    EXPECT_TRUE(is_palindrome(12345678987654321ull));
    EXPECT_TRUE(is_palindrome(123456789987654321ull));
}

TEST(is_palindrome_int, no)
{
    EXPECT_FALSE(is_palindrome(12u));
    EXPECT_FALSE(is_palindrome(112u));
    EXPECT_FALSE(is_palindrome(110u));
}

// A useful view for mixed-case sentence palindromes
auto constexpr palindrome_view =
    std::views::filter([](unsigned char c){ return std::isalnum(c); }) |
    std::views::transform([](unsigned char c){ return static_cast<char>(std::toupper(c)); });

TEST(is_palindrome_sentence, yes)
{
    EXPECT_TRUE(is_palindrome("A man, a plan, a canal: Panama!"sv | palindrome_view));
}

Answer 1

Make a view for numbers

You have a very generic is_palindrome() that takes any bidirectional range. Nice! But then instead of creating an overload for unsigned integrals, why not create a view that allows you to iterate over the digits of numbers? Consider being able to write:

template<std::unsigned_integral Number>
constexpr bool is_palindrome(Number n, int base = 10)
{
    return is_palindrome(digit_view{n, base});
}

Simplify is_palindrome()

While C++20's ranges library makes it simpler to write complex algorithms, sometimes it's even easier when using the good old iterator versions. For example:

constexpr bool is_palindrome(std::ranges::bidirectional_range auto&& s)
{
    return std::equal(begin(s), begin(s) + size(s) / 2, rbegin(s));
}

If you really want to stick with the ranges version, I think this example from cppreference.com looks cleaner.

Remove noexcept or make it conditional

You made is_palindrome() noexcept. However, there is no guarantee that every bidirectional range's iterator functions are noexcept. This is reflected by the fact that std::ranges::starts_with() and std::ranges:equal() also are not noexcept. I would remove it entirely; technically you could make it conditional, but that would require you to check whether every possible operation on the range is noexcept.

Corner cases

By making a very generic version of is_palindrome(), you have to worry about corner cases. Maybe a very strange container is used, or there is something weird with the value type. Just as an example, consider this piece of code:

std::vector<float> foo{NAN, 42,  NAN};
std::vector<float> bar{42,  NAN, 42 };
std::cout << is_palindrome(foo) << '\n';
std::cout << is_palindrome(bar) << '\n';

What should the output be? Is it OK if the two results are not the same?

Answer 2

Since is_palindrome() accepts ranges of any equality-comparable type, palindrome_view doesn't need to be a range of char, and there's need to cast within the transform():

auto constexpr palindrome_view =
    std::views::filter([](unsigned char c){ return std::isalnum(c); }) |
    std::views::transform([](unsigned char c){ return std::toupper(c); });

This view wasn't part of the main code because it's not generic. But it could be made to work for other character types by including <locale> instead of <cctype>:

auto palindrome_locale = std::locale::classic();
auto constexpr palindrome_view =
    std::views::filter([](auto c){ return std::isalnum(c, palindrome_locale); }) |
    std::views::transform([](auto c){ return std::toupper(c, palindrome_locale); });