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 instead, or in this case, consider std::stack — Remy Lebeau
– Remy Lebeau, Commented Mar 18, 2020 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
– Remy Lebeau, Commented Mar 18, 2020 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
– Jmk, Commented Mar 18, 2020 at 19:38
@Ðаn I wish I lived in a world where more teachers believed that. — user4581301
– user4581301, Commented Mar 18, 2020 at 19:48

Lukas-T · Accepted Answer · 2020-03-18 19:56:24Z

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, 2020 at 19:56

answered Mar 18, 2020 at 19:43

Lukas-T

11.4k4 gold badges24 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user4581301 Over a year ago

Right about here is where I'd be dropping a link to 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.

Jmk Over a year ago

How can i know the size of s.data?

user4581301 Over a year ago

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

Landstalker · Accepted Answer · 2020-03-18 20:12:53Z

1

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

edited Mar 18, 2020 at 20:12

answered Mar 18, 2020 at 20:00

Landstalker

1,3688 silver badges9 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related