size limit of allocation in c++?

Question

I use this to allocate a 2D array in cpp:

int s[n][2];

but it seems that when n is very big ( up to 1e6 ), this creates a Runtime error (exitcode: 11).

How to solve this problem?

Answer 1

You are allocating on the stack, and you are getting stack overflow.

You need to allocate your 2d array like this

int** ary = new int*[sizeY];
for(int i = 0; i < sizeY; ++i)
ary[i] = new int[sizeX];

See How do I declare a 2d array in C++ using new?

Or better yet, use Boost::ublas::matrix or Eigen Vector2d, or as Paul McKenzie suggested, use std::vector (easiest of them all)

Answer 2

That is not dynamic allocation. Also, if n is a variable, it isn't even valid ANSI C++, since you cannot declare arrays with a variable number of entries.

To properly allocate dynamically, consider using a std::vector.

#include <vector>
//...
// Simulate s[n]
std::vector<std::vector<int>> s(n, std::vector<int>(2));
//..
// You can now use s similar to a 2 dimensional array.

If for some reason, you require the data to be contiguous for the 2-d array, consider the answers here:

how to create a contiguous 2d array in c++?

Answer 3

That type of declaration allocated memory on the stack. That's probably too big. Use REAL dynamic allocation (new int[n]).

Answer 4

As the other said, the "problem" you're having is because you're not using dynamic memory allocation.

@{Straight Line} showed you a C-like solution to create 2d arrays, and @PaulMcKenzie showed you one using vectors and raised the issue of contiguous storage. However, the latter is different because it doesn't constrain the size of the columns (assuming a [row][col] indexing).

The answer of @dasblinkenlight shows you how to create your own 2d array class; I think this is the essence of C++, getting to define yourself how you intend the memory to be managed, and expose a set of publicly accessible methods to interact with this "object" in your code. A 2d array of size n x p is nothing else than np elements indexed by two subscripts, so that's what you should code. Here a close-to-minimal example of how to do that:

#include <new>

template <class T>
class Array2D
{
public:

    Array2D() 
        : m_ptr(NULL)
        { clear() }
    ~Array2D()
        { clear(); }

    void clear() 
    { 
        // free current allocation if any
        if (m_ptr) 
            delete[] m_ptr; 

        // reset member variables
        m_ptr = NULL; 
        m_nrows = m_ncols = 0; 
    }

    inline unsigned nrows() const { return m_nrows; }
    inline unsigned ncols() const { return m_ncols; }

    void set_size( unsigned nr, unsigned nc ) 
    { 
        // clear any previous allocation
        clear(); 

        // new allocation
        m_ptr   = new T[nr*nc];
        m_nrows = nr;
        m_ncols = nc;
    }

    // access elements using [row][col]
    inline T* operator[] ( unsigned row )
        { return &m_ptr[ row*n_cols ]; }

    // access elements using (row,col)
    inline T& operator() ( unsigned r, unsigned c )
        { return m_ptr[ c + n_cols*r ]; }

protected:

    T *m_ptr;
    unsigned m_nrows, m_ncols;
};

If you know you're going to use matrices a lot though, your first reflex should be to check out what already exists. There are many mature C++ libraries that implement 2d arrays (see eg this comparison), dealing with features, issues and optimisations that you do not want to revisit on your own (unless you really know what you're doing or you really need something simple). You just need to find the library that fits your need for each particular application.