Overload std::for_each for binary functions

[morw...@gmail.com]

I sometimes - often - want to apply binary functions element-wise between two ranges. In order to do so, it would be great to have
an overload of std::for_each for binary functions. It would be something like this:

template<class InputIt1, class InputIt2 class BinaryFunction>
UnaryFunction for_each(InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryFunction f)
{
    for (; first1 != last1; ++first1, ++first2) {
        f(*first1, *first2);
    }
    return f;
}

[Nevin Liber]

On 18 September 2013 07:28, <morw...@gmail.com> wrote:

I sometimes - often - want to apply binary functions element-wise between two ranges. In order to do so, it would be great to have
an overload of std::for_each for binary functions.

1.  Why just binary?  Why not n-ary?

2.  Does it have to be named std::for_each?

--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Billy O'Neal]

I'd assume you actually meant:

 

template<class InputIt1, class InputIt2, class BinaryFunction>
BinaryFunction for_each(InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryFunction f)

{
    for (; first1 != last1; ++first1, ++first2) {
        f(*first1, *first2);
    }
    return f;
}

 

:)

 

I'd also like to add this:

 

template<class InputIt1, class InputIt2, class BinaryFunction>
BinaryFunction for_each(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryFunction f)

 

With possible implementation + example:

 

http://ideone.com/UwSrbo

 

#include <vector>
#include <string>
#include <iostream>
#include <list>
using namespace std;

 

template<class InputIt1, class InputIt2, class BinaryFunction>
BinaryFunction for_each_impl(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryFunction f, std::random_access_iterator_tag, std::random_access_iterator_tag)
{
    std::cout << "Optimized for random access.\n";
    if (last1 - first1 < last2 - first2)

    {
        for (; first1 != last1; ++first1, ++first2) {
            f(*first1, *first2);
        }
    }

    else
    {
        for (; first2 != last2; ++first1, ++first2) {
            f(*first1, *first2);
        }
    }
   
    return f;
}

 

template<class InputIt1, class InputIt2, class BinaryFunction>
BinaryFunction for_each_impl(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryFunction f, std::input_iterator_tag, std::input_iterator_tag)
{
    std::cout << "Generic implementation.\n";
    for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
        f(*first1, *first2);
    }
    return f;
}

 

template<class InputIt1, class InputIt2, class BinaryFunction>
BinaryFunction for_each(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryFunction f)
{
    typedef typename std::iterator_traits<InputIt1>::iterator_category Category1;
    typedef typename std::iterator_traits<InputIt2>::iterator_category Category2;
    return for_each_impl(first1, last1, first2, last2, f, Category1(), Category2());
}

 

template <template <typename, typename> class ContainerT>
void test()
{
    ContainerT<int, std::allocator<int>> example;
    example.push_back(42);
    example.push_back(1729);
    ContainerT<string, std::allocator<string>> example2;
    example2.push_back("forty two");
    example2.push_back("seventeen twenty nine");
    for_each(example.cbegin(), example.cend(), example2.cbegin(), example2.cend(),
        [](int left, string const& right) { std::cout << left << " is " << right << "\n"; });
}

 

int main() {
    test<list>();
    test<vector>();
}

 

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

Malware Response Instructor - BleepingComputer.com

--
 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[morw...@gmail.com]

@Nevin: I had a problem I could solve with std::transform but which would have been more conveniently solved with a binary std::for_each.
Since std::transform only works with unary and binary functors, I thought std::for_each could also have a useful binary overload, but did
not think it further. I didn't check, but there are probably several other algorithms that could have a n-ary overload and don't have it. Also,
I kept the name std::for_each instead of choosing a new one since the logic involved is pretty much the same :)

@Billy: You're totally right about the two mistakes I made. I didn't have my code at hand and hastily wrote this one while I should have
taken more time to avoid the errors. I don't know whether the parameter last2 is useful though; std::transform does not have it for
example.

[Billy O'Neal]

@morwenn29:   All the non-mutating algorithms accepting two ranges have variants accepting both iterators for the second range in N3691. (That is, mismatch, find, is_permutation, and equal) Consider 25.2.11 [alg.equal]:   template<class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1,            InputIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1,            InputIterator2 first2, BinaryPredicate pred); template<class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1,            InputIterator2 first2, InputIterator2 last2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1,            InputIterator2 first2, InputIterator2 last2,            BinaryPredicate pred);

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

Malware Response Instructor - BleepingComputer.com

--

[Bryan St. Amour]

Binary std::for_each is different than the other non-mutating algorithms however, because as a precondition there should be at least as many elements in [first2, last2) than there are in [first1, last1), just like std::transform. My personal opinion is that binary std::for_each should not take in last2 as a parameter.

[Bengt Gustafsson]

Can't this be done for any arity using variadic templates:

template<typename Function, typename InputIterator1, typename... InputIterators> Function for_each(InputIterator1 first1, InputITerator1 last1, InputIterators... firsts, Function f);

This will require a helper variadic function to increment all the first iterators, but that should not be a problem.

On the other hand this does not go well with supplying all the end iterators unless we pass all the firsts and then all the lasts. Or can you put the ... like this to get pairs of iterator parameters, I'm uncertain ablout the comma there:

template<typename Function, typename... InputIterators> Function for_each(InputIterators first1, InputITerators last1..., Function f);

[Bryan St. Amour]

Not quite. The variadic pack has to come at the end of the parameter list, so if you put the function first, then yeah that will work. But it breaks with the traditional order of parameters in the STL. I think the best you can do to support a variadic for_each is to pass the begin iterators in as a tuple,and specify a last iterator to constrain the size of the range, followed by the function. i.e.
   
    template <typename Iter, typename Func, typename... Iters>
    for_each(std::tuple<Iter, Iters...> firsts, Iter last, Func f);

[Vlad from Moscow]

I agree with the opinion that such an algorithm should have another name.

среда, 18 сентября 2013 г., 16:28:44 UTC+4 пользователь morw...@gmail.com написал:

[Zhihao Yuan]

On Wed, Sep 18, 2013 at 4:38 PM, Vlad from Moscow <vlad....@mail.ru> wrote:
> I agree with the opinion that such an algorithm should have another name.

Like std::for_both ? LOL

Actually, I think we could have a zip iterator

http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/zip_iterator.html

and even zip range adaptor to solve this.

We already have std::tuple, I don't see a blocker for zip iterator.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

[Daniel Krügler]

2013/9/18 Zhihao Yuan <z...@miator.net>:

> Actually, I think we could have a zip iterator
>
> http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/zip_iterator.html
>
> and even zip range adaptor to solve this.
>
> We already have std::tuple, I don't see a blocker for zip iterator.

The current "blocker" are the broken iterator requirements which have
the effect that zip-iterator cannot be anything than an InputIterator
;-) But don't take this comment too serious: Yes, we can standardize
zip iterator, but it would be of much more value, if we could fix the
iterator requirements also.

- Daniel

[Magnus Fromreide]

On Wed, 2013-09-18 at 13:35 -0700, Bryan St. Amour wrote:
> Not quite. The variadic pack has to come at the end of the parameter
> list, so if you put the function first, then yeah that will work. But
> it breaks with the traditional order of parameters in the STL. I think
> the best you can do to support a variadic for_each is to pass the
> begin iterators in as a tuple,and specify a last iterator to constrain
> the size of the range, followed by the function. i.e.
>
> template <typename Iter, typename Func, typename... Iters>
> for_each(std::tuple<Iter, Iters...> firsts, Iter last, Func f);

One could also embrace that necessity and use

template <typename Iter, typename Func, typename... Iters>

for_each(Iter first1, Iter last1, Func f, Iters .. firsts)

with the advantage that it covers the already present case with 0 Iters
as well. This also marks the trailing firsts as lesser than the initial
one so they are not to be expected to be used for range checking.

@ Billy:
I also think std::for_each and std::transform are equally mutating since
one can implement them in terms of each other.


From this follows that another overload for transform might be useful as
well:

template <class InputIterator, class OutputIterator, class Operation,
class ... InputIterators>
OutputIterator
transform_n(InputIterator first, InputIterator last, OutputIterator result,
Operation op, InputIterators ... firsts); (*)

If we have one of them then the other one ought to exist as well and as
we already have transform with an additional iterator that speaks in
favor of for_each with an additional iterator, but I think the
generalized versions from above are better.

/MF


(*) transform_n in order to avoid the clashing with
transform(I1, I1, I2, O, B)

[Billy O'Neal]

>I also think std::for_each and std::transform are equally mutating since
one can implement them in terms of each other.

 

No, they can't. They can in the restricted case that the output iterator and the first input iterator to transform are the same.

 

As for "mutating" -- I didn't name them that way. That's what What the Standard Says^TM.

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

Malware Response Instructor - BleepingComputer.com

>
>
>
>

[Magnus Fromreide]

On Wed, 2013-09-18 at 14:56 -0700, Billy O'Neal wrote:
> >I also think std::for_each and std::transform are equally mutating
> since
> one can implement them in terms of each other.
>
> No, they can't. They can in the restricted case that the output
> iterator and the first input iterator to transform are the same.

They can, but it ain't simple, nor beautiful.



transform using for_each:

template <class OutputIterator, class UnaryOperation>
struct helper {
helper(OutputIterator o_, UnaryOperation u_) : o(o_), u(u_) { }
template <class T> void operator()(T t) { *o++ = u(t); }
OutputIterator res() { return o; }
private:
OutputIterator o;
UnaryOperation u;
};

template <class InputIterator, class OutputIterator,

class UnaryOperation>
OutputIterator
transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op)
{
return std::for_each(first, last,
helper<OutputIterator, UnaryOperation>(result, op)).res();
}



for_each using transform:

template <class Function>
struct helper {
typedef std::output_iterator_tag iterator_category;
typedef long difference_type;
typedef void pointer, reference;
struct value_type {
value_type(Function& f_) : f(f_) { }
template <class T> void operator=(T t) { f(t); }
private:
Function& f;
};
helper(Function f_) : f(f_) { }
helper& operator++() { return *this; }
value_type operator*() { return value_type(f); }
Function res() { return f; }
private:
Function f;
};

struct identity {
template <class T> T operator()(T t) const { return t; }
};

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)
{
return std::transform(first, last, helper<Function>(f), identity()).res();
}


I admit to not having tested the above two pieces of code as much as
would be needed if I were to use it but as thought food it should be
enough.

> As for "mutating" -- I didn't name them that way. That's what What the
> Standard Says^TM.

:-)

/MF

[Billy O'Neal]

I stand corrected :)

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

Malware Response Instructor - BleepingComputer.com

[Zhihao Yuan]

On Sep 18, 2013 7:07 PM, "Zhihao Yuan" <z...@miator.net> wrote:
> So that InputIterator requires decltype, ForwardIterator and
> follow ups require iterator_traits<X>::reference.
>
> But of course this breaks user code...

Errr, not really; it just takes some time to adapt to, like std::addressof.

Do you think this is something can be changed with a library issue?

--
Zhihao

[Zhihao Yuan]

On Wed, Sep 18, 2013 at 5:45 PM, Daniel Krügler
<daniel....@gmail.com> wrote:
> The current "blocker" are the broken iterator requirements which have
> the effect that zip-iterator cannot be anything than an InputIterator
> ;-) But don't take this comment too serious: Yes, we can standardize
> zip iterator, but it would be of much more value, if we could fix the
> iterator requirements also.

Ah ha ha ha, yea. There are always something in C++ which
has been "fixed" in many people's mind but is still physically broken...

The change in my mind (I roughly looked around in the standard
and saw no places being affected) is to simply remove the 3rd
bullet from 24.2.5/1:

-- if X is a mutable iterator, reference is a reference to T; if X is
a const iterator, reference is a reference to const T,

So that InputIterator requires decltype, ForwardIterator and
follow ups require iterator_traits<X>::reference.

But of course this breaks user code...

[Marc]

Le mercredi 18 septembre 2013 23:48:55 UTC+2, Magnus Fromreide a écrit :

On Wed, 2013-09-18 at 13:35 -0700, Bryan St. Amour wrote:
> Not quite. The variadic pack has to come at the end of the parameter
> list, so if you put the function first, then yeah that will work. But
> it breaks with the traditional order of parameters in the STL. I think
> the best you can do to support a variadic for_each is to pass the
> begin iterators in as a tuple,and specify a last iterator to constrain
> the size of the range, followed by the function. i.e.
>    
>     template <typename Iter, typename Func, typename... Iters>
>     for_each(std::tuple<Iter, Iters...> firsts, Iter last, Func f);

One could also embrace that necessity and use

template <typename Iter, typename Func, typename... Iters>
for_each(Iter first1, Iter last1, Func f, Iters .. firsts)

with the advantage that it covers the already present case with 0 Iters
as well. This also marks the trailing firsts as lesser than the initial
one so they are not to be expected to be used for range checking.

Note that this is equivalent to:
template <typename Iter, typename...Args>
typename First<Args...>::type for_each(Iter first1, Iter last1, Args...args);
Whether you decide now that f is the first or the last element of args... doesn't change much.

[Daniel Krügler]

2013/9/19 Zhihao Yuan <z...@miator.net>:

> The change in my mind (I roughly looked around in the standard
> and saw no places being affected) is to simply remove the 3rd
> bullet from 24.2.5/1:
>
> -- if X is a mutable iterator, reference is a reference to T; if X is
> a const iterator, reference is a reference to const T,

I'm pretty sure we shouldn't remove that requirement, because this
wording is really required to exist when we look at the standard as a
whole thing. My personal suggestion would be to introduce new
requirement sets that better separate traversal and access
requirements, such as ForwardTraversalIterator requirements.

> So that InputIterator requires decltype, ForwardIterator and
> follow ups require iterator_traits<X>::reference.

I don't understand this conclusion and I see no evidence for it. Note
that Table 106 already clarifies that the return type of the
expression "*r" is "reference" (in code font) and 24.2.1 p11 says that
this means "iterator_traits<X>::reference". And 24.4.1 p1 emphasizes
that iterator_traits<X>::reference has to be defined for input
iterators.

> But of course this breaks user code...

It would break user-code and the library.

- Daniel