Please ..err..nitpick my code (implementing a stack)

This is a discussion on Please ..err..nitpick my code (implementing a stack) within the C++ Programming forums, part of the General Programming Boards category; I started reading up on data structures from scratch after some unconsolidated knowledge gathered from the web. (If anyone is ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    Please ..err..nitpick my code (implementing a stack)

    I started reading up on data structures from scratch after some unconsolidated knowledge gathered from the web.
    (If anyone is interested, the book I'm following is "Data Structure and program design in C++" --by Robert L. Kruse && Alexander J. Ryba)

    Without further ado, here is my implementation of a stack..in a contiguous array.
    (I know the exception handling can be done in a less lazy way.... would do that if I ever use this code in any program)
    Code:
    namespace mm
    {
    
    
    enum stack_error{overflow,underflow,beheaded};
        
    template <typename T, int Size>
    class stack
    {
    private:
        T mem[Size];
        int stack_ptr; // The offset from mem to get the pointer to the head
    public:
        stack():stack_ptr(-1){};
        void push(const T& in)
        {
            if(++stack_ptr >= Size) throw(overflow);
            else mem[stack_ptr] = in;
        }
        T& head()
        {
            if(stack_ptr == -1) throw(beheaded);
            return mem[stack_ptr];
        }
        void pop()
        {
            if(--stack_ptr < -1 ) throw(underflow);
        }
        bool empty(){return stack_ptr==-1?true:false;};
        int size(){return stack_ptr+1;};
    };
    }
    It worked nicely for all test cases I came up with.
    Still.. to make sure...:
    Am I doing something that is considered 'bad' in the norm ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,672
    > if(++stack_ptr >= Size) throw(overflow);
    If you're going to throw an exception, then perhaps you shouldn't modify the internal state at the same time.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Salem View Post
    > if(++stack_ptr >= Size) throw(overflow);
    If you're going to throw an exception, then perhaps you shouldn't modify the internal state at the same time.
    I wanted the modification to carry over to the else..where it is needed even if the if(...) fails.
    But you are correct in a sense that I have to avoid that if I want to reuse the stack after recovering from the error. (But that can be handled in the catch block too, depending upon the error)

    But your suggestion makes it simpler.
    Code:
    if(stack_ptr+1 >= Size) throw(overflow);
    else mem[++stack_ptr] = in;
    Last edited by manasij7479; 10-01-2011 at 03:16 PM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    Registered User gardhr's Avatar
    Join Date
    Apr 2011
    Posts
    151
    Quote Originally Posted by manasij7479 View Post
    I started reading up on data structures from scratch after some unconsolidated knowledge gathered from the web.
    (If anyone is interested, the book I'm following is "Data Structure and program design in C++" --by Robert L. Kruse && Alexander J. Ryba)

    Without further ado, here is my implementation of a stack..in a contiguous array.
    (I know the exception handling can be done in a less lazy way.... would do that if I ever use this code in any program)
    Code:
    namespace mm
    {
    
    
    enum stack_error{overflow,underflow,beheaded};
        
    template <typename T, int Size>
    class stack
    {
    private:
        T mem[Size];
        int stack_ptr; // The offset from mem to get the pointer to the head
    public:
        stack():stack_ptr(-1){};
        void push(const T& in)
        {
            if(++stack_ptr >= Size) throw(overflow);
            else mem[stack_ptr] = in;
        }
        T& head()
        {
            if(stack_ptr == -1) throw(beheaded);
            return mem[stack_ptr];
        }
        void pop()
        {
            if(--stack_ptr < -1 ) throw(underflow);
        }
        bool empty(){return stack_ptr==-1?true:false;};
        int size(){return stack_ptr+1;};
    };
    }
    It worked nicely for all test cases I came up with.
    Still.. to make sure...:
    Am I doing something that is considered 'bad' in the norm ?
    The most glaring problem is that by using an array of constant size, you limit yourself to using it with objects having only the most trivial construction requirements. For more complex types, it just doesn't make sense to have a default constructor called on each and every element, especially considering that they technically shouldn't even "exist" until they are actually pushed into the data structure by the programmer! So if I were to choose a fixed array, I'd simply declare it as an array of bytes, casting each element to the appropriate type and manually invoking constructors/destructors, as necessary.

    Besides that, I would recommend using std::size_t instead of some signed integer type. Accessing the top element, checking bounds, etc is just as easy (without having to resort to that awkward -1 convention), and the intent is much clearer (you wouldn't declare an array of size, say, -1024, would you?).

    Otherwise, the code seems fairly clear and concise. I would be a little more liberal with the spacing, personally, but that's just a matter of taste, I guess.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Probably good to do the same thing here also:
    Code:
    if(--stack_ptr < -1 ) throw(underflow);
    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"

  6. #6
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    324
    A few things I noticed:

    1) C++ instantiates a separate body of code for each permutation of the template parameters. Thus, if a client wanted to have two stacks, say stack<int, 100> and stack<int, 1000> you'd end up with two copies of nearly identical code.

    2) Do you want your users to be limited in the size of a particular stack? Probably not.

    3) The exception of type "beheaded" is probably not familiar with most people. What does it mean?

    The solution to problems 1) and 2) is to use a dynamically growing array, usually doubling each time it becomes full. You can get rid of the Size template parameter and just take a size argument in the constructor. This will reduce code bloat greatly. Also, it will eliminate the problem of requiring default constructors for T. On the other hand, your code complexity will increase.

    Also, just to be a nitpick:

    Code:
    return stack_ptr == -1 ? true : false;
    why not

    Code:
    return stack_ptr == -1;

  7. #7
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by MacNilly View Post
    A few things I noticed:

    1) C++ instantiates a separate body of code for each permutation of the template parameters. Thus, if a client wanted to have two stacks, say stack<int, 100> and stack<int, 1000> you'd end up with two copies of nearly identical code.

    2) Do you want your users to be limited in the size of a particular stack? Probably not.

    3) The exception of type "beheaded" is probably not familiar with most people. What does it mean?

    The solution to problems 1) and 2) is to use a dynamically growing array, usually doubling each time it becomes full. You can get rid of the Size template parameter and just take a size argument in the constructor. This will reduce code bloat greatly. Also, it will eliminate the problem of requiring default constructors for T. On the other hand, your code complexity will increase.

    Also, just to be a nitpick:

    Code:
    return stack_ptr == -1 ? true : false;
    why not

    Code:
    return stack_ptr == -1;
    1. && 2. Good idea.. will try to act on it.
    3. It is just an enum declared on top and I got into some creative nomenclature; didn't derive exception classes because I wanted to keep it simple.
    4. (return)
    It was somewhat foolish coding on my part. :S .. though I changed it after being pointed out in this thread.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 09-08-2009, 10:16 AM
  2. Please Help Me With This Code Of Implementing Stacks
    By raghu_equinox in forum C Programming
    Replies: 3
    Last Post: 10-19-2006, 07:22 AM
  3. implementing a stack with template
    By micha_mondeli in forum C++ Programming
    Replies: 5
    Last Post: 03-31-2005, 06:08 PM
  4. Implementing Mathematical Concepts in Code
    By MisterWonderful in forum Tech Board
    Replies: 6
    Last Post: 03-08-2004, 06:44 AM
  5. Designing and Implementing Test Code
    By manofsteel972 in forum C++ Programming
    Replies: 20
    Last Post: 03-03-2004, 09:38 AM

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