patterncppMinor

Determining if a sequence is a palindrome

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

palindromedeterminingsequence

Problem

To complement this Java question on palindrome identification, I came up with this C++(14) version:

#include 
#include 
#include 

namespace detail
{
    template 
    bool is_palindrome(RandomIt first, RandomIt last, BinaryPredicate pred,
                       std::random_access_iterator_tag)
    {
        return std::equal(first, std::next(first, std::distance(first, last) / 2),
                          std::make_reverse_iterator(last), pred);
    }

    template 
    bool is_palindrome(BidirIt first, BidirIt last, BinaryPredicate pred,
                       std::bidirectional_iterator_tag)
    {
        if (first == last || first == --last) return true;

        for (; first != last; ++first, --last) {
            if (!pred(*first, *last)) return false;
            if (std::next(first) == last) break;
        }

        return true;
    }
} // namespace detail

template 
bool is_palindrome(BidirIt first, BidirIt last, BinaryPredicate pred)
{
    return detail::is_palindrome(first, last, pred,
                                 typename std::iterator_traits::iterator_category {});
}

template 
bool is_palindrome(BidirIt first, BidirIt last)
{
    using V = typename std::iterator_traits::value_type;
    return detail::is_palindrome(first, last,
                                 std::equal_to {},
                                 typename std::iterator_traits::iterator_category {});
}

template 
bool is_palindrome(const SequenceType& sequence, BinaryPredicate pred)
{
    return is_palindrome(std::cbegin(sequence), std::cend(sequence), pred);
}

template 
bool is_palindrome(const SequenceType& sequence)
{
    return is_palindrome(std::cbegin(sequence), std::cend(sequence));
}

Used as such:

#include 
#include 
#include 

int main()
{
    std::cout  lst {str.cbegin(), str.cend()};
    std::cout << is_palindrome(lst) << std::endl;
    return 0;
}

Performance is my primary concern here. Comments and suggested improvements are welcome!

Solution

Following is my solution. It's much less code. It also handles the case of string literals correctly (e.g., is_palindrome("aba")).

In modern C++ (11 and onward), there is no need to differentiate predicate and non-predicate versions of generic algorithms. The fact that the standard library does overload predicate and non-predicate versions is simply due to historical reasons. See this S.O. topic for details.

#include 
#include 
#include 

template >
bool is_palindrome(Iterator beg, Iterator end, Pred pred = Pred{}) {
  if (beg == end) return true;
  end = std::prev(end);
  if (beg == end) return true;
  do {
    if (! pred(*beg++, *end--)) return false;
  }
  while (beg != end && beg != std::next(end));
  return true;
}

template >
bool is_palindrome(const T& x, Pred pred = Pred{}) {
  return is_palindrome(std::begin(x), std::end(x), std::move(pred));
}

template >
bool is_palindrome(const char (&x)[n], Pred pred = Pred{}) {
  return is_palindrome(x, x + n - 1, std::move(pred));
}

Code Snippets

#include <functional>
#include <iterator>
#include <utility>

template <typename Iterator, typename Pred = std::equal_to<void>>
bool is_palindrome(Iterator beg, Iterator end, Pred pred = Pred{}) {
  if (beg == end) return true;
  end = std::prev(end);
  if (beg == end) return true;
  do {
    if (! pred(*beg++, *end--)) return false;
  }
  while (beg != end && beg != std::next(end));
  return true;
}

template <typename T, typename Pred = std::equal_to<void>>
bool is_palindrome(const T& x, Pred pred = Pred{}) {
  return is_palindrome(std::begin(x), std::end(x), std::move(pred));
}

template <std::size_t n, typename Pred = std::equal_to<void>>
bool is_palindrome(const char (&x)[n], Pred pred = Pred{}) {
  return is_palindrome(x, x + n - 1, std::move(pred));
}

Context

StackExchange Code Review Q#118074, answer score: 2

Revisions (0)

No revisions yet.