Determining if a sequence is a palindrome

Question

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

#include <iterator>
#include <algorithm>
#include <functional>

namespace detail
{
    template <typename RandomIt, typename BinaryPredicate>
    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 <typename BidirIt, typename BinaryPredicate>
    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 <typename BidirIt, typename BinaryPredicate>
bool is_palindrome(BidirIt first, BidirIt last, BinaryPredicate pred)
{
    return detail::is_palindrome(first, last, pred,
                                 typename std::iterator_traits<BidirIt>::iterator_category {});
}

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

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

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

Used as such:

#include <iostream>
#include <string>
#include <list>

int main()
{
    std::cout << std::boolalpha;
    std::string str {"abba"};
    std::cout << is_palindrome(str) << std::endl;
    std::list<char> 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!

Answer 1

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 <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));
}