从字符指针获取迭代器 (C++)

Question

我正在挑战自己，只使用 SL 算法、迭代器等编写一个回文测试器。我还想编写程序来处理原始字符串。下面，我在 copy_if 算法中使用原始指针 pal，但是，我如何定义一个迭代器到这里，即使用 begin(pal) 和 end(pal + size) 之类的东西？

#include <algorithm>
#include <iterator>
#include <cctype>

using namespace std;

bool isPalindrome(const char* pal) {
    if (!pal) { return(false); }

    int size = strlen(pal);
    string pal_raw;
    pal_raw.reserve(size);

    // Copy alphabetical chars only (no spaces, punctuations etc.) into pal_raw
    copy_if(pal, pal+size, back_inserter(pal_raw),
        [](char item) {return isalpha(item); }
    );

    // Test if palindromic, ignoring capitalisation
    bool same = equal(begin(pal_raw), end(pal_raw), rbegin(pal_raw), rend(pal_raw),
        [](char item1, char item2) {return tolower(item1) == tolower(item2); }
    );

    return same;
}

int main(){
    char pal[] = "Straw? No, too stupid a fad. I put soot on warts.";
    bool same = isPalindrome(pal);
    return 0;
}

奖励问题：是否可以通过在 equal() 内递增迭代器 'in place' 来消除对 copy_if() 的需求，即当 !isalpha(item) 时？

Answer 1

当涉及到 C++ 库算法时，迭代器实现了指针的概念。而且，正如您所发现的，采用迭代器的 C++ 库算法也非常乐意采用指针。是同一个概念。

并且当您已经有指针开始时，没有某种迭代器可以将指针转换为。

这是真的

std::begin(arr)

和

std::end(arr)

在平面阵列上定义。但是，你猜怎么着：它们 return 是指向数组开头和结尾的指针，而不是某种迭代器 class。

但是，您不能使用 std::begin() 和 std::end()，因为当您需要使用它时，在您的函数内部，数组已经衰减为 char *。 std::begin() 和 std::end() 适用于真实数组，而不是衰减指针。

如果您坚持使用迭代器，您应该将 std::string 传递给您的回文函数，而不是 char *。 std::string 实现了一个 begin() 和一个 end() 方法，return 一个 std::string::iterator，您可以使用。

Answer 2

如果我这样做并且我想让它适用于不同的类型，我会将方法模板化 - 例如：

template<class ITER_T>
bool isPalindrome(ITER_T begin, ITER_T end) {
   // check for palindrome generically between begin and end
}

这样它可以用于 const char * 迭代器，std::string、std::vector<char>、std::map<char> 具有相同的代码。如果实施得当，即使对于其他类型的向量、地图和任何其他你可以获得迭代器的东西，并且项目类型都有定义的比较运算符。

作为奖励，我还可以检查字符数组、字符串或向量的一部分是否为回文。

顺便说一下，这个：

equal(begin(pal_raw), end(pal_raw), rbegin(pal_raw), rend(pal_raw), ...

如果字符串是回文，则不必要地检查每个字符两次……效率不高。在这种情况下，您可以使用 "manual" 循环做得更好（不确定是否有标准算法）。

如果你想让 begin(arr)/end(arr) 在重载函数中工作，你无论如何都需要对其进行模板化，如下所示：

template<size_t N>
bool isPalindrome(const char (&arr)[N]) {
...

然而，您会为每个不同的数组大小获得单独的实例化。因此，无论如何最好使用迭代器进行模板化，并且只为任何 char 数组大小获得一个实例化。

所以要回答 "bonus question"，确实可以通过直接遍历数组来完全避免创建临时字符串（即动态内存分配）：

template<typename ITER_T>
bool isPalindrome(ITER_T begin, ITER_T end) {
    while (begin < end) {
        if (tolower(*begin++) != tolower(*--end))
            return false;
    }
    return true;
}
bool same = isPalindrome(begin(pal), end(pal));

为了测试 isalpha 我留给你练习。提示：您可以在相等性检查和 increment/decrement begin/end 之前执行此操作（提示 #2：我想到的解决方案将使用 continue 关键字）。

同样可以使它与不同于 char 的任意类型一起工作 - 然后可以使用类型特征通过模板特化来抽象出 isalpha/tolower 调用。

从字符指针获取迭代器 (C++)

Get an iterator from a char pointer (C++)

c++

pointers

iterator

c++-standard-library

stl-algorithm