Create a big array in C++

Question

Possible Duplicate:
Segmentation fault on large array sizes

Hi all

I am trying to create a very big array in the VS 2010 using C++.

When I try to create a array like below

int dp[4501][4501]
or
int dp[1000][1000]

It threw an exception "Stack Overflow" Then I change it to:

int dp[100][100]

everything is fine.

So if I want to create a big array like above, what should I do?

Best Regards,

score 9 · Answer 1 · edited May 23 '17 at 12:16

9

Use dynamic allocation or the STL. There was a recent thread about a very similar question. See this.

edited May 23 '17 at 12:16

Community

1
1

answered Jun 29 '10 at 03:12

vpit3833

7,817
2
25
25

score 6 · Answer 2 · edited Jun 29 '10 at 08:43

6

You should use dynamic allocation:

typedef std::vector<int> int_vector;
int_vector dp(10000);

A double array can be simulated by nesting arrays:

typedef std::vector<int_vector> int_double_vector;
int_double_vector dp(4501, int_vector(4501));

edited Jun 29 '10 at 08:43

David Rodríguez - dribeas

204,818
23
294
489

answered Jun 29 '10 at 03:12

GManNickG

494,350
52
494
543

4

I don't like typedef's used like this. Why? Simple: Your `int_array` is actually an *int* **vector**, and your `int_double_array` has nothing to do with a **double** at all. (Plus I have to do *two* lookups to find out what it actually is.) Bad style, IMHO. Use typedef's for really complex or cryptic things only, and even then only if their declarations are frequent throughout your code. (Iterators for maps of vectors of pairs, or function pointers spring to mind.) For declarations used but two or three times, they're a tool of obfuscation. – DevSolar Jun 29 '10 at 07:59
@Dev: I think you're reading way too into it. :) Happy? Double means two, and only coincidentally is the double-precision floating-point type called double, don't let that get in the way of English definitions. Code is for humans. – GManNickG Jun 29 '10 at 08:09
2

The wording int_double_vector _really_ sucks. You should do sth like 2d_int_vector instead. Other than that there is no problem with the typedef, it is hell better than working with a std::vector >::iterator... – ypnos Jun 29 '10 at 08:22
1

"double" in context of programming usually (and in context of "types in programming" almost exclusively) means "double precision floating point". – el.pescado - нет войне Jun 29 '10 at 09:05
4

@ypnos: After 10 years of C++ maintenance coding, I actually much prefer code without a typedef in sight. Yes, that includes `std::vector< std::vector< int > >::const_iterator` and similar stuff. The ratio of useful typedefs vs. obfuscating ones is, in my experience, about 1 in 20. – DevSolar Jun 29 '10 at 14:12

score 5 · Answer 3 · answered Jun 29 '10 at 03:11

5

Put it on the heap.

answered Jun 29 '10 at 03:11

Marc Bollinger

3,109
2
27
32

1

Except don't directly use `new` nor `malloc`. – GManNickG Jun 29 '10 at 03:12
3

There's nothing explicitly wrong with them, especially at the level of understanding where this is aimed. – Marc Bollinger Jun 29 '10 at 03:17
there is nothing explicity wrong with them, but "new int[4501][4501]" is wrong, which is what GMan meant. – Michael Aaron Safyan Jun 29 '10 at 03:27
1

Using manual memory management is bad programming, wrap it up. `std::vector` exists for this purpose. – GManNickG Jun 29 '10 at 03:51

score 2 · Answer 4 · answered Jun 29 '10 at 06:44

2

If you want to avoid new[], or avoid using std::vector, make the array global. This will put the array on heap and stack overflow will not occur.

answered Jun 29 '10 at 06:44

Donotalo

12,748
25
83
121

1

Please no global variables. There are infinitely many better solutions in this case (`vector` is not the only container class). – Philipp Jun 29 '10 at 07:04
2

@Philipp: global variables are useful in certain circumstances. And if you put global variable into namespace (or make a static global member in a struct or class), then there is absolutely nothing wrong with them. Another solution is to make variable (declared within function) static. – SigTerm Jun 29 '10 at 08:25
Global variables usually cause more problems than they solve. And they are definitely not a solution if all you want is heap allocation. – Philipp Jun 29 '10 at 08:44
I guess the OP is trying to solve some programming problem, where getting 'Correct' is everything. Coding like professional programmers is overkill for someone only willing to get his/her solution 'Correct'. Also, using containers instead of plain array will take more time to solve the problem. Once I had such problem. I used std::vector and got Time Limit Exceeded. I just replaced the vector with plain array and got my solution passed. – Donotalo Jun 29 '10 at 08:50
-1 for providing a "bad practice" solution. – Alexandre C. Jun 29 '10 at 09:19
I've mentioned why I've suggested using global. When you solve a problem from programming contest, you don't practice software engineering. – Donotalo Jun 29 '10 at 10:54
For me it was the best solution because I wanted to run a fast test with a small code and I didn't want to bother exactly with new[] and std::vector. Nevertheless, good to underline that it's a bad practice. – Elena Apr 13 '14 at 19:47

score 1 · Answer 5 · edited May 23 '17 at 11:52

1

Text from Parashift faq : Why should I use container classes rather than simple arrays?

EDIT:

Take a look at stackoverflow threads:

When would you use an array rather than a vector/string? Why use iterators instead of array indices?

edited May 23 '17 at 11:52

Community

1
1

answered Jun 29 '10 at 03:15

KV Prajapati

93,659
19
148
186

score 1 · Answer 6 · answered Jun 29 '10 at 03:34

1

Your stack has overflowed with too many bits. You must drain them. Preferably onto a heap of other bits. I suggest /F67108864. The /F stands for "F'ing hell why is the stack so small compared to the heap?". The 67108863 is arbitrary.

answered Jun 29 '10 at 03:34

John

71
1

5

We need tags for answers. Tags like *funny-but-wrong-approach* – Ben Voigt Jun 29 '10 at 04:01
I think setting a stack size large enough to handle the array is a good approach. The slash /F option to the compiler does just that. Adding humour to the answer doesn't invalidate it and make it the wrong approach. – Ivan May 02 '18 at 08:32

score 0 · Answer 7 · answered Jun 29 '10 at 07:03

Your declaration looks a bit as if dp will be used as a matrix. In that case, a dedicated (dense) matrix class such as boost::numeric::ublas::matrix is the simplest solution, easier and more local than a vector of vectors. If the matrix is sparsely populated, use a sparse matrix class instead.

stinky472 · Answer 8 · 2010-06-29T07:58:18.687

So if I want to create a big array like above, what should I do?

Avoid using the stack for these cases (in other words, avoid creating arrays like these which aren't heap-allocated when working inside a function). Just to give you an idea, my thread-local stack is only 16 kilobytes large. 4501 * 4501 * 4 (assuming 4 bytes per int) = ~81 megabytes.

Consider something like this instead:

typedef vector<int> Row;
typedef vector<Row> Matrix;
Matrix dp(4501, Row(4501) );

If you want to create a 10x50 matrix:

Matrix dp(10, Row(50) );

You can use this just like your normal dp array had it not overflowed the stack. This one will be allocated and automatically deallocated to/from the heap so that you don't have to worry about stack overflow when using it.

dp[5][10] = 123;

Good luck!

[Edit] There are also matrix solutions in boost worth looking into but suggesting boost might be a bit premature given the nature of the topic.

Create a big array in C++

8 Answers8

Linked

Related