Why does postfix failed and prefix work fine when pass an iterator as argument and recurse it at tail position?

Question

I come across this problem accidentally.

I have thought google can solve it surely, but after searching multiple keywords, I still can't find answers, which confused me a lot.

When I use prefix at tail position, codes works fine:

template<class ContinerIterator, class F>
constexpr auto fun(ContinerIterator IteratorBegin, ContinerIterator IteratorEnd, F f)
{
    switch (IteratorBegin == IteratorEnd)
    {
    case true: return;
    case false: f(*IteratorBegin);
    }
    return fun(++IteratorBegin, IteratorEnd, f);
}
int main()
{
    std::vector<int> a = { 1, 2, 3, 4 };
    fun(std::begin(a), std::end(a), [](auto &a)->auto{a *= 2; });
    for (auto v : a)
    {
        std::cout << v << std::endl;
    }
    return 0;
}

1

2

3

4

Press any key to continue . . .

Howerer, if I use postfix, IteratorBegin nerve arrives iteratorEnd and goes far and far away, so segmentfault.

template<class ContinerIterator, class F>
constexpr auto fun(ContinerIterator IteratorBegin, ContinerIterator IteratorEnd, F f)
{
    switch (IteratorBegin == IteratorEnd)
    {
    case true: return;
    case false: f(*IteratorBegin);
    }
    return fun(IteratorBegin++, IteratorEnd, f);
}
void test()
{

}
int main()
{
    std::vector<int> a = { 1, 2, 3, 4 };
    fun(std::begin(a), std::end(a), [](auto &a)->auto{a *= 2; });
    for (auto v : a)
    {
        std::cout << v << std::endl;
    }
    return 0;
}

I have tried on MSVC, G++, Clang, all fails. Here is gcc's error list:

Segmentation fault (core dumped)

Here is Clang's:

Error occurred (timeout). Try again later.

It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — NathanOliver, Oct 10 '17 at 16:32
If postfix is implemented according to the usual semantics, it should be obvious. — StoryTeller - Unslander Monica, Oct 10 '17 at 16:33
It’s unusual to see a switch statement used that way. I’d just use a regular old if/else for that. — templatetypedef, Oct 10 '17 at 16:49
@NathanOliver I have tried debug, like step into function, then find IteratorBeginner keep increasing. — Chen Li, Oct 10 '17 at 16:51
@NathanOliver thanks! I am to uncareful and didn't notice the iterator itself is the still the same address, what varies is its value. Maybe it is the result of staying up late many days, lol. — Chen Li, Oct 10 '17 at 17:00

score 3 · Answer 1 · answered Oct 10 '17 at 16:40

The prefix case:

return fun(++IteratorBegin, IteratorEnd, f);

says, first increment IteratorBegin by one, and then call the function fun. After that, return.

On the other hand, the postfix case:

return fun(IteratorBegin++, IteratorEnd, f);

says, first call fun(), then increment the iterator, and then return.

This means that fun() is always being called with the non-incremented iterator.

score 3 · Answer 2 · answered Oct 10 '17 at 16:40

3

When you use postfix increment in the tail call, the recursive call does not get the incremented value of the iterator. It gets the value of the iterator before the increment is applied. Hence, the recursion is infinite. That causes stack overflow.

answered Oct 10 '17 at 16:40

R Sahu

204,454
14
159
270

Vlad from Moscow · Accepted Answer · 2017-10-10T17:04:44.197

This statement

return fun(IteratorBegin++, IteratorEnd, f);

with some exceptions can be considered like

fun(IteratorBegin, IteratorEnd, f);
++IteratorBegin;
return;

So the function is always called with the same value of IteratorBegin.

From the C++ Standard (5.2.6 Increment and decrement)

1 The value of a postfix ++ expression is the value of its operand. [ Note: the value obtained is a copy of the original value —end note ]...

Consider the following simple program

#include <iostream>

void f(int x)
{
    std::cout << "Inside f( x ): x = " << x << std::endl;
}

int main()
{
    int x = 0;

    std::cout << "Before f( x ): x = " << x << std::endl;
    f(x++);
    std::cout << "After  f( x ): x = " << x << std::endl;

    return 0;
}

Its output is

Before f( x ): x = 0
Inside f( x ): x = 0
After  f( x ): x = 1

Also it will be useful to consider the following simple program

#include <iostream>

int x = 0;

void f(int x)
{
    std::cout << "Local (parameter) x = " << x << std::endl;
    std::cout << "Global variable ::x = " << ::x << std::endl;
}

int main()
{
    f(x++);

    return 0;
}

Its output is

Local (parameter) x = 0
Global variable ::x = 1

Why does postfix failed and prefix work fine when pass an iterator as argument and recurse it at tail position?

3 Answers3