Thread: Custom stack problems

  1. #1
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229

    Custom stack problems

    Since a lot of people have been posting about Linked Lists and Stacks and Queues recently, I thought of paying visit to one of my old Stack programs (I have three more for Queues, Circular Queues and Trees). There seems to be some error with the DisplayStack () method. Everything looks fine to me but when I run the code, it crashes. If I comment out the call to DisplayStack, everything works well. I haven't looked at the code in quite sometime and nothing makes sense right now as it's pretty late here (5 am) and I need to hit the bed for a few hours. Hopefully, someone will be able to figure it out and I wouldn't need to think about this when I wake up.

    Code:
    template <typename T>
    class Stack
    {
    private:
    
        struct Object
        {
            T Data; Object* Next;
    
            Object (void)
                : Data (T()) ,
                  Next (nullptr)
            { }
        };
    
        Object* StackTop;
    
    public:
    
         Stack (void);
        ~Stack (void);
    
        void Push(T const& data);
    
        void Pop          (void)      ;
        void DisplayStack (void) const;
    
    };
    
    template <typename T> Stack<T>::Stack (void)
        : StackTop (nullptr)
    { }
    
    template <typename T> void Stack<T>::Push (T const& data)
    {
        Object* ptr = new Object; ptr->Data = data;
    
        if (StackTop == nullptr) StackTop = ptr;
    
        else
        {
            ptr->Next = StackTop;
            StackTop = ptr;
        }
    }
    
    template <typename T> void Stack<T>::Pop (void)
    {
        Object* temp = StackTop;
        StackTop = StackTop->Next;
        delete temp;
    }
    
    template <typename T> void Stack<T>::DisplayStack (void) const
    {
        Object* temp = StackTop;
    
        std::cout << std::endl << temp->Data << "<- Stack Top";
    
        while (temp != nullptr)
        {
            temp = temp->Next;
            std::cout << std::endl << temp->Data;
        }
    }
    
    template <typename T> Stack<T>::~Stack (void)
    {
        Object* temp = StackTop;
    
        while (temp != nullptr)
        {
            StackTop = StackTop->Next;
            delete temp;
            temp = StackTop;
        }
    }
    
    int main (void)
    {
        Stack <std::string> S;
    
        S.Push ("ABCD");
        S.Push ("EFGH");
        S.Push ("IJKL");
        S.Push ("MNOP");
    
        S.DisplayStack ();
    
        return 0;
    }
    There's a tonne more of other methods and operator overloads but I'm not adding all of them as thry were working pretty much fine the last time I ran it. Thanks, 'night.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,398
    * post moved to C++ programming forum *

    Zeus_: don't hijack other people's posts, and don't ask for help on a C++ program in the C programming forum.
    Last edited by laserlight; 12-02-2019 at 06:17 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    775
    You dereference the pointer before you check if it's null.

    BTW, don't put "void" in the parameters when a function takes nothing. Just leave the parentheses empty. In old C you had to do that, but you don't have to do that in C++.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,398
    Quote Originally Posted by Zeus_
    There seems to be some error with the DisplayStack () method.
    There are two oversights that I can see at a glance:
    • It assumes that the stack is not empty.
    • In the loop, it doesn't check that the node pointer is a null pointer before dereferencing it.


    A few other issues:
    • You unnecessarily require T to have a default constructor. If you had written Object's constructor to copy instead, T would not need a default constructor (although it would need a copy constructor). Personally, I would have named Object Node instead, since you're basically implementing the stack with a linked list. Actually, if Object's constructor were to also take the next pointer as an argument, you could implement Push in a single line:
      Code:
      template <typename T> void Stack<T>::Push (T const& data)
      {
          StackTop = new Object(data, StackTop);
      }
    • You might have merely omitted them, but you should also implement or disable the copy constructor and copy assignment operator, and it makes sense to implement the move constructor and move assignment operator.
    • Pop results in undefined behaviour if the stack is empty. If that is by design, then it is better to document it, either with an assertion or at least a comment. Otherwise, it should either throw an exception or be a no-op.
    • You might have merely omitted it, but you're using the version of Pop that just pops without returning the item. Therefore, you need some other way for the stack user to examine the top of the stack.


    It probably would also make sense to rename DisplayStack to just Display since it is clear that you're displaying a stack. Or maybe overload operator<< for ostream since this is kind of canonical debugging output.
    Last edited by laserlight; 12-02-2019 at 07:03 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229
    There are two oversights that I can see at a glance:

    • It assumes that the stack is not empty.
    • In the loop, it doesn't check that the node pointer is a null pointer before dereferencing it.
    Yea..... I don't know why I never did that in any of my programs when I first wrote them, but I'll change them to not assume that the Stack/Queue/Tree/CircQueue is not empty. Actually, when I started reading about all the Object Oriented Programming Paradigms and stuff, I thought it'd be a good idea to implement everything in the OOP way and those were some of the primary programs I wrote for practice.

    You unnecessarily require T to have a default constructor. If you had written Object's constructor to copy instead, T would not need a default constructor (although it would need a copy constructor). Personally, I would have named Object Node instead, since you're basically implementing the stack with a linked list. Actually, if Object's constructor were to also take the next pointer as an argument, you could implement Push in a single line:
    Makes sense, I think I'll change the implementation to do exactly that.

    You might have merely omitted them, but you should also implement or disable the copy constructor and copy assignment operator, and it makes sense to implement the move constructor and move assignment operator.
    I had no idea what a move constructor was when I wrote the program, so I need to revisit my codes and change a few things. I have implemented the copy constructor and copy assignment operator which, now, seems like a really bad idea lol. Will implement the changes....

    Pop results in undefined behaviour if the stack is empty. If that is by design, then it is better to document it, either with an assertion or at least a comment. Otherwise, it should either throw an exception or be a no-op.
    Oh, yep, I'll fix that first as soon as I reach home. I'm starting to wonder all the changes I need to do in my other programs too, which I thought were working properly but I forgot implementing the edge case scenarios, and probably much more.

    You might have merely omitted it, but you're using the version of Pop that just pops without returning the item. Therefore, you need some other way for the stack user to examine the top of the stack.
    I've overloaded the [] operator to do just that.

    It probably would also make sense to rename DisplayStack to just Display since it is clear that you're displaying a stack. Or maybe overload operator<< for ostream since this is kind of canonical debugging output.
    Will do.

    You dereference the pointer before you check if it's null.

    BTW, don't put "void" in the parameters when a function takes nothing. Just leave the parentheses empty. In old C you had to do that, but you don't have to do that in C++.
    I think I need to rewrite all my programs (using Linked Lists) for the stupid negligence I showed when writing these. I'll implement the changes.

    Old habits die hard, I'm used to all the (void) in parentheses because our school teaches us on TurboC++ and they say you must specify it. I think I should suggest them to join this forum as @Salem suggested on the C Programming thread that's hot right now for Stack implementation. They're just teaching a bunch of old (some of which are bad) programming habits. Won't make a difference after a month because the next year batch have Python and Java as choices. C/C++ is not going to be taught any more and we were the last batch learning it.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  6. #6
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229
    This is my operator overload for retrieving the element data of the i'th element. It's probably very inefficient for accessing the millionth element or something like that. What do you guys think I should be returning if the call to Size () returns 0 in an if statement (Size is a function that returns the number of nodes)? Because if the Stack has no elements and I type something like "cout << S [0]", this code will crash. I don't want it to crash when I write code like that (in all Data Structure programs I've written). I can check if the number of nodes is 0 and if it is zero, what should I be returning for it to work fine but not display anything as expected?
    Code:
    template <typename T> T& Stack<T>::operator [] (int Position) const
    {
        ObjectNode* CurrentNode = Top;
    
        if (Position < 0) Position = 0;
        else if (Position > (int)Nodes - 1) Position = (int)Nodes - 1;
        for (int i = 0; i < Position; i++)
            CurrentNode = CurrentNode->Next;
        return CurrentNode->Data;
    }
    EDIT:

    Changed code to this so that -ve indices work differently (returning reverse order of stack elements)

    Code:
    template <typename T> T& Stack<T>::operator [] (int Position) const
    {
        ObjectNode* CurrentNode = Top;
    
        if (Position < 0) Position = (1 - Position > Nodes) ? 0 : (Nodes + Position);
        else if (Position > (int)Nodes - 1) Position = (int)Nodes - 1;
        for (int i = 0; i < Position; i++)
            CurrentNode = CurrentNode->Next;
        return CurrentNode->Data;
    }
    Last edited by Zeus_; 12-11-2019 at 12:37 PM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,398
    Quote Originally Posted by Zeus_
    This is my operator overload for retrieving the element data of the i'th element. It's probably very inefficient for accessing the millionth element or something like that.
    That probably makes it a bad idea: C++ programmers are likely primed to expect operator[] to have random (constant time) access for an index and at least logarithmic time access otherwise (e.g., std::map). Linear time complexity could result in people accidentally coming up with a quadratic time algorithm to say, examine all the stack elements in turn. A solution could be to provide begin() and end() iterators instead.

    Alternatively, there's the argument that a stack conceptually only ever allows you to access the top of the stack, so perhaps you should not provide this at all, like std::stack.
    Last edited by laserlight; 12-11-2019 at 02:36 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229
    Yeah, I figured. It's a bad idea. I'm modifying all my programs so that I can use them instead of the STL for practicing purposes and hobby projects. Thought it'd be a good idea to overload [] (I should probably make it a const reference return so that the data in the stack cannot be manipulated) but then the complexity is O(n) which just makes it worse for the hobby projects I have in mind. I'll add the begin () and end () iterators too when I find the time to code again (not a lot of time these days due to exams). I've added the move constructor and move assignment operator but should I remove the copy ctor and assignment operator or let that stay?
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  9. #9
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229
    This is the code I've got till now.

    TODO:
    - Remove Copy Ctor and Copy Assignment Operator once I know the reason why it's bad (I'm taking a few random guesses but I'm definitely sure)
    - Modify Clear () to use Disabled Nodes instead of de-allocating previously allocated memory. DisabledNodes will be all the ActiveNodes before call to Clear ().
    - Add Top () iterator that returns a read (not write because you should be able to manipulate the stack only through push and pop) pointer pointing to the top of the stack initially. What should be my return type for a Top () iterator? I cannot make it const ObjectNode* because apart from my Stack nothing else knows what an ObjectNode is or am I wrong?
    - Update and upload code for all other data structures and have them examined by you guys...
    - Make a Parentheses Validator using this Stack

    Are my move ctor and assignment operator written correctly? Same question for the copy ctor and assignment. Also, what else should I be adding that you guys think would be good?

    Code:
    template <typename T> class Stack
    {
    private:
    
        struct ObjectNode
        {
            T Data; ObjectNode* Next;
    
            ObjectNode (T const& data , ObjectNode* next)
                : Data (data) ,
                  Next (next)
            { }
        };
    
        size_t ActiveNodes;
        //size_t DisabledNodes;
        ObjectNode* StackTop;
    
    public:
    
         Stack (void);
         Stack (const Stack& Other);
         Stack (Stack&& Other);
        ~Stack (void);
    
        Stack& operator = (const Stack& Other);
        Stack& operator = (Stack&& Other);
    
        void Clear   (void);
        void Display (void) const;
        void Pop     (void);
        void Push    (const T& data);
    
        bool Empty (void) const;
    
        size_t Size (void) const;
    
        const T& At          (int Position) const;
        const T& operator [] (int Position) const;
    };
    
    template <typename T> Stack <T>::Stack (void)
        : ActiveNodes (0) ,
          StackTop (nullptr)
    { }
    
    template <typename T> Stack <T>::Stack (const Stack& Other)
        : ActiveNodes (Other.ActiveNodes) ,
          StackTop (Other.StackTop)
    {
        ObjectNode* CurrentNode = StackTop;
        ObjectNode* OtherCurrentNode = Other.StackTop;
    
        for (size_t i = 0; i < ActiveNodes; i++)
        {
            CurrentNode->Data = OtherCurrentNode->Data;
            CurrentNode->Next = OtherCurrentNode->Next;
            CurrentNode = CurrentNode->Next;
            OtherCurrentNode = OtherCurrentNode->Next;
        }
    }
    
    template <typename T> Stack <T>::Stack (Stack&& Other)
        : ActiveNodes (Other.ActiveNodes) ,
          StackTop (Other.StackTop)
    {
        Other.ActiveNodes = 0;
        Other.StackTop = nullptr;
    }
    
    template <typename T> Stack <T>::~Stack (void)
    {
        ObjectNode* CurrentNode = StackTop;
    
        while (CurrentNode != nullptr)
        {
            StackTop = StackTop->Next;
            delete CurrentNode;
            CurrentNode = StackTop;
        }
    }
    
    template <typename T> Stack <T>& Stack <T>::operator = (const Stack& Other)
    {
        if (this != &Other)
        {
            ObjectNode* CurrentNode = StackTop;
            while (CurrentNode != nullptr)
            {
                StackTop = StackTop->Next;
                delete CurrentNode;
                CurrentNode = StackTop;
            }
    
            ActiveNodes = Other.ActiveNodes;
            StackTop = Other.StackTop;
    
            CurrentNode = StackTop;
            ObjectNode* OtherCurrentNode = Other.StackTop;
    
            for (size_t i = 0; i < ActiveNodes; i++)
            {
                CurrentNode->Data = OtherCurrentNode->Data;
                CurrentNode->Next = OtherCurrentNode->Next;
                CurrentNode = CurrentNode->Next;
                OtherCurrentNode = OtherCurrentNode->Next;
            }
        }
        return *this;
    }
    
    template <typename T> Stack <T>& Stack <T>::operator = (Stack&& Other)
    {
        if (this != &Other)
        {
            ObjectNode* CurrentNode = StackTop;
            while (CurrentNode != nullptr)
            {
                StackTop = StackTop->Next;
                delete CurrentNode;
                CurrentNode = StackTop;
            }
    
            StackTop = Other.StackTop;
            ActiveNodes = Other.ActiveNodes;
    
            Other.ActiveNodes = 0;
            Other.StackTop = nullptr;
        }
    
        return *this;
    }
    
    template <typename T> void Stack <T>::Clear (void)
    {
        ObjectNode* CurrentNode = StackTop;
    
        while (CurrentNode != nullptr)
        {
            StackTop = StackTop->Next;
            delete CurrentNode;
            CurrentNode = StackTop;
        }
    
        ActiveNodes = 0;
    }
    
    template <typename T> void Stack <T>::Display (void) const
    {
        if (ActiveNodes == 0) return;
    
        ObjectNode* CurrentNode = StackTop;
    
        for (size_t i = 0; i < ActiveNodes; i++)
        {
            std::cout << std::endl << CurrentNode->Data;
            CurrentNode = CurrentNode->Next;
        }
    }
    
    template <typename T> void Stack <T>::Push (const T& data)
    {
        StackTop = new ObjectNode (data , StackTop);
        ActiveNodes++;
    }
    
    template <typename T> void Stack <T>::Pop (void)
    {
        if (ActiveNodes == 0) return;
    
        ObjectNode* CurretNode = StackTop;
        StackTop = StackTop->Next;
        delete CurretNode;
        ActiveNodes--;
    }
    
    template <typename T> size_t Stack <T>::Size (void) const
    { return ActiveNodes; }
    
    template <typename T> bool Stack <T>::Empty (void) const
    { return (ActiveNodes > 0) ? false : true; }
    
    template <typename T> const T& Stack <T>::At (int Position) const
    { return operator [] (Position); }
    
    template <typename T> const T& Stack <T>::operator [] (int Position) const
    {
        ObjectNode* CurrentNode = StackTop;
    
             if (Position < 0) Position = (1 - Position > (int)ActiveNodes) ? 0 : ((int)ActiveNodes + Position);
        else if (Position > (int)ActiveNodes - 1) Position = (int)ActiveNodes - 1;
    
        for (int i = 0; i < Position; i++)
            CurrentNode = CurrentNode->Next;
        return CurrentNode->Data;
    }
    Last edited by Zeus_; 12-12-2019 at 01:36 AM. Reason: Removed extra spacing
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,398
    Quote Originally Posted by Zeus_
    - Remove Copy Ctor and Copy Assignment Operator once I know the reason why it's bad (I'm taking a few random guesses but I'm definitely sure)
    You don't need to remove them. Just because they might be relatively expensive doesn't mean no one will ever really want a copy.

    Quote Originally Posted by Zeus_
    - Add Top () iterator that returns a read (not write because you should be able to manipulate the stack only through push and pop) pointer pointing to the top of the stack initially. What should be my return type for a Top () iterator? I cannot make it const ObjectNode* because apart from my Stack nothing else knows what an ObjectNode is or am I wrong?
    Just return a const T&. There's no point returning an iterator unless you actually want to allow the caller to iterate, but if so you need to designate an end iterator.

    Quote Originally Posted by Zeus_
    Are my move ctor and assignment operator written correctly?
    Yes.

    Quote Originally Posted by Zeus_
    Same question for the copy ctor and assignment.
    Your copy constructor looks wrong: you cannot just copy over the StackTop pointer; you need to create a copy of the other stack, and that means using new in a loop to create the node copies and append them to a fresh linked list.

    Your copy assignment operator has the same problem. After you fix it, note that your copy assignment would then only offer the basic exception guarantee: the stack will be in a valid state after the exception is thrown, but the data before the copy assignment attempt would be lost. If you want to offer the strong exception guarantee (an exception would not result in a change to the original state), then you need to copy before you destroy. It looks like this can be solved by using the copy constructor to make a local copy, then using move assignment... but it would be more efficient to stick to offering the basic exception guarantee and just reuse the storage for the nodes already allocated to copy over, and only allocate new storage when the other stack is larger.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229
    Yep, I see the problem with the copy ctor and assignment operator now when I test it. Right now, it's pretty much doing what a typedef would do i.e. creating an alias. I'll fix that. Thanks for your input!

    > Just return a const T&. There's no point returning an iterator unless you actually want to allow the caller to iterate, but if so you need to designate an end iterator.

    Makes sense. Thinking of it, why would someone want to iterate over a stack anyway? Defeats the purpose of it being a stack. Plus, if you do need to access the i'th element there's the [] but no sensible programmer would use a stack as something like a vector, even though I've added that functionality for a O(n) expense.

    How is the [] overloaded in the vector class in the STL? Is it similar to my implementation? (In it's implementation, it probably too is using linked lists right?) I could look at the header files and try and figure this out myself but my mom'll kill me if she doesn't find me studying my core subjects and so I need to wait until later at night when she's asleep.

    Also, I think I'll add a try and catch block in [] overload and Push () to throw an exception if StackTop == nullptr.
    Last edited by Zeus_; 12-12-2019 at 06:24 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  12. #12
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229
    Changed the code to this but realised midway that this would reverse the order of the Stack. Then thought, I could exploit my [] overload to push Other in reverse order so I can get it to be what is expected but that's just too much burden for a copy ctor (the O(n**2), I guess, for just making a copy of the stack!)
    I think I'll have to add another characteristic to ObjectNode so that each node can hold the previous stack node address too so that I can reverse iterate to get copy to work in O(n) time. Will that be good enough for a hobby stack project or is it just overkill?

    Code:
    template <typename T> Stack <T>::Stack (const Stack& Other)
        : ActiveNodes (0) ,
          StackTop (nullptr)
    {
        ObjectNode* OtherCurrentNode = Other.StackTop;
    
        for (size_t i = 0; i < Other.ActiveNodes; i++)
        {
            this->Push (OtherCurrentNode->Data);
            OtherCurrentNode = OtherCurrentNode->Next;
        }
    }
    Thanks
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,398
    Quote Originally Posted by Zeus_
    How is the [] overloaded in the vector class in the STL?
    That is, by definition, dependent on the implementation

    But in practice, it probably essentially looks like this:
    Code:
    return data[index];
    Quote Originally Posted by Zeus_
    Is it similar to my implementation? (In it's implementation, it probably too is using linked lists right?)
    std::vector models a dynamic array; it is therefore very different from a linked list. std::vector's operator[] has random access, just like an array. A linked list trying to implement operator[] to allow indexed access to its elements can never have random access because traversing to the middle of a linked list must surely take linear time, hence a stack implemented with a linked list that offers operator[] suffers from the same problem.

    Quote Originally Posted by Zeus_
    Changed the code to this but realised midway that this would reverse the order of the Stack. Then thought, I could exploit my [] overload to push Other in reverse order so I can get it to be what is expected but that's just too much burden for a copy ctor (the O(n**2), I guess, for just making a copy of the stack!)
    Yes, and that goes back to why operator[] is a bad idea: you're tempted by this operator[] overload even though you know it's inefficient.

    Quote Originally Posted by Zeus_
    I think I'll have to add another characteristic to ObjectNode so that each node can hold the previous stack node address too so that I can reverse iterate to get copy to work in O(n) time. Will that be good enough for a hobby stack project or is it just overkill?
    Basically, you want to implement your stack with a doubly linked list just so that copying can be efficient. That's overkill. You just need to keep track of the previous node when creating the copy of the linked list such that you can set the next pointer of the previous node to point to the current node.
    Last edited by laserlight; 12-12-2019 at 03:05 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    229
    Thanks for all the help!
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using stack of stl with custom container.
    By +Azazel+ in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2009, 10:29 AM
  2. Problems with a custom-made class
    By Kylecito in forum C++ Programming
    Replies: 9
    Last Post: 02-06-2006, 01:35 PM
  3. Problems with my custom string class
    By cunnus88 in forum C++ Programming
    Replies: 15
    Last Post: 11-15-2005, 08:21 PM
  4. problems overloading outstream for custom ADT
    By aciarlillo in forum C++ Programming
    Replies: 4
    Last Post: 04-05-2005, 09:28 AM
  5. [Linked Lists] Custom String Class Add Char problems
    By nickname_changed in forum C++ Programming
    Replies: 1
    Last Post: 07-23-2004, 10:15 PM