Polymorphism in C++
Solution 1:
Understanding of / requirements for polymorphism
To understand polymorphism - as the term is used in Computing Science - it helps to start from a simple test for and definition of it. Consider:
Type1 x;
Type2 y;
f(x);
f(y);
Here, f()
is to perform some operation and is being given values x
and y
as inputs.
To exhibit polymorphism,
f()
must be able to operate with values of at least two distinct types (e.g.int
anddouble
), finding and executing distinct type-appropriate code.
C++ mechanisms for polymorphism
Explicit programmer-specified polymorphism
You can write f()
such that it can operate on multiple types in any of the following ways:
-
Preprocessing:
#define f(X) ((X) += 2) // (note: in real code, use a longer uppercase name for a macro!)
-
Overloading:
void f(int& x) { x += 2; } void f(double& x) { x += 2; }
-
Templates:
template <typename T> void f(T& x) { x += 2; }
-
Virtual dispatch:
struct Base { virtual Base& operator+=(int) = 0; }; struct X : Base { X(int n) : n_(n) { } X& operator+=(int n) { n_ += n; return *this; } int n_; }; struct Y : Base { Y(double n) : n_(n) { } Y& operator+=(int n) { n_ += n; return *this; } double n_; }; void f(Base& x) { x += 2; } // run-time polymorphic dispatch
Other related mechanisms
Compiler-provided polymorphism for builtin types, Standard conversions, and casting/coercion are discussed later for completeness as:
- they're commonly intuitively understood anyway (warranting a "oh, that" reaction),
- they impact the threshold in requiring, and seamlessness in using, the above mechanisms, and
- explanation is a fiddly distraction from more important concepts.
Terminology
Further categorisation
Given the polymorphic mechanisms above, we can categorise them in various ways:
-
When is the polymorphic type-specific code selected?
- Run time means the compiler must generate code for all the types the program might handle while running, and at run-time the correct code is selected (virtual dispatch)
-
Compile time means the choice of type-specific code is made during compilation. A consequence of this: say a program only called
f
above withint
arguments - depending on the polymorphic mechanism used and inlining choices the compiler might avoid generating any code forf(double)
, or generated code might be thrown away at some point in compilation or linking. (all mechanisms above except virtual dispatch)
-
Which types are supported?
- Ad-hoc meaning you provide explicit code to support each type (e.g. overloading, template specialisation); you explicitly add support "for this" (as per ad hoc's meaning) type, some other "this", and maybe "that" too ;-).
-
Parametric meaning you can just try to use the function for various parameter types without specifically doing anything to enable its support for them (e.g. templates, macros). An object with functions/operators that act like the template/macro expects1is all that template/macro needs to do its job, with the exact type being irrelevant. The "concepts" introduced by C++20 express and enforce such expectations - see cppreference page here.
-
Parametric polymorphism provides duck typing - a concept attributed to James Whitcomb Riley who apparently said "When I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck.".
template <typename Duck> void do_ducky_stuff(const Duck& x) { x.walk().swim().quack(); } do_ducky_stuff(Vilified_Cygnet());
-
Subtype (aka inclusion) polymorphism allows you to work on new types without updating the algorithm/function, but they must be derived from the same base class (virtual dispatch)
1 - Templates are extremely flexible. SFINAE (see also std::enable_if
) effectively allows several sets of expectations for parametric polymorphism. For example, you might encode that when the type of data you're processing has a .size()
member you'll use one function, otherwise another function that doesn't need .size()
(but presumably suffers in some way - e.g. using the slower strlen()
or not printing as useful a message in the log). You can also specify ad-hoc behaviours when the template is instantiated with specific parameters, either leaving some parameters parametric (partial template specialisation) or not (full specialisation).
"Polymorphic"
Alf Steinbach comments that in the C++ Standard polymorphic only refers to run-time polymorphism using virtual dispatch. General Comp. Sci. meaning is more inclusive, as per C++ creator Bjarne Stroustrup's glossary (http://www.stroustrup.com/glossary.html):
polymorphism - providing a single interface to entities of different types. Virtual functions provide dynamic (run-time) polymorphism through an interface provided by a base class. Overloaded functions and templates provide static (compile-time) polymorphism. TC++PL 12.2.6, 13.6.1, D&E 2.9.
This answer - like the question - relates C++ features to the Comp. Sci. terminology.
Discussion
With the C++ Standard using a narrower definition of "polymorphism" than the Comp. Sci. community, to ensure mutual understanding for your audience consider...
- using unambiguous terminology ("can we make this code reusable for other types?" or "can we use virtual dispatch?" rather than "can we make this code polymorphic?"), and/or
- clearly defining your terminology.
Still, what's crucial to being a great C++ programmer is understanding what polymorphism's really doing for you...
letting you write "algorithmic" code once and then apply it to many types of data
...and then be very aware of how different polymorphic mechanisms match your actual needs.
Run-time polymorphism suits:
- input processed by factory methods and spat out as an heterogeneous object collection handled via
Base*
s, - implementation chosen at runtime based on config files, command line switches, UI settings etc.,
- implementation varied at runtime, such as for a state machine pattern.
When there's not a clear driver for run-time polymorphism, compile-time options are often preferable. Consider:
- the compile-what's-called aspect of templated classes is preferable to fat interfaces failing at runtime
- SFINAE
- CRTP
- optimisations (many including inlining and dead code elimination, loop unrolling, static stack-based arrays vs heap)
-
__FILE__
,__LINE__
, string literal concatenation and other unique capabilities of macros (which remain evil ;-)) - templates and macros test semantic usage is supported, but don't artificially restrict how that support is provided (as virtual dispatch tends to by requiring exactly matching member function overrides)
Other mechanisms supporting polymorphism
As promised, for completeness several peripheral topics are covered:
- compiler-provided overloads
- conversions
- casts/coercion
This answer concludes with a discussion of how the above combine to empower and simplify polymorphic code - especially parametric polymorphism (templates and macros).
Mechanisms for mapping to type-specific operations
> Implicit compiler-provided overloads
Conceptually, the compiler overloads many operators for builtin types. It's not conceptually different from user-specified overloading, but is listed as it's easily overlooked. For example, you can add to int
s and double
s using the same notation x += 2
and the compiler produces:
- type-specific CPU instructions
- a result of the same type.
Overloading then seamlessly extends to user-defined types:
std::string x;
int y = 0;
x += 'c';
y += 'c';
Compiler-provided overloads for basic types is common in high-level (3GL+) computer languages, and explicit discussion of polymorphism generally implies something more. (2GLs - assembly languages - often require the programmer to explicitly use different mnemonics for different types.)
> Standard conversions
The C++ Standard's fourth section describes Standard conversions.
The first point summarises nicely (from an old draft - hopefully still substantially correct):
-1- Standard conversions are implicit conversions defined for built-in types. Clause conv enumerates the full set of such conversions. A standard conversion sequence is a sequence of standard conversions in the following order:
Zero or one conversion from the following set: lvalue-to-rvalue conversion, array-to-pointer conversion, and function-to-pointer conversion.
Zero or one conversion from the following set: integral promotions, floating point promotion, integral conversions, floating point conversions, floating-integral conversions, pointer conversions, pointer to member conversions, and boolean conversions.
Zero or one qualification conversion.
[Note: a standard conversion sequence can be empty, i.e., it can consist of no conversions. ] A standard conversion sequence will be applied to an expression if necessary to convert it to a required destination type.
These conversions allow code such as:
double a(double x) { return x + 2; }
a(3.14);
a(42);
Applying the earlier test:
To be polymorphic, [
a()
] must be able to operate with values of at least two distinct types (e.g.int
anddouble
), finding and executing type-appropriate code.
a()
itself runs code specifically for double
and is therefore not polymorphic.
But, in the second call to a()
the compiler knows to generate type-appropriate code for a "floating point promotion" (Standard §4) to convert 42
to 42.0
. That extra code is in the calling function. We'll discuss the significance of this in the conclusion.
> Coercion, casts, implicit constructors
These mechanisms allow user-defined classes to specify behaviours akin to builtin types' Standard conversions. Let's have a look:
int a, b;
if (std::cin >> a >> b)
f(a, b);
Here, the object std::cin
is evaluated in a boolean context, with the help of a conversion operator. This can be conceptually grouped with "integral promotions" et al from the Standard conversions in the topic above.
Implicit constructors effectively do the same thing, but are controlled by the cast-to type:
f(const std::string& x);
f("hello"); // invokes `std::string::string(const char*)`
Implications of compiler-provided overloads, conversions and coercion
Consider:
void f()
{
typedef int Amount;
Amount x = 13;
x /= 2;
std::cout << x * 1.1;
}
If we want the amount x
to be treated as a real number during the division (i.e. be 6.5 rather than rounded down to 6), we only need change to typedef double Amount
.
That's nice, but it wouldn't have been too much work to make the code explicitly "type correct":
void f() void f()
{ {
typedef int Amount; typedef double Amount;
Amount x = 13; Amount x = 13.0;
x /= 2; x /= 2.0;
std::cout << double(x) * 1.1; std::cout << x * 1.1;
} }
But, consider that we can transform the first version into a template
:
template <typename Amount>
void f()
{
Amount x = 13;
x /= 2;
std::cout << x * 1.1;
}
It's due to those little "convenience features" that it can be so easily instantiated for either int
or double
and work as intended. Without these features, we'd need explicit casts, type traits and/or policy classes, some verbose, error-prone mess like:
template <typename Amount, typename Policy>
void f()
{
Amount x = Policy::thirteen;
x /= static_cast<Amount>(2);
std::cout << traits<Amount>::to_double(x) * 1.1;
}
So, compiler-provided operator overloading for builtin types, Standard conversions, casting / coercion / implicit constructors - they all contribute subtle support for polymorphism. From the definition at the top of this answer, they address "finding and executing type-appropriate code" by mapping:
-
"away" from parameter types
from the many data types polymorphic algorithmic code handles
to code written for a (potentially lesser) number of (the same or other) types.
"to" parametric types from values of constant type
They do not establish polymorphic contexts by themselves, but do help empower/simplify code inside such contexts.
You may feel cheated... it doesn't seem like much. The significance is that in parametric polymorphic contexts (i.e. inside templates or macros), we're trying to support an arbitrarily large range of types but often want to express operations on them in terms of other functions, literals and operations that were designed for a small set of types. It reduces the need to create near-identical functions or data on a per-type basis when the operation/value is logically the same. These features cooperate to add an attitude of "best effort", doing what's intuitively expected by using the limited available functions and data and only stopping with an error when there's real ambiguity.
This helps limit the need for polymorphic code supporting polymorphic code, drawing a tighter net around the use of polymorphism so localised use doesn't force widespread use, and making the benefits of polymorphism available as needed without imposing the costs of having to expose implementation at compile time, have multiple copies of the same logical function in the object code to support the used types, and in doing virtual dispatch as opposed to inlining or at least compile-time resolved calls. As is typical in C++, the programmer is given a lot of freedom to control the boundaries within which polymorphism is used.
Solution 2:
In C++, the important distinction is run-time vs. compile-time binding. Ad-hoc vs. parametric doesn't really help, as I'll explain later.
|----------------------+--------------|
| Form | Resolved at |
|----------------------+--------------|
| function overloading | compile-time |
| operator overloading | compile-time |
| templates | compile-time |
| virtual methods | run-time |
|----------------------+--------------|
Note - run-time polymorphism may still be resolved at compile-time, but that's just optimization. Needing to support run-time resolution efficiently, and trading off against other issues, is part of what led to virtual functions being what they are. And that's really key for all forms of polymorphism in C++ - each arises from different sets of trade-offs made in a different context.
Function overloading and operator overloading are the same thing in every way that matters. The names and the syntax for using them doesn't affect polymorphism.
Templates allow you to specify lots of function overloads at once.
There's another set of names for the same resolution-time idea...
|---------------+--------------|
| early binding | compile-time |
| late binding | run-time |
|---------------+--------------|
These names are more associated with OOP, so it's a bit odd to say that a template or other non-member function uses early binding.
To better understand the relationship between virtual functions and function overloading, it's also useful to understand the difference between "single dispatch" and "multiple dispatch". The idea can be understood as a progression...
- First, there are monomorphic functions. The implementation of the function is uniquely identified by the function name. None of the parameters is special.
- Then, there is single dispatch. One of the parameters is considered special, and used (along with the name) to identify which implementation to use. In OOP, we tend to think of this parameter as "the object", list it before the function name etc.
- Then, there is multiple dispatch. Any/all parameters contribute to identifying which implementation to use. Therefore, once again, none of the parameters needs to be special.
There's obviously more to OOP than an excuse to nominate one parameter as special, but that is one part of it. And relating back to what I said about trade-offs - single dispatch is quite easy to do efficiently (the usual implementation is called "virtual tables"). Multiple dispatch is more awkward, not just in terms of efficiency, but also for separate compilation. If you're curious, you might look up "the expression problem".
Just as it's a bit odd to use the term "early binding" for non-member functions, it's a bit odd to use the terms "single dispatch" and "multiple dispatch" where polymorphism is resolved at compile-time. Usually, C++ is considered not to have multiple dispatch, which is considered a particular kind of run-time resolution. However, function overloading can be seen as multiple-dispatch done at compile-time.
Getting back to parametric vs. ad-hoc polymorphism, these terms are more popular in functional programming, and they don't quite work in C++. Even so...
Parametric polymorphism means that you have types as parameters, and the exact same code is used irrespective of what type you use for those parameters.
Ad-hoc polymorphism is ad-hoc in the sense that you provide different code depending on the particular types.
Overloading and virtual functions are both examples of ad-hoc polymorphism.
Again, there's some synonyms...
|------------+---------------|
| parametric | unconstrained |
| ad-hoc | constrained |
|------------+---------------|
Except these aren't quite synonyms, though they're commonly treated as though they were, and that's where confusion is likely to arise in C++.
The reasoning behind treating these as synonyms is that by constraining polymorphism to particular classes of types, it becomes possible to use operations specific to those classes of types. The word "classes" here can be interpreted in the OOP sense, but really just refers to (usually named) sets of types that share certain operations.
So parametric polymorphism is usually taken (at least by default) to imply unconstrained polymorphism. Because the same code is used irrespective of the type parameters, the only supportable operations are those that work for all types. By leaving the set of types unconstrained, you severely limit the set of operations you can apply to those types.
In e.g. Haskell, you can have...
myfunc1 :: Bool -> a -> a -> a
myfunc1 c x y = if c then x else y
The a
here is an unconstrained polymorphic type. It could be anything, so there's not much we can do with values of that type.
myfunc2 :: Num a => a -> a
myfunc2 x = x + 3
Here, a
is constrained to be a member of the Num
class - types that act like numbers. That constraint allows you to do number-ish things with those values, such as add them. Even the 3
is polymorphic - type inference figures out that you mean the 3
of type a
.
I think of this as constrained parametric polymorphism. There's only one implementation, but it can only be applied in constrained cases. The ad-hoc aspect is the choice of which +
and 3
to use. Each "instance" of Num
has it's own distinct implementation of these. So even in Haskell "parametric" and "unconstrained" aren't really synonyms - don't blame me, it's not my fault!
In C++, both overloading and virtual functions are ad-hoc polymorphism. The definition of ad-hoc polymorphism doesn't care whether the implementation is selected at run-time or compile-time.
C++ gets very close to parametric polymorphism with templates if every template parameter has type typename
. There are type parameters, and there's a single implementation no matter which types are used. However, the "Substitution Failure Is Not An Error" rule means that implicit constraints arise as a result of using operations within the template. Additional complications include template specialization for providing alternative templates - different (ad-hoc) implementations.
So in a way C++ has parametric polymorphism, but it's implicitly constrained and could be overridden by ad-hoc alternatives - ie this classification doesn't really work for C++.
Solution 3:
As to ad-hoc polymorphism, it means function overloading or operator overloading. Check out here:
http://en.wikipedia.org/wiki/Ad-hoc_polymorphism
As to parametric polymorphism, template functions can also be counted in because they don't necessarily take in parameters of FIXED types. For example, one function can sort array of integers and it can also sort array of strings, etc.
http://en.wikipedia.org/wiki/Parametric_polymorphism
Solution 4:
This may not be of any help, but I made this to introduce my friends to programming by giving out defined functions, like START
, and END
for the main function so it was not too daunting (they only used the main.cpp file). It contains Polymorphic classes and structs, templates, vectors, arrays, preproccessor directives, friendship, operators and pointers (all of which you should probably know before attempting polymorphism):
Note: It is not finished, but you can get the idea
main.cpp
#include "main.h"
#define ON_ERROR_CLEAR_SCREEN false
START
Library MyLibrary;
Book MyBook("My Book", "Me");
MyBook.Summarize();
MyBook += "Hello World";
MyBook += "HI";
MyBook.EditAuthor("Joe");
MyBook.EditName("Hello Book");
MyBook.Summarize();
FixedBookCollection<FairyTale> FBooks("Fairytale Books");
FairyTale MyTale("Tale", "Joe");
FBooks += MyTale;
BookCollection E("E");
MyLibrary += E;
MyLibrary += FBooks;
MyLibrary.Summarize();
MyLibrary -= FBooks;
MyLibrary.Summarize();
FixedSizeBookCollection<5> Collection("My Fixed Size Collection");
/* Extension Work */ Book* Duplicate = MyLibrary.DuplicateBook(&MyBook);
/* Extension Work */ Duplicate->Summarize();
END
main.h
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <type_traits>
#include <array>
#ifndef __cplusplus
#error Not C++
#endif
#define START int main(void)try{
#define END GET_ENTER_EXIT return(0);}catch(const std::exception& e){if(ON_ERROR_CLEAR_SCREEN){system("cls");}std::cerr << "Error: " << e.what() << std::endl; GET_ENTER_EXIT return (1);}
#define GET_ENTER_EXIT std::cout << "Press enter to exit" << std::endl; getchar();
class Book;
class Library;
typedef std::vector<const Book*> Books;
bool sContains(const std::string s, const char c){
return (s.find(c) != std::string::npos);
}
bool approve(std::string s){
return (!sContains(s, '#') && !sContains(s, '%') && !sContains(s, '~'));
}
template <class C> bool isBook(){
return (typeid(C) == typeid(Book) || std::is_base_of<Book, C>());
}
template<class ClassToDuplicate> class DuplicatableClass{
public:
ClassToDuplicate* Duplicate(ClassToDuplicate ToDuplicate){
return new ClassToDuplicate(ToDuplicate);
}
};
class Book : private DuplicatableClass<Book>{
friend class Library;
friend struct BookCollection;
public:
Book(const char* Name, const char* Author) : name_(Name), author_(Author){}
void operator+=(const char* Page){
pages_.push_back(Page);
}
void EditAuthor(const char* AuthorName){
if(approve(AuthorName)){
author_ = AuthorName;
}
else{
std::ostringstream errorMessage;
errorMessage << "The author of the book " << name_ << " could not be changed as it was not approved";
throw std::exception(errorMessage.str().c_str());
}
}
void EditName(const char* Name){
if(approve(Name)){
name_ = Name;
}
else{
std::ostringstream errorMessage;
errorMessage << "The name of the book " << name_ << " could not be changed as it was not approved";
throw std::exception(errorMessage.str().c_str());
}
}
virtual void Summarize(){
std::cout << "Book called " << name_ << "; written by " << author_ << ". Contains "
<< pages_.size() << ((pages_.size() == 1) ? " page:" : ((pages_.size() > 0) ? " pages:" : " pages")) << std::endl;
if(pages_.size() > 0){
ListPages(std::cout);
}
}
private:
std::vector<const char*> pages_;
const char* name_;
const char* author_;
void ListPages(std::ostream& output){
for(int i = 0; i < pages_.size(); ++i){
output << pages_[i] << std::endl;
}
}
};
class FairyTale : public Book{
public:
FairyTale(const char* Name, const char* Author) : Book(Name, Author){}
};
struct BookCollection{
friend class Library;
BookCollection(const char* Name) : name_(Name){}
virtual void operator+=(const Book& Book)try{
Collection.push_back(&Book);
}catch(const std::exception& e){
std::ostringstream errorMessage;
errorMessage << e.what() << " - on line (approx.) " << (__LINE__ -3);
throw std::exception(errorMessage.str().c_str());
}
virtual void operator-=(const Book& Book){
for(int i = 0; i < Collection.size(); ++i){
if(Collection[i] == &Book){
Collection.erase(Collection.begin() + i);
return;
}
}
std::ostringstream errorMessage;
errorMessage << "The Book " << Book.name_ << " was not found, and therefore cannot be erased";
throw std::exception(errorMessage.str().c_str());
}
private:
const char* name_;
Books Collection;
};
template<class FixedType> struct FixedBookCollection : public BookCollection{
FixedBookCollection(const char* Name) : BookCollection(Name){
if(!isBook<FixedType>()){
std::ostringstream errorMessage;
errorMessage << "The type " << typeid(FixedType).name() << " cannot be initialized as a FixedBookCollection";
throw std::exception(errorMessage.str().c_str());
delete this;
}
}
void operator+=(const FixedType& Book)try{
Collection.push_back(&Book);
}catch(const std::exception& e){
std::ostringstream errorMessage;
errorMessage << e.what() << " - on line (approx.) " << (__LINE__ -3);
throw std::exception(errorMessage.str().c_str());
}
void operator-=(const FixedType& Book){
for(int i = 0; i < Collection.size(); ++i){
if(Collection[i] == &Book){
Collection.erase(Collection.begin() + i);
return;
}
}
std::ostringstream errorMessage;
errorMessage << "The Book " << Book.name_ << " was not found, and therefore cannot be erased";
throw std::exception(errorMessage.str().c_str());
}
private:
std::vector<const FixedType*> Collection;
};
template<size_t Size> struct FixedSizeBookCollection : private std::array<const Book*, Size>{
FixedSizeBookCollection(const char* Name) : name_(Name){ if(Size < 1){ throw std::exception("A fixed size book collection cannot be smaller than 1"); currentPos = 0; } }
void operator+=(const Book& Book)try{
if(currentPos + 1 > Size){
std::ostringstream errorMessage;
errorMessage << "The FixedSizeBookCollection " << name_ << "'s size capacity has been overfilled";
throw std::exception(errorMessage.str().c_str());
}
this->at(currentPos++) = &Book;
}catch(const std::exception& e){
std::ostringstream errorMessage;
errorMessage << e.what() << " - on line (approx.) " << (__LINE__ -3);
throw std::exception(errorMessage.str().c_str());
}
private:
const char* name_;
int currentPos;
};
class Library : private std::vector<const BookCollection*>{
public:
void operator+=(const BookCollection& Collection){
for(int i = 0; i < size(); ++i){
if((*this)[i] == &Collection){
std::ostringstream errorMessage;
errorMessage << "The BookCollection " << Collection.name_ << " was already in the library, and therefore cannot be added";
throw std::exception(errorMessage.str().c_str());
}
}
push_back(&Collection);
}
void operator-=(const BookCollection& Collection){
for(int i = 0; i < size(); ++i){
if((*this)[i] == &Collection){
erase(begin() + i);
return;
}
}
std::ostringstream errorMessage;
errorMessage << "The BookCollection " << Collection.name_ << " was not found, and therefore cannot be erased";
throw std::exception(errorMessage.str().c_str());
}
Book* DuplicateBook(Book* Book)const{
return (Book->Duplicate(*Book));
}
void Summarize(){
std::cout << "Library, containing " << size() << ((size() == 1) ? " book collection:" : ((size() > 0) ? " book collections:" : " book collections")) << std::endl;
if(size() > 0){
for(int i = 0; i < size(); ++i){
std::cout << (*this)[i]->name_ << std::endl;
}
}
}
};
Solution 5:
Here is a basic example using Polymorphic classes
#include <iostream>
class Animal{
public:
Animal(const char* Name) : name_(Name){/* Add any method you would like to perform here*/
virtual void Speak(){
std::cout << "I am an animal called " << name_ << std::endl;
}
const char* name_;
};
class Dog : public Animal{
public:
Dog(const char* Name) : Animal(Name) {/*...*/}
void Speak(){
std::cout << "I am a dog called " << name_ << std::endl;
}
};
int main(void){
Animal Bob("Bob");
Dog Steve("Steve");
Bob.Speak();
Steve.Speak();
//return (0);
}