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(), к которым у вас есть доступ, являются версии const, которые возвращают std::string::const_iterator, а не std::string::iterator.

Соглашение для итераторов заключается в том, что конечный итератор указывает один за конец диапазона и не может быть разыменован - разумеется, если вы передаете str.end() в качестве параметра end. Это означает, что *begin == *end недопустимо, вам нужно сначала уменьшить значение end один раз. У вас также будет проблема с диапазонами с нечетным числом элементов. При выполнении ++begin и --end без дальнейшей проверки ваши итераторы могут пересекаться в рекурсии, а не вызывать условие begin == end.

Также обратите внимание, что для максимальной переносимости глобальные идентификаторы не должны начинаться с подчеркивания.

Answer 2

str.begin() не является константой, а аргумент str равен const.

Вы можете либо изменить метод приема итератора, чтобы он принимал const_iterator s, либо вы можете изменить метод приема строки, чтобы принимать неконстантный string.

Или вы могли бы отбросить постоянство str, но это была бы патентная Плохая Идея ^TM .

_{(Я бы также заключил в скобки ваш оператор возврата в методе принятия итераторов, чтобы прояснить ваше намерение, но это ни здесь, ни там.)}

Answer 3

Как упоминалось ранее, ваши итераторы должны быть постоянными, но с вашим алгоритмом что-то не так.Он отлично работает, если у вас есть строка нечетной длины, но видите ли вы, что происходит, когда ваша строка имеет четную длину?Рассмотрим палиндром:

aa

Ваш алгоритм будет проходить через итератор, указывающий на фронт и конец.Все хорошо, тогда он перейдет на следующий уровень, и все будет хорошо, но это не конец.Потому что ваше первое условие никогда не будет верным.Вам нужно проверять не только начало == конец, но начало + 1 == конец или начало == конец-1, если вы предпочитаете.В противном случае ваши итераторы будут расстроены.

Answer 4

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

Answer 5

Какую ошибку вы получаете?

Вы пробовали это?

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

Answer 6

Вы не объявили вторую функцию до вызова ее в первой функции. Компилятор не может его найти и пытается преобразовать str.begin () (string :: iterator) в константную строку &. Вы можете переместить первую функцию за второй функцией.