Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does gcc optimise away this C++11 foreach loop using my custom iterator?

I was trying to write some code for doing functional-style creation of sequences. I wrote one function, range(a, b), which returns an object that you can iterate over, foreach-style, to go through the numbers a, a + 1, ..., b - 1. Then I wrote another function, map(f, t), which returns another iterable object where each element in the sequence is the result of calling f with the corresponding element of the iterable object t.

This works as expected if I compile using -O1 or lower; with -O2 or higher, my foreach loop (in main at the bottom) gets completely optimised away and nothing is printed. Why does this happen, what have I done wrong? Here's my code:

template<typename T>
struct _range {
    T a;
    T b;

    _range(T a, T b):
        a(a),
        b(b)
    {
    }

    struct iterator {
        T it;

        iterator(T it):
            it(it)
        {
        }

        bool operator!=(const iterator &other) const
        {
            return it != other.it;
        }

        void operator++()
        {
            ++it;
        }

        T operator*() const
        {
            return it;
        }
    };

    iterator begin() const
    {
        return iterator(a);
    }

    iterator end() const
    {
        return iterator(b);
    }
};

template<typename T>
_range<T> range(const T a, const T b)
{
    return _range<T>(a, b);
}

template<typename F, typename T>
struct _map {
    const F &f;
    const T &t;

    _map(const F &f, const T &t):
        f(f),
        t(t)
    {
    }

    struct iterator {
        const F &f;
        typename T::iterator it;

        iterator(const F &f, typename T::iterator it):
            f(f),
            it(it)
        {
        }

        bool operator!=(const iterator &other) const
        {
            return it != other.it;
        }

        void operator++()
        {
            ++it;
        }

        int operator*() const
        {
            return f(*it);
        }
    };

    iterator begin() const
    {
        return iterator(f, t.begin());
    }

    iterator end() const
    {
        return iterator(f, t.end());
    }
};

template<typename F, typename T>
_map<F, T> map(const F &f, const T &t)
{
    return _map<F, T>(f, t);
}

#include <algorithm>
#include <cstdio>

int main(int argc, char *argv[])
{
    for (int i: map([] (int x) { return 3 * x; }, range(-4, 5)))
        printf("%d\n", i);

    return 0;
}
like image 879
Vegard Avatar asked Jan 22 '13 20:01

Vegard


1 Answers

Summarizing the existing comments:

range(-4, 5) creates a temporary, and (in most cases) temporaries only live until the end of the full-expression in which they are created. So in your case, the returned _range object is valid during the construction of the _map, but as soon as said _map is returned from map, the full-expression ends and the _range object is destroyed.

That said, because _map holds the arguments passed to its constructor by const ref rather than by value, this means that by the time the range-based for begins executing, your _map::t is already a dangling reference – classic undefined behavior.

To fix this, simply have _map store its data members by value.

like image 166
ildjarn Avatar answered Oct 04 '22 02:10

ildjarn