6
\$\begingroup\$

I'm trying to implement a palindrome check for each element in a vector and return a vector with only the palindromes. This should work for different type .e.g strings int vector of ints.I have done a templated solution but I feel like this doesn't take full advantage of templates.

//main.cpp
  // Checking palindrome with integers
  Palindrome <int>pal = {125125, 4947, 74347, 11};
  pal.FindPalindromeDataset();
  pal.Print();

  // Checking palindrome with strings
  Palindrome <std::string>pal1  = {"yay", "world", "level", "hello"};
  pal1.FindPalindromeDataset();
  pal1.Print();

  // Checking palindrome with vector of ints
  Palindrome<std::vector<int> > pal3 = {{6, 2, 2, 6},
                                        {1, 2, 2},
                                        {1, 4, 6, 3, 5, 3, 6, 4, 1},
                                        {5, 2, 2, 6, 9, 1, 2}};
    

//palindrome.hpp
#ifndef PALINDROME_HHP
#define PALINDROME_HHP

#include <vector>
#include <iostream>

template <class T>
class Palindrome {
public:
  //! Construct from a std::initializer list 
  Palindrome(std::initializer_list<T> _dataset) : dataset(_dataset)
  {}

  //! Print the palindromeDataset
  void Print() const;
  
  /* Traverse to check if each element of the vector is a palindrome
   * and push them in the new array
   */
  void FindPalindromeDataset()
  {
    for (auto i : dataset)
    {
      if (IsPalindrome(i))
      {
        palindromeDataset.push_back(i);
      }
    }
  }
  
private:
  //! Is the element of the vector palindrome
  bool IsPalindrome(const T& s) const;

  //! Initial dataset
  std::vector<T> dataset;
  
  //! Dataset after palindrome check
  std::vector<T> palindromeDataset;
};

#endif
#include "palindrome.hpp"
#include "iostream"
#include "string"

template <>
void Palindrome<int>::Print() const
{
  std::cout << "{";
  for (auto iter = palindromeDataset.begin(); iter != palindromeDataset.end();)
  {
    std::cout << *iter;
    if (++iter != palindromeDataset.end())
    {
      std::cout << ", ";
    }
  }
  std::cout << "}"<<std::endl;
}

template <>
void Palindrome<std::string>::Print() const
{
  std::cout << "{";
  for (auto iter = palindromeDataset.begin(); iter != palindromeDataset.end();)
  {
    std::cout << *iter;
    if (++iter != palindromeDataset.end())
    {
      std::cout << ", ";
    }
  }
  std::cout << "}"<<std::endl;
}

template <>
void Palindrome<std::vector<int>>::Print() const
{
  std::cout << "{";
  for (auto iter1 = palindromeDataset.begin(); iter1 != palindromeDataset.end();)
  {
    std::cout << "{";
    for (auto iter2 = iter1->begin(); iter2 != iter1->end();)
    {
      std::cout << *iter2;
      if (++iter2 != iter1->end())
      {
        std::cout << ", ";
      }
    }
    std::cout << "}";
    if (++iter1 != palindromeDataset.end())
    {
      std::cout << ", ";
    }
  }
  std::cout << "}"<<std::endl;
}

template <>
bool Palindrome<int>::IsPalindrome(const int& s) const
{
  int x = s;
  long int rev = 0;
  if (x<0)
  {
    return false;
  }
  
  while (x!=0)
  {
    rev= rev*10+(x%10);
    x=x/10;
  }
  return s == rev;
}

template <>
bool Palindrome<std::string>::IsPalindrome(const std::string& s) const
{
  const size_t len = s.size();
  if (!len)
  {
    return true;
  }
  
  size_t l = 0;
  size_t r = len - 1;
  while (l < r)
  {
    if (s[l] != s[r])
    {
      return false;
    }
    ++l;
    --r;
  }
  return true;
}

template <>
bool Palindrome<std::vector<int>>::IsPalindrome(const std::vector<int>& s) const
{
  const size_t len = s.size();
  if (!len)
  {
    return true;
  }
  
  size_t l = 0;
  size_t r = len - 1;
  while (l < r)
  {
    if(s[l] != s[r])
    {
      return false;
    }
    ++l;
    --r;
  }
  return true;
}
\$\endgroup\$
7
\$\begingroup\$

First: This seems like an application of "The OO Antipattern". I don't see why you need class Palindrome at all; and if you must keep it, you certainly shouldn't store the entire dataset — just process it once in the constructor and keep the palindromes!

Similarly, Palindrome<T>::Print() seems like it ought to be generalized to "print this thing, whatever it is"; that operation has nothing to do with palindromes and can be split out into its own utility function.

So we're left with this:

template<class T>
std::vector<T> keep_only_palindromes(std::vector<T> dataset) {
    std::erase_if(dataset, [](auto&& elt) {
        return !is_palindromic(elt);
    });
    return dataset;
}

template<class T>
class PrintableVector {
    const std::vector<T> *v_;
public:
    explicit PrintableVector(const std::vector<T>& v) : v_(&v) {}
    friend std::ostream& operator<<(std::ostream& os, const PrintableVector& me) {
        os << "{ ";
        for (auto&& elt : *me.v_) os << elt << ", ";
        os << "}";
        return os;
    }
};

Then we could rewrite your test cases as:

int main() {
    auto pal = keep_only_palindromes(
        std::vector<int>{125125, 4947, 74347, 11}
    );
    std::cout << PrintableVector(pal) << "\n";

    auto pal1 = keep_only_palindromes(
       std::vector<std::string>{"yay", "world", "level", "hello"}
    );
    std::cout << PrintableVector(pal1) << "\n";

    std::vector<std::vector<int>> pal2_data = {
        {6, 2, 2, 6},
        {1, 2, 2},
        {1, 4, 6, 3, 5, 3, 6, 4, 1},
        {5, 2, 2, 6, 9, 1, 2}
    };
    auto pal2 = keep_only_palindromes(pal2_data);
    std::cout << PrintableVector(pal2) << "\n";
}

By the way, it's very nice that you wrote test cases! Very few people do. Your test cases are useful because they show how you intend the class to be used — and allow me to show how I intend my rewrite to be used!

I do notice that you don't test any corner cases, such as 1, 0, -1, "", {42}, or {}. This is not so great.


Your IsPalindrome for anything iterable is going to be exactly the same. So prefer to write something like

template<class T>
auto is_palindromic(const T& seq)
    -> decltype(std::begin(seq), std::rbegin(seq), true)
{
    return std::equal(
        std::begin(seq), std::end(seq),
        std::rbegin(seq), std::rend(seq)
    );
}

There I'm using return type SFINAE to say that this template should be considered for instantiation only when the expression std::begin(seq), std::rbegin(seq), true is well-formed. In C++20 you could convey the intent better with something like this:

template<class T>
concept sequence = requires (const T& seq) {
    seq.begin(); seq.rbegin();
};

template<class T> requires sequence<T>  // !!
bool is_palindromic(const T& seq) {
    return std::equal(
        std::begin(seq), std::end(seq),
        std::rbegin(seq), std::rend(seq)
    );
}

In either case, you'd still have to write your other overload

bool is_palindromic(int x)

by hand.

A version of this code with slightly less handwaving and more arcane syntax is at https://godbolt.org/z/aqPfGx — might be interesting to take a look, even if some of the arcane syntax is intimidating (and, honestly, unnecessary — if I were going to print out a vector of vectors in C++, "I wouldn't start from here").

\$\endgroup\$
2
\$\begingroup\$

I. Construction is split in several phases. Or, in other words, a freshly constructed object is not in a finalized, ready-to-use state and needs one more explicit initialization call. This is a very strong antipattern, which could obviously lead to errors.
A more decent solution would be to filter the dataset right inside the constructor, and not keep two vectors at once, thus doubling the space needed (especially when one of the vectors is only needed as an argument to create the other, and is unsable and inaccessible otherwise). (One drawback to this design is obviously that the construction would be very strict, but this is okay as long as we neglect the possibility that the constructed palindrome filter could never be actually used.)

II. The code for Print is absolutely identical between ints and strings, and for vectors, only differs in printing-an-element part.

III. The palindrome filter itself could be more useful perhaps, if it was implemented simply as a function operating on ranges, similar to those defined in <algorithm>; or at least if it implemented idiomatic iterator/begin/end interface. std::remove_if with IsPalindrome as predicate would be a good start.

IV. And the constructor itself (as it's written) could be templated, accepting an arbitrary argument pack and forwarding it to dataset ctor.

\$\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.