STL-like palindrome checking

Question

I just read this article on how to write a standard-like algorithm and wanted to try it myself by writing (as suggested in the article) an algorithm to test if a sequence given by two bidirectional iterators is a palindrome.

Here is my code with two different ways of calling the algorithm (is_palindrome and alt_is_palindrome):

#include <cctype>       // std::tolower
#include <functional>   // std::equal_to
#include <iostream>     // std::cout
#include <iterator>     // std::iterator_traits<T>::value_type
#include <string>
#include <vector>

template<typename Iterator>
using ItVType  = typename std::iterator_traits<Iterator>::value_type;

template<typename Iterator>
using StdEqual= typename std::equal_to<ItVType<Iterator>>;

template<typename BidirectionalIterator, typename Compare=StdEqual<BidirectionalIterator>>
bool is_palindrome(BidirectionalIterator first, BidirectionalIterator last, Compare comp=Compare())
{
    for(; first != last && first != --last; ++first)
        if(not comp(*first,*last))
            return false;

    return true;
}

template<typename BidirectionalIterator, typename Compare>
bool alt_is_palindrome(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
    for(; first != last && first != --last; ++first)
        if(not comp(*first,*last))
            return false;

    return true;
}

template<typename BidirectionalIterator>
inline bool alt_is_palindrome(BidirectionalIterator first, BidirectionalIterator last)
{
    return alt_is_palindrome(first, last, StdEqual<BidirectionalIterator>());
}

int main()
{
    std::vector<std::string> vs = { "", "palindrome", "abba", "abcBA"};

    std::cout << "case sensitive:" << std::endl;
    for(auto const& s : vs)
        std::cout << s << " is "
            << ( is_palindrome(begin(s),end(s)) ? "" : "not " )
            << "a palindrome." << std::endl;
    std::cout << std::endl;


    auto my_comp = [](auto const& lhs, auto const& rhs)
    {
        return tolower(lhs) == std::tolower(rhs);
    };

    std::cout << "case insensitive:" << std::endl;
    for(auto const& s : vs)
        std::cout << s << " is "
            << ( is_palindrome(begin(s),end(s), my_comp) ? "" : "not " )
            << "a palindrome." << std::endl;
}

So first: I like the style of is_palindrome better with the default arguments, but I haven't seen it used in that way before (maybe I just haven't seen enough code...). Is there a preferred way to declare this? If so, is it 'just' a convention or are there actual benefits (performance, security,...) to it?

The second thing I am not sure about are my range-based for-loops and the lambda function int the main function. As you see I took their respective variables by auto const&. I have sometimes seen people take them as auto&&, but I am not quite sure about he implications of this. Is this way preferred?

If you note anything else that isn't quite right or nice (e.g. the kind of type aliases I use), please let me know, too.

Answer 1

Nothing wrong with these:

template<typename Iterator>
using ItVType  = typename std::iterator_traits<Iterator>::value_type;

template<typename Iterator>
using StdEqual= typename std::equal_to<ItVType<Iterator>>;

But I find them a bit disturbing being so unbound (they are in the global namespace). Maybe just a feeling. I personally would put them in an anonymous namespace.

I also prefer

template<typename BidirectionalIterator,
         typename Compare=StdEqual<BidirectionalIterator>>
bool is_palindrome(BidirectionalIterator first,
                   BidirectionalIterator last, 
                   Compare               comp=Compare())

Over

template<typename BidirectionalIterator,
         typename Compare>
bool alt_is_palindrome(BidirectionalIterator first,
                       BidirectionalIterator last,
                       Compare               comp)

template<typename BidirectionalIterator>
inline bool alt_is_palindrome(BidirectionalIterator first,
                              BidirectionalIterator last)

Putting it all in one function does not reduce readability.
But the huge template type names do bother me slightly. Template names are usually short (because they are not real type).

template<typename I,typename Compare=StdEqual<I>>
  // requires BindirectionalIterator<I>()
bool is_palindrome(I first, I last,Compare comp=Compare())

I change my mind this is fine.

for(; first != last && first != --last; ++first)
    if(not comp(*first,*last))
        return false;

But you may want to look at some algorithms.

return std::equal(first, last, std::reverse_iterator(last), comp);

Admittedly I now compare twice as many elements (so not an improvement in this case (informational only)). But if you are using random access elements you can reduce this by calculating the mid point manually.

auto dist    = std::distance(first, last);
auto halfway = first;
std::advance(halfway, dist/2);   
return std::equal(first, halfway, std::reverse_iterator(last), comp);

Looks like this should not compile:

 is_palindrome(begin(s),end(s))

That should be std::begin() and std::end() so it looks like you have a hidden using namespace std; somewhere.

If you are going to declare your lambda like this:

auto my_comp = [](auto const& lhs, auto const& rhs)
{
    return tolower(lhs) == std::tolower(rhs);
};

You may as well put it in a separate function. The point of lambdas is you can see them in place.

is_palindrome(begin(s),end(s),
              [](auto const& lhs, auto const& rhs) {return tolower(lhs) == std::tolower(rhs);}
             );