4
\$\begingroup\$

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!

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

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));
}
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ – Daniel Jan 28 '16 at 8:12
  • \$\begingroup\$ +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). \$\endgroup\$ – Daniel Jan 28 '16 at 8:55
  • \$\begingroup\$ @Daniel Agreed. \$\endgroup\$ – Lingxi Jan 28 '16 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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