3
\$\begingroup\$

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));
}
\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

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?

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I considered the digit_view but succumbed to premature optimisation without benchmarking! Passing base as an argument is a good idea. Good catch on the corner cases - I totally overlooked that! Thanks once again for improving my C++ competence. \$\endgroup\$ Jan 17 at 8:09
  • 1
    \$\begingroup\$ Needs std::ranges::distance() rather std::ranges::size() if it's to work with non-sized ranges (such as the filter view in the tests). \$\endgroup\$ Jan 17 at 11:17
  • \$\begingroup\$ True. It might be expensive though, as it would have to go through the whole range just to get the distance to the end, which would invoke the filter and other range adapters you chain together multiple times. I wonder if that could be avoided. \$\endgroup\$
    – G. Sliepen
    Jan 17 at 12:31
  • \$\begingroup\$ Yes - distance() will do size() if possible (the quick way) but will fall back to counting iterations rather than failing to compile. I don't think it can avoid invoking the filter function all the way through when it counts (though perhaps std::views::filter is allowed to cache results); the transform view is a straight pass-through for advancing the iterator (it only intervenes for dereferencing), so that may well optimise out. \$\endgroup\$ Jan 17 at 14:55
2
\$\begingroup\$

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); });
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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