CODEWITHSUNDEEP
c++arraysvector
Sergey Ivanov
Sergey Ivanov

Reputation: 3929

Program terminates in initialization of large array

I have V = 3997962, and I want to have an array of that size consisting of vectors of ints in C++.

When I initialize it like this:

const int V = 3997962;

vector<int> array[V];

The program terminates without prompting to any error.

Is it stack overflow error? How can I go about this?

Should I define it like this:

vector<int>* test = new vector<int>[V];

How can I pass this variable to a function? And how it should be defined as an argument? Do I need to delete it after all?

Upvotes: 1

Views: 240

Answers (5)

Mustafa
Mustafa

Reputation: 1854

While the vector data is located on the heap. The vector object size itself is (on a 64bit, Linux) 24 bytes, so you are locating 24*3997962 ~ 95MB on the stack. The default stack limit on a linux machine for example is ~8MB (try ulimit -a to check). So it is likely a stack over flow.

Upvotes: 1

WhozCraig
WhozCraig

Reputation: 66224

You're asking for 3997962 * sizeof(std::vector<int>) in automatic storage space if this is declared local to some function. To better understand how much space the basic management members of a std::vector<int> occupy, consider:

#include <iostream>
#include <vector>

int main()
{
    std::cout << sizeof(std::vector<int>) << '\n';
}

Output (OSX 10.10, 64bit clang 3.5)

24

thusly, (at least on my platform) you're requesting at least 3997962 * 24, or 95951088 bytes ( roughly 92 MB) of automatic storage. So yes, you're very likely blowing out your automatic storage space. To place all but the primary management data of a single vector on the heap, you can:

std::vector<std::vector<int>> vv(N);

which will create a vector of N vectors of int, all of which are initially empty and heap-managed. the core management data internal to the base vector vv is still in automatic storage, but as you can see:

#include <iostream>
#include <vector>

int main()
{
    std::cout << sizeof(std::vector<std::vector<int>>) << '\n';
}

Output

24

the footprint in automatic storage is considerably reduced

To address your followup questions of:

  • How can I pass this variable to a function?
  • How it should be defined as an argument?

How to pass this (the first question) depends entirely on whether you need to modify its content, and will effect how you declare the parameter (the second question). To avoid expensive copies, pass it by reference. Second, if the callee doesn't need to modify the data, pass it as const:

// read-only, pass as const-reference
void doesnt_modify(const std::vector<std::vector<int>>& vv)
{
    // use here, can't modify
}

// writable, pass as reference
void can_modify(std::vector<std::vector<int>>& vv)
{
    // use here, can modify
}

Upvotes: 1

jxh
jxh

Reputation: 70422

If this is a local variable, you are basically asking for almost 8 million pointer variables in automatic storage. This will likely fail due to stack overflow.

You can instead use a vector of vectors.

vector<vector<int>> array(V);

The above results in a vector called array that is populated with V default initialized vector<int>s.

Upvotes: 6

Joseph Mansfield
Joseph Mansfield

Reputation: 110658

It is very likely a stack overflow.

You are allocating V vector<int>s. While the elements of those vectors will be allocated on the heap, the vectors themselves (which contain a pointer and a few other objects) are being allocated on the stack. If you have V of these, you will likely hit your stack limit.

vector<int>* test = new vector<int>[V];

This is one possible solution, but not ideal. It will require you to delete[] the array later, with delete[] test;. You could get around this problem by wrapping this dynamically allocated array in a smarter pointer, but keep reading for a better solution.

How you would pass this to other functions is not really relevant (you should design function parameters completely independent of how the client might allocate them), but you could just pass the pointer around:

void f(vector<int>* param);
f(test);

The parameter could alternatively be written as vector<int> param[], which might better express that this pointer points to an array. consts could also be added where you want immutability. However, we can find a nicer solution by avoiding using new and raw pointers entirely.

Instead, I would recommend having a vector<vector<int>>:

vector<vector<int>> test(V);

Now you only actually have one vector on the stack. The elements of that vector, which are themselves vectors, will be allocated on the heap, and their elements also.

Upvotes: 6

Vlad from Moscow
Vlad from Moscow

Reputation: 310980

You should provide that the array would have static storage duration. Either define it outside any function in some name space or use keyword static if you want to define it in a function (for example main)

static std::vector<int> array[V];

because the stack memory is very limited.

Otherwise define it in the heap or use the same vector. For example

std::vector<vector<int>> array( V );

Or

std::vector<vector<int>> array;
array.reserve( V );

Take into account that class std::vector has member function max_size that allows to obtain information about the maximum acceptable size of the vector.

Upvotes: 1

Related Questions