We can increase the abstraction level of our algorithms via the techniques of classical object-oriented (OO) programming, as seen in languages such as Java and C#. The OO approach is to decide exactly which behaviors we'd like to be customizable, and then declare them as the public virtual member functions of an abstract base class:
class container_of_ints {
public:
virtual int size() const = 0;
virtual int& at(int) = 0;
};
class array_of_ints : public container_of_ints {
int data[10] = {};
public:
int size() const override { return 10; }
int& at(int i) override { return data[i]; }
};
class list_of_ints : public container_of_ints {
struct node {
int data;
node *next;
};
node *head_ = nullptr;
int size_ = 0;
public:
int size() const override { return size_; }
int& at(int i) override {
if (i >= size_) throw std::out_of_range("at");
node *p = head_;
for (int j=0; j < i; ++j) {
p = p->next;
}
return p->data;
}
~list_of_ints();
};
void double_each_element(container_of_ints& arr)
{
for (int i=0; i < arr.size(); ++i) {
arr.at(i) *= 2;
}
}
void test()
{
array_of_ints arr;
double_each_element(arr);
list_of_ints lst;
double_each_element(lst);
}
Inside test, the two different calls to double_each_element compile because in classical OO terminology, an array_of_ints IS-A container_of_ints (that is, it inherits from container_of_ints and implements the relevant virtual member functions), and a list_of_ints IS-A container_of_ints as well. However, the behavior of any given container_of_ints object is parameterized by its dynamic type; that is, by the table of function pointers associated with this particular object.
Since we can now parameterize the behavior of the double_each_element function without editing its source code directly--simply by passing in objects of different dynamic types--we say that the function has become polymorphic.
But still, this polymorphic function can handle only those types which are descendants of the base class container_of_ints. For example, you couldn't pass a std::vector<int> to this function; you'd get a compile error if you tried. Classical polymorphism is useful, but it does not get us all the way to full genericity.
An advantage of classical (object-oriented) polymorphism is that the source code still bears a one-to-one correspondence with the machine code that is generated by the compiler. At the machine-code level, we still have just one double_each_element function, with one signature and one well-defined entry point. For example, we can take the address of double_each_element as a function pointer.