C++ polymorphism of a object in an array

Question

I'm an embedded software engineer and coming from the world of bits and C. In that world, there are data in flash memory represented by const in C. And there are data in RAM. RAMs are expensive and limited, while flash memory is cheap and enough. Also, dynamic memory allocation using new, delete, malloc etc is not allowed due to fragmentation problem or safety regulations, static designs are preferred.

I've around 2000 objects which have similar constant properties but different behaviors. So for them, I defined Shape Class as a base class which holds shared properties of my objects. And to represent different behavior, Shape Class has one abstract method called Print() which will be overwritten by parents.

ShapeList is the important part. It is a const array consists of "const Shapes" so that they will be placed into flash memory section by linker.

Below program produces an output:

I'm a Shape has 3 dots
I'm a Shape has 4 dots
I'm a Shape has 5 dots

While expected output is:

I'm a Triangle has 3 dots
I'm a Rectangle has 4 dots
I'm a Pentagon has 5 dots

I need polymorphic behavior. When I print Triangle, it should behave like a Triangle, not as a Shape. How can I do this?

Thanks.

#include <array>
#include <cstdio>
class Shape
{
    public:
    const int DotCount;
    Shape(const int dot): DotCount(dot) {}
    virtual void Print(void) const; // this is virtual method
};

void Shape::Print(void) const
{
    printf("I'm a Shape has %d dots\n", DotCount);
}

class Triangle: public Shape
{
    public:
    Triangle(void): Shape(3) { }
    void Print(void) const;
};

void Triangle::Print(void) const
{
    printf("I'm a Triangle has %d dots\n", DotCount);
}

class Rectangle: public Shape
{
    public:
    Rectangle(void): Shape(4) { }
    void Print(void) const;
};

void Rectangle::Print(void) const
{
    printf("I'm a Rectangle has %d dots\n", DotCount);
}

class Pentagon: public Shape
{
    public:
    Pentagon(void): Shape(5) { }
    void Print(void) const;
};

void Pentagon::Print(void) const
{
    printf("I'm a Pentagon has %d dots\n", DotCount);
}

const std::array<const Shape, 3> ShapeList = { Triangle(), Rectangle(), Pentagon() };

int main(void)
{
    ShapeList.at(0).Print();
    ShapeList.at(1).Print();
    ShapeList.at(2).Print();
    return(0);
}

More problem: Today I realized that there is another problem with virtual functions. When I add any virtual functions into base class, compiler start ignoring "const" directive and place object automatically to the RAM instead of flash memory. I don't know why. I've asked this question to IAR. The conclusion I got so far is that Polymorphic behavior is not possible with ROMable classes even with heap :/

Answer 1

This version doesn't use dynamic memory:

Triangle tri;
Rectangle rect;
Pentagon pent;
const std::array<const Shape*, 3> ShapeList {
    &tri, &rect, &pent
};
for (unsigned int i = 0; i < ShapeList.size(); i++)
    ShapeList[i]->Print();

---

In languages like C#, you can use the as keyword to achieve "polymorphism". In C++, it looks something like this:

    const Triangle* tri = dynamic_cast<const Triangle*>(ShapeList[i]);
    if (tri)
        static_cast<Triangle>(*tri).SomethingSpecial();

If the pointer returned by dynamic_cast is valid, you can call Triangle's special function. This for example will allow you to have a loop that iterates over ShapeList and call only Triangle methods. If you can use exceptions, consider wrapping it in a try catch block and catching std::bad_cast.

Note: you need a const pointer because ShapeList[i] is const. The reason the static_cast is necessary is because you're calling a non-const method on a const pointer. You can add the const qualifier, like SomethingSpecial() const and then just do tri->SomethingSpecial(). Otherwise, you just cast the const off.

For example:

static_cast<Triangle*>(tri)->SomethingSpecial();
// error: static_cast from type 'const Triangle*' to type 'Triangle*' 
// casts away qualifiers

This will work:

const_cast<Triangle*>(tri)->SomethingSpecial();

Answer 2

As others have pointed out, the convenient and common way doesn't work like that. Fixing it results in code which is at odds with the restrictions of your target platform. You can, however, emulate polymorphism differently in several different ways.

You can segregate the objects by type like this:

const Triangle tris[] = {tri1, tri2, ...};
const Rectangle rects[] = {rect1, rect2, ...};
// for correct order, if needed
const Shape * const shapes[] = {&tris[0], &rects[2], &rects[0], ...}:

You still need to make all methods (that behave differently for the various types) virtual, and you pay an extra pointer (two if you count the vtable pointer, which would be a bit unfair) per object. You could also remove everything virtual in favor of an explicit tag:

enum ShapeKind { Triangle, Rectangle, Pentagon };
struct Shape {
    ShapeKind kind;
    int sides;
    ...
};

Use a union if the various subclasses need very different member data. This has numerous severe restrictions and leads to rather ugly code, but can work well. For example, you need know your hierarchy up front and the subclasses need to be roughly the same size. Note that this is not necessarily faster than the virtual alternative, but when it's applicable it can take less space (a byte instead of a vtable pointer) and make introspection leaner.

Answer 3

You can use polymorphism along with all of your constraints with a minor change to your code:

const Triangle triangle;
const Rectangle rectangle;
const Pentagon pentagon;

const std::array<const Shape*, 3> ShapeList = { &triangle, &rectangle, &pentagon };

Answer 4

Any easy fix would be to add a string the shape which defines what type of shape it is.

class Shape
{
    public:
    const int DotCount;
    const char* shapeType
    Shape(const int dot, const char* type): DotCount(dot), shapeType(type) {}
    void Print(void) const;
};

void Shape::Print(void) const
{
    printf("I'm a "); printf(shapeType); printf(" has %d dots\n", DotCount);
}

class Triangle: public Shape
{
    public:
    Triangle(void): Shape(3, "Triangle") { }
};

Answer 5

Another solution I have found in C for polymorphic dynamic dispatch without dynamic allocation is to pass vtable pointers manually, like GHC’s desugaring of typeclasses in Haskell. This approach would also be reasonable in C++, because it’s lightweight and strictly more general than what C++’s object system allows.

An overloaded/polymorphic function takes a pointer to a struct of function pointers for each typeclass to which a parameter’s type belongs—equality comparison, ordering, &c. So you might have:

template<class Container, class Element>
struct Index {
  size_t (*size)(const Container& self);
  const Element& (*at)(const Container& self, size_t index);
};

enum Ordering { LT, EQ, GT };

template<class T>
struct Ord {
  Ordering (*compare)(const T& a, const T& b);
};

template<class Container, class Element>
const Element* maximum(
  const Index<Container, Element>& index,
  const Ord<Element>& ord,
  const Container& container) {

  const size_t size = index.size(container);
  const Element* max = nullptr;

  for (size_t i = 0; i < size; ++i) {
    const Element& current = index.at(container, i);
    if (!max || ord.compare(current, *max) == GT)
      max = &current;
  }

  return max;

}

Since the type parameters are “phantom types” not used representationally, the linker should be able to deduplicate this kind of function, if you’re worried about code size. The type-unsafe but perhaps more compiler-friendly alternative would be to use void*.

In C++, you can also pass the vtable functions as template parameters if you know them at compile time—that is, manual devirtualisation. This admits more optimisations (e.g., inlining) but obviously doesn’t allow dynamic dispatch.

One caveat: since you don’t have partial function application or closures, you will find it an interesting experience to make partial specialisations, such as the Haskell:

instance (Ord a) => Ord [a] where ...

Which says that a list of things [a] has an ordering if the elements a have an ordering.