Palindrome test

Question

This is some code that determines if a string of characters is a palindrome or not. My professor says that there is a performance issue with the program, but I can't quite put my finger on it. Can someone find out the 'performance' issue?

Initially, I thought maybe the process is slower as it uses two memory containers, as opposed to simply comparing two halves of a single string.

int main()
{
    char c;
    bool check = true;
    stack<char> cstack;
    queue<char> cqueue;
    cout << "Enter a string and press return." << endl;
    cin.get(c);
    while (c != '\n') {
        cstack.push(c);
        cqueue.push(c);
        cin.get(c);
    }
    while (check && !cqueue.empty()) {
        if (cstack.top() != cqueue.front())
            check = false;
        cstack.pop();
        cqueue.pop();
    }
    if (check)
        cout << "Yes it is!" << endl;
    else
        cout << "No it's not." << endl;
    return 0;
}

Answer 1

1. While it is not quite definitive, it looks like you use using namespace std;.
   That namespace is not designed for wholesale inclusion, being vast and subject to change at the whim of the implementation, aside from providing what is standardised.
   Read "Why is “using namespace std” considered bad practice?" for more detail.

2. Synchronizing C++ iostreams with C stdio, as happens by default, is quite expensive. Call std::ios_base::sync_with_stdio(false); to fix that.

3. You should desist from using std::endl, as spurious manual flushing flushes any pretense at performance down the drain.
   For those rare cases where it is actually necessary for correctness, use std::flush for explicitness.

4. You assume reading from std::cin always succeeds. That's generally unsupportable, please handle failure gracefully.

5. You are reading character-by-character. Each and every read has significant overhead, which you could simply avoid by using std::getline(). Using the proper abstraction is also significantly more readable.

6. You are storing the input twice, once in a std::queue and once in a std::stack. Even only storing it in just one std::deque (the underlying implementation for both) would be a considerable improvement.

7. Consider encapsulating the test whether the input is a palindrome into its own reusable function, separate from actually getting it.

8. Testing whether something is a palindrome seems a favorite passtime of many beginners.
   Thus, there are a myriad posts on how to efficiently and elegantly do that in C++, for example "Check if a string is palindrome or two strings are the opposite of each other".
   The important points are avoiding expensive copies, and only comparing each element once.

9. If you want one of two values, conditional on some expression, consider the conditional operator expr ? true_expr : false_expr. It is designed for that.

10. return 0; is implicit for main(). Make of that what you will.

Answer 2

I see two improvement points in the code.

1. It is better to use getLine() and store the input in char* instead of reading each char and appending to a stack
2. It is more than enough to iterate till half of the string as the remaining half is checked in the first half iteration cstack.top() != cqueue.front()

Answer 3

Initially, I thought maybe the process is slower as it uses two memory containers, as opposed to simply comparing two halves of a single string.

I think you hit on an excellent idea right there. I'd read a line of input into a string, the compare the first half of the string to the second half in reverse order.

• You can use std::getline to read the string.
• You can use your_string.size() / 2 to get half the length.
• You can use your_string.cbegin() to get an iterator to the beginning of the string.
• You can use your_string.crbegin() to get a reverse iterator to the string (one that iterates through from the end to the beginning).
• You can use std::mismatch to compare the two halves of the string.
• As Deduplicator pointed out, you probably want a function that does nothing but check whether a string is a palindrome.

If you wanted to minimize changes to your code, you could just read the string into the deque, then to do the comparison, pop one element from the front, and one element from the back, and compare them. The input was palindromic if and only if all the elements match until the deque has fewer than two elements.