C++ STL: Trouble with string iterators

Question

I'm making a simple command line Hangman game.

void Hangman::printStatus()
{
    cout << "Lives remaining: " << livesRemaining << endl;
    cout << getFormattedAnswer() << endl;
}

string Hangman::getFormattedAnswer()
{
    return getFormattedAnswerFrom(correctAnswer.begin(), correctAnswer.end());
}

string Hangman::getFormattedAnswerFrom(string::const_iterator begin, string::const_iterator end)
{
    return begin == end? "" : displayChar(*begin) + getFormattedAnswerFrom(++begin, end);
}

char Hangman::displayChar(const char c)
{
    return c;
}

(Eventually, I'll change this so displayChar() displays a - or a character if the user has guessed it, but for simplicity now I'm just returning everything.)

When I build and run this from VS 2010, I get a popup box:

Debug Assertion Failed!

xstring Line: 78

Expression: string iterator not dereferenceable

What am I doing wrong?

Could you try getting the backtrace while debugging, to be sure the code you posted causes this behaviour? — jpalecek, May 27 '10 at 23:04
Is there a particular reason that you are using a recursive implementation? An iterative implementation would be simpler. — James McNellis, May 27 '10 at 23:05
@James yeah, you're right. I implemented it iteratively and now it works. — Nick Heiner, May 27 '10 at 23:08
Looks like an off-by-one type of issue when begin == end - 1 — Justin Ardini, May 27 '10 at 23:19

score 8 · Accepted Answer · edited May 23 '17 at 12:01

8

The problem is in the evaluation of:

displayChar(*begin) + getFormattedAnswerFrom(++begin, end)

In executing this statement, it is evident that your compiler is first incrementing begin, returning the "next" begin for use as the first argument to getFormattedAnswerFrom, and then dereferencing begin for the argument to displayChar.

When begin is one behind end, then begin != end so displayChar(*begin) + getFormattedAnswerFrom(++begin, end) will run. Your compiler increments begin, so now begin == end, and the dereference of begin is invalid.

See also: Order of evaluation in C++ function parameters

edited May 23 '17 at 12:01

Community

1
1

answered May 27 '10 at 23:18

Daniel Trebbien

38,421
18
121
193

Does the C++ spec define the order of evaluation of sub-expressions of binary operators or is it just common to go right-to-left, as your assert? – David Gladfelter May 27 '10 at 23:23
@David: It's UB, at least for primitive types. For user types it's unspecfied, but could be undefined, too (I don't know exactly). – jpalecek May 27 '10 at 23:25
@David, I don't think that the C++ standard specifies whether `*begin` or `++begin` will execute first. I didn't intend to assert right-to-left evaluation of subexpressions, so I have updated my answer. – Daniel Trebbien May 27 '10 at 23:33
In fact, I once worked at a company that used the Intel *and* Visual C++ compilers. The Intel compiler tended to evaluate left-to-right and the Visual C++ compiler tended to evaluate right-to-left. This led to a few issues where some test cases would succeed if compiled with `icc` but fail if compiled with `cl`. – Daniel Trebbien May 27 '10 at 23:39
I thought that plain order of operations went left-to-right? In any case, this is yet another example of why ++x or x++ should be avoided if used as part of a greater expression. – Puppy May 27 '10 at 23:50

score 0 · Answer 2 · answered May 27 '10 at 23:04

0

If correctAnswer is empty, correctAnswer.begin() will be the same as correctAnswer.end() and not be dereferenceable.

answered May 27 '10 at 23:04

fbrereto

35,429
19
126
178

3

But shouldn't it immediately terminate the recursion then? – jpalecek May 27 '10 at 23:07
3

He has a check for that. Are you saying that even if begin == end, displayChar(*begin) + getFormattedAnswerFrom(++begin, end); will still be computed? – Anthony May 27 '10 at 23:08
@jpalecek: Ah yes, that's true. – fbrereto May 27 '10 at 23:09

Puppy · Answer 3 · 2010-05-27T23:46:55.273

0

It seems fine to me. However, remember any heap or stack corruption could produce this error. You need to grab the stack trace and look inside correctAnswer, and ensure that both it and the instance of Hangman in question are valid objects.

Also, I'm just flat out a little concerned about your functions here. They seem very strange. Why not just replace with std::for_each?

Edit@comment:
If you have C++0x, you can just do

std::for_each(correctAnswer.begin(), correctAnswer.end(), [this](const char& ref) {
    std::cout << this->displayChar(ref);
});

Else, you will have to do something that looks a little like this:

struct helper {
    Hangman* ptr;
    void operator()(const char& ref) {
        std::cout << ptr->displayChar(ref);
    }
};
helper Helper;
Helper.ptr = this;
std::for_each(correctAnswer.begin(), correctAnswer.end(), Helper);

edited May 27 '10 at 23:46

answered May 27 '10 at 23:18

Puppy

144,682
38
256
465

Edited in. You shouldn't have problems with that. – Puppy May 27 '10 at 23:48
Intriguing. Can you explain the syntax of the top example? What's the significance of `[this]`? – Nick Heiner May 27 '10 at 23:55
When using lambda captures, [this] is a special dispensation where the this pointer is captured by value, and the resulting lambda is considered to be a member lambda, effectively. http://msdn.microsoft.com/en-us/library/dd293599.aspx#methodLambdaExpressions Strictly, I didn't have to dereference this inside the body, but did anyway. – Puppy May 28 '10 at 00:06

C++ STL: Trouble with string iterators

3 Answers3