How to Pass a Polymorphic Object to an STL Algorithm

Published April 17, 2018 - 3 Comments

As we can read in the opening chapter of Effective C++, C++ is a federation of 4 languages:

the procedural part coming from C,
the object-oriented part,
the STL part (following a functional programming paradigm),
the generic part with templates.

And what’s more, all of those 4 sub-languages are part of one whole: the C++ language. Those 4 paradigms begin united in one language gives opportunities for them to interact – and often, those interactions create interesting situations.

Today we’re focusing on one particular interaction, between the object-oriented model and the STL. There could be multiple forms for this interaction, and the case we will look at is how to pass a polymorphic (that is, having virtual methods) function object to an STL algorithm.

This is a case that was presented to me and whose resolution I’d like to share with you. As you’ll see, those two worlds don’t integrate seamlessly with each other, but we can make a bridge between them without too much effort.

polymorphic object stl C++

Polymorphic function objects?

By function object, I mean an object that has an operator(). That can be a lambda or a functor.

And polymorphic can mean many things in practice, but in this context I’m referring to runtime polymorphism with virtual methods.

So our polymorphic function object can look like this:

struct Base
{
    int operator()(int) const
    {
        method();
        return 42;
    }
    virtual void method() const { std::cout << "Base class called.\n"; }
};

In fact, this is a totally debilitated function object that does nothing meaningful, but that will be useful for us to focus our attention on the effect of passing it to an STL algorithm. The original case had a richer domain, but it is not the point here.

Anyway, such polymorphic objects are designed to be inherited from. Here is a Derived class that overrides the virtual method:

struct Derived : public Base
{
    void method() const override { std::cout << "Derived class called.\n"; }
};

Let’s now use a Derived object to invoke an algorithm:

void f(Base const& base)
{
    std::vector<int> v = {1, 2, 3};
    std::transform(begin(v), end(v), begin(v), base);
}

int main()
{    
    Derived d;
    f(d);
}

What do you think this code outputs?

Unveil the output below to check if you were correct:

Base class called.
Base class called.
Base class called.

Isn’t it surprising? We passed a Derived object to the algorithm, but the algorithm doesn’t call the overriden virtual function! To understand what happened, let’s have a look at the prototype of the std::transform algorithm:

template< typename InputIterator, typename OutputIterator, typename Function>
OutputIt transform(InputIterator first, InputIterator last, OutputIterator out, Function f);

Look closely at the last parameter (the function) and notice that it is passed by value.

But as explain in Item 20 of Effective C++, polymorphic objects get sliced off when we pass them by value: even if the Base const& reference base was referring to a Derived object, making a copy of base creates a Base object, and not a Derived object.

So we need a way to make the algorithm use a reference to the polymorphic object, and not a copy.

How do we do that?

Wrapping into another function object

This is probably the idea that comes to mind first: a computer science problem? Let’s create an indirection!

If our object must be passed by reference, and the algorithm only accept copies, we can create an intermediary object that holds a reference to the polymorphic object, and that can be itself passed by copy.

The simplest way to implement this intermediary function object is with a lambda, that takes base by reference:

std::transform(begin(v), end(v), begin(v), [&base](int n){ return base(n); }

The code now outputs:

Derived class called.
Derived class called.
Derived class called.

It works, but has the drawback of burdening the code with a lambda existing for technical purposes only.

In the above example the lambda is pretty short, but it could become cumbersome in more production-like code:

std::transform(begin(v), end(v), begin(v), [&base](module::domain::component myObject){ return base(myObject); }

That is a mouthful of code that adds no functional meaning to the codeline.

A compact solution: using `std::ref`

There is another way around the problem of passing the polymorphic object by value, and it consists in using std::ref:

std::transform(begin(v), end(v), begin(v), std::ref(base));

It has the same effect as the lambda. Indeed, the code still outputs:

Derived class called.
Derived class called.
Derived class called.

Now there is a possibility that reading this made you go like this:

C++ polymorphic STL algorithm

It certainly did to me.

How on earth could this code compile in the first place? std::ref returns a std::reference_wrapper, which is no more than an object modelling a reference (except that you can reassign it to refer to anther object with its operator=).

How could it play the role of a function object?

I dug into the documentation of std::reference_wrapper on cppreference.com and found this:

std::reference_wrapper::operator()

Calls the Callable object, reference to which is stored. This function is available only if the stored reference points to a Callable object.

So this is a specific featured baked in std::reference_wrapper: when std::ref takes a function object F, the returned object is also a function object that takes a reference to F and offers an operator() that calls F. Exactly what we needed here.

And you will notice that however big or nested in namespaces the type of polymorphic type is, what we pass to the algorithms remains std::ref(base).

A better solution?

It seems that the solution using std::ref supersedes the one using a lambda because it does the same thing but with less code.

Now there may be other solutions to this problem, and even better ones. If you see another way to go about that, I’ll be delighted to read about it in the comments sections just below!