พาลินโดรมแบบเทมเพลต

Question

ฉันกำลังพยายามใช้การตรวจสอบพาลินโดรมสำหรับแต่ละองค์ประกอบในเวกเตอร์และส่งคืนเวกเตอร์ที่มีเพียงพาลินโดรม สิ่งนี้ควรใช้ได้กับเวกเตอร์ int. e ของสตริงประเภทต่างๆฉันได้ทำโซลูชันที่เป็นเทมเพลตแล้ว แต่ฉันรู้สึกว่านี่ไม่ได้ใช้ประโยชน์จากเทมเพลตอย่างเต็มที่

//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;
}

Answer 1

แม่: นี้ดูเหมือนว่าแอพลิเคชันของ"การ OO Antipattern" ฉันไม่เห็นว่าทำไมคุณถึงต้องการclass Palindromeเลย และถ้าคุณต้องเก็บไว้คุณไม่ควรจัดเก็บชุดข้อมูลทั้งหมดอย่างแน่นอน - เพียงแค่ประมวลผลครั้งเดียวในตัวสร้างและเก็บ palindromes ไว้!

ในทำนองเดียวกันPalindrome<T>::Print()ดูเหมือนว่ามันควรจะพูดทั่วไปว่า "พิมพ์สิ่งนี้ไม่ว่าจะเป็นอะไรก็ตาม"; การดำเนินการนั้นไม่มีส่วนเกี่ยวข้องกับ palindromes และสามารถแยกออกเป็นฟังก์ชันยูทิลิตี้ของตัวเองได้

ดังนั้นเราจึงเหลือสิ่งนี้:

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;
    }
};

จากนั้นเราสามารถเขียนกรณีทดสอบของคุณใหม่เป็น:

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";
}

อย่างไรก็ตามเป็นเรื่องดีมากที่คุณเขียนกรณีทดสอบ! มีคนทำน้อยมาก กรณีทดสอบของคุณมีประโยชน์เพราะแสดงให้เห็นว่าคุณตั้งใจจะใช้ชั้นเรียนอย่างไร - และช่วยให้ฉันแสดงให้เห็นว่าฉันตั้งใจจะใช้การเขียนซ้ำของฉันอย่างไร!

ฉันจะแจ้งให้ทราบว่าคุณไม่ได้ทดสอบกรณีมุมใด ๆ เช่น1, 0, -1, "", หรือ{42} {}นี้ไม่ได้ดีมาก

---

สิ่งที่คุณIsPalindromeทำซ้ำได้จะเหมือนกันทุกประการ ดังนั้นชอบเขียนอะไรเช่น

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)
    );
}

ฉันใช้ประเภทการส่งคืน SFINAEเพื่อบอกว่าเทมเพลตนี้ควรได้รับการพิจารณาสำหรับการสร้างอินสแตนซ์เฉพาะเมื่อนิพจน์std::begin(seq), std::rbegin(seq), trueมีรูปแบบที่ดีเท่านั้น ใน C ++ 20 คุณสามารถถ่ายทอดเจตนาได้ดีขึ้นด้วยสิ่งนี้:

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)
    );
}

ไม่ว่าในกรณีใดคุณยังคงต้องเขียนโอเวอร์โหลดอื่น ๆ

bool is_palindromic(int x)

ด้วยมือ.

เวอร์ชันของรหัสนี้ที่มีการโบกมือน้อยลงเล็กน้อยและไวยากรณ์ที่มีความลับมากขึ้นอยู่ที่ https://godbolt.org/z/aqPfGx - อาจจะดูน่าสนใจแม้ว่าไวยากรณ์อาร์เคนบางส่วนจะดูน่ากลัว (และโดยสุจริตไม่จำเป็น - ถ้าฉันจะพิมพ์เวกเตอร์เวกเตอร์ใน C ++ "ฉันจะไม่เริ่มจากที่นี่")

Answer 2

I. การก่อสร้างแบ่งออกเป็นหลายขั้นตอน หรือกล่าวอีกนัยหนึ่งคืออ็อบเจ็กต์ที่สร้างขึ้นใหม่ไม่อยู่ในสถานะสรุปพร้อมใช้งานและต้องการการเรียกใช้งานการเริ่มต้นที่ชัดเจนอีกครั้ง นี่เป็นปฏิปักษ์ที่แข็งแกร่งมากซึ่งอาจนำไปสู่ข้อผิดพลาดอย่างเห็นได้ชัด
ทางออกที่ดีกว่าคือการกรองชุดข้อมูลภายในตัวสร้างและไม่เก็บเวกเตอร์สองตัวพร้อมกันดังนั้นจึงต้องเพิ่มพื้นที่เป็นสองเท่า (โดยเฉพาะอย่างยิ่งเมื่อต้องใช้เวกเตอร์ตัวใดตัวหนึ่งเป็นอาร์กิวเมนต์เพื่อสร้างอีกตัวหนึ่งและไม่สามารถใช้งานได้และ ไม่สามารถเข้าถึงได้เป็นอย่างอื่น) (ข้อเสียเปรียบประการหนึ่งของการออกแบบนี้เห็นได้ชัดว่าการก่อสร้างจะเข้มงวดมาก แต่ก็ไม่เป็นไรตราบใดที่เราละเลยความเป็นไปได้ที่จะไม่สามารถใช้ตัวกรองพาลินโดรมที่สร้างขึ้นได้จริง)

II. รหัสสำหรับPrintเป็นอย่างที่เหมือนกันระหว่าง ints และสตริงและเวกเตอร์แตกต่างกันเพียง แต่ในส่วนของการพิมพ์ใช้องค์ประกอบ

สาม. ตัวกรองพาลินโดรมเองอาจมีประโยชน์มากกว่าถ้ามันถูกนำไปใช้เป็นฟังก์ชันที่ทำงานในช่วงคล้ายกับที่กำหนดไว้ใน<algorithm>; หรืออย่างน้อยถ้ามันใช้สำนวนiterator/ begin/ endinterface std::remove_ifด้วยเพรดิเคตIsPalindromeจะเป็นการเริ่มต้นที่ดี

^{IV. และตัวสร้างเอง (ตามที่เขียนไว้) สามารถเป็นเทมเพลตได้โดยยอมรับชุดอาร์กิวเมนต์โดยพลการและส่งต่อไปยังdatasetctor}