Palindrome evaluator in C++

Question

I started learning C++ a few days ago, and this is my first full program. It takes in words until an end-of-file character prompt is given, and then outputs which of those words are palindromes and the longest palindrome of those words.

I want to know if my evaluation for whether each string is a palindrome is acceptable given the little knowledge I have about C++ thus far, and by acceptable I mean like not costly or just not agreeable for good C++ code. I was unsure if it would be better to access characters by position in each string with like a "double iterator" to check if they were the same while the iterators converged, or if just making a reversed string and checking is a better approach like I did.

Also, just if my general program structure looks okay - I'm rather unsure if my desire to have void functions to clean up my main function is really a good thing to do or otherwise.

#include <iostream>
#include <list>
#include <iomanip>

using std::cin;         using std::cout;        using std::string;
using std::istream;     using std::list;        using std::endl;
using std::setw;

istream& read(istream& is, list<string>& word_list)
{
    word_list.clear();
    string word;
    while(is >> word)
        word_list.push_back(word);

    is.clear();
    return is;
}

void evaluate(list<string>& words, string& longest)
{
    longest.clear();
    typedef string::size_type str_sz;

    list<string>::iterator it = words.begin();
    while (it != words.end())
    {
        if (*it == string(it->rbegin(), it->rend()))
        {
            longest = max(longest, *it);
            ++it;
        }
        else
        {
            it = words.erase(it);
        }
    }
}

void output(const list<string>& palindrs, const string& longest)
{
    if (palindrs.empty())
        cout << "No palindromes were given :(" << endl;
    else{
        cout << "The palindrome(s) given are: " << '\n' << endl;
        for (list<string>::const_iterator it = palindrs.begin(); 
            it != palindrs.end(); ++it)
            cout << setw(5) << "- \"" << *it << "\"" << endl;

        cout << '\n' << "And the longest palindrome is \"" <<
             longest << "\"!";
    }
}

int main()
{
    list<string> words;

    cout << "Please enter some words." << endl;
    read(cin, words);

    string longest;
    evaluate(words, longest);

    output(words, longest);

    return 0;
}

Answer 1

Your code looks so good, it is quite impressive of you were learning c++ few days ago. i'm sure you will get a decent code-review but here my humble attempt.

It always preferred to pass the std::string by const reference if you don't modify it. also, std::vector is preferred over std::list. here link for more details

In your read function. It redirects all input into this container until EOF is received. However, the used container might need to reallocate memory too often, or you will end with a std::bad_alloc exception when your system gets out of memory. In order to solve these problems, you could reserve a fixed amount N of elements and process these amount of elements. here an alternative example to your read function by using std::copy_n and std::istream_iterator like so,

words.reserve(N);
std::copy_n(std::istream_iterator<std::string>(std::cin),
    N,
    std::back_inserter(words));

In your evaluate function, it is fine but not efficient doe to the call of std::string constructor in every iteration along with deleting un-palindrome elements. it is better to create another container for palindrome elements and check the main container elements if it has palindrome element. possible implementation:

std::vector<std::string> palindromes;
for (const auto& word : words)
{
    if(is_palindrome(word))
        palindromes.emplace_back(word);
}

The is_palindrome function, we test the given string for whither it is palindrome or not, like so:

bool is_palindrome(const std::string& str)
{
    if (str.empty())
        return false;

    using str_sz = std::string::size_type;
    for (str_sz i = 0, j = str.length() -1; i < j ; ++i, --j)
    {
        if (str[i] != str[j])
            return false;
    }
    return true;
}

thanks to @screwnut for suggesting to std::copy_if instead of for-range while the for-loop is bit clear and simple. but std::copy_if will allow us to use lambda instead of calling is_palindrome function, that might be helpful if you simply write it like this:

std::copy_if(words.begin(), words.end(), 
             std::back_inserter(palindromes), 
             [](const std::string& str)
             {return std::equal(str.begin(), str.begin() + str.size() / 2, str.rbegin());});

Lastly, for longest string, you may take advantage of STL by using std::max_element which is return iterator.

std::max_element(palindromes.begin(), palindromes.end(),
    [](const std::string& lhs, const std::string& rhs)
{
    return lhs.size() < rhs.size();
});

put all to gather:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    const std::size_t TotalWords = 3;
    std::vector<std::string> words;
    words.reserve(TotalWords);

    std::cout << "Please enter some words." << std::endl;
    std::istream_iterator<std::string> in(std::cin);
    std::copy_n(in, TotalWords, std::back_inserter(words));

    std::vector<std::string> palindromes;

    auto comp = [](const std::string& str)
    {
        return std::equal(str.begin(), str.begin() + str.size() / 2, str.rbegin());
    };

    std::copy_if(words.begin(), words.end(), std::back_inserter(palindromes), comp);

    if (palindromes.empty())
    {
        std::cout << "No palindromes were given" << std::endl;
    }
    else
    {
        auto longest = std::max_element(palindromes.begin(), palindromes.end(),
            [](const std::string& lhs, const std::string& rhs)
        {
            return lhs.size() < rhs.size();
        });
        std::ostream_iterator<std::string> out(std::cout, "\n ");
        std::cout << "Palindromes: \n ";
        std::copy(palindromes.begin(), palindromes.end(), out);
        std::cout << "\rLongest: " << *longest << std::endl;
    }
}

Answer 2

I offer this code as something to look forward to be able to write in the future, not as something I would want you to come up with right now. What you have is great for someone at your level of C++.

The most important aspect of this code is its use of set. set is a container that keeps its element ordered, even as you add more element to it. It's contents will always kept sorted. By default, set will perform it's duties by comparing elements with a plain less-than comparator, i.e. <. So, by default, a set<int> will keep a bunch of ints ordered from the smallest to the greatest.

Though that's the default, you can change the comparison function. The standard library already has some options ready for you to use. For example, to keep the ints sorted from greatest to smallest, use set<int, greater<>> instead of just set<int>.

But what we want to do here is keep string sorted according to their length, from longest to shortest. The standard library doesn't have something ready made for us but we can follow the example of greater<>. It would look like this:

template<class T = void>
struct longer;

template<>
struct longer<void>
{
    template< class T, class U>
    constexpr auto operator()(T&& lhs, U&& rhs) const ->decltype(std::forward<T>(lhs) > std::forward<U>(rhs))
    {
        return lhs.length() > rhs.length();
    }
};

Again, I don't expect you to grasp this fully. Just keep it way in the back of your head and revisit this post in a year...

Ok, so I have my custom-made comparator. I can declare my container that will hold the palindromes. As I add strings to this container, they will automatically be kept in sorted order by length.

But wait, here's an important detail, it's possible that I may have more than one palindrome of the same length! No sweat, use multiset. It does the exact same thing as set but allows multiple values where the comparison will say they are equal, i.e. of the same length in our case.

int main()
{
    multiset<string, longer<>> palindromes;

Good. Now, I have to read in strings from the user, decide if they are palindromes and save them in my special container. The following lines of code are quite compressed. It's a single statement that does all what I just described.

copy_if(istream_iterator<string>(cin), istream_iterator<string>(), inserter(palindromes, palindromes.end()), [](string const& word)
    {
        return equal(word.begin(), word.begin() + word.size() / 2, word.rbegin());
    });

Let's break it down:

copy_if(istream_iterator<string>(cin), istream_iterator<string>(),

copy_if is a function from the standard library that takes a range of elements, applies a predicate on every element and if the condition is satisfied, copies the element to some output. In C++, the word range can take many strange shapes. My range here is the standard input! That's a range? Well, you can present it as such. This code will prompt the user to input some strings. Every time the user presses Enter, that's a new string in the range. The end of the range is when the user uses the OS-specific end-of-input command, e.g. Ctrl-D in bash or Ctrl-Z in DOS.

inserter(palindromes, palindromes.begin()),

That's the output. That's where elements that satisfy the predicate will but copied. The inserter function is how I tell copy_if to call the member function .insert() on my multiset. Why do I specify .begin()? That's make little sense. The multiset will keep the elements sorted according to the rules I gave it. It should not keep adding the elements at the beginning!

Well, that inserter function is a very generic one. It works for all kinds of container. With a vector, it would do as I wrote it. But with a set or multiset, that .begin() is just a hint and will be discarded.

On to the predicate:

[](string const& word)
{
    return equal(word.begin(), word.begin() + word.size() / 2, word.rbegin());
});

Well, I have no shame to say that I just copy-pasted @MORTAL's code for that part. :) That's a lambda, an in-place function that you don't need to write somewhere, you just write exactly where you need it. Apart from the funny syntax, the body is the same as the more mundane but equivalent function.

So now we have all palindromes saved and ordered by length order. Let's print them out:

copy(palindromes.begin(), palindromes.end(), ostream_iterator<string>(cout, "\n"));

Another call to the copy family. This is a plain copy and it will copy all elements where I tell it to. In this case, all elements will printed to standard output, with a newline in between. They will show up from the longest to the shortest.

And we're done.

    return 0;
}

I will add one last thing. The fact that I use a set (or multiset) does mean that this code is doing a bit more work than what you needed given your problem statement. That is, you did not necessarily wanted to keep all the palindromes sorted, you just wanted to know which one was the longest. But I offered this solution as an example to leverage stuff from the standard library that can do a lot of work for you transparently.