1

I want to make a bool matrix named connectionsOf with size of up to 40 000. Here is my code:

int index = 40000;
bool connectionsOf[index][index];

However, when I run it on a file with 37 000 numbers to fill up the matrix, there is a segmentation fault. Browswing around on stackoverflow, I discovered it's because the index number is too high that it blows the stack. Is there a way to make this stack possible though? such as static, const, dynamic, pointers? and if so, what should I replace my code with?

masrtis
  • 1,282
  • 17
  • 32
Vera Vi
  • 19
  • 1
  • 2
  • 2
    Thats not an array of size 40000; its (40000*40000) or **1600000000**. Just a wee bit over your likely stack limit (and this won't compile in C++ anyway, as it is effectively a VLA). – WhozCraig May 08 '13 at 16:22
  • 1
    @WhozCraig: I think it will compile with GCC, as a GNU extension. – rodrigo May 08 '13 at 16:40
  • you need to dynamic allocate the memory, but why you need that huge number, can't you process in chunks? – Lefsler May 08 '13 at 17:02
  • or you can use as a int vector with bit shift, so in every int you can store 8 bool and with var &0x00000001 you can check the bit – Lefsler May 08 '13 at 17:03

4 Answers4

4

You can simulate a two-dimensional bit array (and likely save a bit of memory) by writing a wrapper around boost::dynamic_bitset.

class BitMatrix
{
public:
    BitMatrix (int size) : size_(size), bits_(size_ * size_) {}
    void set(int x, int y) { bits_.set(y * size_ + x); }
    bool test(int x, int y) { return bits_.test(y * size_ + x); }
private:
    int size_;
    boost::dynamic_bitset bits_;
};

If you know the size at compile time, you can also use this technique with std::bitset.

Michael Kristofik
  • 34,290
  • 15
  • 75
  • 125
  • There's a _specialization_ of `std::vector` (see http://www.cplusplus.com/reference/vector/vector-bool/) which implements the "dynamically-sized bitset". It can be used for this. – FrankH. May 24 '13 at 08:02
2

Answer to your question depends on compiler you are using. For gcc see this question. But why do you need to allocate such large data massif on stack, not on heap? And, by the way, you need to allocate 200 x 200 array to get 40 000 items (200^2).

Community
  • 1
  • 1
eraxillan
  • 1,552
  • 1
  • 19
  • 40
2

you're abusing stack. 40'000 x 40'000 x sizeof(bool) = (at least) 800'000'000. that's a lot (800MB in a single chunk)

try:

index = 40000;
bool** connections = new bool*[index];
for (int t = 0; t < index; ++t) {
    connections[t] = new bool[index];
}

be sure to dispose of it adequately, too (the same as above, just reverse - first iterate and dispose array elements, then dispose table itself)

Tomasz W
  • 1,841
  • 1
  • 16
  • 25
  • it's a 2D array, not 1D.. I'm not quite sure what you mean by disposing/when since I need to access the matrix during run-time with user input. – Vera Vi May 08 '13 at 18:35
  • This code makes an array-of-arrays. "Dispose" here means that everything allocated by `new []` must be deallocated by `delete []`. You have to delete the inner arrays first before deleting the outer array. – Michael Kristofik May 09 '13 at 14:33
  • why do people repeat the nonsense of "beeellions of `new` calls" for "2D arrays" over and over ... – FrankH. May 24 '13 at 08:05
0

You should be able to set the stack size via compiler flags.

Pochi
  • 2,026
  • 1
  • 15
  • 11
  • how does one go about doing this? since my program will be tested on a computer different then mine, is there a way to do this from my files? – Vera Vi May 08 '13 at 18:35