Class to implement stack with dynamic array,gives segmentation fault in a code grader

Question

I tried to implement a stack with a dynamic array and sumbit the code in a code grader, but it keeps giving me segmentation faults.I think i might be out of array bounds somewhere but i can not resolve it.Any ideas?

#include <iostream>

using namespace std;
template <typename T>
class stack {
  public:
     int length;
     T *data;
     int top=0;
    stack (int size) {
      length=size;
      data=new T[length]();
      top=0;
    }
    stack (const stack &s) {
      length=s.size();
      data=new T[length]();
      if(s.data!=NULL){
        for(int i=0; i<length; i++){
          data[i]=s.data[i];top++;
        }}
    }
    ~stack () {
        if(data!=NULL){
        delete[] data;}
        data=NULL;
    }
    bool empty () {
      return top==0;
    }
    void push (const T &x) {
      data[top]=x;
      top++;
    }
    T pop () {
      return data[--top];
    }
    int size ()const{
      return top;}
    friend ostream & operator << (ostream &out,const stack &s) {
      if(s.size()==0){
        out<<"[]";}
      else{
        out<<'[';
        for(int i=0; i<s.size()-1; i++){
          out<<s.data[i]<<", ";
        }
        out<<s.data[s.size()-1]<<']';}
      return out;
    }
    const stack & operator = (const stack &s){
      top=s.top;
      for(int i=0; i<length; i++){
        data[i]=s.data[i];}
      return *(this);
    }
};

A sample of an addition that the grader makes to the code is this:

#ifndef CONTEST
int main(){
stack<int> s(10);
cout << "s is empty: "<< s << endl;
s.push(42);
cout << "s has one element: " << s << endl;
s.push(17);
s.push(34);
cout << "s has more elements: " << s << endl;
cout << "How many? " << s.size() << endl;
stack<int> t(5);
t.push(7);
cout << "t: " << t << endl;
t = s;
cout << "popping from s: " << s.pop() << endl;
s.push(8);
stack<int> a(s);
t.push(99);
a.push(77);
cout << "s: " << s << endl;
cout << "t: " << t << endl;
cout << "a: " << a << endl;
// now with doubles...
stack<double> c(4);
c.push(3.14);
c.push(1.414);
cout << "c contains doubles " << c << endl;
// and with characters...
stack<char> k(4);
k.push('$');
cout << "k contains a character " << k << endl;
}
#endif

And it is supposed to output this:

s is empty: []
s has one element: [42]
s has more elements: [42, 17, 34]
How many? 3
t: [7]
popping from s: 34
s: [42, 17, 8]
t: [42, 17, 34, 99]
a: [42, 17, 8, 77]
c contains doubles [3.14, 1.414]
k contains a character [$]

@jimk use [`std::vector`](https://en.cppreference.com/w/cpp/container/vector) instead, or in this case, consider [`std::stack`](https://en.cppreference.com/w/cpp/container/stack) — Remy Lebeau, Mar 18 '20 at 19:33
@jimk some problems I see in your code - `push()` does not do any bounds checking to make sure the `length` is not exceeded, `pop()` does not check if the list is empty, and `operator=` does not account for stacks of different lengths (which your `main()` does use!). — Remy Lebeau, Mar 18 '20 at 19:37
Thank you,but in my case i must do it without std::vectors.If someone could hint me a source of segmentation fault it would be great. — Jmk, Mar 18 '20 at 19:38
Thanks,but it actually runs as it should in a debugger,the only problem is that somehow it does not run in the grader. — Jmk, Mar 18 '20 at 19:42
Running code in the debugger isn't all that useful by itself. What you want to do is step and watch what the program does. When the program does something unexpected you've usually found a bug. — user4581301, Mar 18 '20 at 19:43
@Ðаn I wish I lived in a world where more teachers believed that. — user4581301, Mar 18 '20 at 19:48

Lukas-T · Answer 1 · 2020-03-18T19:56:24.873

2

Your copy-assingment operator (operator=) does something vastly different than your copy-constructor. In fact, it does not actually copy the object, but only the elements from data. But there it doesn't account for different numbers of elements.

The assignment t = s; causes a segmentation fault.

const stack & operator = (const stack &s){
    top=s.top; // s.top could be larger than the current size, no checks?
    for(int i=0; i<length; i++) { //this->length == 10, but
        data[i]=s.data[i];}       //s.data contains only 7 elements!
    return *(this);
}

Technically it's undefined behaviour, luckily it manifested in a segmentation fault here.

A copy-assignment operator will usually do the same thing as a copy-constructor. Some links for reference and code examples: Rule of 5/3/0 and What is the copy-and-swap idiom?

edited Mar 18 '20 at 19:56

answered Mar 18 '20 at 19:43

Lukas-T

11,133
3
20
30

Right about here is where I'd be dropping a link to [What is the copy-and-swap idiom?](https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom) because it's the easiest solution and even if it's a bit slow, it's probably fast enough. – user4581301 Mar 18 '20 at 19:46
How can i know the size of s.data? – Jmk Mar 18 '20 at 19:53
1

@jimk `s.length`, but take a look at the copy and swap link. It makes assignment operators brutally easy to write and almost impossible to get wrong. – user4581301 Mar 18 '20 at 19:54

Landstalker · Answer 2 · 2020-03-18T20:12:53.167

This is a minimal code wich reproduce error:

int main() {
    stack<int> s(10);
    s.push(42);
    stack<int> a(s);
    a.push(77);
}

your size function return juste top and not the size :

int size()const {
    return top;
}

Therefore, in your copyconstructor, you create space juste for top elements:

stack(const stack &s) {
        length = s.size();
        data = new T[length]();
//...
}

In your case, you can not write :

a.push(77);

Because you allocate s.top elements and your array have no more space. you write out of bond wich cause segmentation fault

Class to implement stack with dynamic array,gives segmentation fault in a code grader

2 Answers2