8
\$\begingroup\$

My goal was to replicate Ruby's each_cons and each_slice:

(0..5).each_cons(3) {|a, b, c| print a, b, c, "\n"}
012
123
234
345

I made two functions, for_each_cons, and for_each_slice. They work similarly to their Ruby counterparts, except the slice is always passed to separate arguments. The slice size is deducted from the passed function's number of arguments.

const std::vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for_each_cons(vec, [](int a, int b, int c){
    printf("%d %d %d\n", a, b, c);
});

for_each_slice(vec, [](int a, int b, int c){
    printf("%d %d %d\n", a, b, c);
});

Outputs:

0 1 2
1 2 3
2 3 4
3 4 5

0 1 2
3 4 5

And here's the implementation. For simple code it seems to generate similar assembly to manual implementations, although it's largely because it requires random access iterators.

#include <utility>

namespace detail
{
    template <typename Fun>
    struct function_params
        : public function_params<decltype(&Fun::operator())>
    {};

    template <typename Class, typename Ret, typename... Args> // for lambdas
    struct function_params<Ret(Class::*)(Args...) const> {
        static constexpr int n_args = sizeof...(Args);
    };

    template <typename Class, typename Ret, typename... Args> // for mutable lambdas
    struct function_params<Ret(Class::*)(Args...)> {
        static constexpr int n_args = sizeof...(Args);
    };

    template <typename Ret, typename... Args> // for function pointers
    struct function_params<Ret(*)(Args...)> {
        static constexpr int n_args = sizeof...(Args);
    };

    template<typename It, typename Fun, int N = function_params<Fun>::n_args, std::size_t... I>
    void for_each_cons_impl(It first, It last, Fun f, std::index_sequence<I...>) {
        for(auto it = first; it + N - 1 < last; ++it)
            f(*(it + I)...);
    }

    template<typename It, typename Fun, int N = function_params<Fun>::n_args, typename Indices = std::make_index_sequence<N>>
    void for_each_cons(It first, It last, Fun f) {
        for_each_cons_impl(first, last, f, Indices());    
    }

    template<typename It, typename Fun, int N = function_params<Fun>::n_args, std::size_t... I>
    void for_each_slice_impl(It first, It last, Fun f, std::index_sequence<I...>) {
        for(auto it = first; it + N - 1 < last; it += N)
            f(*(it + I)...);
    }

    template<typename It, typename Fun, int N = function_params<Fun>::n_args, typename Indices = std::make_index_sequence<N>>
    void for_each_slice(It first, It last, Fun f) {
        for_each_slice_impl(first, last, f, Indices());    
    }
}

template<typename It, typename Fun>
void for_each_cons(It first, It last, Fun f) {
    detail::for_each_cons(first, last, f);
}

template<typename Rng, typename Fun>
void for_each_cons(Rng &&rng, Fun f) {
    for_each_cons(rng.begin(), rng.end(), f);
}

template<typename It, typename Fun>
void for_each_slice(It first, It last, Fun f) {
    detail::for_each_slice(first, last, f);
}

template<typename Rng, typename Fun>
void for_each_slice(Rng &&rng, Fun f) {
    detail::for_each_slice(rng.begin(), rng.end(), f);
}

Any hints and criticism are welcome.

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

The two main issues I see are that

  1. You require RandomAccessIterators although these should be implementable with ForwardIterators as well since you never have to skip an element.
  2. This will fail for functors with an overloaded or templated operator() such as those with auto parameters

Also, what happens if the range's length isn't divisible by the step size in the second case?

As 2 isn't really possible to solve since in the overloaded case there may be multiple valid values for n_args you could allow the user to pass the number of arguments as a first parameter. You could then default that value to 0 (which is never valid) and infer the number of parameters as you currently do if it is set to 0.

\$\endgroup\$
1
  • \$\begingroup\$ 1. You're right. I'm still experimenting with the most optimal way to do this, and possibly making it work with input iterators by caching the values; 2. I didn't think about this, thanks. 3. the trailing values are ignored; I had a choice between this or raising an exception, and chose this. \$\endgroup\$
    – Adrian17
    Commented May 29, 2015 at 11:17
2
\$\begingroup\$

There are at least a couple of things that you could improve in your code without changing the way it works:

  • I would have used std::size_t for the number of parameters of a function. It is more consistent with std::index_sequence that uses std::size_t underneath.

  • You don't have to always pollute the template parameters list when using the indices trick. If you don't need a type alias or a constant in the parameters type or in the return type, then simply move it to the body of the function. It will make it easier for users to understand the signature:

    template<typename It, typename Fun, std::size_t... I>
    void for_each_cons_impl(It first, It last, Fun f, std::index_sequence<I...>) {
        static constexpr std::size_t N = function_params<Fun>::n_args;
        for(auto it = first; it + N - 1 < last; ++it)
            f(*(it + I)...);
    }
    
    template<typename It, typename Fun>
    void for_each_cons(It first, It last, Fun f) {
        static constexpr std::size_t N = function_params<Fun>::n_args;
        using Indices = std::make_index_sequence<N>;
        for_each_cons_impl(first, last, f, Indices());    
    }
    
  • Functions are sometimes big objects, you could use forwarding references and std::forward instead of passing everything by value:

    template<typename It, typename Fun>
    void for_each_cons(It first, It last, Fun&& f) {
        static constexpr std::size_t N = function_params<Fun>::n_args;
        using Indices = std::make_index_sequence<N>;
        for_each_cons_impl(first, last, std::forward<Fun>(f), Indices());    
    }
    

    However, you will have to use function_params<std::decay_t<Fun>>::n_args instead of function_params<Fun>::n_args in order for this to run.

  • But actually, your implementation of function_params lacks many cases for volatile functions as well as functions with ref-qualifiers. You could avoid the std::decay_t of the previous point if you completed your specialization set. However I have to admit that there is no simple workaround and that you have to write every specialization by hand. That's cumbersome, but unless you want to dirty your hands with generative macros, that's currently the only way.

  • Since you are using random-access iterators anyway, you might as well use the brackets syntax instead of the addition & dereference syntax:

    template<typename It, typename Fun, std::size_t... I>
    void for_each_cons_impl(It first, It last, Fun&& f, std::index_sequence<I...>) {
        static constexpr std::size_t N = function_params<Fun>::n_args;
        for(auto it = first; it + N - 1 < last; ++it)
            std::forward<Fun>(f)(it[I]...);
    }
    
  • On the other hand, you can also make your code work for forward iterators with only a few changes, replacing the pointer arithmetic operations by calls to std::distance, std::advance and std::next:

    template<typename It, typename Fun, int N = function_params<Fun>::n_args, std::size_t... I>
    void for_each_slice_impl(It first, It last, Fun f, std::index_sequence<I...>) {
        for(auto it = first; std::distance(it, last) > N - 1; std::advance(it, N))
            f(*std::next(it, I)...);
    }
    

    Keep in mind that the complexity is higher for forward iterators than for random-access iterators though. There might be ways to reduce it by manually keeping track of the distance between it and last instead of computing it by advancing the iterators for every iteration of the loop.

  • Since we are dealing with iterators, I would have kept names consistent with those in the standard library and named them begin and end instead of first and last. last is especially confusing since the last iterator is conceptually the one before the end iterator, it was even proposed to add the function last to containers in N3585 to return and iterator pointing to the last element.

\$\endgroup\$
5
  • \$\begingroup\$ I'd say arguments being first and last is consistent with the standard library; even the Ranges proposal (D4382) keeps this naming (although I agree it's a bit confusing). The rest of your points I'll have to experiment with later, thanks. When I do these changes, would you suggest editing my post or making a new one? \$\endgroup\$
    – Adrian17
    Commented May 29, 2015 at 10:55
  • \$\begingroup\$ @Adrian17 If you want to post the revised version of your code so that it can be revised again, then please post a new question. We don't accept edits on questions when they invalidate the answers :) \$\endgroup\$
    – Morwenn
    Commented May 29, 2015 at 11:13
  • \$\begingroup\$ @Adrian17 But I have to say that it is actually a surprise to me that the parameters are named first and last everywhere in the standard specification, I would have sworn that they were named begin and end. It's my mistake. \$\endgroup\$
    – Morwenn
    Commented May 29, 2015 at 11:15
  • \$\begingroup\$ About passing function objects by value, I think understand, but... I was looking into VC's and GCC's <algorithm> and they seem to pass them into internal implementations by value, why is that? \$\endgroup\$
    – Adrian17
    Commented May 29, 2015 at 11:29
  • \$\begingroup\$ @Adrian17 I guess that most of these functions existed before forwarding references. I actually suggested to use forwarding references instead because this is what std::apply does. It is more recent, and they probably do it for a reason. \$\endgroup\$
    – Morwenn
    Commented May 29, 2015 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.