Turn recursion into loop

Question

I have an unknown type T that might be non-copy- or move-assignable, a function T op(const T &foo, Other bar) that computes and returns a new T based on an existing one, and a recursive function:

template<typename Iter, typename T>
T foldLeft(Iter first, Iter last, const T &z, std::function<T(T, Other)> op)
{
    if (first == last) {
        return z;
    }
    return foldLeft(std::next(first), last, op(z, *first), op);
}

The compiler can't always optimize the tail call, because T might have a non-trivial destructor. I'm trying to manually rewrite it with a loop, but can't figure out how to reassign to z.

If you are returning a T, then it must be copy or move constructible, so why would it not be copy or move assignable? I guess you will need to create a new object each time, maybe dynamically allocating it? — BoBTFish
– BoBTFish, Commented Apr 9, 2016 at 8:42
Like when T is std::unique_ptr<int>...? I want to do it on stack though, for better performance. — Zizheng Tai
– Zizheng Tai, Commented Apr 9, 2016 at 8:43
it's better to use an extra typename Fun template parameter instead of explicitly using std::fuction. That way, also regular functions and lambdas will work. — TemplateRex
– TemplateRex, Commented Apr 9, 2016 at 8:47
@TemplateRex Thanks, that's how I'm actually doing it. Here it's just a simplification. — Zizheng Tai
– Zizheng Tai, Commented Apr 9, 2016 at 8:48
You can explicitly new/delete into a buffer you provide, that could live on the stack, with char buffer[sizeof(T)];, but it'd be nasty. If you require copy construction, can you really not require copy assignment? — BoBTFish
– BoBTFish, Commented Apr 9, 2016 at 8:56

Zizheng Tai · Accepted Answer · 2016-04-09 10:11:12Z

5

You may do the following, but the restriction is strange, and using std::accumulate seems simpler

template<typename Iter, typename T, typename Fn>
T foldLeft(Iter first, Iter last, const T &z, Fn op)
{
    std::aligned_storage_t<sizeof (T), alignof (T)> buf;
    T* res = new (&buf) T(z);
    for (auto it = first; it != last; ++it) {
        auto&& res2 = op(res, it);
        res->~T();
        res = new (&buf) T(std::move(res2));
    }
    T final_res = *res;
    res->~T();
    return final_res;
}

Note that it is not exception safe.

edited Apr 9, 2016 at 10:11

Zizheng Tai

6,7283 gold badges41 silver badges93 bronze badges

answered Apr 9, 2016 at 9:10

Jarod42

227k15 gold badges214 silver badges350 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Zizheng Tai Over a year ago

Exactly what I needed. Thanks! I need to roll my own version of std::accumulate because it requires the initial value to be both CopyAssignable and CopyConstructible, which makes folding over something like a std::unique_ptr impossible.

Jarod42 Over a year ago

If you work with std::unique_ptr, using move assign would be simpler.

Collectives™ on Stack Overflow

Turn recursion into loop

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related