Like Tree3Likes

Encapsulated array - size defined by user at runtime

This is a discussion on Encapsulated array - size defined by user at runtime within the C++ Programming forums, part of the General Programming Boards category; I'm creating a small program for my data structures class that simulates a critical system. Thus, using heap memory is ...

  1. #1
    Registered User MyDoom's Avatar
    Join Date
    Jul 2013
    Posts
    9

    Encapsulated array - size defined by user at runtime

    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++.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    2,391
    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.
    Code:
    namespace life
    {
        const bool change = true;
    }

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,285
    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.
    Right 98% of the time, and don't care about the other 3%.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by MyDoom View Post
    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.
    iMalc and antred like this.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Registered User MyDoom's Avatar
    Join Date
    Jul 2013
    Posts
    9
    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.

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,587
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Oct 2006
    Posts
    2,391
    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.
    Code:
    namespace life
    {
        const bool change = true;
    }

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by Elysia View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,283
    Quote Originally Posted by MyDoom View Post
    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.

  10. #10
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by MyDoom View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,285
    Quote Originally Posted by MyDoom View Post
    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.
    MyDoom likes this.
    Right 98% of the time, and don't care about the other 3%.

  13. #13
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,587
    Quote Originally Posted by iMalc View Post
    VLAs only exist in C, not C++...
    Yet. It is voted into C++0y (C++14).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Registered User
    Join Date
    May 2010
    Posts
    2,740
    It is voted into C++0y
    Are you sure? I believe it's been proposed, but that doesn't equal approval.

    Jim

  15. #15
    Registered User
    Join Date
    Oct 2006
    Posts
    2,391
    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.
    Code:
    namespace life
    {
        const bool change = true;
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Arrary with user defined size
    By GCNDoug in forum C++ Programming
    Replies: 8
    Last Post: 04-09-2008, 04:34 PM
  2. Array Help Please (user defined size)
    By Planetx33 in forum C++ Programming
    Replies: 9
    Last Post: 04-07-2007, 04:36 PM
  3. need to read a User defined file during runtime
    By john_newbie in forum C Programming
    Replies: 8
    Last Post: 03-06-2004, 01:08 AM
  4. Arrays of user-defined size?
    By Captain_Penguin in forum C++ Programming
    Replies: 7
    Last Post: 09-12-2002, 04:07 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21