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

Question

I am challenging myself to write a Palindrome tester using only SL algorithms, iterators etc. I also want to program to work with raw strings. Below, I use the raw pointer pal in the copy_if algorithm, but instead, how could I define an iterator to go here, i.e. by using something like begin(pal) and 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;
}

Bonus Question: Is it possible to eliminate the need to copy_if() by incrementing the iterators 'in place' from within equal() i.e. when !isalpha(item)?

Answer 1

Iterators implement the concept of pointers, when it comes to C++ library algorithms. And, as you've discovered, C++ library algorithms that take iterators are perfectly happy to also take pointers. It's the same concept.

And when you already have pointers to begin with there is no iterator, of some kind, that the pointers can be converted to.

It is true that

std::begin(arr)

and

std::end(arr)

are defined on flat arrays. But, guess what: they return a pointer to the beginning and the end of the array, and not an iterator class of some kind.

However, you cannot use std::begin(), and std::end() because by the time you need to use it, inside your function, the array was already decayed to a char *. std::begin() and std::end() works on real arrays, and not decayed pointers.

If you insist on using iterators, you should pass a std::string to your palindrome function, instead of a char *. std::string implements a begin() and an end() method that return a std::string::iterator, that you can use.

Answer 2

If I'd do that and I'd want to make it work for different types, I'd templatize the method - for example:

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

That way it would work for const char * iterators, std::string, std::vector<char>, std::map<char> with the same code. And if implemented properly, even for other types of vectors, maps and anything else which you can get iterator for and the item type has a comparison operator defined.

As a bonus, I could then also check if a part of character array, string or a vector is a palindrome.

By the way, this:

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

is unnecessarily checking each character twice, if the string is a palindrome ... not very efficient. In this case you could do perhaps better with a "manual" loop (not sure if there is a std algo for that).

---

If you'd like to make the begin(arr)/end(arr) work inside the overloaded function, you'd need to templatize it anyway, like this:

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

However then you get separate instantiation for each different array size. So it is better anyway to templatize using the iterators and only get a single instantiation for any char array size.

---

So to answer the "bonus question", it is indeed possible to avoid creating the temporary string (i.e. dynamic memory allocation) at all, by iterating over the array directly:

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

To test for isalpha I leave to you for your practice. Hint: you can do that before the equality check and increment/decrement the begin/end appropriately (hint #2: the solution I have in mind will use the continue keyword).

The same to make it work with arbitrary type different from char - then type traits can be used to abstract out the isalpha/tolower calls via template specializations.