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!

• Yuushi: Looks good, can't really see anything to critique here.
• Lingxi: Why differentiate iterator types? Just stick to the one using bi-directional iterators. The one using random-access-iterators does practically the same thing and is no better.
• Daniel: @Lingxi It is better because std::distance is linear time for non std:: random_access_iterator_tag iterators.
• Lingxi: @Daniel You don't actually need to use std::distance(). Do you?
• Lingxi: Guess you would be interested in this :-)

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

• Daniel: Your proposed solution for the string literal case will cause incorrect results for other array types (without the null terminator). IMHO, the user should be aware of the nature of C-strings and use the iterator-based versions. But this type of scenario is probably why the standard library doesn't include range-based algorithms.
• Daniel: +1 for the default predicate suggestion. But I don't agree with your other changes for the reasons given in the question comments. It may be a small performance difference, but it will be there. And I've seen algorithm implementations of the standard library which differentiate on much less obvious cases (e.g. std::reverse in libcpp).
• Lingxi: @Daniel Agreed.