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