Write a custom virtual table in C++
Consider the following scenario, a class hierarchy that provides sorting functions and a factory (yes, it’s a simplified example):
#include <span>
struct ISorter{
virtual void sort(std::span<double>) const = 0;
virtual ~ISorter() = default;
};
struct HeapSorter : ISorter {
void sort(std::span<double>) const override;
};
struct MergeSorter : ISorter {
void sort(std::span<double>) const override;
};
const ISorter& getSorter(int id){
switch(id){
case 0: {static HeapSorter s; return s;}
case 1: {static MergeSorter s; return s;}
// ...
}
}Usage would be
void bar(std::vector<double>& vd){
getSorter(42).sort(vd);
const auto& s = getSorter(42);
s.sort(vd);
}While the code works, some might rightfully argue that relying on globals is not ideal.
While this factory even works when using multiple shared libraries, having a global variable can be problematic. Is it thread-safe? How many resources does it use for the whole lifetime of the application?
Most people I’ve spoken to proposed two alternate solutions for changing the current implementation.
The first is to keep the class hierarchy, and use std::unique_ptr:
std::unique_ptr<ISorter> getSorter(int id){
switch(id){
case 0: return std::make_unique<HeapSorter>();
case 1: return std::make_unique<MergeSorter>();
// ...
}
}The usage is mostly unchanged (depending on if getSorter returned a pointer or a reference)
void bar(std::vector<double>& vd){
getSorter(42)->sort(vd);
const auto s = getSorter(42);
s->sort(vd);
}The main disadvantage is that every call to getSorter will allocate memory. But at least the is no more a single instance shared anymore between all users of the factory.
The second proposed approach, for avoiding any allocation, and eventually removing the class hierarchy, is to use std::variant:
std::variant<HeapSorter, MergeSorter, ...> getSorter(int id);Unfortunately std::variant is not as practical to use in this case, a helper can remove most boilerplate, but it still feels like it leads to unnecessary code duplication:
struct visitor {
std::span<double> sd;
void operator()(const HeapSorter& s) {
s.sort(sd);
}
void operator()(const MergeSorter& b) {
s.sort(sd);
}
};
void bar(std::vector<double>& vd){
std::visit(visitor{vd}, getSorter(42));
const auto s = getSorter(42);
std::visit(visitor{vd}, s);
}Alternate approach
As, in this case, all subclasses accessible through getSorter are stateless there is a much simpler approach that does not require class hierarchies or templates: function pointers!
#include <span>
typedef void sorter( std::span<double> sd );
// actual implementations as free functions
void heapsort( std::span<double> sd );
void mergesort( std::span<double> sd );
void shellsort( std::span<double> sd );
void bubblesort( std::span<double> sd );
sorter* getSorter(int id){
switch(id){
case 0: return heapsort;
case 1: return mergesort;
// ...
}
}The usage is simple, even if requires a little change, as there is no sort member function to call anymore (but read further, this change can be avoided!):
void bar(std::vector<double>& vd){
getSorter(42)(vd);
const auto s = getSorter(42);
s(vd);
}But what if the implementation of getSorter returns nullptr? With the class hierarchy, this state was not possible, as we got a reference and not a pointer.
We can avoid it by returning a function reference!
sorter& getSorter(int id){
switch(id){
case 0: return heapsort;
case 1: return mergesort;
// ...
}
}It works the same as a function pointer (in fact it decays to a function pointer very quickly, similar to arrays):
void bar(std::vector<double>& vd){
getSorter(42)(vd);
const auto s = getSorter(42);
s(vd);
}Using a function pointer (or reference) is as easy to use as the class hierarchy, and does not depend on some lazily initialized global state, which might require synchronization between threads.
It also does not need some template machinery or an additional dispatch mechanism. Note that the std::variant approach also has the disadvantage that it requires changing the return type if we are going to add or remove some sorters.
Classes with multiple member functions
Note that the shown use-case does not rely on the fact that the class hierarchy has a single public member function, but on the fact that the implementation was stateless.
Multiple (stateless) member functions are not an issue they can show how to customize the API instead of returning a pointer/reference to a function.
Consider following class hierarchy, which provides overloaded sorting functions specialized for some data types.
struct ISorter{
virtual void sort(std::span<double>) const = 0;
virtual void sort(std::span<int>) const = 0;
virtual ~ISorter() = default;
};In this case, it is not possible to use a function pointer, but it is possible to create a structure of function pointers:
struct sorter{
typedef void double_sorter( std::span<double> sd );
typedef void int_sorter( std::span<int> si );
double_sorter* sort_doubles;
int_sorter* sort_ints;
};
// actual implementations as free functions
void heapsort( std::span<double> sd );
void mergesort( std::span<double> sd );
void heapsort( std::span<int> si );
void mergesort( std::span<int> si );
// ...
sorter getSorter(int id){
switch(id){
case 0: return {heapsort, heapsort};
case 1: return {mergesort, mergesort};
// ...
}
}
// usage
void bar(std::vector<double>& vd){
getSorter(42).sort_doubles(vd);
const auto s = getSorter(42);
s.sort_doubles(vd);
}There are three interesting observations to make:
The first is that we return struct sorter by value, not by pointer or reference.
struct sorter is equivalent to a class hierarchy with a handwritten vtable, but it has value semantic.
Even using memcpy to copy one struct sorter to another is a valid and well-defined operation. This might help to optimize some operations, the first that comes to mind is std::vector::resize, even if for most use-cases it will not be relevant. Also, note that the implementation uses function pointers instead of references, otherwise struct sorter will not be assigneable anymore, because references cannot be reassigned.
The second thing is that function overloads are not an issue when assigning functions to the member variables of struct sorter. If an overload is missing, the compiler will complain.
The third thing to notice is how struct sorter can be used; we need to access the member variable, and contrary to ISorter, it is not possible to provide overloads, as there is no such thing as "overloaded member variables", which makes using struct sorter less user-friendly.
A better interface
Fortunately the interface of struct sorter can be improved by adding operator() to sorter:
struct sorter{
void operator()(std::span<double> sd) const {
sort_doubles(sd);
}
void operator()(std::span<int> si) const {
sort_ints(si);
}
private:
typedef void double_sorter( std::span<double> sd );
typedef void int_sorter( std::span<int> si );
double_sorter* sort_doubles;
int_sorter* sort_ints;
public:
sorter(double_sorter*, int_sorter*);
};
void bar(std::vector<double>& vd){
getSorter(42)(vd);
const auto s = getSorter(42);
s(vd);
}With operator() we have provided an equivalent interface of a function pointer with overloads for different types.
Verifying pre and post-conditions
Actually, hiding the function pointer behind operator() (or another member function) is a good technique for restricting interfaces and validate our code.
For example, an obvious post-condition of a sorting function is that the data is sorted.
Contracts 🗄️ are not there yet in the language (maybe in C++26?), and it is also not obvious how they should work with virtual functions and function pointers.
By creating a facade for accessing virtual functions and function pointers, it is trivial to validate postconditions:
struct sorter{
void operator()(std::span<double> sd) const {
sort_doubles(sd);
assert(std::is_sorted(sd.begin(), sd.end()));
}
void operator()(std::span<int> si) const {
sort_ints(si);
assert(std::is_sorted(si.begin(), si.end()));
}
private:
typedef void double_sorter( std::span<double> sd );
typedef void int_sorter( std::span<int> si );
double_sorter* sort_doubles;
int_sorter* sort_ints;
public:
sorter(double_sorter*, int_sorter*);
};Similarly, we can test for preconditions.
For example, when sorting double, a sensible precondition would be that there aren’t any nan values (inf is generally not an issue, and -0 needs special care as -0 < 0 is false, so it might make sense to either ignore it or put its absence as a precondition):
struct sorter{
void operator()(std::span<double> sd) const {
assert(std::none_of(sd.begin(), sd.end(), [](double d){ return std::isnan(d); }));
sort_doubles(sd);
assert(std::is_sorted(sd.begin(), sd.end()));
}
void operator()(std::span<int> si) const {
sort_ints(si);
assert(std::is_sorted(si.begin(), si.end()));
}
private:
typedef void double_sorter( std::span<double> sd );
typedef void int_sorter( std::span<int> si );
double_sorter* sort_doubles;
int_sorter* sort_ints;
};As long as all implementations are private and accessible only through sorter/getSorter, the pre and post-conditions for all sorting algorithms can be implemented only once.
What about stateful class hierarchies?
If the state is the same (or mostly the same) shared between all subclasses, then it can be added easily to the structure and passed by reference to the free functions. Notice that in this case, depending on the state, the structure might not be trivial to copy anymore. It might not be copyable at all.
If the state heavily changes between subclasses, using a common structure provides fewer advantages.
For example, consider the following struct IDevice
struct IDevice {
void write(std::span<const unsigned char> sd) = 0;
void flush() = 0;
int available_for_read() = 0;
void read(std::span<unsigned char> sd) = 0;
// ...
};
struct RamDevice : IDevice {
void write(std::span<const unsigned char> sd) override;
void flush() override;
// ...
};
struct DiskDevice : IDevice {
void write(std::span<const unsigned char> sd) override;
void flush() override;
// ...
};RamDevice needs to store the data somewhere, it might have a std::vector<unsigned char> member variable.
DiskDevice does not need this member variable, but since writing and reading from the disk is generally a slow operation, it might make sense to have a std::vector<unsigned char> buffer.
On the contrary RamDevice does not need a handle to a file, while DiskDevice does.
Even with stateful data, in this case, one might consider not using a class hierarchy, as most of the internal state is shared (only FILE* would be unused by RamDevice).
struct device {
std::vector<unsigned char> buffer;
FILE* f;
typedef void write_fun_(std::span<const unsigned char> sd, std::vector<unsigned char>& buffer, FILE* file);
write_fun_* write_fun;
void write(std::span<const unsigned char> sd){
write_fun(sd, buffer, f);
}
typedef void flush_fun_(std::vector<unsigned char>& buffer, FILE* file);
flush_fun_* flush_fun;
void flush(){
flush_fun(buffer, f);
}
// and so on
};The obvious disadvantage is that all implementations (thus every flush and write function) need to take a buffer and a file handle, even if for some of those the file handle is an unused parameter.
Also note that both IDevice and device are not a very good example, because most systems already provide an equivalent abstraction.
FILE* is already an opaque type, and it does not necessarily store the content only on disk. In fact, through fmemopen and open_memstream on POSIX systems, it is possible to read and write to a memory buffer. On GNU/Linux systems it is also possible, thanks to fopencookie to create custom `FILE`s.
On Windows, with CreateFile and the flags FILE_ATTRIBUTE_TEMPORARY | FILE_FLAG_DELETE_ON_CLOSE archived, the file, unless there is not enough memory will not be written on the disk. It is possible to convert a HANDLE to FILE* through _open_osfhandle and _fdopen.
For other systems, there might be some other functions available. Unfortunately, the C standard only specifies fopen. At least in C++, when using the stream API, it is possible to create a subclass with the desired behavior.
Performance considerations
I did not make any performance considerations.
The main use-case I’m advocating to use a handwritten virtual table is to avoid a class hierarchy, as it leads to simpler code, and it might help to state more explicitly some invariants.
Function pointers and virtual functions are roughly equivalent, on a case-by-case basis the compiler might or might not be able to determine which function to call directly and eventually even inline the function call.
Some simple test shows that avoiding the class hierarchy helps to reduce the amount of generated code, but it does not mean that the resulting binary is measurably faster. The main reason might be those compiler-generated vtables not only handle (multiple) virtual inheritance but also dynamic casting and the typeid operator.
If static operator() 🗄️ gets accepted, it would help to make the stateless case even more efficient (again: difference might not be measurable).
What about interactions between multiple member functions?
Depending on the implementation, I would probably recommend using the class hierarchy, unless a bigger refactor is fine.
To keep the code as simple as possible, no member function should call public or protected member functions. If this is not the expected behavior, changing the class hierarchy to a handwritten virtual table is generally a lot of work/refactoring.
Aren’t hand-crafted virtual tables only relevant for C programs
They are surely relevant for C programs because this is how class hierarchies are mimicked.
Contrary to C programs, we can hide the hand-crafted virtual table by making it private and providing a nice interface through normal member functions or operator().
Disadvantages
First, they are less flexible than a class hierarchy with virtual functions. A subclass can have completely different member variables from another subclass, and there is no way one can access the member variables of another leaf of the class hierarchy. With a custom polymorphic structure, everything is shared, and constructs like std::variant or reinterpret_casts can help for holding different types of variables, but for bigger classes, the code will be generally harder to maintain compared to a class hierarchy.
Another evident disadvantage is code duplication. To provide an equivalent interface I needed to create
-
a
typedeffor the function pointer -
a member variable where to store the function
-
a wrapper function for providing a better interface and for supporting overloads
and find meaningful names for those three entities that are conceptual the same thing.
The typedef is not strictly necessary, but it helps to make the code more readable:
struct sorter1{
void operator()(std::span<double> sd) const {
sort_doubles(sd);
}
void operator()(std::span<int> si) const {
sort_ints(si);
}
private:
typedef void double_sorter( std::span<double> sd );
typedef void int_sorter( std::span<int> si );
double_sorter* sort_doubles;
int_sorter* sort_ints;
};
// vs
struct sorter2{
void operator()(std::span<double> sd) const {
sort_doubles(sd);
}
void operator()(std::span<int> si) const {
sort_ints(si);
}
private:
void (*sort_doubles)( std::span<double> sd );
void (*sort_ints)( std::span<int> si );
};Unfortunately, I do not see how to remove the duplication of the member variable and member function, even with macros, while trying to keep the code readable.
Advantages
If one uses the limitations of this approach to design interfaces, it helps to avoid that objects can become stateful by accident (unless relying on some global state).
This means that struct sorter; is by design stateless, while for ISorter it is very easy to become stateful by accident, just by adding a member variable.
Once it is ensured that the implementations are required to be stateless (or re-use a better-defined state), it makes it possible to avoid dynamic allocations and keep a simple interface for the user. It also avoids the machinery of std::variant with std::visit or alternate approaches with a union.
struct sorter, if desired, has value semantic, and is easy to use in a constexpr context too.
There are also no virtual destructors, and no need to remember to write override for catching errors; function signature mismatches are a compilation error without further annotations.
Do you want to share your opinion? Or is there an error, some parts that are not clear enough?
You can contact me anytime.