Stack implementation using vectors and templates with no overflow version 1.2

Question

Below is the code for stack along with one or two extra options. Kindly let me know if there are any concerns/critical issues. Below are the two link for previous versions.

Original

Version 1.1

//*************Version 1.2: Begineer's Implementation of Stack ***************//


#include <iostream>
#include <fstream>

template <class T>
class Mystack
{
private:
    T *input;
    int top;
    int capacity;

public:
    Mystack();
    Mystack(const Mystack<T> &source);
    Mystack<T> & operator=(const Mystack<T> &source);
    ~Mystack();
    void push(T const& x);
    void pop();
    T& topElement() const;
    bool isEmpty() const;
    void print(std::ostream &os) const;
};

template <class T>
Mystack<T>::Mystack() //default copy constructor
{
    top = -1;
    capacity = 5;
    input = new T[capacity];
}

template <class T>
Mystack<T>::Mystack(const Mystack<T> &source)            // copy constructor
{
    input = new T[source.capacity];
    top = source.top;
    capacity = source.capacity;
    for (int i = 0; i <= source.top; i++)
    {
        input[i] = source.input[i];
    }
}

template <class T>
Mystack<T> & Mystack<T>::operator=(const Mystack<T> &source)       // assignment operator overload 
{
    input = new T[source.capacity];
    top = source.top;
    capacity = source.capacity;

    for (int i = 0; i <= source.top; i++)
    {
        input[i] = source.input[i];
    }
    return *this;
}


template <class T>
Mystack<T>::~Mystack()                           // destructor
{
    delete[] input;
}

template <class T>
void Mystack<T>::push(T const& x)               //Passing x by Const Reference 
{                                               // Valus of x cannot be changed now in the function!
    if (top + 1 == capacity)
    {
        T *vec = new T[capacity * 2];
        for (int i = 0; i <= top; i++)
        {
            vec[i] = std::move(input[i]);
        }
        delete[]input;                          // Avoiding Memory Leak.
        input = vec;
        capacity *= capacity;
    }
    input[++top] = x;
}

template <class T>
void Mystack<T>::pop()                         //pop the element from the top of stack
{
    if (isEmpty())
    {
        throw std::out_of_range("Stack Underflow");
    }
    else
    {
        std::cout << "The popped element is" << input[top--];

    }
}

template <class T>
bool Mystack<T>::isEmpty() const                    //const: none of the class members can be modified in this function 
{
    if (top == -1)
    {
        std::cout << "Is Empty" << std::endl;
        return true;
    }
    else
    {
        std::cout << "Not Empty" << std::endl;
        return false;
    }
}

template <class T>
T& Mystack<T>::topElement() const                      // returns top element of the stack
{
    if (top == -1)
    {
        throw std::out_of_range("No Element to Display");
    }
    else
    {
        std::cout << "The top element is : " << input[top];
        return input[top];
    }
}

template <class T>
void Mystack<T>::print(std::ostream &os) const         //a more of a general print function, can be used to write to a file 
{
    for (int i = 0; i <= top; i++)
    {
        os << input[i] << " ";
    }
}

int main()
{
    Mystack<int> intstack, inttemp;
    Mystack<float> floatstack, floattemp;
    Mystack <int> temp(intstack);
    Mystack<char> charstack, chartemp;
    int choice;
    std::ofstream some_file("testfile.txt");     // creation of file 
    int int_elem;
    float float_elem;
    char char_elem;
    std::cout << "Enter the type of stack" << std::endl;
    std::cout << "1. int ";
    std::cout << "2. float ";
    std::cout << "3. Char" << std::endl;
    std::cin >> choice;
    if (choice == 1)
    {
        int  ch = 1;
        while (ch > 0)
        {
            std::cout << "\n1. Push ";
            std::cout << "2. Top ";
            std::cout << "3. IsEmpty ";
            std::cout << "4. Pop ";
            std::cout << "5. Stack content to File";
            std::cout << "6. Copy Constrcutor";
            std::cout << "7. Assignemnt Operator";
            std::cout << "8. Print ";
            std::cout << "9. Exit" << std::endl;
            std::cout << "Enter the choice" << std::endl;
            std::cin >> ch;
            switch (ch)
            {
            case 1:
                std::cout << "Enter the number to be pushed" << std::endl;
                std::cin >> int_elem;
                intstack.push(int_elem);
                break;
            case 2:
                std::cout << "Get the TOP Element" << std::endl;
                try
                {
                    intstack.topElement();
                }
                catch (std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error:" << oor.what() << std::endl;
                }
                break;
            case 3:
                std::cout << "Check Empty" << std::endl;
                intstack.isEmpty();
                break;
            case 4:
                std::cout << "POP the element" << std::endl;
                try
                {
                    intstack.pop();
                }
                catch (const std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error: " << oor.what() << '\n';
                }
                break;
            case 5:
                std::cout << "Stack data to file" << std::endl;
                intstack.print(some_file);                          //printing data to a file
                break;
            case 6:
                {
                    Mystack<int> s4(intstack);                       // copy constructor called
                    s4.print(std::cout);
                    break;
                }
            case 7:
                inttemp = intstack;                                  // assignment operator overload
                inttemp.print(std::cout);
                break;
            case 8:
                intstack.print(std::cout);
                break;
            case 9:
                exit(0);
            default:
                std::cout << "Enter a valid input" << std::endl;
                break;
            }
        }
    }
    else if (choice == 2)
    {
        int  ch = 1;
        while (ch > 0)
        {
            std::cout << "\n1. Push ";
            std::cout << "2. Top ";
            std::cout << "3. IsEmpty ";
            std::cout << "4. Pop ";
            std::cout << "5. Write Data to a file";
            std::cout << "6. Copy Constrcutor Use";
            std::cout << "7. Assignemnt Operator Use";
            std::cout << "8. Print ";
            std::cout << "9. Exit" << std::endl;
            std::cout << "Enter the choice" << std::endl;
            std::cin >> ch;
            switch (ch)
            {
            case 1:
                std::cout << "Enter the number to be pushed" << std::endl;
                std::cin >> float_elem;
                floatstack.push(float_elem);
                break;
            case 2:
                std::cout << "Get the TOP Element" << std::endl;
                try
                {
                    floatstack.topElement();
                }
                catch (std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error:" << oor.what() << std::endl;
                }
                break;
            case 3:
                std::cout << "Check Empty" << std::endl;
                floatstack.isEmpty();
                break;
            case 4:
                std::cout << "POP the element" << std::endl;
                try
                {
                    floatstack.pop();
                }
                catch (const std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error: " << oor.what() << '\n';
                }
                break;
            case 5:
                std::cout << "Stack data to file" << std::endl;
                floatstack.print(some_file);                                //data to file
                break;
            case 6:
            {
                Mystack<float> s5 = floatstack;                            // copy constructor called
                s5.print(std::cout);
                break;
            }
            case 7:
                floattemp = floatstack;                                     // assignment operator overload
                floattemp.print(std::cout);
                break;
            case 8:
                floatstack.print(std::cout);
                break;
            case 9:
                exit(0);
            default:
                std::cout << "Enter a valid input" << std::endl;
                break;
            }
        }
    }
    else if (choice == 3)
    {
        int  ch = 1;
        while (ch > 0)
        {
            std::cout << "\n1. Push ";
            std::cout << "2. Top ";
            std::cout << "3. IsEmpty ";
            std::cout << "4. Pop ";
            std::cout << "5. Write Data to a file";
            std::cout << "6. Copy Constrcutor Use";
            std::cout << "7. Assignemnt Operator Use";
            std::cout << "8. Print ";
            std::cout << "9. Exit" << std::endl;
            std::cout << "Enter the choice" << std::endl;
            std::cin >> ch;
            switch (ch)
            {
            case 1:
                std::cout << "Enter the number to be pushed" << std::endl;
                std::cin >> char_elem;
                charstack.push(char_elem);
                break;
            case 2:
                std::cout << "Get the TOP Element" << std::endl;
                try
                {
                    charstack.topElement();
                }
                catch (std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error:" << oor.what() << std::endl;
                }
                break;
            case 3:
                std::cout << "Check Empty" << std::endl;
                charstack.isEmpty();
                break;
            case 4:
                std::cout << "POP the element" << std::endl;
                try
                {
                    charstack.pop();
                }
                catch (const std::out_of_range &oor)
                {
                    std::cerr << "Out of Range error: " << oor.what() << '\n';
                }
                break;
            case 5:
                std::cout << "Stack data to file" << std::endl;
                charstack.print(some_file);
                break;
            case 6:
            {
                Mystack<char> s6 = charstack;   // copy constructor called
                s6.print(std::cout);
                break;
            }
            case 7:
                chartemp = charstack;
                chartemp.print(std::cout);
                break;
            case 8:
                charstack.print(std::cout);
                break;
            case 9:
                exit(0);
            default:
                std::cout << "Enter a valid input" << std::endl;
                break;
            }
        }
    }
    else
        std::cout << "Invalid Choice";
    std::cin.get();
}

Your long header comment reminded me of this. I'm sure you can trim it down a bit. And if you are using a version control software (certainly should be), then the version history comments are useless. — glampert, Jan 6 at 22:22
Have to agree with @glampert. Those comments really belong in your version control system not as part of the code. — Loki Astari, Jan 7 at 1:43
I don't know what version control software is and I have never used it, I did the commenting manually. Anyways I am gonna delete the comments and will try to improve the code as per suggestions given. Thanks! — Unbreakable, Jan 7 at 4:36
@Unbreakable: Go here github.com and create an account. You can use their system for free. You will find a lot of developers/code already here. You can use git locally only and only need to push up to github.com when you want to make things public. Example github.com/Loki-Astari Example of file being changed github.com/Loki-Astari/ThorsSerializer/commits/master/Json/… — Loki Astari, Jan 7 at 7:00
@Unbreakable, learning about version control is possibly the most important lesson you could learn from posting this question. The value to you as a developer from effectively using a version controlling system is just so high that after you get used to using it you will wonder how you ever went without it. — shuttle87, Jan 7 at 14:18

Loki Astari · Accepted Answer · 2015-01-07 01:52:09Z

Assignment operator Leaks

Mystack<T> & Mystack<T>::operator=(const Mystack<T> &source)

The current version leaks memory and is not exception safe.

Look up the copy and swap idiom. That will solve our problems.

Push is not exception safe

    delete[]input;                          // Avoiding Memory Leak.
    input = vec;
    capacity *= capacity;

It is not enough to just delete the memory. You should only do that once the state of the object is consistent. Otherwise an exception can cause your object to become corrupted. The best way to do this is to swap the state of the current object and do the delete last.

    std::swap(input, vec);
    capacity *= capacity;

    // At this point the state of the object has been changed.
    // Thus any exceptions are not going to be problematic.
    // Thus it is safe to do dangerous operations that may potentially throw.
    delete [] vec;                          // Avoiding Memory Leak. (note we swapped)

Remove all the print statements in your code.

template <class T>
bool Mystack<T>::isEmpty() const                    //const: none of the class members can be modified in this function 
{
    if (top == -1)
    {
        std::cout << "Is Empty" << std::endl;
        return true;
    }
    else
    {
        std::cout << "Not Empty" << std::endl;
        return false;
    }
}

This should just be:

template <class T>
bool Mystack<T>::isEmpty() const  {
    return top == -1;
}

@Loki: I have tried to implement the suggestions here. Is there any other concept I can learn from stack code. — Unbreakable, Jan 12 at 13:50
And many many thanks for putting effort in reviewing the code. I really appreciate your patience and help. — Unbreakable, Jan 12 at 13:59

Morwenn · Answer 2 · 2015-01-06 18:22:35Z

There is an error

There is actually an error in your code, a hard one, a compilation error: you use std::out_of_range without including <stdexcept>. In some implementations, this header may be included by <iostream> or <fstream>, but this is no guaranteed by the C++ standard. Including <stdexcept> whenever you use a standard exception is good practice.

Stream operations

It is not cear from your code which header is incuded for main and which one is included for the stack implementation. Note that for the stack alone, including <ostream> is enough. Also, as @Loki said in a previous iteration of the review, please provide an overload of operator<< to actually print your stack to a stream, this is the standard way of doing things.

It's kind of strange to print things when you do operations. Containers are supposed to be reusable enough to have some requirements about efficiency. Printing things while doing the operations may slow down a program if the stack is used often (and produce unreadable diagnostic when you don't actually care about the stack).

Growth factor

Not even the standard data structures (e.g. std::vector) do that, but it would be handy to allow users to control the growth factor of the stack. Some vector implementations have a factor growth of 2 (e.g. libstdc++'s one) while some other implementations have a different growth factor (e.g. folly's one) and argue that the growth factor can be directly related to performance. It could be a good idea to let users change the growth factor when they feel it might generate faster code.

I simple include all the needed headers in my program.. How do you differentiate which is one is used for which..? — Unbreakable, Jan 9 at 22:53
@Unbreakable std::ostream is in <ostream>, std::istream in <istream>, etc... The header <iostream> includes <ostream>, <istream>, <ios> and <streambuf> and defines global variabes like std::cout. — Morwenn, Jan 9 at 23:29

shuttle87 · Answer 3 · 2015-01-06 18:37:49Z

Capacity bug

In the push function I noticed 2 things, first you used std::move which I like a lot and secondly:

if (top + 1 == capacity)
{
    T *vec = new T[capacity * 2];

when you resize the array here the capacity appears to double. However you store the capacity member as the square of the previous value when you do:

capacity *= capacity;

I'm assuming you meant to instead have:

capacity *= 2;

Otherwise when you resize there will be unnecessarily allocated memory that never gets used.

See Morwenn's answer for additional suggestions on improving this.

Output in member functions.

If you are making a container class it's good to not have any console output in the member functions if possible. Users of this class probably want to use it as a container and choose for themselves when they write output to the console. If they are there for debugging purposes perhaps wrap those in a define block for debugging, so for example:

template <class T>
bool Mystack<T>::isEmpty() const                    //const: none of the class members can be modified in this function 
{
    if (top == -1)
    {
        std::cout << "Is Empty" << std::endl;
        return true;
    }
    else
    {
        std::cout << "Not Empty" << std::endl;
        return false;
    }
}

would be changed to:

template <class T>
bool Mystack<T>::isEmpty() const                    //const: none of the class members can be modified in this function 
{
    if (top == -1)
    {
#ifdef DEBUG
        std::cout << "Is Empty" << std::endl;
#endif
        return true;
    }
    else
    {
#ifdef DEBUG
        std::cout << "Not Empty" << std::endl;
#endif
        return false;
    }
}

Another alternative would be to use some sort of logging.

Variable names

In some places you have variables that are separated from their usage by many lines of code. In this case having descriptive variable names is even more important that usual.

I would most certainly rename the choice variable to something more descriptive such as type_choice.

Duplicated code/long functions.

The main function is way too long in terms of lines of code. You really should aim to keep the number of lines of code as short as possible, especially in main.

With structured programming main is supposed to be the entry point to your program, not the whole program itself. Instead of having everything in main just limit it to setting up resources and calling the functions that run your programs logic. This makes it much easier for people reading your code to get started with understanding what your program is supposed to do. Now main is a bit more self-documenting and shows the structure of your program better.

As far as I can tell most of those lines come from duplicated code for dealing with the menu system:

    std::cout << "\n1. Push ";
    std::cout << "2. Top ";
    std::cout << "3. IsEmpty ";
    std::cout << "4. Pop ";
    std::cout << "5. Stack content to File";
    std::cout << "6. Copy Constrcutor";
    std::cout << "7. Assignemnt Operator";
    std::cout << "8. Print ";
    std::cout << "9. Exit" << std::endl;
    std::cout << "Enter the choice" << std::endl;

This block appears verbatim the same 2 times and slightly differently once. This seems like a violation of the Don't repeat yourself principle. Not to mention this is a huge maintenance nightmare, which version is the correct version of the menu? What happens if you miss an edit when updating the menu? The worst part of such copy-and-paste style programming is that you now have to change multiple places when making an edit. This is creating unnecessary work for the future maintainers.

You could refactor the code such that this printout was in a function.

void print_menu(){
    std::cout << "\n1. Push ";
    std::cout << "2. Top ";
    std::cout << "3. IsEmpty ";
    std::cout << "4. Pop ";
    std::cout << "5. Stack content to File";
    std::cout << "6. Copy Constrcutor";
    std::cout << "7. Assignemnt Operator";
    std::cout << "8. Print ";
    std::cout << "9. Exit" << std::endl;
    std::cout << "Enter the choice" << std::endl;
}

Or better still you could refactor that part of the code. As far as I can see you have these different cases only to instantiate different types such as:

Mystack<int> s4(intstack);
Mystack<float> s5 = floatstack;

a much better approach would be to move the logic for choosing a type to be closer to the point of instantiation.

So instead of:

if(type_choice == 1){
   //all the menu code
   Mystack<int> s4(intstack);                       
}
else if (type_choice == 2){
   //all the menu code
   Mystack<float> s5 = floatstack;
}

It's much much better to do this:

//all the menu code
if(type_choice == 1){
   Mystack<int> s4(intstack);                       
}
else if (type_choice == 2){
   Mystack<float> s5 = floatstack;
}

We eliminate the duplicate code this way and we keep the related functionality that deals with instantiating the containers with the correct types all in the same place in the code.

I will look into your suggestions. Thanks! Its a good learning experience for me. — Unbreakable, Jan 6 at 18:43
In switch case 6, If I was not giving curly braces I was getting compiler error. I generally don't use braces in switch cases. Why it is essential to give braces in this scenario. Error: Red squiggly under switch "Transfer of control bypasses the initialization of" — Unbreakable, Jan 8 at 0:45

asked	8 months ago
viewed	147 times
active	8 months ago

current community

your communities

more stack exchange communities

Stack implementation using vectors and templates with no overflow version 1.2

3 Answers 3

Assignment operator Leaks

Push is not exception safe

Remove all the print statements in your code.

There is an error

Stream operations

Growth factor

Capacity bug

Output in member functions.

Variable names

Duplicated code/long functions.

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ algorithm stack or ask your own question.

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Stack implementation using vectors and templates with no overflow version 1.2

3 Answers 3

Assignment operator Leaks

Push is not exception safe

Remove all the print statements in your code.

There is an error

Stream operations

Growth factor

Capacity bug

Output in member functions.

Variable names

Duplicated code/long functions.

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ algorithm stack or ask your own question.

Linked

Related

Hot Network Questions