6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ since 's' is a 'std::string' no need for 'std::begin(s)', 'std::end(s)'. just apply it directly like 's.begin()', 's.end()'. \$\endgroup\$ – MORTAL Mar 18 '15 at 13:27
4
\$\begingroup\$

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);}
             );
\$\endgroup\$
  • \$\begingroup\$ I agree something like BidIter would make it nicer to read as long as there are no concepts. As for the std::reverse_iterator: I didn't know of those before. That's nice to have, but I don't think that they help me because the point of the double comparison in my for loop is that the range has to be traversed just until the "middle" is reached, regardless of the length being even or odd. Regarding std::begin(): would the best way to address this by the two-step with using std::begin(); or should I use std::string::begin directly in this case? \$\endgroup\$ – johannes Mar 18 '15 at 8:11
  • \$\begingroup\$ I always go for I is an iterator. With concepts this becomes even better (not worse). As I would add a line requires BindirectionalIterator<I>() \$\endgroup\$ – Martin York Mar 18 '15 at 13:03
  • \$\begingroup\$ You are correct. You need to do the test for middle. \$\endgroup\$ – Martin York Mar 18 '15 at 13:29
  • \$\begingroup\$ I would avoid using using std::begin();. But I would use std::begin() the extra 5 letters std:: each time is not a big penalty to pay. ` \$\endgroup\$ – Martin York Mar 18 '15 at 13:39
  • 1
    \$\begingroup\$ @johannes: See my update above. Where I add the C++17 concept as a comment. That way you get the best of all worlds. Short template name and its commented what it should be and when C++17 comes along just remove the double slash and the compiler checks it. \$\endgroup\$ – Martin York Mar 18 '15 at 13:50

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.