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 to 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);
MyMemoryAlloc contains a memory manager written by you, which allocates memory from the global variable and also releases it when something like MyDealloc is called. 1st version of the MyMemoryAlloc() is equivalent of malloc, which returns a void* raw pointer and 2nd version is typesafe version like new/new[].
myMemoryPool is correctly aligned. And he'll still need new in order to construct the objects.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.
struct stack in the question appears to have a member of type std::string, and THAT uses new (not even placement new) extensively. If indirect use of placement new isn't prohibited, one could use std::array or std::vector with a custom allocator in order to construct the objects.