dynamic memory allocation w/o new

hey all...

i'm having issues with a data structures assignment and could use some help if anyone has some insight. the short version is that i need to dynamically allocate space for a stack based on user input at run time, but i'm unable to use new/malloc or any other operator for space in the heap...apparently we're supposed to use only the stack. i've been researching for a while, and the best i can come up with are vectors. does anyone know if they use heap memory, or have any other ideas? any help would be greatly appreciated.

thanks,
brian

vectors use memory from the heap. I don't know off the top of my head how to dynamically allocate memory from the stack. Infact, that doesn't even make sense. I'd reread that assignment of yours... or perhaps question your teacher's credentials.

You could do things like this but you can't allocate from the stack if I recall.

Code:

#include <iostream>
#include <cstdlib>

int main()
{
    int input;
    
    std::cout<<"Enter the number:";
    std::cin>>input;
    
    int array[input];
    
    for(int i = 0; i < input; i++)
    {
        array[i] = rand() % 10;
    }
    
    for(int i = 0; i < input; i++)
    {
        std::cout<<array[i]<<std::endl;
    }
    
    return 0;
}

The only way aside from doing it manually would be something like the nonstandard alloca function. It dynamically allocates memory but stores it in the current stack frame instead of on the heap. That's the only in-core solution I can think of. If you're allowed to use files, you can come up with something dynamic, but it'll be slow.

Unless this is some bizarre exercise in creative problem solving, I'd wonder about your teacher too.

Code:

std::cout<<"Enter the number:";
std::cin>>input;
int array[input];

Some compilers may allow you to do this, but it's non-standard IIRC

i need to dynamically allocate space for a stack based on user input at run time, but i'm unable to use new/malloc or any other operator for space in the heap...apparently we're supposed to use only the stack.

The only idea that comes to mind is what prog-bman posted. I think it's called a variable length array, but it's only standard in C. You can do it in C++ if your compiler supports it, for example any of the gcc compilers.

All the other C++ STL classes like vector and stack are going to be using the heap internally.

'allocating' is simply the act of requesting ownership of a managed resource. a memory manager could aquire data from local stack space, the heap, or even both - from the point of view of the application it's just somewhere to store something. and when implementing a memory manager in c++ don't forget to invoke constructors/destructors properly - otherwise *very bad things* will happen...

Originally Posted by swoopy

The only idea that comes to mind is what prog-bman posted. I think it's called a variable length array, but it's only standard in C. You can do it in C++ if your compiler supports it, for example any of the gcc compilers.

As a matter of fact, variable length arrays are not supported by C++ at all. Furthermore, it is only supported in the C standard of 1999 (C99) and NOT in the 1989 C standard (C89).

Some C++ compilers will support VLA as an extension (probably if they are also C99 compilers). But it is definitely not valid C++. There are relatively few compilers that support C99.

And, even in C99, the implementation of a VLA makes use of dynamic memory behind the scenes with a number of compilers.

There's something to be said about doing it manually by using inline assembly to fiddle with your stack. That's not portable, but the problem sounds either misinterpreted or nonportable to begin with.

Code:

#include <iostream>

int main()
{
  int size, n;
  int *stack;

  std::cout << "Enter a size: ";
  std::cin >> size;

  n = size * 4;

  __asm {
    sub  esp,n      ; Allocate n dwords
    mov  stack,esp  ; Save the starting addr
  }

  for (int i = 0; i < size; i++)
    *stack++ = i;

  for (int i = 0; i < size; i++)
    std::cout << *--stack << '\n';

  __asm add  esp,n; // Fix the stack
}

thanks for the insight everybody...

this prof is an ex-d.o.d./aerospace guy and i think his point here is that he's trying to get us to see the limitations of c++ and use ada instead. apparently ada is able to dynamically allocate to the stack on the fly and is much faster than using the heap...apparently useful in real time situations, like trying to evade surface radar while flying an airplane. i think, at least for this particular assignment, i'll stop bucking the system and just use ada.
-b

Ah, your prof is an ada zealot. zealots of any language actually do more harm than good. Like C++, ada has both it's strengths and weaknesses.

If he's arguing that you should use ada for realtime applications because allocation on the stack is faster, then he's wrong. In hard real time applications, one of the basic guidelines is not to use dynamic memory allocation in any form.

The notion of stack and heap are a little different in ada than they are in C++ (as the Ada runtime does things differently) as well.

All auto variables in C++ are allocated (in principle anyway) on the stack. If the dynamically allocated something doesn't have to be contiguous ......

Code:

// untested, intended to illustrate approach

struct Node
{
    Node *next;
    SomeType data;
    Node() : next(0) {};
};

void PrintStack(Node *stack)
{
      while (stack != NULL)
      {
            // print out stack->data
            stack = stack->next;
      } 
}

typedef void ((*func)(Node *));

void ActInternal(func function, int size, Node *first, Node *last)
{
     if (size == 0) 
        function(first)
     else
     {
          Node here;
          last->next = &here;
          // do something to populate here.data
          ActInternal(function, size-1, first, &here);
     }
}

void Act(func function, int size)
{
     Node first;
     // do something to populate first.data
     ActInternal(func, size-1, &first, &first);
}

int main()
{
    Act(PrintStack, 25);
}

This code will mean that PrintStack will see a stack of 25 dynamically allocated elements (albeit as a linked list) that are on the stack.

<applause> Spot on grumpy!
And a really neat code answer as well