This is a solution to a problem posted on linkedin STL/Multithreading group.

(the link is here but you need a linkedin account and join that group in order to view the post).

However, the problem to resolve is described here:

.... 
.... 

class A 

class B 

class C 
........ 

Class a { 

A *a 

B *b 

C *b 

}; 

Now, Class a is not using all A,B, C at the same time .....
I have around 40 forward declarations... 
Is possible to optimize it somehow..
so, I can declared pointer to class on need bases instead 
of wasting memory for pointers to all 40 odd classes?

Posted by a Firmware Developer Engineer, so really an embedded system can have memory constrained.

As I understand the question, I make the following assumptions:

1. actual objects can change during execution: runtime constructor/destructor of objects, it’s like a small dynamic container
2. all classes are unrelated, so inheritance cannot be a choice by design (or at the cost of refactoring all 40 classes). Or, however, at the cost of an eavy interface refactoring.
3. objects are “heavy” for the (embedded?) system (looks like some specific resource manager, when ctor and dtor are critical operation to make only iff they really needed): insertion/deletion are not very frequently
4. have to maintain a limited number of instantiated objects at the same time, say N, subset of say M different classes
5. you need a maximum of one instance of each class, no more
6. memory constraints: from the input case: sizeof(40 ptr) = 40 * 4 bytes=160bytes –> you consider it too much

(as turn out later, the need to compact this structure is due to the number of instances, millions, so it would be a great goal to save even just 50%).

union could be a solution for your memory constraints, allocating as much object ptr as you need. But for every ptr you then need a selector to store which class the actual pointer is, and fill your code with a lot of switch/case statements for different code-path. Sounds like old plain C.

A more elastic solution could be, if you use N<<40 (call M) max different pointers at the same time, use a small 40 uchar look-up table T to store index to a N slots ptr array (S).Some example:

• M=40, N=6 memory footprint will be: 6*4+40*1=64 bytes instead of 160.
• M=40, N=3 memory footprint 3*4+40*1=52 bytes instead of 160: more than 70% off.
• This solution has the same memory footprint if you needs 30 objects ptr (30*4+40=160 bytes).

Obviously you can optimize the T table too: using bitset you can save a few bytes more.

The solution #1

• Every class you want to use must inherit from a base class (Int2Type) and use a unique integer ID, the position in the T table. The class is a pure syntactical sugar, so no extra-cost in storage if you use it as a base class
• refactor the old code is really easy. Look the code. Another solution can externalize the type –> int conversion, making absolutely no change in old code
• The current solution can be utilized for up to 254 different classes. You can change this behaviour using another type instead of unsigned char, or maybe make it a template
• Performance considerations:
  • requesting a ptr have cost two to 2 small-tables
  • you can amortize this access cost by storing the reference obtained
• The syntax for accessing each class is very easy and straightforward: container.get<CLASS>.doAnything()
• You can put any sort of class in the container, and general polymorphism can be applied too
• If you have subset of classes and only one object instance for each subset will exist at the same time, you can put the same ID value for the classes. Obviously you need polymorphism in that case. For example: class A : public Base, public Int2Type<10> class B : public Base, public Int2Type<10> class C : public Base, public Int2Type<10> …. S.get<A>.doAnything()

This is a schema describing a possible state of the container:

As you can see, in the example two classes (A1 and A2) have the same parent A class and share the same T position, so only one instance of the two classes could be put in the structure at a time.

This is the code:

template <int I>
struct Int2Type			
{ enum { value = I }; typedef Int2Type<I> type; };

template <typename T> 
static int getIndex()	
{ return T::value; }

template <int MAX_CLASSES,int MAX_OBJ_SLOTS>
class CDynamicContainer
{
public:
	enum { FREE_SLOT = 0xff};
	enum { max_classes_object=MAX_CLASSES};
	enum { max_object_slots=MAX_OBJ_SLOTS};

	unsigned char LookUp[MAX_CLASSES];
	void * S[MAX_OBJ_SLOTS];
	CDynamicContainer()
	{
		memset (&LookUp,FREE_SLOT,sizeof(LookUp));
		memset (&S,0,sizeof(S));
	}
	~CDynamicContainer ()
	{
		// remember to free stuff if needed
		for (int i=0;i<MAX_OBJ_SLOTS;i++)
			if (!S[i]) delete S[i];
	}

	template <class T>
	void push (const T * obj)
	{
		alloc_slot (getIndex<T>(),(void*)obj);
	}

	template <class T>
	void remove ()
	{
		free_slot (getIndex<T>());
	}

	// remove and free object
	template <class T>
	void remove_and_delete ()
	{
		T * p=&get<T>();
		free_slot (getIndex<T>());
		delete p;
	}

	template <class T>
	bool isAvail ()
	{
		return LookUp[getIndex<T>()]!=FREE_SLOT;
	}

	template <class T>
	T& get()
	{
		return *((T*)get(getIndex<T>()));
	}

	void dump ()
	{
		for (int i=0;i<MAX_OBJ_SLOTS;i++)
		{
			printf ("%d : 0x%x\n",i,S[i]);
		}
	}

private:
	void alloc_slot (int class_type, void * ptr)
	{
		assert (T[class_type]==void_slot);
		for (int i=0;i<MAX_OBJ_SLOTS;i++)
			if (!S[i])
			{
				S[i]=ptr;
				LookUp[class_type]=i;
				return;
			}
		//ERROR: rethink max slot size
		assert (false);
	}

	void free_slot (int class_type)
	{
		assert (LookUp[class_type]!=void_slot);
		S[LookUp[class_type]]=NULL;
		LookUp[class_type]=FREE_SLOT;
	}

	void * get (int class_type)
	{
		assert (LookUp[class_type]!=FREE_SLOT);
		return S[LookUp[class_type]];
	}

};

struct A : public Int2Type<0>
{
	A ()				{}
	void whoami ()		{printf ("Class A\n");}
};

struct B : public Int2Type<1>
{
	void whoami ()		{printf ("Class B\n");}
};

struct C : public Int2Type<2>
{
	void whoami ()		{printf ("Class C\n");}
	void myspecific()	{printf ("Do anything a C class must do\n");}
};

struct D : public Int2Type<3>
{
	void whoami ()		{printf ("Class D\n");}
	void myspecific()	{printf ("Do anything a D class must do\n");}
};

void main ()
{
	CDynamicContainer<40,3> s;
	printf ("sizeof container= %d instead of %d\n",
		sizeof(s),
		s.max_classes_object*sizeof(void*));
	s.push (new A());
	printf ("A is available? %s\n",s.isAvail<A>()?"YES":"NO");
	s.push (new B());
	printf ("C is available? %s\n",s.isAvail<C>()?"YES":"NO");
	s.push (new C());
	printf ("C is available? %s\n",s.isAvail<C>()?"YES":"NO");
	s.get<A>().whoami();
	s.get<B>().whoami();
	s.get<C>().whoami();
	s.get<C>().myspecific();
	s.remove_and_delete<C> ();
	s.push (new D());
	printf ("C is available? %s\n",s.isAvail<C>()?"YES":"NO");
	// Only one time indirection penalty
	D & DRef = s.get<D>();	
	DRef.whoami ();
	DRef.myspecific ();
}

This is the output of the example:

sizeof container= 52 instead of 160
 A is available? YES
 C is available? NO
 C is available? YES
 Class A
 Class B
 Class C
 Do anything a C class must do
 C is available? NO
 Class D
 Do anything a D class must do

The class it’s obviously not complete, only a start point.

But enough to make some further consideration:

You could:

• insert exception handling, maybe using a define to switch it off
• make copy ctor/assign operator
• use the new move semantics
• externalize the Type-2-int, to remove the inheritance
• compact the index type, using compile-time bitset shift, to optimize further the memory footprint of the look-up table. In this case, 7 bit instead of 8.
• multithreading support
• if objects are delete/insert in the structure very frequently, maybe the search cost in the slot_alloc function could be prohibitive. In this scenario, an hashmap could play better with key equal to class::value.