0

我有一个初学者问题：

bool _isPalindrome(const string& str)
{
    return _isPalindrome(str.begin(), str.end()); // won't compile
}

bool _isPalindrome(string::iterator begin, string::iterator end)
{
    return begin == end || *begin == *end && _isPalindrome(++begin, --end);
}

我在这里做错了什么？为什么不str.begin()将类型检查为 a string::iterator？

更新：更好的版本：

bool BrittlePalindrome::_isPalindrome(string::const_iterator begin, string::const_iterator end)
{
    return begin >= end || *begin == *(end - 1) && _isPalindrome(++begin, --end);
}
4

6 回答 6

5

str.begin()是非常量，而参数str 是常量。

您可以将接受迭代器的方法更改为接受const_iterators，也可以将接受字符串的方法更改为接受非常量string。

或者你可以抛弃strconst-ness，但这将是 Bad Idea TM的专利。

（我还会在迭代器接受方法上用括号括起您的 return 语句，以使您的意图更清楚，但这既不是这里也不是那里。）

于 2010-05-27T22:09:44.493 回答
5

假设您在第一个函数之前声明了第二个函数，主要问题是您通过const引用传递字符串。

这意味着您可以访问的begin()和的唯一重载end()是返回std::string::const_iterator而不是的 const 版本std::string::iterator。

迭代器的约定是结束迭代器指向超出范围末尾的一个并且不可取消引用 - 当然如果您str.end()作为end参数传递。这意味着*begin == *end无效，您需要先递减 end 一次。您还将遇到具有奇数个元素的范围的问题。通过这样做++begin并且--end没有进一步检查，您的迭代器可能会在递归中交叉而不是触发begin == end条件。

另请注意，为了获得最大的可移植性，全局标识符不应以下划线开头。

于 2010-05-27T22:10:20.910 回答
2

如前所述，您的迭代器必须是常量迭代器，但您的算法还有其他问题。如果你有一个奇数长度的字符串，它工作得很好，但是你看到当你的字符串是偶数长度时会发生什么吗？考虑回文：

啊

您的算法将传入一个指向前面和结尾的迭代器。一切都好，然后它会更上一层楼，一切都会很好，但它不会结束。因为你的第一个条件永远不会成立。您不仅需要检查是否 begin==end，还需要检查 begin+1==end 或 begin==end-1（如果您愿意）。否则你的迭代器会很沮丧。

于 2010-05-27T22:19:54.017 回答
1

你遇到了什么错误？

你试过这个吗？

bool _isPalindrome(string::const_iterator begin, string::const_iterator end)

于 2010-05-27T22:12:25.960 回答
1
  1. 替换iterator为const_iterator
  2. 交换函数定义
  3. 递减end

代码：

bool isPalindrome(string::const_iterator begin, string::const_iterator end)
{
  return (begin == end || begin == --end || 
          *begin == *end && isPalindrome(++begin, end));
}

bool isPalindrome(const string& str)
{
    return isPalindrome(str.begin(), str.end());
}
于 2010-05-27T22:35:36.250 回答
0

在第一个函数中调用它之前，您还没有声明第二个函数。编译器找不到它，因此尝试将 str.begin() (string::iterator) 转换为 const string &。您可以将第一个函数移到第二个函数后面。

于 2010-05-27T22:18:02.243 回答