Chapter 22
Bridging Static and Dynamic Polymorphism
Chapter 18 described the nature of static polymorphism (via templates) and dynamic polymorphism (via inheritance and virtual functions) in C++. Both kinds of polymorphism provide powerful abstractions for writing programs, yet each has tradeoffs: Static polymorphism provides the same performance as nonpolymorphic code, but the set of types that can be used at run time is fixed at compile time. On the other hand, dynamic polymorphism via inheritance allows a single version of the polymorphic function to work with types not known at the time it is compiled, but it is less flexible because types must inherit from the common base class.
This chapter describes how to bridge between static and dynamic polymorphism in C++, providing some of the benefits discussed in Section 18.3 on page 375 from each model: the smaller executable code size and (almost) entirely compiled nature of dynamic polymorphism, along with the interface flexibility of static polymorphism that allows, for example, built-in types to work seamlessly. As an example, we will build a simplified version of the standard library’s function<> template.
22.1 Function Objects, Pointers, and std::function<>
Function objects are useful for providing customizable behavior to templates. For example, the following function template enumerates integer values from 0 up to some value, providing each value to the given function object f:
bridge/forupto1.cpp
#include <vector>
#include <iostream>
template<typename F>
void forUpTo(int n, F f)
{
for (int i = 0; i != n; ++i)
{
f(i); // call passed function f for i
}
}
void printInt(int i)
{
std::cout << i << ’ ’;
}
int main()
{
std::vector<int> values;
// insert values from 0 to 4:
forUpTo(5,
[&values](int i) {
values.push_back(i);
});
// print elements:
forUpTo(5,
printInt); // prints 0 1 2 3 4
std::cout << ’
’;
}
The forUpTo() function template can be used with any function object, including a lambda, function pointer, or any class that either implements a suitable operator() or a conversion to a function pointer or reference, and each use of forUpTo() will likely produce a different instantiation of the function template. Our example function template is fairly small, but if the template were large, it is possible that these instantiations could increase code size.
One approach to limit this increase in code size is to turn the function template into a nontemplate, which needs no instantiation. For example, we might attempt to do this with a function pointer:
bridge/forupto2.hpp
void forUpTo(int n, void (*f)(int))
{
for (int i = 0; i != n; ++i)
{
f(i); // call passed function f for i
}
}
However, while this implementation will work when passed printInt(), it will produce an error when passed the lambda:
forUpTo(5,
printInt); //OK: prints 0 1 2 3 4
forUpTo(5,
[&values](int i) { //ERROR: lambda not convertible to a function pointer
values.push_back(i);
});
The standard library’s class template std::function<> permits an alternative formulation of forUpTo():
bridge/forupto3.hpp
#include <functional>
void forUpTo(int n, std::function<void(int)> f)
{
for (int i = 0; i != n; ++i)
{
f(i) // call passed function f for i
}
}
The template argument to std::function<> is a function type that describes the parameter types the function object will receive and the return type that it should produce, much like a function pointer describes the parameter and result types.
This formulation of forUpTo() provides some aspects of static polymorphism—the ability to work with an unbounded set of types including function pointers, lambdas, and arbitrary classes with a suitable operator()—while itself remaining a nontemplate function with a single implementation. It does so using a technique called type erasure, which bridges the gap between static and dynamic polymorphism.
22.2 Generalized Function Pointers
The std::function<> type is effectively a generalized form of a C++ function pointer, providing the same fundamental operations:
• It can be used to invoke a function without the caller knowing anything about the function itself.
• It can be copied, moved, and assigned.
• It can be initialized or assigned from another function (with a compatible signature).
• It has a “null” state that indicates when no function is bound to it.
However, unlike a C++ function pointer, a std::function<> can also store a lambda or any other function object with a suitable operator(), all of which may have different types.
In the remainder of this chapter, we will build our own generalized function pointer class template, FunctionPtr, to provide these same core operations and capabilities and that can be used in place of std::function:
bridge/forupto4.cpp
#include "functionptr.hpp"
#include <vector>
#include <iostream>
void forUpTo(int n, FunctionPtr<void(int)> f)
{
for (int i = 0; i != n; ++i)
{
f(i); // call passed function f for i
}
}
void printInt(int i)
{
std::cout << i << ’ ’;
}
int main()
{
std::vector<int> values;
// insert values from 0 to 4:
forUpTo(5,
[&values](int i) {
values.push_back(i);
});
// print elements:
forUpTo(5,
printInt); // prints 0 1 2 3 4
std::cout << ’
’;
}
The interface to FunctionPtr is fairly straightforward, providing construction, copy, move, destruction, initialization, and assignment from arbitrary function objects and invocation of the underlying function object. The most interesting part of the interface is how it is described entirely within a class template partial specialization, which serves to break the template argument (a function type) into its component pieces (result and argument types):
bridge/functionptr.hpp
// primary template:
template<typename Signature>
class FunctionPtr;
// partial specialization:
template<typename R, typename… Args>
class FunctionPtr<R(Args…)>
{
private:
FunctorBridge<R, Args…>* bridge;
public:
// constructors:
FunctionPtr() : bridge(nullptr) {
}
FunctionPtr(FunctionPtr const& other); // see functionptr-cpinv.hpp
FunctionPtr(FunctionPtr& other)
: FunctionPtr(static_cast<FunctionPtr const&>(other)) {
}
FunctionPtr(FunctionPtr&& other) : bridge(other.bridge) {
other.bridge = nullptr;
}
//construction from arbitrary function objects:
template<typename F> FunctionPtr(F&& f); // see functionptr-init.hpp
// assignment operators:
FunctionPtr& operator=(FunctionPtr const& other) {
FunctionPtr tmp(other);
swap(*this, tmp);
return *this;
}
FunctionPtr& operator=(FunctionPtr&& other) {
delete bridge;
bridge = other.bridge;
other.bridge = nullptr;
return *this;
}
//construction and assignment from arbitrary function objects:
template<typename F> FunctionPtr& operator=(F&& f) {
FunctionPtr tmp(std::forward<F>(f));
swap(*this, tmp);
return *this;
}
// destructor:
~FunctionPtr() {
delete bridge;
}
friend void swap(FunctionPtr& fp1, FunctionPtr& fp2) {
std::swap(fp1.bridge, fp2.bridge);
}
explicit operator bool() const {
return bridge == nullptr;
}
// invocation:
R operator()(Args… args) const; // see functionptr-cpinv.hpp
};
The implementation contains a single nonstatic member variable, bridge, which will be responsible for both storage and manipulation of the stored function object. Ownership of this pointer is tied to the FunctionPtr object, so most of the implementation provided merely manages this pointer. The unimplemented functions contain the interesting parts of the implementation and is described in the following subsections.
22.3 Bridge Interface
The FunctorBridge class template is responsible for the ownership and manipulation of the underlying function object. It is implemented as an abstract base class, forming the foundation for the dynamic polymorphism of FunctionPtr:
bridge/functorbridge.hpp
template<typename R, typename… Args>
class FunctorBridge
{
public:
virtual ~FunctorBridge() {
}
virtual FunctorBridge* clone() const = 0;
virtual R invoke(Args… args) const = 0;
};
FunctorBridge provides the essential operations needed to manipulate a stored function object through virtual functions: a destructor, a clone() operation to perform copies, and an invoke. operation to call the underlying function object. Don’t forget to define clone() and invoke() to be const member functions.1
Using these virtual functions, we can implement FunctionPtr’s copy constructor and function call operator:
bridge/functionptr-cpinv.hpp
template<typename R, typename… Args>
FunctionPtr<R(Args…)>::FunctionPtr(FunctionPtr const& other)
: bridge(nullptr)
{
if (other.bridge) {
bridge = other.bridge->clone();
}
}
template<typename R, typename… Args>
R FunctionPtr<R(Args…)>::operator()(Args… args) const
{
return bridge->invoke(std::forward<Args>(args)…);
}
22.4 Type Erasure
Each instance of FunctorBridge is an abstract class, so its derived classes are responsible for providing actual implementations of its virtual functions. To support the complete range of potential function objects—an unbounded set—we would need an unbounded number of derived classes. Fortunately, we can accomplish this by parameterizing the derived class on the type of the function object it stores:
bridge/specificfunctorbridge.hpp
template<typename Functor, typename R, typename… Args>
class SpecificFunctorBridge : public FunctorBridge<R, Args…> {
Functor functor;
public:
template<typename FunctorFwd>
SpecificFunctorBridge(FunctorFwd&& functor)
: functor(std::forward<FunctorFwd>(functor)) {
}
virtual SpecificFunctorBridge* clone() const override {
return new SpecificFunctorBridge(functor);
}
virtual R invoke(Args… args) const override {
return functor(std::forward<Args>(args)…);
}
};
Each instance of SpecificFunctorBridge stores a copy of the function object (whose type is Functor), which can be invoked, copied (by cloning the SpecificFunctorBridge), or destroyed (implicitly in the destructor). SpecificFunctorBridge instances are created whenever a FunctionPtr is initialized to a new function object, completing the FunctionPtr example:
bridge/functionptr-init.hpp
template<typename R, typename… Args>
template<typename F>
FunctionPtr<R(Args…)>::FunctionPtr(F&& f)
: bridge(nullptr)
{
using Functor = std::decay_t<F>;
using Bridge = SpecificFunctorBridge<Functor, R, Args…>;
bridge = new Bridge(std::forward<F>(f));
}
Note that while the FunctionPtr constructor itself is templated on the function object type F, that type is known only to the particular specialization of SpecificFunctorBridge (described by the Bridge type alias). Once the newly allocated Bridge instance is assigned to the data member bridge, the extra information about the specific type F is lost due to the derived-to-based conversion from Bridge * to FunctorBridge<R, Args…> *.2 This loss of type information explains why the term type erasure is often used to describe the technique of bridging between static and dynamic polymorphism.
One peculiarity of the implementation is the use of std::decay (see Section D.4 on page 731) to produce the Functor type, which makes the inferred type F suitable for storage, for example, by turning references to function types into function pointer types and removing top-level const, volatile, and reference types.
22.5 Optional Bridging
Our FunctionPtr template is nearly a drop-in replacement for a function pointer. However, it does not yet support one operation provided by function pointers: testing whether two FunctionPtr objects will invoke the same function. Adding such an operation requires updating the FunctorBridge with an equals operation:
virtual bool equals(FunctorBridge const* fb) const = 0;
along with an implementation within SpecificFunctorBridge that compares the stored function objects when they have the same type:
virtual bool equals(FunctorBridge<R, Args…> const* fb) const override {
if (auto specFb = dynamic_cast<SpecificFunctorBridge const*>(fb)) {
return functor == specFb->functor;
}
//functors with different types are never equal:
return false;
}
Finally, we implement operator== for FunctionPtr, which first checks for null functors and then delegates to FunctorBridge:
friend bool
operator==(FunctionPtr const& f1, FunctionPtr const& f2) {
if (!f1 || !f2) {
return !f1 && !f2;
}
return f1.bridge->equals(f2.bridge);
}
friend bool
operator!=(FunctionPtr const& f1, FunctionPtr const& f2) {
return !(f1 == f2);
}
This implementation is correct. However, it has an unfortunate drawback: If the FunctionPtr is assigned or initialized with a function object that does not have a suitable operator== (which includes lambdas, for example), the program will fail to compile. This may come as a surprise, because FunctionPtrs operator== hasn’t even been used yet, and many other class templates— such as std::vector—can be instantiated with types that don’t have an operator== so long as their own operator== is not used.
This problem with operator== is due to type erasure: Because we are effectively losing the type of the function object once the FunctionPtr has been assigned or initialized, we need to capture all of the information we need to know about the type before that assignment or initialization is complete. This information includes forming a call to the function object’s operator==, because we can’t be sure when it will be needed.3
Fortunately, we can use SFINAE-based traits (discussed in Section 19.4 on page 416) to query whether operator== is available before calling it, with a fairly elaborate trait:
bridge/isequalitycomparable.hpp
#include <utility> // for declval()
#include <type_traits> // for true_type and false_type
template<typename T>
class IsEqualityComparable
{
private:
// test convertibility of == and ! == to bool:
static void* conv(bool); // to check convertibility to bool
template<typename U>
static std::true_type test(decltype(conv(std::declval<U const&>() ==
std::declval<U const&>())),
decltype(conv(!(std::declval<U const&>() ==
std::declval<U const&>())))
);
// fallback:
template<typename U>
static std::false_type test(…);
public:
static constexpr bool value = decltype(test<T>(nullptr,
nullptr))::value;
};
The IsEqualityComparable trait applies the typical form for expression-testing traits as introduced in Section 19.4.1 on page 416: two test() overloads, one of which contains the expressions to test wrapped in decltype, and the other that accepts arbitrary arguments via an ellipsis. The first test() function attempts to compare two objects of type T const using == and then ensures that the result can be both implicitly converted to bool (for the first parameter) and passed to the logical negation operator operator!) with a result convertible to bool. If both operations are well formed, the parameter types themselves will both be void*.
Using the IsEqualityComparable trait, we can construct a TryEquals class template that can either invoke == on the given type (when it’s available) or throw an exception if no suitable == exists:
#include <exception>
#include "isequalitycomparable.hpp"
template<typename T,
bool EqComparable = IsEqualityComparable<T>::value>
struct TryEquals
{
static bool equals(T const& x1, T const& x2) {
return x1 == x2;
}
};
class NotEqualityComparable : public std::exception
{
};
template<typename T>
struct TryEquals<T, false>
{
static bool equals(T const& x1, T const& x2) {
throw NotEqualityComparable();
}
};
Finally, by using TryEquals within our implementation of SpecificFunctorBridge, we are able to provide support for == within FunctionPtr whenever the stored function object types match and the function object supports ==:
virtual bool equals(FunctorBridge<R, Args…> const* fb) const override {
if (auto specFb = dynamic_cast<SpecificFunctorBridge const*>(fb)) {
return TryEquals<Functor>::equals(functor, specFb->functor);
}
//functors with different types are never equal:
return false;
}
22.6 Performance Considerations
Type erasure provides some of the advantages of both static polymorphism and dynamic polymorphism, but not all. In particular, the performance of generated code using type erasure hews more closely to that of dynamic polymorphism, because both use dynamic dispatch via virtual functions. Thus, some of the traditional advantages of static polymorphism, such as the ability of the compiler to inline calls, may be lost. Whether this loss of performance will be perceptible is application-dependent, but it’s often easy to tell by considering how much work is performed in the function being called relative to the cost of a virtual function call: If the two are close (e.g., using FunctionPtr to simply add two integers), type erasure is likely to execute far more slowly than a static-polymorphic version. If, on the other hand, the function call performs a significant amount of work—querying a database, sorting a container, or updating a user interface—the overhead of type erasure is unlikely to be measurable.
22.7 Afternotes
Kevlin Henney popularized type erasure in C++ with the introduction of the any type [HenneyValued-Conversions], which later became a popular Boost library [BoostAny] and part of the C++ standard library with C++17. The technique was refined somewhat in the Boost.Function library [Boost-Function], which applied various performance and code-size optimizations and eventually became std::function<>. However, each of the early libraries addressed only a single set of operations: any was a simple value type with only a copy and a cast operation; function added invocation to that.
Later efforts, such as the Boost.TypeErasure library [BoostTypeErasure] and Adobe’s Poly library [AdobePoly], apply template metaprogramming techniques to allow users to form a type-erased value with some specified list of capabilities. For example, the following type (constructed using the Boost.TypeErasure library) handles copy construction, a typeid-like operation, and output streaming for printing:
using AnyPrintable = any<mpl::vector<copy_constructible<>,
typeid_<>,
ostreamable<>
>>;
1 Making invoke() const is a safety belt against invoking non-const operator() overloads through const
FunctionPtr objects, which would violate the expectations of programmers.
2 Although the type could be queried with dynamic_cast (among other things), the FunctionPtr class makes the bridge pointer private, so clients of FunctionPtr have no access to the type itself.
3 Mechanically, the code for the call to operator== is instantiated because all of the virtual functions of a class template (in this case, SpecificFunctorBridge) are typically instantiated when the class template itself is instantiated.