3
\$\begingroup\$

This is my attempt at answering "Palindrome from all the substrings" which asks to detect if a string contains a palindrome as a substring.

The algorithm implemented here is the one described in its accepted answer.

First, here is the main function (based on the corresponding main in the initial question):

int main()
{
    size_t n_str;
    std::cin >> n_str;

    for (size_t i = 0; i < n_str; ++i)
    {
        std::string str;
        std::cin >> str;

        std::cout << (contains_palindrome(str) ? "YES" : "NO") << std::endl;
    }

    return EXIT_SUCCESS;
}

Second, I decided to extend contains_palindrome from exclusively accepting an std::string to taking any container (e.g. std::vector<char>, std::array<int,N>, ...) as an argument:

template <class T>
bool contains_palindrome(const T& s)
{
    if (s.size() < 2) return false;

    for (auto it = s.cbegin(),
            next = std::next(it),
           nnext = std::next(next);
         nnext != s.cend();
         it = next, next = nnext, std::advance(nnext, 1))
        if (*it == *next || *it == *nnext)
            return true;

    return *std::prev(s.cend()) == *std::prev(s.cend(), 2);
}

NB: <cstdlib>, <iostream>, <iterator> and <string> are required.


QUESTION(S):

Is there any instance of bad practice in the code? In particular,

  1. is the template correct according to the desired behaviour? Am I right in assuming that contains_palindrome will work as expected on any class implementing the methods size(), cbegin() and cend()?
  2. is the use of iterators done correctly? In particular, I made sure to call the "c versions" of begin() and end() (after declaring s as const) and used std::prev(it), std::next(it) and std::advance(it,1) instead of, respectively, it-1, it+1 and it++: is this, as I was told, good practice? Are there other instances of good practice related to iterators that I overlooked?
  3. I used iterators because I learned that it is "the [right] way to do it in C++" but what do I gain over the following C-like approach?

    for (size_t i = 0; i < s.size()-2; ++i)
        if (s[i] == s[i+1] || s[i] == s[i+2])
            return true;
    
    return s[s.size()-1] == s[s.size()-2];
    
\$\endgroup\$
2
\$\begingroup\$

Well, especially with templates, the devil is in the details.

  1. Yes, the template has the desired behavior, if it works. Your code expects a readable bidirectional range knowing its size which is not a raw array.

    You really don't need to ask for the ranges size, compare iterators instead.

    Asking for the previous position is inexcusable if you don't need it.
    Instead of checking curr vs curr+1 and curr vs curr+2 in the loop and finally end-1 vs end-2 after, check begin vs begin+1 before the loop and curr vs curr+2 and curr+1 vs curr+2 in the loop

    Until the Ranges TS is incorporated into the core standard, making a range from an iterator-pair is uncomfortable, while getting a start- and end-iterator from a range is easy. So, go with the common interface using two iterators.

    Also consider adding a specialization for single-pass-ranges. Allow requesting it manually, as it should be more efficient if dereferencing an iterator is expensive.

    See the answer to question 2 about .cbegin() and co.

  2. Calling the "c versions" of the member-functions restricts your codes generality.

    They aren't part of the core range-interface, being just convenience-functions for non-generic code, so not all types have them. See std::initializer_list<T> for a common one.

    Even though raw arrays are perfectly fine, they lack member-functions.

    In summary, always use the free functions, especially in generic code.

  3. Using iterators instead of the indexing-operator allows you to efficiently use a type without cheap random-access, like lists, files, and so on.

    The aim is to require the minimum interface you can get away with without compromising efficiency, so your algorithm is as generally useable as possible.

    Some algorithms will take advantage of additional capabilities to provide more efficiency or other additional guarantees.

\$\endgroup\$

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.