CODEWITHSUNDEEP
c++
Ziad Abd El-Monem
Ziad Abd El-Monem

Reputation: 5

What is the maximum size of a vector?

Why can't this code handle n=100000000 (8 zeros)?

The code will be terminated by this error:

terminate called after throwing an instance of 'std::bad_alloc'

So, the word "DONE" won't be printed out.

using namespace std;

int main()
{
    vector <long long> v1;
    long long n; cin>>n;
    for(long long i=0;i<n;i++){
        v1.push_back(i+1);
    }
    cout<<"DONE"<<endl;
}

Although the maximum size of v1 is 536870911.

Upvotes: 0

Views: 2385

Answers (3)

Remy Lebeau
Remy Lebeau

Reputation: 596216

std::vector contains a pointer to a single dynamically allocated contiguous array. As you call push_back() in your loop, that array has to grow over time whenever the vector's size() exceeds is capacity(). As the array grows large, it becomes more difficult for a new larger contiguous array to be allocated to copy the old array elements into. Eventually, the array is so large that a new copy simply can't be allocated anymore, and thus std::bad_alloc gets thrown.

To avoid all of those reallocations while looping, call the vector's reserve() method before entering the loop:

int main() {
    vector <long long> v1;
    long long n; cin>>n;

    v1.reserve(n); // <-- ADD THIS!

    for(long long i = 0; i < n; ++i){
        v1.push_back(i+1);
    }

    cout<<"DONE"<<endl;
}

That way, the array is allocated only 1 time.

Upvotes: 1

eerorika
eerorika

Reputation: 238351

What is the maximum size of a vector?

Depends on several factors. Here are some upper limits:

  • The size of the address space
  • The maximum representable value of std::vector::size_type
  • The theoretical upper limit given by std::vector::max_size
  • Available memory - unless system overcommits and you don't access the entire vector
  • Maximum available memory for a single process may be limited by the operating system.
  • Available contiguous address space which can be less than all of the free memory due to fragmentation.

The address space isn't an issue in 64 bit world.

Note that the size of the element type affects the number of elements that fit in a given range of memory.

The most likely the strictest limit in your case was the available memory. 536870911 is one long long short of 4 gigabytes.

Upvotes: 7

SacrificerXY
SacrificerXY

Reputation: 334

From cppref max_size() docs:

This value typically reflects the theoretical limit on the size of the container ...

At runtime, the size of the container may be limited to a value smaller than max_size() by the amount of RAM available.

Upvotes: 3

Related Questions