Polymorphic objects on the stack?

Question

In Why is there no base class in C++?, I quoted Stroustrup on why a common Object class for all classes is problematic in c++. In that quote there is the statement:

Using a universal base class implies cost: Objects must be heap-allocated to be polymorphic;

I really didn't look twice at it, and since its on Bjarnes home page I would suppose a lot of eyes have scanned that sentence and reported any misstatements.

A commenter however pointed out that this is probably not the case, and in retrospect I can't find any good reason why this should be true. A short test case yields the expected result of VDerived::f().

struct VBase {
    virtual void f() { std::cout <<"VBase::f()\n"; }
};

struct VDerived: VBase {
    void f() { std::cout << "VDerived::f()\n"; }
};

void test(VBase& obj) {
    obj.f();
}

int main() {
    VDerived obj;
    test(obj);
}

Of course if the formal argument to test was test(VBase obj) the case would be totally different, but that would not be a stack vs. heap argument but rather copy semantics.

Is Bjarne flat out wrong or am I missing something here?

Addendum: I should point out that Bjarne has added to the original FAQ that

Yes. I have simplified the arguments; this is an FAQ, not an academic paper.

I understand and sympathize with Bjarnes point. Also I suppose my eyes was one of the pairs scanning that sentence.

Raddled

There have been suggestions that there is no actual need for a vtable in this example. It is trivial to add a VDerived2 class, construct in main, call test, with the expected result as suggested by the question, thus a vtable needs to be present. – Raddled

One funny consequence: you didn't wrote a virtual destructor, but here it's perfectly okay because it's not required. Yet most compilers (with warnings activated) will bash you on the head... – Renin

@Matthieu g++ -Wall(4.4.3) is politely quiet. Of course destructors, virtual or not, would add nothing to my example and non relevant code is always, well, not relevant. – Raddled

This is a great question about a very daft verbal blunder by BS and people's tendency to mistakenly assume he can't misspeak. It's a shame that the (obvious) accepted answer is diluted by the raft of irrelevant commentary and speculation elsewhere. Pointers/references can act polymorphically. Individual objects cannot. The storage location/duration of ptr/ref or object is completely irrelevant to these plainly obvious facts. – Dendriform

Answer 1

Looks like polymorphism to me.

Polymorphism in C++ works when you have indirection; that is, either a pointer-to-T or a reference-to-T. Where T is stored is completely irrelevant.

Bjarne also makes the mistake of saying "heap-allocated" which is technically inaccurate.

^{(Note: this doesn't mean that a universal base class is "good"!)}

Aqua

edit: Nevermind, I just re-looked over the example above. I'm not sure anymore. – Denominative

@John: Rubbish. It's a call through VBase&. Here's an example that shows your assertion is wrong. [edit: lol, ok] – Aqua

+1 - looks like Polymorphism to me too. Here's a variation that also displays polymorphic behaviour, and here's another that demonstrates that the polymorphic behaviour disappears if I remove the "virtual". – Wiltz

+1, not sure how many times I did struct SillyVisitor : Visitor { ... } v;. Now v is heap allocated? Lulz. – Initiatory

@Tomalak What would you prefer to "heap-allocated" here? – Raddled

@CaptainGiraffe: Dynamically allocated. The physical description "heap" is out-moded, irrelevant and in fact oft-inaccurate. – Aqua

@Tomalak Good point, heap is not mentioned in the standard. I take it you would prefer freestore as a contrast to the stack? – Raddled

@CaptainStore: Freestore would be in contrast to "the heap". Dynamically allocated objects usually go into the freestore (though custom allocators can scupper that). – Aqua

(And polymorphism is related to dynamic allocation, but most certainly not dependent on it!) – Aqua

Technically it is polymorphism of course. It is also pretty unnecessary polymorphism. I think Bo's answer is more to the point. – Codie

@Sebastian: Sorry but I don't understand what you are saying. – Aqua

Answer 2

I think Bjarne means that obj, or more precisely the object it points to, can't easily be stack-based in this code:

int f(int arg) 
{ 
    std::unique_ptr<Base> obj;    
    switch (arg) 
    { 
    case 1:  obj = std::make_unique<Derived1      >(); break; 
    case 2:  obj = std::make_unique<Derived2      >(); break; 
    default: obj = std::make_unique<DerivedDefault>(); break; 
    } 
    return obj->GetValue(); 
}

You can't have an object on the stack which changes its class, or is initially unsure what exact class it belongs to.

^{(Of course, to be really pedantic, one could allocate the object on the stack by using placement-new on an alloca-allocated space. The fact that there are complicated workarounds is beside the point here, though.)}

The following code also doesn't work as might be expected:

int f(int arg) 
{ 
    Base obj = DerivedFactory(arg); // copy (return by value)
    return obj.GetValue();
}

This code contains an object slicing error: The stack space for obj is only as large as an instance of class Base; when DerivedFactory returns an object of a derived class which has some additional members, they will not be copied into obj which renders obj invalid and unusable as a derived object (and quite possibly even unusable as a base object.)

Summing up, there is a class of polymorphic behaviour that cannot be achieved with stack objects in any straightforward way.

---

Of course any completely constructed derived object, wherever it is stored, can act as a base object, and therefore act polymorphically. This simply follows from the is-a relationship that objects of inherited classes have with their base class.

Incumbent

obj is "stack-based": it's a pointer on the stack! "You can't have an object on the stack which changes its class, or is initially unsure what exact class it belongs to." Nor can you have any such object on the heap! Pointers & references are capable of polymorphism. Underlying objects are not (& don't suffer identity crises). Location/storage duration of the ptr/ref or object mean nothing. Dynamic storage in your example only eases address-of & extends lifetime. I could just as easily stack-allocate all 3 Deriveds & write a function/ternary to assign 1 of their addresses to obj. – Dendriform

Whenever I need the kind of polymorphy that DerivedFactory provides, I use heap objects even if a simple copy-by-value to an object of "automatic" storage duration would totally suffice if it weren't for the polymorphy. You say "just as easily", but I seriously doubt that you can provide a good solution for this. Feel free to prove me wrong, of course – Incumbent

"copy-by-value"? Not required. Polymorphism is orthogonal to storage durations of referee & referer. It only requires that you use a reference/pointer as route. That can be automatic and/or refer to an automatic object. Example: struct FactoryWarehouse { Derived1 d1; Derived2 d2; DerivedDefault dd; Base *get_pointer_to_some_derived(unsigned const index) { switch (index) { case 1: return &d1; case 2: return &d2; default: return ⅆ } } }; Sure, a bit contrived, but you can use the returned Base * polymorphically, showing that, again, the whole thing about storage duration is a red herring. – Dendriform

Sure you can do that, but if you need to reconstruct an object you need to manually do a destructor call and placement new on d1, d2, dd. I wasn't saying that polymorphy is tied to storage duration: Just to achieve a simple object construction/deconstruction one will use the heap. Which I think is what Bjarne meant. But point taken, this whole thing could be explained with more detail and precision. As it stands, it's rather simplified, but I don't find it overly wrong or misleading. – Incumbent

Answer 3

Having read it I think the point is (especially given the second sentence about copy-semantics) that universal base class is useless for objects handled by value, so it would naturally lead to more handling via reference and thus more memory allocation overhead (think template vector vs. vector of pointers).

So I think he meant that the objects would have to be allocated separately from any structure containing them and that it would have lead to many more allocations on heap. As written, the statement is indeed false.

PS (ad Captain Giraffe's comment): It would indeed be useless to have function

f(object o)

which means that generic function would have to be

f(object &o)

And that would mean the object would have to be polymorphic which in turn means it would have to be allocated separately, which would often mean on heap, though it can be on stack. On the other hand now you have:

template <typename T>
f(T o) // see, no reference

which ends up being more efficient for most cases. This is especially the case of collections, where if all you had was a vector of such base objects (as Java does), you'd have to allocate all the objects separately. Which would be big overhead especially given the poor allocator performance at time C++ was created (Java still has advantage in this because copying garbage collector are more efficient and C++ can't use one).

Weingarten

Can you elaborate on that? He clearly says "Objects must be heap-allocated to be polymorphic" but clearly that is not true. At the very least, he may have a point (which I would like to understand) but his assertion doesn't appear to hold true in any case. – Denominative

@Jan: It would certainly be a poor thing to do, but Bjarne's assertion as to why is incorrect. – Aqua

@John: Indeed, his assertion as written is wrong. I was trying to find what was the logic leading to that incorrect statement. – Weingarten

@Jan Hudec: I figured it was something like that. I don't think he thought it out all the way, though. On the other hand, do note that while using templates will save you the vtable lookup, it will also incur a (potentially expensive) copy and additionally trade-off executable size (depending on how many instantiations of f you end up with.) – Denominative

template <typename T> f(T o) "which ends up being more efficient for most cases" - I don't see these cases unless T is very small. Otherwise the copy operation might outweigh level of indirection saved using the template as T is not a reference in your function. – Visible

Answer 4

Bjarne's statement is not correct.

Objects, that is instances of a class, become potentially polymorphic by adding at least one virtual method to their class declaration. Virtual methods add one level of indirection, allowing a call to be redirected to the actual implementation which might not be known to the caller.

For this it does not matter whether the instance is heap- or stack-allocated, as long as it is accessed through a reference or pointer (T& instance or T* instance).

One possible reason why this general assertion slipped onto Bjarne's web page might be that it is nonetheless extremely common to heap-allocate instances with polymorphic behavior. This is mainly because the actual implementation is indeed not known to the caller who obtained it through a factory function of some sort.

Visible

That the implementation is not known to the caller makes the assertion of any kind of allocation method even more bananas... not less. – Aqua

Answer 5

I think he was going along the lines of not being able to store it in a base-typed variable. You're right in saying that you can store it on the stack if it's of the derived type because there's nothing special about that; conceptually, it's just storing the data of the class and it's derivatives + a vtable.

edit: Okay, now I'm confused, re-looking at the example. It looks like you may be right now...

Denominative

Not exactly. I agreed what he was doing was legal, but completely read over the use of references that basically voided Bjarne's assertion. I agreed that what he was doing was okay, but I disagreed that it was a case of polymorphism, which it was. – Denominative

Answer 6

I think the point is that this is not "really" polymorphic (whatever that means :-).

You could write your test function like this

template<class T>
void test(T& obj)
{
    obj.f();
}

and it would still work, whether the classes have virtual functions or not.

Ours

What would be the litmus test for "really polymorphic" then? – Raddled

I don't see how being able to do that means anything. After all, you could just as easily use a pointer and take a reference of the object, and it would still behave polymorphically whether the object was allocated on the heap or on the stack. – Denominative

That's still the same example. Adding templates doesn't change anything. – Aqua

It's not exactly the same example though; the template would be instantiated for every different derivative type. That'd be equivalent to writing out the function for every different type you wanted to throw into it when you compare it to having a function that just takes derived types. For example, if a library were to define a derivative class VDerivedTwo, any code using VBase& will accept VDerivedTwo, even if it was unaware. This template example would need to be instantiated again. Then again, if you just used T=VBase, the instantiation would be 100% equivalent and therefore meaningless.. – Denominative

Ir is the same example, as the example is just using one instantiation of one object. There will also be just one instantiation of my template, and the result is exactly the same, except there is no need for vtables – Ours

@JohnChadwick: Oh, true. Sorry, I missed that in Bo's code. Yes, this example is rather impertinent to the question. :) – Aqua

@BoPersson: How is it the same example? You removed the polymorphism and replaced it with a completely different paradigm. – Aqua

@Bo Persson: Actually, no, it will still use the vtable with T = VBase. If you use a derivative type, you have to know the derivative type ahead of time, and it would still cause another instantiation of the template. I'm not sure what point you're trying to make; if T = VBase, it's still polymorphic... – Denominative

@John - My point is that T is not VBase in my code, T is VDerived and there is no polymorphism. It works anyway, so we don't need the magic Object base class for all objects. Also, at least the compiler I use will see VDerived's static type and not use a virtual call, even if the function is virtual. – Ours

Which doesn't change anything at all. If i call test<VBase>(object);, your code sure as hell does use the vtable. And that means if I only have a VBase& type, and I call test() on it, T will equal VBase, as is often times the case. You have proven that you know how templates work (conceptually) but have still yet to prove your answer has any relevance to the question and it's example... If you need solid proof that sometimes T will need to equal VBase, imagine getting back VBase& from another library; you can't get around it now, because you don't know the derived type. – Denominative

+1 Bjarne may have overstated things, but I thought the same thing as Bo. As long as you allocate on the stack, you can use static polymorphism because you have all type information. Maybe you should use it then. Dynamic polymorphism is only necessary when you have to lose type information by storing in a pointer-to-base. – Codie

@Sebastian: None of that changes the fact that Bjarne's assertion is patently false. – Aqua

Answer 7

Polymorphism without heap allocation is not only possible but also relevant and useful in some real life cases.

_{This is quite an old question with already many good answers. Most answers indicate, correctly of course, that Polymorphism can be achieved without heap allocation. Some answers try to explain that in most relevant usages Polymorphism needs heap allocation. However, an example of a viable usage of Polymorphism without heap allocation seems to be required (i.e. not just purely syntax examples showing it to be merely possible).}

---

Here is a simple Strategy-Pattern example using Polymorphism without heap allocation:

Strategies Hierarchy

class StrategyBase {
public:
    virtual ~StrategyBase() {}
    virtual void doSomething() const = 0;
};

class Strategy1 : public StrategyBase {
public:
    void doSomething() const override { std::cout << "Strategy1" << std::endl; }
};

class Strategy2 : public StrategyBase {
public:
    void doSomething() const override { std::cout << "Strategy2" << std::endl; }
};

A non-polymorphic type, holding inner polymorphic strategy

class A {
    const StrategyBase* strategy;
public:
    // just for the example, could be implemented in other ways
    const static Strategy1 Strategy_1;
    const static Strategy2 Strategy_2;

    A(const StrategyBase& s): strategy(&s) {}
    void doSomething() const { strategy->doSomething(); }
};

const Strategy1 A::Strategy_1 {};
const Strategy2 A::Strategy_2 {};

Usage Example

int main() {    
  // vector of non-polymorphic types, holding inner polymorphic strategy
  std::vector<A> vec { A::Strategy_1, A::Strategy_2 };

  // may also add strategy created on stack 
  // using unnamed struct just for the example
  struct : StrategyBase {
    void doSomething() const override {
      std::cout << "Strategy3" << std::endl;
    }
  } strategy3;

  vec.push_back(strategy3);

  for(auto a: vec) {
    a.doSomething();
  }
}

Output:

Strategy1
Strategy2
Strategy3

Code: http://coliru.stacked-crooked.com/a/21527e4a27d316b0

Glossitis

Answer 8

Let's assume we have 2 classes

class Base
{
public:
    int x = 1;
};

class Derived
    : public Base
{
public:
    int y = 5;
};

int main()
{
    Base o = Derived{ 50, 50 };

    std::cout << Derived{ o }.y;

    return 0;
}

The output will be 5 and not 50. The y is cut off. If the member variables and the virtual functions are the same, there is the illusion that polymorphism works on the stack as a different VTable is used. The example below illustrates that the copy constructor is called. The variable x is copied in the derived class, but the y is set by the initialization list of a temporary object.

The stack pointer has increased by 4 as the class Base holds an integer. The y will just be cut off in the assignment.

When using Polymorphism on the heap you tell the new allocator which type you allocate and by that how much memory on heap you need. With the stack this does not work. And neither memory is shrinking or increasing on the heap. As at the time of initialization you know what you're initializing and exact this amount of memory is allocated.

Dialectal