Encapsulated array - size defined by user at runtime

**MyDoom** · 09-11-2013

I'm creating a small program for my data structures class that simulates a critical system. Thus, using heap memory is not an option, as speed is important. It's a basic stack implementation that allows the user to decide the type and size of the stack. So, for example, the user could tell it to use integers with a total allocation of 500 units.

I need to encapsulate an array inside a Stack class that uses a template, such as this:

Code:

template <typename T, std::size_t size>
class Stack
{
public:
    Stack(void);
    void push(T value);

private:
    T m_stack[size];
    int top;
};

So I can use it like so:

Code:

Stack<int, 10> stack;

However since templates are compile-time only, I can't allow the user to define the size in the second template argument. I can't use any STL containers such as a vector. I'm not allowed to use new, malloc(), or anything that allocates memory on the heap, yet the array must be dynamically allocated. I don't think using a maximum size for the array inside the class is allowed, or a VLA.

Is there any such method to accomplish this? I've researched this extensively, and asked my professor but he is very good at avoiding answering questions directly. In fact, we are encouraged to use Ada, since this is much easier in Ada, but I refuse, I must use C++.

**Elkvis** · 09-11-2013

using heap memory has zero impact on performance, except at the moment that it's allocated or freed. if this is something that is happening only once in the program, you can probably ignore the performance penalty.

**grumpy** · 09-11-2013

You're indulging in premature optimisation. The relative performance of accessing different types of memory (say heap and stack) are determined by things outside program control (how the processor manages caches and pipelines, the strategy by which an operating allocates stack space for your program, etc etc).

Overloading of operators new and delete can provide an option.

**brewbuck** · 09-11-2013

Originally Posted by MyDoom

I'm not allowed to use new, malloc(), or anything that allocates memory on the heap, yet the array must be dynamically allocated.

It's impossible to dynamically allocate something if you are not allowed to dynamically allocate anything. The problem is impossible.

EDIT: A pseudo-solution would be to allocate the thing to a size which is larger than the largest possible stack -- i.e. artificially impose a limit on how large the stack can be.

**MyDoom** · 09-11-2013

Yes, as long as the heap memory is allocated only once, it shouldn't matter, but using the new keyword at all is not an option. I found an old thread here (you also posted here, grumpy), which I strongly believe was started by a student taking the same professor I currently have. Indeed, he is an Ada zealot and ex-DoD/Aerospace guy.

I think this restriction is unrealistic and goes against efficient C++ convention, at least modern day convention. I may end up just using Ada and later C++ for fun, with proper heap allocation.

**Elysia** · 09-11-2013

If you can't use new, then the only option is to use the (for now) non-standard extension VLA. I don't know any other compiler than GCC that supports it.
Still, this is silliness. Be it stack or heap, memory is memory. I don't see why you are not allowed to use dynamic memory? If it's speed you're concerned about, you should use a profiler. Using dynamic memory can be slow, but it won't matter if the critical path is elsewhere.
You can also use custom allocators for STL containers so you can use them without them directly calling new.
Though, for embedded systems, I would probably say Ada is better. It's much simpler to analyse, I believe. Don't take it as a fact, however.

**Elkvis** · 09-11-2013

whether you're using C++ or ADA, they'll both be using dynamic memory for this task. it's really just a question of language semantics and implementation.

**brewbuck** · 09-11-2013

Originally Posted by Elysia

Though, for embedded systems, I would probably say Ada is better. It's much simpler to analyse, I believe. Don't take it as a fact, however.

Simpler analysis is one of the reasons dynamic memory is commonly avoided in embedded systems. Allocating memory at runtime makes it difficult to make provable statements about memory use. Also, you can't leak something that wasn't allocated.

**rcgldr** · 09-11-2013

Originally Posted by MyDoom

I'm not allowed to use new, malloc(), or anything that allocates memory on the heap, yet the array must be dynamically allocated. I don't think using a maximum size for the array inside the class is allowed, or a VLA.

Is there any such method to accomplish this?

You could have a program that inputs the type and count, generates source code that includes the template, compile and link the generated source code, then spawn a process to run the generated program.

Some simple embedded systems rely on compile time defines to pre-allocate memory, and do not implement any type of dynamic memory at all, other than some type of structure like an array or linked list of pointers to buffers uses as queues. For example, in the case of some operating systems for ARM embedded processors, the number of tasks, buffers, inter-task messages, ... , are all compile time defines.

**vart** · 09-11-2013

you can overload new

use your own pool memory - allocated once at the start-up according to users settings (for example enough to store 500 ints)

Then your Stack will reside in this pool

your overloaded new will be nothrow (for example) and return memory chunk from the pool when available or null when not enough memory is left in the pool
delete will return memory to this pool

**iMalc** · 09-12-2013

Originally Posted by MyDoom

I can't use any STL containers such as a vector. I'm not allowed to use new, malloc(), or anything that allocates memory on the heap, yet the array must be dynamically allocated. I don't think using a maximum size for the array inside the class is allowed, or a VLA.

VLAs only exist in C, not C++, and at any rate some compilers such as Microsoft's do not support a new enough version of the C standard to have them at all.
Given those ridiculous restrictions, the only thing I imagine you are left with is alloca, assuming your compiler supports it properly.
That does not allocate on the heap, and does allocate dynamically.

**grumpy** · 09-12-2013

Originally Posted by MyDoom

Yes, as long as the heap memory is allocated only once, it shouldn't matter, but using the new keyword at all is not an option. I found an old thread here (you also posted here, grumpy), which I strongly believe was started by a student taking the same professor I currently have. Indeed, he is an Ada zealot and ex-DoD/Aerospace guy.

I think this restriction is unrealistic and goes against efficient C++ convention, at least modern day convention. I may end up just using Ada and later C++ for fun, with proper heap allocation.

If you want dynamic memory allocation in C++ without using the new keyword, then use C's malloc() function. Strictly speaking, malloc() is deprecated in C++, but deprecated is not the same as non-standard (at least, not yet). But it does allocate on (what is often described as) the heap.

But, frankly, I'd find another professor. Ada is a terrific and vastly underappreciated language in industry, IMHO, and certainly worth learning. But trying to advocate its advantages over C++ in this misleading manner does nobody a service.

The purpose of teaching data structures is to teach useful techniques related to data structures, and effective techniques are generally workable in any programming language. The purpose is not to sneak in edge cases in an attempt to nudge students toward a particular programming language.

**Elysia** · 09-12-2013

Originally Posted by iMalc

VLAs only exist in C, not C++...

Yet. It is voted into C++0y (C++14).

**jimblumberg** · 09-12-2013

It is voted into C++0y

Are you sure? I believe it's been proposed, but that doesn't equal approval.

Jim

**Elkvis** · 09-12-2013

since the new standard is still far from final, it's fair to say that nothing has been approved yet, but my understanding is also that is a planned improvement for the next C++ standard.

Thread: Encapsulated array - size defined by user at runtime

Thread Tools

Search Thread

Display

Encapsulated array - size defined by user at runtime

Similar Threads

Arrary with user defined size

Array Help Please (user defined size)

need to read a User defined file during runtime

Arrays of user-defined size?