C++ STL：问题与迭代器

Question

我有一个初学者的问题：

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()为什么不检查类型为string::iterator？

更新：更好的版本：

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

Answer 1

假设你有第二个功能之前的声明第一个函数，主要问题是你传递的字符串是const引用。

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

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

还要注意的是最大的可移植性，全局标识符不应该以下划线开始。

Answer 2

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

您可以将迭代器接受方法更改为接受const_iterator s，或者可以将字符串接受方法更改为接受非const string。

或者你可以抛弃str的固定性，但这将是一个专利坏主意^TM。

_{（我还要加上括号您return语句在迭代器接受的方法来使你的意图更加清晰，但那是不伦不类。）}

Answer 3

你得到什么错误？

你试过这个吗？

布尔_isPalindrome（字符串::为const_iterator开始，字符串::为const_iterator结束）

Answer 4

调用它的第一功能之前，你有没有声明的第二个功能。编译器找不到它，因此试图将str.begin（）（string :: iterator）转换为一个常量字符串&。您可以将第一个功能移到第二个功能的后面。

Answer 5

正如前面所提到的迭代器必须不断迭代器，但有别的东西错了你的算法。如果你有一串奇数长度的字符串，它可以正常工作，但是当你的字符串甚至是长度时，你会看到会发生什么？考虑回文：

AA

你的算法将指向前方偏末端的迭代器通过。一切都很好，那么它会进入一个新的水平，而且一切都会很好，但不会结束。因为你的第一个条件永远不会是真的。你不仅需要检查begin == end，而且如果你愿意的话，如果begin + 1 == end或begin == end-1。否则，你会迭代器会不高兴。

Answer 6

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