C++ allocating memory using array

concerning this question on how to allocate memory without using new or malloc, suppose I have a structure linked list

struct stack {
 string info;
 stack next*;

};

The answer provided says use global byte array. How would I implement an linked list by allocating t开发者_StackOverflow社区o global byte array?

One way is to have a memory pool declared in data segment and have your own memory allocation function.

char myMemoryPool[10000000]; // global variable (can be enclosed in namespace)

And you have to write your own memory manager:

void* MyMemoryAlloc (size_t SIZE)
{
 //... use SIZE
}

Usage:

A* p = (A*)MyMemoryAlloc(sizeof(A) * 3);

Or more precisely,

template<typename T>
T* MyMemoryAlloc (unsigned int UNITS)
{
//... use (sizeof(A) * UNITS)
}

Usage:

A *p = MyMemoryAlloc<A>(3);

Instead of a pointer, use an index into the array. (Actually, a pointer is nothing but an index into the byte array representing all virtual memory). You'll have to keep track of which indexes (or ranges of indexes) are used.

This is called a pool-based allocator.

It's not too clear what the question is supposed to mean. You could just declare a large block of stack, and use them, perhaps using a bit vector of some sort to keep track of which ones are free or not, or simply keeping the free elements in their own list (since you have a pointer in the type). A more generic solution (not counting on the pointer) would involve a union:

union StackPoolElement
{
    StackPoolElement* next;
    double dummyForAlignment;
    unsigned char data[sizeof(Stack)];
};
static StackPoolElement pool[10000];

You can then overload operator new and operator delete in Stack to allocate from this pool. (But of course, that's using new and delete. Which is what makes the question so stupid; a generic solution, which doesn't depend on the presence of a pointer in the object, will need some form of new to initialize the object.)

The one thing that you can't do is just declare a global byte array, since there is no guarantee that it will be correctly aligned (and I've used more than one compiler where it wouldn't be). If you want a byte array, it must be in some sort of a union to guarantee sufficient alignment. (On all of the machines I know, adding a double to the union is sufficient. But it's not guaranteed either.) And if you're using a byte array, you still need some form of new to construct your objects; either you overload operator new and operator delete in your class, to allocate using the byte array (and then allocate instances of the class using new and delete, as normal), or you use some form of placement new.