# Determining if a sequence is a palindrome

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!

• Looks good, can't really see anything to critique here. Jan 28, 2016 at 2:14
• 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. Jan 28, 2016 at 7:33
• @Lingxi It is better because std::distance is linear time for non std:: random_access_iterator_tag iterators. Jan 28, 2016 at 7:46
• @Daniel You don't actually need to use std::distance(). Do you? Jan 28, 2016 at 7:48
• Guess you would be interested in this :-) Jan 28, 2016 at 8:29

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

• 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. Jan 28, 2016 at 8:12
• +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). Jan 28, 2016 at 8:55
• @Daniel Agreed. Jan 28, 2016 at 8:58