# [C++] virtual member functions in a templated class

This topic is 3224 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm currently working with this templated class:
template <typename T>
class Hoge
{
void foo();
void bar(const Hoge &hoge)
{
if (member == hoge)    // <- note operator== used here
...do stuff...
}
};


I plan to extend this class so it can be derived from, and the base class can be used to call the virtual methods in the derived. So I now have this:
template <typename T>
class Hoge
{
virtual void foo();
virtual void bar(const Hoge<T> &hoge)
{
if (member == hoge)
...do stuff...
}
};


The only thing that has been changed is "virtual" has been added before each of the function names. If I declare this class with a non-POD type of T, the compiler complains that my class type of T does not have an operator==, even though I never call the bar() function from my code for that type. Both MSVC2005 and gcc-4.1.2 give me the same error. If I remove the virtual keyword from bar(), but leave it for foo(), the error goes away. I was under the impression that functions in a templated class weren't instanciated until they were actually used. Can anyone enlighten me as to why this isn't the case with virtuals? And is there any way around this so that I don't have to require the users of my template class to add an operator== to their code if they'll never need it?

##### Share on other sites
This is an artifact of the way virtual functions work -- they get entered into a table of function pointers, at which point it's very hard (and generally not useful) for the compiler to be able to figure out which ones are called and which ones aren't.

There might be a workaround for your situation -- care to post some actual code instead of this foo and bar nonsense?

##### Share on other sites
I don't know this for certain, but if I had to speculate I would say that, essentially, any function that goes into the v-table is treated as instantiated.

When you think about it, the entries in the v-table must always "line up" for each derived class -- you can't just drop things from the v-table because a derived class might use them. If this space must be reserved in the v-table, then it has to have something to point at, to have something to point at, that code has to be compiled and located somewhere in memory -- and if that happens, all the usual requirements apply.

Does the intended non-POD type purposely not provide the equality operator, or is it an issue of not wanting to write it? If equality does not make sense for the type, would introducing a dummy equality operator be acceptable?

##### Share on other sites
Quote:
 Original post by MaulingMonkeyThere might be a workaround for your situation -- care to post some actual code instead of this foo and bar nonsense?

The actual code is quite large and not something that I can just post. The same results can be achieved using the snippets I've provided, however.

Part of the problem is this class provides quite a bit of generic functionality, and various types of T use the functions in the class that they need. You might suggest that I could split up the class based on the different classes of T, but that's not really an ideal solution here.

Quote:
 Original post by RavyneDoes the intended non-POD type purposely not provide the equality operator, or is it an issue of not wanting to write it? If equality does not make sense for the type, would introducing a dummy equality operator be acceptable?

I would say not wanting to write the equality operator is part of it, but in some cases where the template is used, equality doesn't make sense -- and in those cases, the class doesn't ever call the bar() function in the template.

Is it possible to create a dummy equality operator somehow, without too much extra code? :)

Thanks to both of you for your replies -- at least I know now that even templated classes are instanciated due to the v-table.

##### Share on other sites
Sidenote: Inside the class declaration Class<T>, you don't have to use Class<T> but only Class:

template <typename T>class Hoge{    virtual void foo();    virtual void bar(const Hoge &hoge) // Hoge<T> only necessary                                       // class declaration    {        if (member == hoge)            ...do stuff...    }};

But that shouldn't cause errors.

Sidenote2: Virtual Member Function Templates (not in your case, just saying as it might be interesting here; you only have a Virtual Member Function) cannot be declared (8.1.1 Virtual Member Functions, in the Book).

Further, as you have only posted pseudo code, I can only guess what fits your needs.

Solution:
You have to actually define a fitting operator==:
template <typename T>class Hoge {        T member;        virtual void foo() {};        virtual void bar(const Hoge &hoge) {                if (member == hoge)                        ;        }};template <typename T>inline bool operator == (T const &lhs, Hoge<T> const &rhs) {        return true;}int main () {        Hoge<int> hoge;}

Solution B:
As Ravyne pointed out, at the point of instantiation, vtables must be derived by the compiler. I fail to find a reference, but my personal guess is that the body of the function is needed and hence compiled because e.g. another unit of translation can potentially define a class that derives from an instantiation of your class template, but that deriving class doesn't override your abstract function. Then, that unit of translation would need the definition. The translation unit of your template couldn't know.

Otoh this reason might be easier to stomach: If your function is not purely virtual (as in "virtual T f() = 0;"), the vtable entry can't be initialised with 0, but must be initialized with the address of an existing function. A class template member function can obviously only exist when it is instantiated. While not impossible, it would cause a lot of epic PITA to manage a partially initialized, partially uninitialized vtable. It could cause PITA for the compiler, but could also end in performance trouble at runtime.

##### Share on other sites
Crap. In my haste to post before a meeting, I realize I made a fatal mistake with the initial code sample I provided. My apologies to everyone, I really should have waited and double checked the content afterward.

Here's the relevant functions in the class and some sample code. The Hoge class provides a container for objects of any type, wrapped around std::vector. The class really does much more than this, but as I said earlier, I can't post it all.

template <typename T>class Hoge{	std::vector<T>	mList;public:	virtual void add(const T &var)	{		mList.push_back(var);	}	virtual bool remove(const T &var)   // <- parameter is of type 'T', not 'Hoge'	{		std::vector<T>::iterator iter = mList.begin();		for (; iter < mList.end(); ++iter)		{			if (var == *iter)			{				mList.erase(iter);				return true;			}		}		return false;	}};

With a POD type, this works just fine, but it fails when using a non-POD type that doesn't implement an eqality operator:

class SomeClass{public:	SomeClass() : mData(NULL)	{	}	~SomeClass() { };private:	SomePtr *mData;};void main(void){	Hoge<int> foo;	// works fine	foo.add(5);	foo.add(2);	// error C2678: binary '==' : no operator found which takes a left-hand operand of type 'const SomeClass' (or there is no acceptable conversion)	Hoge<SomeClass> bar;	SomeClass a, b;	bar.add(a);	bar.add(b);}

So does this mean I have to implement operator== in SomeClass, regardless? Sticking something in my source code like...
template <typename T>inline bool operator==(const T &a, const T &b){	return true;}

while compiles, is really just asking for trouble. :)

##### Share on other sites
Quote:
 So does this mean I have to implement operator== in SomeClass, regardless?

Yes, if you want to be able to use it as a template parameter to your "Hoge" class.

I am curious though, what kind of functionality do you plan to extend "Hoge" with?

##### Share on other sites
Quote:
 Original post by rip-offI am curious though, what kind of functionality do you plan to extend "Hoge" with?

Presently two extensions are planned. One will provide an insertion sort, placing the add()ed value into a proper position into the list.

The second (and more complicated) will provide a method to add values to the list, in a way that their base addresses are never changed once they are added. This second method will likely do it's own memory management, as std::vector isn't designed for stuff like that -- but this is the primary reason for adding 'virtual' to the base interface in the first place: so the user can use one of the derived classes but still pass the base class handle to existing code that uses it.

Thanks again to everyone who replied, I guess I'm off to go write a bunch of dummy operator== functions now...

##### Share on other sites
1) You should have 'typename std::vector<T>::iterator iter = mList.begin();'. The language requires that, though not all compilers complain.

2) Don't write search loops like that yourself. Use std::find(). If you want to remove all matching instances instead of just the first, you can use std::remove() or std::remove_if().

Quote:
 Original post by bpointPresently two extensions are planned. One will provide an insertion sort, placing the add()ed value into a proper position into the list.

3) You should be aware that insertion into a vector is O(N).

4) You could always just use std::sort to keep things sorted. You probably don't need to sort after every individual add().

Quote:
 The second (and more complicated) will provide a method to add values to the list, in a way that their base addresses are never changed once they are added.

5) It is impossible to both do that, and keep elements in a contiguous chunk the way that std::vector does. When it's time to resize, the memory "in front of" the current allocation might simply not be available.

Quote:
 but this is the primary reason for adding 'virtual' to the base interface in the first place: so the user can use one of the derived classes but still pass the base class handle to existing code that uses it.

7) This kind of thing is normally handled with compile-time polymorphism, because there's no reason to make the decision at runtime about what container to use. To make code that can operate on any kind of container (or at least several different kinds) but which uses compile-time polymorphism, it's usual to template on an iterator type. (This is more flexible than templating on a container type and requesting the .begin() and .end() of the container; with the iterator template, you can operate on a portion of a container, or on an array.) See, for example, the standard library algorithms.

In short: you are trying to fight against design decisions made by the language standards committee when they standardized the standard library. These decisions were not made lightly. Please reconsider.

##### Share on other sites
Quote:
 Original post by Zahlman5) It is impossible to both do that, and keep elements in a contiguous chunk the way that std::vector does. When it's time to resize, the memory "in front of" the current allocation might simply not be available.

I never said the elements had to be in a single contiguous chunk. This array will use multiple chunks scattered around in memory, but with the use of operator[], the array can appear to the user as if it was contiguous.

In any case, I've hit a new brick wall. There are other functions in the original class that make use of other operators (such as > and +) that now are required once I added 'virtual' to the rest of the class. I can kinda deal with adding operator==, but I will absolutely not add all of these other operators to all of my existing classes when they simply just doesn't make sense.

To that end, the virtual plan is off. Some code in our existing code base will have to be re-worked to support the new derived class types directly, since we won't be able to use virtual to call to the derived class, but I guess that's just what C++ requires.

##### Share on other sites
Quote:
 There are other functions in the original class that make use of other operators (such as > and +) that now are required once I added 'virtual' to the rest of the class. I can kinda deal with adding operator==, but I will absolutely not add all of these other operators to all of my existing classes when they simply just doesn't make sense.

If you look at how the standard library solves this then it uses overloads that take functors which define equality or ordering in addition to using operator= or < by default if the class happens to define them (I can't see what operator+ would be needed for since this can only make sense for a tiny subset of classes). For example, you may want to search for a Person by the first name or the last name. Or you may want case insensitive and case sensitive searches. How would a single operator== handle all the potentially infinite number of ways how we would want to compare objects?

##### Share on other sites
Quote:
Original post by bpoint
Quote:
 Original post by Zahlman5) It is impossible to both do that, and keep elements in a contiguous chunk the way that std::vector does. When it's time to resize, the memory "in front of" the current allocation might simply not be available.

I never said the elements had to be in a single contiguous chunk. This array will use multiple chunks scattered around in memory, but with the use of operator[], the array can appear to the user as if it was contiguous.

So you're going to make a linked list of increasing-sized chunks? or just what?

Quote:
 In any case, I've hit a new brick wall. There are other functions in the original class that make use of other operators (such as > and +) that now are required once I added 'virtual' to the rest of the class. I can kinda deal with adding operator==, but I will absolutely not add all of these other operators to all of my existing classes when they simply just doesn't make sense.

Hold on. This isn't a consequence of the virtual-ness, it's a consequence of the template. If you write a member function that includes '*iter + 3', and the type of *iter is T, then it has to be sensible to add 3 to a T instance. If it isn't, then either the implementation needs to be changed, or that member function doesn't make sense for a Hoge<T>.

##### Share on other sites
Quote:
 Original post by ZahlmanSo you're going to make a linked list of increasing-sized chunks? or just what?

Actually, the implementation is more along the lines of storing the data into various multiple 'physical' arrays, then updating a virtual map which just contains pointers and the indicies used by that section.

For example, an insertion into the middle of the array would simply internally allocate a new list, copy the data into it, and patch up the virtual map, so the pointers of the elements never change. Most of the code is already written as a proof-of-concept, and it works quite well.

Quote:
 Original post by ZahlmanHold on. This isn't a consequence of the virtual-ness, it's a consequence of the template. If you write a member function that includes '*iter + 3', and the type of *iter is T, then it has to be sensible to add 3 to a T instance. If it isn't, then either the implementation needs to be changed, or that member function doesn't make sense for a Hoge.

I beg to differ. Functions in templates aren't instanctiated until they are used. The templated class can provide lots of other useful functionality for various types of T, and those who wish to use that functionality will implement the operators necessary so they can call those functions. Those who do not need those functions should not be required to implement them.

By simply adding virtual to the class's functions, the whole template becomes instanctiated, and all types of T are now required to implement everything the template requires even if they'll never use them.

It's just unfortunate that this is the way the compilers work.

##### Share on other sites
Quote:
 Original post by bpointBy simply adding virtual to the class's functions, the whole template becomes instanctiated, and all types of T are now required to implement everything the template requires even if they'll never use them.

No:

template <typename T>class Hoge {        T member;        void frobnicate () {                ++member.pipapo *= member(5) -                                   this->pipapo->pipapo +                                   this->template y *                                   sizeof member.x.y.z;        }        virtual void foo() {};        virtual void bar(const Hoge &hoge) {                if (member == hoge)                        ;        }};template <typename T>inline bool operator == (T const &lhs, Hoge<T> const &rhs) {        return true;}int main () {        Hoge<int> hoge;}

We can even use members of class Hoge that don't exist (yet) by delaying lookup to the second parse by adding this->.

Quote:
 It's just unfortunate that this is the way the compilers work.

As was pointed out sooner, at the point of instantiation we need a well-defined vtable, not a vtable that is partially undefined.

##### Share on other sites
Quote:
 Original post by phresnelNo:*** Source Snippet Removed ***

But your frobnicate() function isn't virtual. And if you make it virtual (so that a derived class can implement some other unique form of frobnicate()), then you run into the exact same problem I have.

Quote:
 Original post by phresnelAs was pointed out sooner, at the point of instantiation we need a well-defined vtable, not a vtable that is partially undefined.

I'm no compiler writer, but I really don't see why the vtable can't just be initialized to null. At the point a particular function is either called or referenced, then the compiler can insert it into the vtable for that instance. Functions which were never referenced will just have null vtable entries, and certainly won't cause any problems as they're never used.

##### Share on other sites
Quote:
 Original post by bpointI'm no compiler writer, but I really don't see why the vtable can't just be initialized to null. At the point a particular function is either called or referenced, then the compiler can insert it into the vtable for that instance. Functions which were never referenced will just have null vtable entries, and certainly won't cause any problems as they're never used.

Because it would require if(a != null) check on *every* function call. And this is a kinda of a big deal when it comes to performance, especially considering vtable is a completely internal concept which can be reliably constructed by compiler.

All corner cases however are courtesy of C++'s arcane rules and general mess.

Templates are compile-time polymorphism and generally don't mix well with run-time polymorphism.

Can't you use traits concept to achieve what you want? Do you really need run-time polymorphism to choose between two algorithms?

##### Share on other sites
Quote:
Original post by bpoint
Quote:
Original post by phresnel
Quote:
 Original post by bpointBy simply adding virtual to the class's functions, the whole template becomes instanctiated, and all types of T are now required to implement everything the template requires even if they'll never use them.

No:

*** Source Snippet Removed ***

But your frobnicate() function isn't virtual. And if you make it virtual (so that a derived class can implement some other unique form of frobnicate()), then you run into the exact same problem I have.

Quote:
 Original post by bpointBy simply adding virtual to the class's functions, the whole template becomes instanctiated, and all types of T are now required to implement everything the template requires even if they'll never use them.

Quote:
 Original post by phresnelNo:...

Quote:
 Original post by bpointI'm no compiler writer, but I really don't see why the vtable can't just be initialized to null. At the point a particular function is either called or referenced, then the compiler can insert it into the vtable for that instance. Functions which were never referenced will just have null vtable entries, and certainly won't cause any problems as they're never used.

Quote:
 Original post by Humble MeWhile not impossible, it would cause a lot of epic PITA to manage a partially initialized, partially uninitialized vtable. It could cause PITA for the compiler, but could also end in performance trouble at runtime.

##### Share on other sites
Quote:
Original post by Antheus
Quote:
 Original post by bpointAll corner cases however are courtesy of C++'s arcane rules and general mess.

Which language do you know that also supports templates as a core language element but with less mess? To be honest, I only know that C++ has templates (and, if you want, Objective-C++).

Quote:
 Templates are compile-time polymorphism ...

Saying "Templates are compile-time polymorphism" is like saying "Cars are streets" or "Balls in the form of a truncated icosahedron are soccer". I don't really know what that phrase wants to express.

Quote:
 ... and generally don't mix well with run-time polymorphism.

##### Share on other sites
Quote:
 Original post by AntheusBecause it would require if(a != null) check on *every* function call. And this is a kinda of a big deal when it comes to performance, especially considering vtable is a completely internal concept which can be reliably constructed by compiler.

I was referring to the building of the vtable at compile time. Yes, the compiler would have to do an if() check for a given object's vtable at every function call or reference, but this could be done at compile time and not at runtime.

Quote:
 Original post by AntheusCan't you use traits concept to achieve what you want? Do you really need run-time polymorphism to choose between two algorithms?

It would be nice if we could use runtime polymorphism, but no, we don't really need it. The original idea of making everything virtual was because all of the planned extentions to this class would have the exact same basic interface functions (add/insert/remove/etc). It just seemed like a logical extention to make the base class virtual, so the newer extended classes could be used without modification to our existing code base.

I suppose something like boost::enable_if<> could be used here to check if the typename T being used implements the operators used by the base Hoge class. Hoge would have to be split into two different parts, though -- one with just the basic stuff, and another with all the extras. I guess the polymorphism would still work fine, but I'd have to write some code to test it.

##### Share on other sites
Quote:
Original post by bpoint
Quote:
 Original post by AntheusBecause it would require if(a != null) check on *every* function call. And this is a kinda of a big deal when it comes to performance, especially considering vtable is a completely internal concept which can be reliably constructed by compiler.

I was referring to the building of the vtable at compile time. Yes, the compiler would have to do an if() check for a given object's vtable at every function call or reference, but this could be done at compile time and not at runtime.

Quote:
 Humble MeI fail to find a reference, but my personal guess is that the body of the function is needed and hence compiled because e.g. another unit of translation can potentially define a class that derives from an instantiation of your class template, but that deriving class doesn't override your abstract function. Then, that unit of translation would need the definition. The translation unit of your template couldn't know.

Surely we can discuss the whole compilation model of C++ in another thread. If we could replace it by something better (but not worse!), I am in.

##### Share on other sites
Quote:
Original post by phresnel
Quote:
 Original post by bpointBy simply adding virtual to the class's functions, the whole template becomes instanctiated, and all types of T are now required to implement everything the template requires even if they'll never use them.

Argh, yes, me and my bad Engrish. It happens when you live in a foreign country and only speak in your native tounge once a month to call home.

I suppose I should have said something like:

"By simply adding virtual to the functions in the class which I plan to derive from, those particular functions in the template incidentally become instanctiated as well, and all types of T are now required to implement the functions and operators used by the virtual template functions even if they'll never use them."

Better? :)

Quote:
 Original post by Humble MeWhile not impossible, it would cause a lot of epic PITA to manage a partially initialized, partially uninitialized vtable. It could cause PITA for the compiler, but could also end in performance trouble at runtime.

Yes, I didn't forget you said this. Again, I'm no compiler writer, but I still don't think it would be that difficult to maintain a partial vtable, which would have no affect on runtime performance. If you can show me where I am wrong in my thinking, please do. :)

##### Share on other sites
There is probably a reason why the STL containers are not all derivates of the same base class. They are simply too different to be able to support the same interface. They are all similar to use, and that's largely thanks to iterators.

If you need things like dummy operator== (which just introduces potential bugs to anything using these classes) you must be on the wrong track.

Runtime polymorphism:
template <class T, class U>void foo(BaseContainer<T>& container, const U& value){    container.add(value);}int main(){    SortedArray<int> sorted;    foo(sorted, 1);    FixedInMemoryArray<int> fixed;    foo(fixed, 1);}

Same thing with templates:
template <class Container, class T>void foo(Container& container, const T& value){    container.add(value);}int main(){    SortedArray<int> sorted;    foo(sorted, 1);    FixedInMemoryArray<int> fixed;    foo(fixed, 1);}

Pretty much the same thing, except the compiler can catch errors when assignment operator is required but missing (as you don't need to cripple your classes with non-working functionality).

##### Share on other sites
Quote:
Original post by bpoint
Quote:
Original post by phresnel
Quote:
 Original post by bpointBy simply adding virtual to the class's functions, the whole template becomes instanctiated, and all types of T are now required to implement everything the template requires even if they'll never use them.

Argh, yes, me and my bad Engrish. It happens when you live in a foreign country and only speak in your native tounge once a month to call home.

Actually, you're english is pretty good, and that was the reason why I assumed that you are wrong, and didn't assume that it was just bad wording :D

Quote:
 I suppose I should have said something like:"By simply adding virtual to the functions in the class which I plan to derive from, those particular functions in the template incidentally become instanctiated as well, and all types of T are now required to implement the functions and operators used by the virtual template functions even if they'll never use them."Better? :)

Hehe, indeed. Or shorter: "Making a class-template-member-function virtual causes that function to be instantiated eagerly (as compared to the lazy instantiation of non-virtual class-template-member-functions)." :)

## Into more detail about why partially initialized vtables can cause PITA

Quote:
Quote:
 Original post by Humble MeWhile not impossible, it would cause a lot of epic PITA to manage a partially initialized, partially uninitialized vtable. It could cause PITA for the compiler, but could also end in performance trouble at runtime.

Yes, I didn't forget you said this. Again, I'm no compiler writer, but I still don't think it would be that difficult to maintain a partial vtable, which would have no affect on runtime performance. If you can show me where I am wrong in my thinking, please do. :)

The problems are mainly the same as the problems for implementing the keyword "export" ("Why we can't afford export"), which is only implemented in one and only one C++ compiler frontend.

Most easily understood might be that C and C++ have so called "translation units", where a unit is, simply speaking, a single sourcecode file (as compared to header files). Virtually all C and C++ compilers will compile each single sourcefile into a corresonding, so-called "object file", which contains machine code (i.e. it contains compiled code; that code is not necessarily actual machine code), plus a directory of entities (functions, classes) that can be found in that object file. Finally, you pass all object-files to the "linker", who will assemble a working program from those, based on the information that can be found in the directories. At that final level, it is hard (as in PITA), not impossible, to do further optimizations and things like keeping track of the initialization status of vtables upon binary data.

To give an exemplary and heavily eased example for how compiling works in C and C++:

sourcefile-a.cpp
extern int alphaCentauri () ;int main () {    alphaCentauri ();}

The compiler has only access to this sourcefile. This is also the reason why he can't inline the call to alphaCentauri(). So, he emits a request in form of a "missing reference" into the object file:

sourcefile-a.obj
  Contains:      [main () : int] at 0x00  Missing References:      [alphaCentauri () : int] at 0x04  Machine Code:      0x12 0x01 0x02 0x03    // let's assume here is a call instruction      0x00 0x41 0xa2 0xb3      0x30 0x21 0x92 0xc3      0x03 0x31 0x02 0xf3

sourcefile-a.cpp
int alphaCentauri () {    return 0xBEEF;}

sourcefile-b.obj
  Contains:      [alphaCentauri () : int] at 0x00  Missing References:  Machine Code:      0xa2 0xb3 0xc6 0x41       0x02 0xf3 0x03 0x31       0x30 0xc3 0xBE 0xEF     // heh, our "BEEF" :D      0x01 0x02 0x03 0x12

The linker now has access to both object files and can do the final "Cleaning". He sees that in sourcefile-a.obj there's a missing reference to a function with the signature "alphaCentauri () : int", so he looks up whether one of the other object-files defines such function. If he can't find the definition, he emits something like

  undefined reference to alphaCentauri() in sourcefile-a.obj+0x04

. But as we where clever, we passed all necessary object files to it, and so the linker can finally replace the dummy value with the actual address of alphaCentauri(). It now also becomes evident that this is also the time to transform all relative addresses into absolute ones.

Our final binary then looks like:
      0x12 0x01 0x02 0x03          0x20 0x41 0xa2 0xb3 // 32 = 0x20      0x30 0x21 0x92 0xc3      0x03 0x31 0x02 0xf3      0xa2 0xb3 0xc6 0x41    // function "alphaCentauri()" starts here      0x02 0xf3 0x03 0x31       0x30 0xc3 0xBE 0xEF       0x01 0x02 0x03 0x12

[Edited by - phresnel on April 23, 2009 7:36:30 AM]

##### Share on other sites
Quote:
 Original post by phresnelInto more detail about why partially initialized vtables can cause PITA

After thinking it through a bit more: you're right. I hadn't fully considered the case of multiple translation units, where the base class could be used in a different (and already compiled) source file. In this case, the compiler can only use the vtable to call into the class's functions, so there would certainly be problems if the vtable was only partially initialized.

Thanks for the in-depth explanation!

##### Share on other sites
Quote:
Original post by phresnel
Quote:
Original post by Antheus
Quote:
 Original post by bpointAll corner cases however are courtesy of C++'s arcane rules and general mess.

Which language do you know that also supports templates as a core language element but with less mess? To be honest, I only know that C++ has templates (and, if you want, Objective-C++).

Quote:
 Templates are compile-time polymorphism ...

Saying "Templates are compile-time polymorphism" is like saying "Cars are streets" or "Balls in the form of a truncated icosahedron are soccer". I don't really know what that phrase wants to express.

Quote:
 ... and generally don't mix well with run-time polymorphism.

The context of this thread and problem statement perhaps?

Specifically this:
Quote:
 Presently two extensions are planned. One will provide an insertion sort, placing the add()ed value into a proper position into the list.The second (and more complicated) will provide a method to add values to the list

There is a container with lots of added functionality. Storage however may vary, yet only needs to perform rudimentary operation of add(), and consequently remove() and get(). To facilitate reuse, polymorphism of sorts must be employed.

First question that arises is whether allocator parameter as defined by std:: containers is sufficient to accomplish this.

If not, then same effect can be achieved without run-time polymorphism (avoiding it due to v-table problems) using templates only. Specifically, because of, again:
Quote:
 Presently two extensions are planned.
They are planned, foreseen and well defined, not YAGNI.

So instead of analyzing v-table madness into painstaking detail, why not first solve the problem in accordance with requirements the way std::stack solves it.
template < class T, class Container >
where Container provides the rudimentary functionality required by storage (add, remove, get).

The implementation of container can then be one of STL classes, or a custom one, defining only needed operations.