Passing function objects into std algorithms by reference

Question

Isn't it better to pass function objects into the STL algorithms by forwarding reference rather then by value? It would allow one to utilize ref-qualifiers of operator () of function objects passed.

There are a couple of questions about std::for_each algorithm on SO (1, 2), which are considering a problem with changing of observable state of function object passed to std::for_each.

Passing functional objects by lvalue leference would solve the problem as a side effect even for those of algorithms, which can't return functional object (due to they should return, say, output iterator last value or something else).

For example the algorithm std::for_each can be changed from (copied from libc++):

template<typename _InputIterator, typename _Function>
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
  for (; __first != __last; ++__first)
    __f(*__first);
  return _GLIBCXX_MOVE(__f);
}

to:

template<typename _InputIterator, typename _Function>
_Function &&
for_each(_InputIterator __first, _InputIterator __last, _Function && __f)
{
  for (; __first != __last; ++__first)
    _GLIBCXX_FORWARD(_Function, __f)(*__first);
  return _GLIBCXX_FORWARD(_Function, __f);
}

or (if such breaking changing is allowed) std::for_each can return void without loss of functionality. Similar changes (change from passing by value to passing by forwarding reference and change all invocations to calling std::forwarded function object instead of just non-const-lvalue) are possible for all the rest <numeric>'s and <algorithm>'s algorithms.

I know a partial workaround: is to pass object, wrapped by std::ref (or std::cref to enforce const this), but there are issues with forwarding operator () cv-ref-qualifiers from wrapped functional object to wrapper's operator ().

Another workaround is to explicitly specify reference argument type into alorithm's template parameter list, but currently Function parameter sadly always follows the InputIterator and OutputIterator parameters in the list:

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
#include <utility>

#include <cstdlib>

int main()
{
    std::list< int > l{{1, 2, 3, 4}};
    std::copy_n(std::cbegin(l), l.size(), std::ostream_iterator< int >(std::cout, " "));
    std::cout << std::endl;
    struct F
    {
        int state;
        void operator () (int i) { state += i; }
    } f{0};
    using I = std::list< int >::const_iterator;
    std::for_each< I, F && >(std::cbegin(l), std::cend(l), std::move(f));
    std::cout << f.state << std::endl;
    return EXIT_SUCCESS;
}

By the way the change would allow to pass a non-copyable and/or non-moveable function objects to the algorithms w/o wrapping them.

Answer 1

Isn't it better to pass function objects into the STL algorithms by forwarding reference rather then by value?

Yes, it would be better. And it would be better if there were a requirement that the functor need not be CopyConstructible, CopyAssignable, MoveConstructible or MoveAssignable. However the standard specifically says in 25.1:

Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely. Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as reference_wrapper<T> (20.9.4), or some equivalent solution. — end note]

This issue was considered all the way back in 1998 as LWG 92. And at that time the Note I quote above was added (the Note has since been modified as reference_wrapper<T> didn't exist at the time).

This was a good resolution for vendors of the std::lib, and a good resolution for members of the committee who had the job of fixing the specification, but not so much for people such as yourself wanting to use stateful functors.

And of course, at that time, forwarding references weren't available as a possible solution. Also at that time, it was common for std::implementations to pass the functor around by value within an algorithm, which would further destroy its state (as demonstrated in the description of LWG 92.

You have correctly touched upon all of the points connected to this issue:

• Clients can use std::ref instead, but this won't respect reference-qualified functors.

• Clients can explicitly specify functor reference parameters, but this won't prohibit implementations from copying the functor within the algorithm.

• Explicitly specifying functor reference parameters is extremely inconvenient for the client since they are always ordered last in the template parameter list.

Fwiw, libc++ is the only std::implementation that was written which forbade itself from internally copying functors. I.e. if you code up the LWG 92 example:

#include <algorithm>
#include <iostream>
#include <list>
#include <numeric>

template <class C>
void
display(const C& c)
{
    std::cout << '{';
    if (!c.empty())
    {
        auto i = c.begin();
        std::cout << *i;
        for (++i; i != c.end(); ++i)
            std::cout << ", " << *i;
    }
    std::cout << '}' << '\n';
}

class Nth {    // function object that returns true for the nth element 
  private: 
    int nth;     // element to return true for 
    int count;   // element counter 
  public: 
    Nth (int n) : nth(n), count(0) { 
    } 
    bool operator() (int) { 
        return ++count == nth; 
    } 
};

int
main()
{
    std::list<int> coll(10);
    std::iota(coll.begin(), coll.end(), 0);
    display(coll);
    auto pos = std::remove_if(coll.begin(), coll.end(), Nth{3});
    coll.erase(pos, coll.end());
    display(coll);
}

The results today are:

libc++

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{0, 1, 3, 4, 5, 6, 7, 8, 9}

g++

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{0, 1, 3, 4, 6, 7, 8, 9}

VS-2015

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{0, 1, 3, 4, 6, 7, 8, 9}

g++'s libstdc++ and VS-2015 are still copying Nth internal to remove_if just as described 18 years ago by Nico Josuttis.

Changing the code to:

    Nth pred{3};
    auto pos = std::remove_if(coll.begin(), coll.end(), std::ref(pred));

does portably change the results to:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{0, 1, 3, 4, 5, 6, 7, 8, 9}

Imho, this is just a run-time error waiting to happen to programmers not familiar with the long history of the std::lib.