recursive subclass

[trantran]

I am writing a class that uses different policies stored in classes
I want to declare this class by simply selecting the policies by writing

my_great_class<policy45, policy22, policy12> (There can be a varying number of policies)

which would translate automatically into:

struct empty_class{};
struct policy12: empty_class{
// code...
};
struct policy23: policy12{
// code...
};
struct policy45: policy23{
// code...
};
struct my_great_class: policy45{
// code...
};

I want to use subclasses to benefit from empty subclass optimisation which will diminish my memory footprint for my structures
Therefore, the following would be inaceptable to me:

template <typename... Ts>
struct my_great_class:Ts...{
}

There surely must be a way (?) to do recursively inherited subclasses with variadic template but I tried and couldn't find it.
Anyone knows how to do this?

[trantran]

Actually, I've just found a way:

template <int... P>      struct policies;
template <int H, int... T>   struct policies<H, T...>:public policies<T...>{};
template <>                  struct policies<>{};

enum{policy12, policy24, policy56 /*etc..*/};

template <int... P>
struct policies<policy12, P...>:public policies<P...>{
    // code...
}

// repeat for all desired policies with appropriate code


// and use like this:

policies<policy12, policy24 /*etc...*/> my_chosen_policies;

Any alternative ways? Improvements?

[mike_2000_17]

Neat piece of code!

However, there is one major problem. The problem is that each individual policy (where you have the code) will be instantiated for every unique combination of P... packs. For example, if you have these two instances in your code:

policies<policy12, policy24> my_policies_1;
policies<policy24, policy12> my_policies_2;

you will have the following template instantiations generated by the compiler:

struct policies<policy12, policy24> : public policies<policy24> {
  // code for policy12
};

struct policies<policy24> : public policies<> {
  // code for policy24
};

struct policies<policy24, policy12> : public policies<policy12> {
  // code for policy24
};

struct policies<policy12> : public policies<> {
  // code for policy12
};

You see, the problem is that, here you have repeating instantiations of the same code, for no reason (i.e., the repeating code is not instantiated differently at all). This is wasteful, and will lead to code-bloat and longer compilation times. This is the real tricky part with using templates in this way, you have to carefully analyse the generation of instantiations.

Here is a way to fix that problem:

template <int... P> struct policies;
template <int P> struct policy;

template <int H, int... T> 
struct policies<H, T...> : public policy<H>, 
                           public policies<T...> { };

template <int H> struct policies<H> : public policy<H> {};

enum { policy12, policy24, policy56 /*etc..*/ };

template <>
struct policy<policy12> {
    // code...
}

// repeat for all desired policies with appropriate code

// and use like this:

policies<policy12, policy24 /*etc...*/> my_chosen_policies;

The above still takes advantage of empty base-class optimization, but leads to only a single instantiation for each policy. In fact, a simpler scheme would be this:

template <typename... P> struct policies;

template <typename P, typename... T> 
struct policies<P, T...> : public P, 
                           public policies<T...> { };

template <typename P> struct policies<P> : public P {};

struct policy12 {
    // code...
}

// repeat for all desired policies with appropriate code

// and use like this:

policies<policy12, policy24 /*etc...*/> my_chosen_policies;

I much prefer this, because it's simpler.

[trantran]

Thank you Mike for brillantly pointing out a significant flaw in my proposed solution.

I've been thinking more about the EBCO and experimenting a little bit and (suprisingly) found that:
1) vs2013 does not implement EBCO
2) g++ 4.8.2 does

I also found that if a compiler does implement the EBCO, then very simple code like this would work just fine (contrary to what I had previously written given my then inaccurate understanding of EBCO)

template <typename... Ps> policies : Ps... {};

struct policy12{
    // code
};

// used as

policies < policy12 /*, etc...*/> my_chosen_policies

And the above code can be used instead of your proposed code because it (apparently) does the same thing in an even more simpler form.

Now, let's go back to my flawed solution.
It has a major useful feature: if the subclasses have virtual function you only get a single vtable! This mean that on a 64-bit machine with 5 policies, the final class would occupy simply 8 bytes per object instead of 40 !
Furthermore the code repetition is for typically very small snippets of code of policies and there might (?) be some speed improvement due to increased locality of that code that it would result in.

In conclusion, the enormous memory saving can compensate for the code bloating and still make it an interesting way to deal with the problem.

But clearly, as you brillantly pointed out, this is not perfect.

So is there a way where we could benefit both from the virtual fct memory shrinkage AND absence of repetition of code?

(And also, is there a way to get EBCO with vs2013?)

[mike_2000_17]

It has a major useful feature: if the subclasses have virtual function you only get a single vtable!

That's a good point. I didn't think of that. To have a single vtable pointer you need a single inheritance chain.

So is there a way where we could benefit both from the virtual fct memory shrinkage AND absence of repetition of code?

To be honest, I'm wondering why you would want policy classes to have virtual functions in the first place. I can hardly think of a reason why that would be useful, and even less so within your original solution, since you can't use the policies as polymorphic base-classes anyways (due to the varying tail-end of the inheritance chain). I think you need to give me a use case for this, because it makes no sense to me otherwise.

Given that this requires a single inheritance chain, it's pretty hard to get unique instantiations for each policy, since they need to be inserted somewhere in that chain. Therefore, each policy will always depend on the tail-end of that chain (that it inherits from).

So, I don't think you can really have it both ways.

However, you might be able to avoid virtual functions by implementing the dynamic polymorphism externally to the policy classes. My tutorial on this subject might enlighten you.

And also, is there a way to get EBCO with vs2013?

Ask Microsoft. But don't get your hopes up, they've ignored similar requests in the past. The MSVC compiler is really not a compiler you should rely on for professional coding of any kind. There are many little things like that that MSVC doesn't implement or doesn't implement correctly. Also, EBCO is partially required (or implied) by the standard. In my book, the only worthy compilers for practical use are GCC, ICC, and Clang.

[trantran]

"I'm wondering why you would want policy classes to have virtual functions in the first place."

Actually this is not the case. Here is what happenned:
1) I realised that my structures was getting bigger when adding policies using vs2013
2) I thought that it was a EBCO problem which I incorrectly thought could only be corrected by a recursive inheritance chain which on experiment did indeed correct the problem with vs2013
3) I later realised that this was not a EBCO problem after reading on EBCO and seeing no increase in my structure using G++ and normal multiple inheritance
4) At this point, I still needed my technique as a hack around vs2013 shortcomings (that unfortunately your technique would not specifically solve) but I realise switching compiler might not be a bad idea after all!
5) Then I realise my technique has another advantage (single vtable) and I realised that I could also use it for other reason then vs2013 repair.
6) A great use is not for policies (other than vs2013 repair) but for multiple virtual interfaces that I can simply chain to avoid completely the cost on structure size! That (very useful) use remain even if I switch compiler.
7) I this point I would certainly benefit from information for possible compiler switch:
a) on windows: what do you suggest as working platform: compiler, ide, etc
b) on linux: same question especially for ide and ui (since that seem to evolve very quickly in later years)
8) I looked at your tutorial and you have a very impressive bio!

[iamthwee]

Sounds to me like poor implementation rather than the shortcommings of the compiler.

And now you've got so far down the rabbit hole you can't go back.

[mike_2000_17]

6) A great use is not for policies (other than vs2013 repair) but for multiple virtual interfaces that I can simply chain to avoid completely the cost on structure size! That (very useful) use remain even if I switch compiler.

I'm sorry, but I fail to understand how this could be useful at all. Let me setup a simple example scenario, let's say we are writing a library to represent different kinds of animals. Then, we could have a number of "policy" classes (or virtual interfaces, or whatever you want to call them) for different actions that animals do:

struct Walker {
  virtual void walk();
};

struct Runner {
  virtual void run();
};

struct Crawler {
  virtual void crawl();
};

struct Eater {
  virtual void eat();
};

struct TailWagger {
  virtual void wagTail();
};

// ...

So, under normal (OOP) circumstances, you could do this:

struct Dog : Walker, Runner, Eater, TailWagger {
  // ... dog-specific code (if any) here ...
};

And then, you could have Dog objects act polymorphically inside functions like this:

void wagTailThreeTimes(TailWagger& tw) {
  tw.wagTail();
  tw.wagTail();
  tw.wagTail();
};

int main() {
  Dog d;
  wagTailThreeTimes(d);
};

Now, using your solution for a recursive subclassing, you could re-implement the above using an approach like this (or a variant of it, which all boil down to the same thing):

struct NullTerminatingTrait {
  template <typename... Tail>
  struct bind { };
};

template <typename... Args>
struct AnimalTraits;

template <>
struct AnimalTraits<> { };

template <typename T, typename... Tail>
struct AnimalTraits<T, Tail...> : T::template bind< Tail..., NullTerminatingTrait > { };


struct Walker {
  template <typename Next, typename... Tail>
  struct bind : Next::template bind< Tail... > {
    virtual void walk();
  };
};

struct Runner {
  template <typename Next, typename... Tail>
  struct bind : Next::template bind< Tail... > {
    virtual void run();
  };
};

struct Crawler {
  template <typename Next, typename... Tail>
  struct bind : Next::template bind< Tail... > {
    virtual void crawl();
  };
};

struct Eater {
  template <typename Next, typename... Tail>
  struct bind : Next::template bind< Tail... > {
    virtual void eat();
  };
};

struct TailWagger {
  template <typename Next, typename... Tail>
  struct bind : Next::template bind< Tail... > {
    virtual void wagTail();
  };
};

// ...

struct Dog : AnimalTraits< Walker, Runner, Eater, TailWagger > {

};

But, then, the problem is that in order to implement the wagTailThreeTimes function, you would have to do this:

template <typename T, typename... Tail>
void wagTailThreeTimes(TailWagger::bind<T, Tail...>& tw) {
  tw.wagTail();
  tw.wagTail();
  tw.wagTail();
};

Now, you see the issue is that not only do you cause the code of each "policy" to be instantiated again for each Tail... argument-pack, you also cause the code for each polymorphic use of each "policy" to be instantiated again for each argument-pack. Moreover, you now have to make these functions into templates. And at the end, you end up with a solution that is kind of in between static dispatching (overloading) and dynamic dispatching (virtual calls), but in the worst possible way, i.e., getting the worse of both worlds. Not to mention that compilation times are going to be terrible with this scheme. Also, the fact that this version of wagTailThreeTimes needs to be aware (via Tail) of a significant (if not all) of the inheritance chain of the most-derived class seems to defeat the whole philosophy of polymorphism (i.e., the principle of "I don't know, nor do I care to know, what the actual most-derived class is").

I simply don't see how it could be useful to do this. Especially since you could simply do this:

template <typename AnyTailWagger>
void wagTailThreeTimes(AnyTailWagger& tw) {
  tw.wagTail();
  tw.wagTail();
  tw.wagTail();
};

Which essentially achieves the same level of polymorphism at the same instantiation cost, minus the run-time cost and minus the template deduction cost (at compile-time), and doesn't require a virtual table (thus, less memory). Moreover, that scheme does not require you to use one or another solution as far as implementing the EBCO or how you decide to arrange your inheritance chain, it only requires that the class has a wagTail() function (virtual or not).

To me, it seems far more practical to implement the dynamic polymorphism externally from the "policy" classes, using simple wrappers. By this method, you would just implement the classes like this:

struct TailWagger {
  void wagTail() {
    // code for wagging the tail
  };
};

struct AnyTailWagger {
  virtual void wagTail() = 0;

  template <typename P>
  struct Wrapped;

  template <typename P>
  static Wrapped<P> wrap(P& p);
};

template <typename P>
struct AnyTailWagger::Wrapped : AnyTailWagger {
  P* p;
  Wrapped(P* aP) : p(aP) { };

  void wagTail() { p->wagTail(); }; 
};

template <typename P>
AnyTailWagger::Wrapped<P> AnyTailWagger::wrap(P& p) {
  return AnyTailWagger::Wrapped<P>(&p);
};


void wagTailThreeTimes(AnyTailWagger& tw) {
  tw.wagTail();
  tw.wagTail();
  tw.wagTail();
};

template <typename GenTailWagger>
void wagTailThreeTimes(GenTailWagger& gtw) {
  auto tw = AnyTailWagger::wrap(gtw);
  wagTailThreeTimes(tw);
};

I find this nicer because, at this point, you get minimal instantiations of the important code (e.g., the implementation of the TailWagger class, and the implementation of the wagTailThreeTimes functions), and the rest is just some thin wrapping. By adding on the dynamic polymorphism externally, you minimize the design constraints on the inheritance hierarchy of your final derived classes, and so, you can remain more flexible and use simpler schemes.

If you have an idea in mind about how one could use virtual functions within those kinds of "policy" classes, then I'm all ears. Just try to stay close to this simple "animal-traits" example, so that things remain within grasp.

a) on windows: what do you suggest as working platform: compiler, ide, etc
b) on linux: same question especially for ide and ui (since that seem to evolve very quickly in later years)

First of all, there is no reason (and in fact you should avoid) constraining yourself or your project to a single compiler or IDE. Certainly not the latter. For any platform, I recommend using a cross-platform build system to manage the configuration of the compilations (choosing compiler, finding external dependencies, incrementally compiling only the "new" code, etc.). My favorite build-system is cmake, and it is very widely used. The same thing goes for most tools, i.e., try as much as possible to avoid IDE-bound single-platform tools. With the exception of debugging tools (which are better handled natively by the IDE), the rest should be portable tools, like version control (e.g., Git), unit-testing (e.g., CTest), documentation (e.g., doxygen), etc..

Most cross-platform build-systems can employ any compiler you choose (or it can choose one for you). Switching compilers does not require any additional work, except re-running the build configuration script. Also, use out-of-source builds, this keeps the source directories clean of any artifacts that come with compilation (object files, pre-compiled headers, etc...). For example, I regularly maintain about 5-6 different build directories for the same project, each for a specific platform and compiler (or options, such as turning on debug symbols). It's generally a good idea to compile and test your code with different compilers, especially if you intend to distribute or maintain a high standard of quality.

For Windows, I would say that you should probably just stick with MinGW (GCC) as the compiler. But checking that your stuff at least compiles under MSVC is good too. Heavy debugging (step-through, stack frames, etc.) under Visual Studio is still superior to other IDEs, so you might want to use it for that purpose. But for day-to-day coding, I find that CodeBlocks is perfectly adequate.

For Linux, the choice is between Clang and GCC. Clang is really nice when it comes to diagnostics and speed of compilation (and memory consumption). The main drawback is that it is not quite as stable as GCC, and probably doesn't produce quite as good code (performance-wise), although I haven't looked into that. So, I would say, use either one. They are interchangeable anyways (same options, same binary formats, etc.). As for IDEs, I like KDevelop, it's a nice and fast IDE with lots of nice native support for the different tools like cmake, git/svn, gdb, valgrind, etc... and a clang plugin is in the works, I think. Otherwise, you can use CodeBlocks, or any other IDE. The thing is, once you use platform-agnostic (portable) tools like cmake, git, etc.., you are no longer tied with a particular IDE, so, anything will do just fine, even a simple text-editor.

For GUIs, definitely go for Qt, regardless of the platform, it works like a charm anywhere, and it's easy and feature-rich.

[trantran]

Thank you Mike for your beautiful explanation.

I think it is helpful to separate the different threads that this discussion has taken.

1) There is a discussion on interfaces. The technique (any special name for it?) you are proposing is the way to go relative to:
a) my recursive inheritance: on this I agree that your method appears immensely superior
b) multiple inheritance: you seem to think that multiple inheritance is not a good way for multiple interface (and iamthwee seem to say that because of this, the vs2013 shortcoming is a non-issue). In effect, your technique trades memory for an extremely minimal decrease in execution speed (creation of wrappers), the trade is immensely favorable, and it is very hard to object unless you see other benefit for the use of multiple inheritance for multiple interfaces.

2) Policies vs intefaces. Here what I meant with policies is quite different and I think your technique wouldn't be useful for it (of course you might have other tricks in your bag...). In effect, my policies affect the structure of my classes. Let me give you 2 examples relative to a single-link-list:
a) size policy: the list either stores a size (speed optimisation) or recalculate it each time (space optimisation - which can be useful when you have a huge array of list and most of them are empty)
b) index vs pointer: wether your id for the next item in an index relative to a stored pointer (space optimisation) or a pointer (speed optimisation)
So in both case you may have 0 size change to the structure or had 8 bytes (typically) and you also need different functions versions to deal with it.
By using policies, it works perfectly with zero execution cost.
To implement the policies, assuming maximum memory-optimisation, then we have 2 cases:
a) using EBCO-implementing compiler: a multiple inheritance is the way to go. No need at all for my "recursive inheritance" hack. C++ works wonder for this.
b) using a non-EBCO compiler such as vs2013: trouble in paradise. Here there still remain no other way found in our discussion than my "recursive inheritance". This is a shortcoming of the compiler (note to iamthwee: if you don't accept this as a significant compiler shortcoming, than we'll be happy to also here your (hopefully much simpler) solution/workaround!).

So at this point, the question left to answer: any other way to implement these policies despite vs2013 shortcoming?

[mike_2000_17]

1) There is a discussion on interfaces.

The technique (any special name for it?) you are proposing is the way to go

This technique is generally called type erasure. In this context, you could also call it "non-intrusive run-time polymorphism". A nice demo of that is "Inheritance Is The Base Class of Evil (it starts simple, but ramps up beautifully).

you seem to think that multiple inheritance is not a good way for multiple interface

Multiple interfaces are not a good idea to begin with (caveat: in that statement, I'm not including interfaces that refine each other (e.g., LivingBeing -> Animal -> Mammal -> Canine)). And when you do have to implement multiple interfaces in a single class, multiple inheritance is a really problematic thing to deal with, it's too intrusive (i.e. "locks up" the design too much, and you always have to dread that diamond).

In effect, your technique trades memory for an extremely minimal decrease in execution speed (creation of wrappers)

The wrappers do not, in general, impose any overhead. It's all washed away by the compiler. The wrapper just tells the compiler "do this dispatching dynamically", and it does so. The only overhead that will remain is what is necessary to accomplish the dynamic dispatching (object indirection and a virtual table lookup), which is what you would get anyways if you had virtual functions directly in your original class (i.e., that's just the price of dynamic dispatching).

The only real trade-off with this technique is the added complexity of the code, i.e., we replace a virtual keyword with a base-class, a wrapper class template and a factory function (and possibly some "clone" functions). It's mostly washed away at run-time, but code complexity also has a cost of its own.

2) Policies vs intefaces.

Let me give you 2 examples relative to a single-link-list:
a) size policy: ...
b) index vs pointer: ...

These are two great examples of situations where you would indeed use Policies (in the canonical GP sense, refer to the first chapter of Andrei Alexandrescu's classic book (aka the bible of generic programming)). These are literally textbook examples of where Policy classes make sense.

But let's look at the characteristics of these 2 problems:

• You have a very limited set of possibilities (size or no size, pointer or id).
• You cannot afford any run-time overhead whatsoever, in terms of memory, speed and levels of indirection.
• The chosen policies are static, in the sense that you cannot switch them at run-time.
• It is unlikely that a user will instantiate all combinations at one point or another (i.e., they'll mostly pick the default, maybe occasionally chose a particular combination).

These factors make those two problems textbook examples of where policy classes make sense (as I briefly mentioned in my tutorial).

And, of course, the type erasure technique that I showed is not appropriate here because that was pertaining to the discussion of having virtual functions within those policy classes (which I did not, and still don't, see a purpose for). So, in this discussion of policy classes, that solution is irrelevant.

N.B.: I'm sure those example problems are not real, right? Cause if they are, I would have a few things to point out that would eliminate those two problems altogether.

a) using EBCO-implementing compiler: multiple inheritance...
b) using a non-EBCO compiler: ... my "recursive inheritance".

That sounds about right.

In many cases though, there is a third option, which is to split up the policies into different nested classes (or detail classes). Among the non-optional data members of your container (or main class), often there are groupings and often each group can be lumped-in with a particular policy. So, as opposed to trying to achieve a perfect EBCO'd chain of "main class + policy classes", you only have to achieve simple EBCO for "group of data members + related policy class", which you typically would lump in a nested class (or a class in a "detail" namespace).

A fourth option is to have non-stateful policies. If you have a closed set of possible policies (there are X number of possible policies, can never be more), and in all those cases, there is no additional data required (state), then you can simply lump the policy functions as static member functions of a class, and this way, you don't need to hold an object of that policy class (and the need for EBCO vanishes). This is a very common technique too (I've used it plenty of times, and seen it used plenty of times too).

But you're right, if your problem does not fall under those two categories I just mentioned, your (a) and (b) solutions correctly describe the situation. And for portability, sadly, you have to aim for the lowest common denominator, which is almost always MSVC, i.e., use option (b).

Fortunately, the main shortcoming that I originally pointed out about your "recursive inheritance" solution was the problem of the number of instantiations (combinatorial explosion). And since we are discussing these textbook examples of where policy classes are appropriate, well, if you look at the characteristics I pointed out, then it is clear that this shortcoming is not going to be an issue for these problems.

N.B.: Remember not to use the EBCO chain (e.g., the "recursive inheritance") at the top-level class, you need to do that in a "detail" or nested class, so that it's hidden from the user (for diagnostics, documentation, etc.).

[trantran]

Thank you for this very clear presentation which neatly sums up the situation.

"I'm sure those example problems are not real, right? Cause if they are, I would have a few things to point out that would eliminate those two problems altogether."

Actually they are very real indeed. It is part of the core of what I am writing now. Were the things you wanted to point out what followed (mostly the nested EBCO) or is there still another useful trick in your bag ?

The nested EBCO is a neat trick (and that will indeed simplify the example given of my current code). Unfortunately, it's sort of a hack because you have to be lucky to find such other data and the relationship of the non-policy data to the policy is often far-fetch (if not inexistent), so it's a adhoc solution that is not always generalisable - and I usually want to avoid adhoc situations as much as possible as it makes the code more complex and very difficult to maintain.

[trantran]

On second thought, unless I am missing something, I think there is a flaw in your type erasure technique.
We have all those animals that walk, run, bark, etc...
Now, suppose we want to create an array of barking interface: so it will contain animal that barks and the other animal will have a default no_barking do nothing fct.
But to create this array, you will need to create as many wrappers as there are elements since each element will point to the wrapper (which itself points to the actual animal). That can be a significant memory cost (not to mention memory allocation time cost if this is repeated often).
Of course, one could say: why don't you just store in the array the animal itself, which would remove this problem?
Well, apart from that design to be less "clean", you could later have other objects, unrelated to animals (for example: door_bells) that barks and that you would want to include in the array.
Now if you use multiple inheritance, this is the same problem (even worse) since that memory is allocated already for all interfaces in each object.
However, if you use my "recursive subclass" technique you solve (?) the problem: you simply put in the array any object that contain the barking interface in its recursive base classes and you're done: zero memory cost (except for the initial virtual pointer common to all interfaces) and zero execution time.

[trantran]

Another question!

I have been fine-tuning my recursive inheritance to the point that I can simply define the class I want to insert in the inheritance chain simply like this:

template <typename...T> 
struct policy_name: T...{
 // code here
};

which of course can be simplified by using the preprocessor with:

#define POLICY (NAME) template<typename T...> struct NAME: T...

// which can be use like this:

POLICY (policy_name){
    // code here
};

However I try to avoid completely any pre-processing code (as far as possible!) so I would love to be able to avoid the above pre-processing code.
What I would idealy like is simply use existing structures and type:

inherit_recursively < existing_struct_1, existing_struct_2 /*,etc*/ > my_policies`

where existing_struct_1 are plain vanilla structure such as:

struct my_policy{
    // code
};

which I would be able to do IF I could find a way to transform at compile-time an existing structure into a template (like the above one) by using a template and metaprogramming.

I don't think it is possible, but given all the possibilities of C++11 and the boundless (and brain-wrecking!) imagination of C++ programmers, who knows?

Are you aware of any way to do that?

( Important note: I am not interested in a way to transform the recursively inheritable templatised policy described at the beginning into a chain using templates (I have that already), only a way to transform a plain-vanilla structure into that precise template form)

[mike_2000_17]

Actually they are very real indeed. It is part of the core of what I am writing now. Were the things you wanted to point out what followed (mostly the nested EBCO) or is there still another useful trick in your bag ?

No, the things I was referring to were not the things I mentioned afterwards. So, here they are.

Firstly, the idea of not keeping track of the size of the list is just really quite terrible, for these reasons:

• That information comes essentially for free, i.e., a simple increment on insertions, and decrement on removals.
• The memory cost of storing the size value is a constant cost (O(1)) on the container's size, which is already the size of two pointers (head, tail) and of the state of the allocator (if any), adding an integer to that is not a big deal (also, as long as it's within a single cache line (usually 64 bytes), size doesn't really matter). The only case where that memory overhead would matter is if you had a large number of small lists, in which case, you would never use a linked-list in the first place.
• Finding the size of a linked-list through traversal is so terribly inefficient (it thrashes the cache) that you would be better off disabling any size-query functions if the size is not being tracked.
• If you are using an ID instead of a pointer for the "next" node, then your allocator (pool) would have to keep track of the size anyways (to know when to allocate more space), and therefore, your two policies are not independent. And therefore, if one wanted to get the "minimal memory" option, then one would have to choose "size + ID" policies, making the "size vs no-size" policy even less relevant.

So, that's for the "size vs no-size" policy, which, in summary, I would say is not useful at all, you should just track the size, period.

As for the "ID vs pointer" policy, there are a few problems with that as well. First of all, this policy is really a matter of allocator policy (I assume you provide an allocator policy too, right?). It would be very difficult to sensibly separate this policy from the allocator policy, as it is essentially a refinement over the allocator policy.

Second, I'm not sure how much memory you expected to be able to save with this, the answer is at most 4 bytes per node (on most 64bit platform: ID will be 4 bytes, pointer will be 8 bytes). Because of alignment, you will not be able to shrink the ID any further (e.g., even if you use a short, it will still consume 4 bytes (2 bytes of padding for proper alignment)), and alignment might even bring the memory savings down to 0 (if aligned on 64bit boundaries).

Third, if you use IDs, then how will you translate them to pointers (to get to the next node)? I know this is simple, you just apply a pointer offset (e.g., base_ptr + id). Where it gets to be not so trivial is where are you going to store that base-pointer? Obviously, you would store that in your allocator (along with the size). But what about iterators? If you want to provide iterators that can traverse the list, those iterators will have to store, at least, the base-pointer and the ID of the current node, in order to translate the next ID to the next node. So, that further reduces the benefit of doing this (and it also introduces other issues, such as shared-state).

Finally, how are you going to deal with removals? This is a tricky problem, and there is no "free-lunch" here. There are a few options. For one, you could use a compact contiguous storage, meaning that each removal leads to a "rotate" operation to re-compact the contiguous storage of nodes, but this implies that every removal is not O(n) because not only do you have to re-compact the storage, you also have to update all "next ID" values. The other option is to use a non-compact storage, i.e., leaving "holes" in your storage. That solves the O(n) removal problem, but it leaves you with the problem of keeping track of where the holes are. There are number of ways to do this, but they all incur memory and run-time overhead. There is the Boost.Pool way. There are also other options, like the extension allocators provided by GCC.

I guess my point with this is that the "id vs pointer" policy really doesn't convey the correct idea here. This is not so much about whether individual nodes store next pointers or IDs, but about what storage strategy you use for the list as a whole. The typical options would be: node-by-node allocation (from the Allocator object), vector-like allocation (or deque), unrolled list, pooled allocation, etc.. all of which will lead to a particular appropriate choice for both "size vs no-size" and "id vs pointer" aspects.

So, you might provide the user with those policy options instead, which would constitute a single policy argument (in addition to the allocator argument). It's important, in general, to choose the correct formulation of your policies and make sure they are truly independent (not like "size vs no-size" and "id vs pointer", which are inter-dependent).

The nested EBCO is a neat trick (and that will indeed simplify the example given of my current code). Unfortunately, it's sort of a hack because you have to be lucky to find such other data and the relationship of the non-policy data to the policy is often far-fetch (if not inexistent), so it's a adhoc solution that is not always generalisable - and I usually want to avoid adhoc situations as much as possible as it makes the code more complex and very difficult to maintain.

On the contrary, it is a very generalizable solution. Here is a very common pattern when writing data structures:

// in some header: "detail/my_container_impl.hpp"

namespace my_lib {

namespace detail {

template < .... >
class my_container_base : public /* EBCO bases */ {

  /* ... all the "real" code ... */

};

};

};

// in the interface header: "my_container.hpp"

#include "detail/my_container_impl.hpp"

namespace my_lib {

template < .... >
class my_container {
  private:
    detail::my_container_base data_;

  public:

    /* .. public interface functions, forwarded to 'data_' .. */


};

};

This makes the my_container class template very clean from a user's perspective, for both documentation and diagnostics. There is no extra overhead with this in general, and it can be applied to all situations. The point is that the nasty implementation details, like EBCO contraptions or meta-programs, are hidden in the detail::my_container_base class, and will rarely surface in diagnostics or documentation. This is indeed a very general solution, in fact, I have rarely seen a production-quality data-structure implemented without this pattern, it's pretty much mandatory (to pass code reviews) as far as I'm concerned.

Now to the other discussion (about interfaces):

Now, suppose we want to create an array of barking interface: so it will contain animal that barks and the other animal will have a default no_barking do nothing fct.

Well, the variant of type erasure that I showed was not intended to be used that way. I was just making a point about non-intrusively adding dynamic dispatching to a class. Now, you moved the goal post to another problem, which requires yet another variant of the technique (similar to the demo I linked to in my previous post), which I'm happy to demonstrate.

But to create this array, you will need to create as many wrappers as there are elements since each element will point to the wrapper (which itself points to the actual animal).

Not quite. I have a few more tricks up my sleeve for that. The basic (non-owning) type erasure pattern can be implemented like this:

class AnyDoer {
  private:
    struct concept_ {
      virtual void doWork() = 0;
      virtual ~concept_() { };
      virtual concept_* clone() = 0;
    };
    template <typename Doer>
    struct model_ : concept_ {
      Doer* p_obj;
      model_(Doer* aPObj) : p_obj(aPObj) { };
      void doWork() {
        p_obj->doWork();
      };
      concept_* clone() {
        return new model_<Doer>(p_obj);
      };
    };

    std::unique_ptr<concept_> p_impl;

  public:
    template <typename Doer>
    AnyDoer(Doer& obj) : p_impl(new model_<Doer>(&obj)) { };

    AnyDoer(const AnyDoer& rhs) : p_impl(rhs.p_impl->clone()) { };
    AnyDoer& operator=(const AnyDoer& rhs) {
      p_impl.reset(rhs.p_impl->clone());
    };

    AnyDoer(AnyDoer&&) = default;
    AnyDoer& operator=(AnyDoer&&) = default;

    void doWork() {
      p_impl->doWork();
    };
};

With that, the container would store "AnyDoer" objects by value, but it is true that those objects are just wrapping a pointer to an object that contains a vtable pointer and a pointer to the original object (Doer). And yes, you have the dynamic allocation overhead there.

However, you can get rid of that extra indirection and that extra allocation by noticing that regardless of the actual type of the "Doer", the size of model_<Doer> is the same (two pointers). Therefore, because you know the static size of that object, you can store it statically, instead of dynamically, thus eliminating the extra indirection and dynamic allocation. Here is one way that trick can be done (non-owning):

class AnyDoer {
  private:
    struct concept_ {
      virtual void doWork() = 0;
      virtual ~concept_() { };
      virtual void clone_into(void*) noexcept = 0;
    };
    template <typename Doer>
    struct model_ : concept_ {
      Doer* p_obj;
      model_(Doer* aPObj) : p_obj(aPObj) { };
      void doWork() {
        p_obj->doWork();
      };
      void clone_into(void* ptr) noexcept {
        new(ptr) model_<Doer>(p_obj);
      };
    };

    struct dummy_doer {
      void doWork();
    };

    char data[sizeof(model_<dummy_doer>)];

    concept_* p_impl() noexcept { 
      return reinterpret_cast<concept_*>(data);
    };

  public:
    template <typename Doer>
    AnyDoer(Doer& obj) {
      // create the model in the data buffer:
      new(data) model_<Doer>(&obj);
    };

    AnyDoer(const AnyDoer& rhs) noexcept {
      rhs.p_impl()->clone_into(this->data);
    };

    AnyDoer& operator=(const AnyDoer& rhs) noexcept {
      p_impl()->~concept_();
      rhs.p_impl()->clone_into(data);
    };

    AnyDoer(AnyDoer&&) = delete;
    AnyDoer& operator=(AnyDoer&&) = delete;

    ~AnyDoer() {
      p_impl()->~concept_();
    };

    void doWork() {
      p_impl()->doWork();
    };
};

The owning version would simply require substituting the raw pointer for a unique-pointer (or shared, if needed), and a few modifications in the cloning facilities.

With this scheme, the overhead is minimal. For each object, you have a vtable pointer and a pointer to the actual object. In a standard OOP solution, you would have a pointer to the (polymorphic) object, which itself will have a vtable pointer. In other words, the vtable pointer overhead is simply moved from being a part of the object to being paired-up with the object pointer externally. And depending on the usage, this may or may not be an advantage overall.

Of course, one could say: why don't you just store in the array the animal itself, which would remove this problem?
Well, apart from that design to be less "clean", you could later have other objects, unrelated to animals (for example: door_bells) that barks and that you would want to include in the array.

Yeah, obviously, storing the animal (most-derived) objects themselves in the container is not an option, from a polymorphic point of view. Clearly, that's not a viable solution.

Now if you use multiple inheritance, this is the same problem (even worse) since that memory is allocated already for all interfaces in each object.

Yes, that's clear. The type erasure technique that I just showed moves the storage of the vtable pointer (for each interface) from a per-object basis to a per-usage basis. In other words, whenever you want to dynamically use an object via a particular interface, you pair it up with a vtable pointer to perform the dispatching, i.e., it's on a per-usage basis. In the multiple inheritance version, every object is already packaged with all the vtable pointers you could potentially need somewhere. This may or may not be a good thing, depending on the situation (Are you always using all the interfaces? Do you use some of them, some of the time? etc..).

However, if you use my "recursive subclass" technique you solve (?) the problem: you simply put in the array any object that contain the barking interface in its recursive base classes and you're done: zero memory cost (except for the initial virtual pointer common to all interfaces) and zero execution time.

That's where there is a hick-up. The problem here is that your "barking" interface is not a class, but a class template which takes, as argument, a whole sequence of other possible interfaces (that are recursively subclassed). In other words, one object might derive from the Barking< Jumping, TailWagging > class, while another derives from the Barking< Biting, Digging, Jumping, TailWagging > class. You cannot create a container that will hold all "barking" objects with this type of recursive subclassing solution, unless you impose some very strict ordering of the interfaces (which is not a viable general solution). That's the whole reason why I brought up the type erasure technique in the first place, as an alternative to the multiple inheritance solution, because, for virtual interfaces, your recursive subclassing cannot work.

For non-virtual interfaces (e.g., GP-style interfaces), your solution is perfectly reasonable.

[mike_2000_17]

I have been fine-tuning my recursive inheritance to the point that I can simply define the class I want to insert in the inheritance chain simply like this:

    template <typename...T> 
    struct policy_name: T...{
     // code here
    };

But... that's not a recursive inheritance solution. That's the multiple inheritance solution. There must be some kind of a confusion here.

What I would idealy like is simply use existing structures and type:

 inherit_recursively < existing_struct_1, existing_struct_2 /*,etc*/ > my_policies

where existing_struct_1 are plain vanilla structure such as:

 struct my_policy{
      // code
 };

Well, assuming you are aiming for a multiple inheritance version, then, you can use the technique I demonstrated a few posts back. It went like this:

template <typename... P> struct policies;

template <typename P, typename... T> 
struct policies<P, T...> : public P, 
                           public policies<T...> { };

template <typename P> struct policies<P> : public P {};
struct policy12 {
    // code...
}

// repeat for all desired policies with appropriate code

// and use like this:
policies<policy12, policy24 /*etc...*></policy12> my_chosen_policies;

That gives you exactly that effect, except that it doesn't implement the recursive inheritance scheme.

For a semi-recursive version, this might be the best approximation:

struct NullTerminatingTrait {
  template <typename... Tail>
  struct bind { };
};

template <typename... Args>
struct AnimalTraits;

template <>
struct AnimalTraits<> { };

template <typename T, typename... Tail>
struct AnimalTraits<T, Tail...> : T::template bind< Tail..., NullTerminatingTrait > { };

template <typename Derived>
struct AnimalTrait {
  template <typename Next, typename... Tail>
  struct bind : Derived, Next::template bind< Tail... > {};
};


struct Walker : AnimalTrait<Walker> {
  void walk() {
    // code to walk.
  };
};

// same for others traits.


// use as follows:
AnimalTraits<Walker, Barker /*etc...*></Walker> my_traits;

As for a purely recursive inheritance solution, I'm afraid you are out of luck. I don't see how this could be possible at all.

IF I could find a way to transform at compile-time an existing structure into a template (like the above one) by using a template and metaprogramming.

The closest thing to that is that little trick in my last version (with the CRTP AnimalTrait template), or something similar. But, otherwise, it is completely impossible to "transform a class into a template". This is a one-way street. Templates are instantiated and become classes, it doesn't work the other way, it simply cannot, period. It is even more impossible if your aim is to actually insert an additional (recursive) base-class onto the class, that's insanely beyond the realm of what is possible.

[trantran]

Let's go step by step:

1) list size

First the idea of not keeping track of the size is just terrible

Of course, it depends!
You neatly list the case where it is not appropriate in a typical use of a list, certainly not in the type of list I had allured to, mainly the case where you have thousands of list most of which are empty. In what circumstance would you encounter typically this? In a hash table, the list being used to deal with collisions.
So I do avoid to keep the useless size in this situation and I am quite happy with the result, but I thought you might have another trick that would allow me to have a policy with / without size without using multiple inheritance (because of vs2013 lack of EBCO) and without using my recursive inheritance which up to now still remains the only way to do this when there are many similar policies at the same time.

2) ID vs pointer

Second I'm not sure how much memory you expected to be able to save with this, the answer is at most 4 bytes... because of alignment

Wrong. Maximum is 7 bytes if you use a character index and you use the #pragma pack (1) directive. But typically 4 bytes saving will be the case. That is significant in my situation for many other reason it would be too long and totally digressive to explain.

All the rest: memory allocation, location of base ptr, etc I have dealt very successfuly with and again it is too long and irrelevant here to explain. And yes in my case (because of pooled allocation) "size vs no-size" and "id vs pointer" ARE independent.

3) ECBO hack

Still even if you hide it in the implementation, the devil remains in the implementation which will be more difficult to maintain because it is not logic to associate unrelated data to other functions just to do a workaround because of vs2013 non-ecbo.

4) Type erasing example

Noting to add here. I agree the type erasing is a very useful technique. Thanks!

5) Accessing base classes in recursive inheritance

That's where there is a hick-up. The problem her is that your "barking" interface is not a class, but a class template...

Touché. You've a very good point that I had not thought about. The example I gave is just therefore plain wrong.

6) Is the recursive inheritance still useful?

Yes.
a) it still remains remains the only solution for multiple policies in vs2013 if one wants to benefit from ECBO. If you have any other solution for this, I'd be very happy to learn about it
b) there is another use I always had in mind but never wrote about: implementation of a variant class. But I am not quite sure about this yet: I have to give it more thoughts.

7) Defining classes to make them ready for my recursive inheritance template

Me:
I have been fine-tuning my recursive inheritance to the point that I can simply define the class I want to insert in the inheritance chain simply like this:

         template <typename...T>
         struct policy_name: T...{
         // code here
         };

You:
But... that's not a recursive inheritance solution. That's the multiple inheritance solution. There must be some kind of a confusion here.

Yes there is a confusion but it is not where you think it is.
I meant that if someone has a class defined in the way above, than I can use that class as is as argument to a recursive inheritance template which transform a list of such template class arguments into an instantiation where each of the class is part of a recursive single inheritance chain.
I did not meant that the class above itself was recursive (obviously).

8) Transforming a class into a template

it is completele impossible to "transform a class into a template"

That's quite unfortunate but that's why I thought too. I will therefore use my pre-processor directive (as shown in previous post) as syntactic sugar.

[trantran]

Note: the very poor formating above is because it was the only way I could post it since a stubborm "incorrect format for code" bug was blocking the posting otherwise

[mike_2000_17]

You neatly list the case where it is not appropriate in a typical use of a list, certainly not in the type of list I had allured to, mainly the case where you have thousands of list most of which are empty. In what circumstance would you encounter typically this? In a hash table, the list being used to deal with collisions.

I guess you have something specific in mind, and if you can justify your choices, then great! No harm done in raising questions.

Generally, I despise linked-lists. Every time I've included them in the possible options for some performance-sensitive code, the comparative benchmarks releaved that they were by far the worst choices. At this point, I've pretty much given up on ever using them.

I use linked-lists sometimes in non-performance-critical code when I want a self-managing list (i.e., just the chain, not the top-level class), which is also why it's used for hash table buckets.

Anyhow, I'm just not very impartial when judging linked-lists.

So, if your application is for buckets of a hash table, then why would you not just use the chain of nodes, without the "list" class, as it is normally done.

I thought you might have another trick that would allow me to have a policy with / without size without using multiple inheritance (because of vs2013 lack of EBCO) and without using my recursive inheritance which up to now still remains the only way to do this when there are many similar policies at the same time.

Why do you want me to provide an alternative to the recursive inheritance solution? We already established, a few posts back, that it is a perfectly good solution for this particular scenario (policy classes, not for interfaces). I don't tend to look for alternatives to an already good solution. That is, unless you have a different requirement that this recursive inheritance solution doesn't meet?

Wrong. Maximum is 7 bytes if you use a character index and you use the #pragma pack (1) directive.

Well.. I didn't consider doing that... I mean... the idea of violating the native memory alignment of the platform in "active" memory would never cross my mind. I hope you can benchmark this to justify it.

All the rest: memory allocation, location of base ptr, etc I have dealt very successfuly with and again it is too long and irrelevant here to explain. And yes in my case (because of pooled allocation) "size vs no-size" and "id vs pointer" ARE independent.

Alright then, you seem to have things under control. Your broader context / application must be quite different from what I have in mind (i.e., I was just defaulting to the "reimplementing std::forward_list" kind of situation / application).

Still even if you hide it in the implementation, the devil remains in the implementation which will be more difficult to maintain because it is not logic to associate unrelated data to other functions just to do a workaround because of vs2013 non-ecbo.

Implementation details for performance-sensitive data-structures are always messy. There's just no way to avoid it. The best you can do is make sure to contain the mess (so that it doesn't get out to the users), and to comment the heck out of it (if you use a "hack", explain it in a comment block). The reality is, the code just can't be pretty all the way down to where the rubber meets the road.

a) it still remains remains the only solution for multiple policies in vs2013 if one wants to benefit from ECBO. If you have any other solution for this, I'd be very happy to learn about it

True.

b) there is another use I always had in mind but never wrote about: implementation of a variant class. But I am not quite sure about this yet: I have to give it more thoughts.

How would it be different from the boost::variant class? It seems that that implementation is as good as it gets, no? And I can't see EBCO factoring in anywhere.

I meant that if someone has a class defined in the way above, than I can use that class as is as argument to a recursive inheritance template which transform a list of such template class arguments into an instantiation where each of the class is part of a recursive single inheritance chain.
I did not meant that the class above itself was recursive (obviously).

Well... that makes me think of a very obvious solution, what about this:

struct dummy { };

template <template <typename> class... Args>
struct policies;

template <template <typename> class P, template <typename> class... Args>
struct policies<P, Args...> : P< policies<Args...> > { };

template <template <typename> class P>
struct policies<P> : P<dummy> { };

template <typename Base>
struct policy12 : Base {
  //.. code
};

template <typename Base>
struct policy24 : Base {
  //.. code
};

// .. so on..

Wow... I feel extremely stupid for not having thought of that solution before. I think this is syntactically much nicer than any of the other version of the recursive inheritance solution. But still, it's the same solution.

Note: the very poor formating above is because it was the only way I could post it since a stubborm "incorrect format for code" bug was blocking the posting otherwise

I fixed it. It was due to have most than a single starting space after a quote. In other words, you cannot write:

>   this is a quote

You have to write:

> this is a quote

because the parser wants to think that it's a code block within a quote (which is also not working very well), or something like that.

[trantran]

So I think we've covered everything on the subject.

Your recursive template came out practically the same as my last fine-tuned version, the only difference being that you can actually simplify your code further by getting rid of the dummy structure and the initial declaration and modifying slightly your template argument. Like this:

template <template <typename...> class P, template <typename...> class... Args>
struct policies : P< policies<Args...> > { };

template <template <typename...> class P>
struct policies<P> : P<> { };

template <typename... Base>
struct policy12 : Base... {
//.. code
};

template <typename... Base>
struct policy24 : Base... {
//.. code
};