Classically polymorphic functions

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.