Getting Segmentation fault in string assignment

Question

This is a partial code for a bit-masking problem. I have n sets of colored balls and each set has 10 types of balls. For each set the types of balls present is given by a bit-mask string, like "0000000001" means only type one ball is present. I am creating 2^n size array for each possible combination of "sets" and assigning the strings to those combinations. In the given snippet, I am assigning each individual set in the 2^n array with it's corresponding string/balls distribution.

This snippet is using 2^n sized string array and it gives seg-fault after 4 assignments. I have also tried with a 2^n sized integer array, it gives seg-fault after 10 assignments. I have also tried vector instead of array.

The code works perfectly for small n like 5, 10. However, I am getting errors for n=100.

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n; cin>>n;
    int p[n]; string b[n];
    int maxNum=0, minCost=INT_MAX;

    for(int i=0; i<n; i++)  cin>>p[i]>>b[i];
    string arr[1<<n];
    for(int i=0; i<(1<<n); i++) arr[i]= "0000000000";

    for(int k=0; k<n; k++){  
        cout<<k<<" "<<b[k]<<endl;;
        arr[(1<<k)]= b[k];
    }

    cout<<minCost<<" "<<maxNum;

    return 0;
}

Alternate Code:

int main(){
    int n; cin>>n;
    int p[n]; int b[n];
    int maxNum=0, minCost=INT_MAX;

    int arr[1<<n]= {0};
    string st;
    for(int i=0; i<n; i++){ 
        cin>>p[i]>>st;
        bitset<32> bits(st);
        b[i]= bits.to_ulong();
    }
    
    for(int k=0; k<n; k++){  
        cout<<k<<" "<<b[k]<<endl;
        arr[(1<<k)]= b[k];
    }

    cout<<minCost<<" "<<maxNum;

    return 0;
}

Input for testing:

100
825559123 1101000000
723927316 1100000000
630882051 0100000000
970018301 0000110000
802701997 0001000000
368727086 1000000000
941759437 0000000000
863301206 1000000000
158330925 1100100000
952862749 0000000000
102106508 0000000000
642189578 1010000000
416170041 0100000000
503483274 0000000000
926633515 0010000000
233734818 1000000000
169465305 0010000000
925756481 0001010000
380740929 0000000000
923546464 1000000000
352640896 1100000000
538094174 0000001001
884232717 1110000000
881618727 0000000100
341770070 1000000000
370990187 1000101000
818894502 0000000000
756416297 0000000000
750141952 1010000000
156721241 0000100000
352780300 1001000100
158047482 1000000000
277595007 1000010000
557738195 1001001000
577045284 0110010000
378282174 1001000000
171102340 0100000000
808446042 1000000000
492238964 0100110000
871761380 1001000000
106063154 0000000000
929340033 0000000000
826793542 1110000000
882429992 1110000000
353710255 1101000000
989939310 0100100010
932975557 1010000100
860332788 0100000000
138524161 0100000000
715186358 0110000000
105450969 1101000000
722369284 1011000000
285470513 0000100000
116472373 1100000000
114558691 1000000000
639736702 1001000000
494962263 1100000000
542209831 0000000000
177483931 1000000000
182207145 0000000000
846803150 0000000000
735034366 0100000000
266040888 0000000000
907666010 0000000000
977358840 1000000000
112286012 0000000000
622971034 0000100000
443656670 0000000000
607470566 0000000000
115391310 0010010100
565221300 1000000010
762620672 0001000000
604911457 1001100000
577865036 1100000000
825870042 0000000000
287371290 1010000000
127073701 1000000000
993638645 1000000000
590442752 1101000000
315610523 1000000000
129874582 0100000000
330774796 0000000000
180125061 1011000000
742953948 1100000000
254364525 1000010000
215720197 1010100000
187594300 1011000000
327723812 1100000000
562306542 0100100001
875275760 0000000000
559574213 0001000000
458791850 0000000000
266378640 0111000000
944284996 1000000000
169188494 0011000010
917209852 1001100000
905699840 0110000000
519566989 1000000000
237060575 0000000000
647909317 0010000000

I'm not sure you can allocate memory like that in C++. You need to use `new`. Also, you may want to check [this](https://people.eecs.ku.edu/~jrmiller/Courses/JavaToC++/StackAllocatedArrays.html) — smac89, Sep 14 '20 at 17:57
You can allocate memory like this in C. GNU C++ allows some modern C features as an extension. — Christopher Yeleighton, Sep 14 '20 at 18:07
@smac89 Yeah, I got it. I was allocating too much memory. Thanks. — Mudit Soni, Sep 14 '20 at 18:09
If you had used `std::vector` instead of using the non-legal C++ syntax, the problem probably wouldn't have occurred. This is another reason why those variable-length-arrays are nothing but trouble if you're writing C++ code. — PaulMcKenzie, Sep 14 '20 at 18:09
This question has some related info on the limitations of this extension: [https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — drescherjm, Sep 14 '20 at 18:09
Making a vector of 0 elements will put them in trouble equally effectively. — Christopher Yeleighton, Sep 14 '20 at 18:13
@ChristopherYeleighton -- With `std::vector`, there is a chance that the error gets detected if `at()` were used. The bottom line is that a lot of this could have been prevented if `std::vector` were used and used properly. — PaulMcKenzie, Sep 14 '20 at 18:16

Shane Reilly · Accepted Answer · 2020-09-14T18:09:41.553

0

1<<100 = 1267650600228229401496703205376. You will not be able to create an array that large.

As mentioned in the comments, if you are allocating memory dynamically, you should be allocating it on the heap using new.

Also, it is bad practice to use #include <bits/stdc++.h>.

edited Sep 14 '20 at 18:09

answered Sep 14 '20 at 18:00

Shane Reilly

251
1
5

Oh you are right. I didn't think of that. Guess, my approach is wrong then. – Mudit Soni Sep 14 '20 at 18:06
2

@MuditSoni a lot of people get fooled by the garbage examples they find. Rule of thumb, when you find code that starts with `#include using namespace std;`, examine it carefully before taking any of it's advice. It could be good -but-lazy code written by a good-but-lazy code, but it could also be complete trash written by someone who doesn't know any better. – user4581301 Sep 14 '20 at 18:09
2

Mind you, that leads to the classic problem of " How will I know if it's crap or not while I'm still learning and don't know what good code looks like?" The answer to that [is good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – user4581301 Sep 14 '20 at 18:10
You cannot allocate an array using `operator new`. – Christopher Yeleighton Sep 14 '20 at 18:15
Yes you can. `int *myArray = new int[SIZE];` – Shane Reilly Sep 14 '20 at 18:25
Technically he's right. That's operator `new[]`. The distinction become important in a few cases, but I wouldn't sweat over it here. – user4581301 Sep 14 '20 at 19:38

score 0 · Answer 2 · answered Sep 14 '20 at 18:11

0

1 << 100 == 0, so your arr will be empty. Accessing an empty array causes a segmentation fault.

answered Sep 14 '20 at 18:11

Christopher Yeleighton

454
2
6

This is a very likely result, but signed integer overflow is undefined behaviour, so technically you can't be sure of what you'll get. 0 is not guaranteed. – user4581301 Sep 14 '20 at 19:43
This is a compile-time constant, not a run-time behaviour. – Christopher Yeleighton Sep 14 '20 at 19:45
The point still stands. Whatever value you get will be consistent after compilation, but you can't assume it will be 0 without more information. – user4581301 Sep 14 '20 at 19:48
I can `static_assert` it. – Christopher Yeleighton Sep 14 '20 at 19:49

Getting Segmentation fault in string assignment

2 Answers2