29

On an online course I am learning about vectors. In one of the examples they explained that: std::vector::max_size() should give me the maximum size the vector can reach. I decided to test it:

#include <iostream>
#include <exception>
#include <vector>

int main(void) {
    std::vector <int> nums;
    int max = nums.max_size();
    std::cout << "Max: " << max << std::endl;
    for (int i = 0; i < max; i++) {
        try {
            nums.push_back(i);
        }
        catch (std::bad_alloc ex) {
            std::cerr << ex.what() << std::endl;
            std::cout << "Failed at: " << i << std::endl;
            break;
        }
    }

    return 0;
}

And this is the result of running it:

Max: 1073741823
bad allocation
Failed at: 204324850

It was 869416973 ints short.

So I started googling it. Here I read that it returns the "the maximum potential size the container can reach", and adds "but the container is by no means guaranteed to be able to reach that size". I would have imagined that it would fail, but not by that much. It just got 1/5 of the way before failing. Why is std::vector::max_size so off? And what I see of more importance, is there a way of really knowing the potential size of a vector?

10
  • Number of elements in the vector is not the same as size. sizeof is in bytes
    – stark
    May 18, 2020 at 18:08
  • 14
    Maximum realizable size will depend on how much RAM you have available, and the amount of RAM you have available can vary widely from one millisecond to the next (as other programs allocate and free chunks of RAM); so there's no easy way of returning a meaningful value regarding how big the vector might be capable of growing on your hardware at this exact moment May 18, 2020 at 18:19
  • 6
    max_size() for containers is weird, and not particularly useful. With 20/20 hindsight, it probably should not exist. May 19, 2020 at 13:36
  • @JeremyFriesner: RAM should be virtual memory, right? The amount of RAM hardly matters, except that the program will become slow due to swapping. May 19, 2020 at 20:46
  • @ThomasWeller many of the computers I use are deliberately configured without any swap space, because a computer that can't keep up with its task load due to swapping is even less useful than a computer that had to invoke the OOM-killer on some processes to recover RAM. At least in the latter case, the killed processes can be auto-respawned and then useful work can resume without manual intervention. So I think the amount of RAM definitely matters :) May 19, 2020 at 20:55

4 Answers 4

26

Note that the max_size function returns a theoretical maximum number of elements, it doesn't say anything about the amount of memory needed.

If we assume that sizeof(int) == 4 (pretty common) then 204324850 elements would need 817299400 bytes of contiguous memory (that's almost 780 MiB).

You get a bad_alloc exception because the vector simply can't allocate enough memory to hold all the elements.

3
  • 1
    Also the data structure bookkeeping would take memory, and with small data elements like that, it could be significant. But I think vector will only have constant overhead since it just allocates the elements consecutively in memory, so no need for extra pointers or such.
    – ilkkachu
    May 19, 2020 at 12:17
  • Shouldn't max_size be a constant since it returns a theoretical maximum? Which will always be the same? May 19, 2020 at 17:35
  • 1
    @TimotejLeginus It's implementation defined. It could depend on factors outside the standard library, like the operating system, target hardware, and other things. May 20, 2020 at 4:00
22

std::vector::max_size() should give me the maximuim size the vector can reach

This is not quite correct. max_size gives you a theoretical upper bound. Vector definitely won't support any size larger than that, but that doesn't necessarily mean that you can create all vectors up to that size.

The most limiting factor will be the amount of free memory that the operating system is willing or able to assign for the process. There is no standard way to get that size, and even implementation specific ways are not straight forward.

Another potential limit is longest free contiguous address space, which may be fragmented. This probably won't be a problem for 64 bit programs with their astronomically large address space, but it is a consideration for systems with 32 bit or smaller address.


Failed at: 204324850

Assuming 4 byte int, that is about 780 Megabytes (non-metric).


In conclusion: Instead of trying to find out how much memory your program could use at run time, you should figure out the amount of memory that you know will be sufficient. Don't allocate more than that. Make sure that the computer has sufficient memory, and the operating system is not configured to limit the memory use to lesser amount. Use 64 bit address space.

6
  • 1
    Fun fact: reserve() doesn't dirty the memory it allocates, so you only need the virtual address space, not the backing store (physical RAM + swap space) to actually handle it. Most OSes allow "overcommit" so your program could just crash during push_back into already reserved space if your system doesn't have enough free RAM. May 19, 2020 at 20:35
  • @PeterCordes interesting, is the C++ standard OK with the program crashing on push_back?
    – Paul
    May 19, 2020 at 22:38
  • IDK if it's strictly ISO C++ compliant, but even if you don't reserve first, any allocation that isn't insanely huge will usually succeed (on OSes that overcommit), and then crash when you try to use it. That includes when std::vector tries to allocate + copy when growing without reserve. So the whole std::bad_alloc exception model doesn't really match how modern mainstream OSes work in practice, when you're constrained by limited RAM + swap, not address space (i.e. the normal case in 64-bit code where address space is nearly unlimited compared to RAM size, except on huge servers.) May 19, 2020 at 22:57
  • 1
    @Paul The C++ standard acknowledges that there are finite implementation limits, that may prevent the implementation from successfully processing the program. As long as the language implementation documents that there is a limit on memory use (well, duh) then crashing wouldn't violate conformance as far as I can tell.
    – eerorika
    May 19, 2020 at 23:03
  • Regarding Windows, from Raymond: "The system [...] does enough bookkeeping to ensure that if you write data to the pages that you committed, then the system will have a place to hold this data and produce it upon demand", so sounds like it shouldn't happen. devblogs.microsoft.com/oldnewthing/20170419-00/?p=95995
    – Paul
    May 20, 2020 at 7:54
9

Think about it this way; the vector is written in a way that it can internally handle up to (say) 32 bits worth of elements, so max_size will give you some number in the ~2-4 billion range. But you are running the code on a system with only 1MB of memory, so of course you can never grow the container that big. But, the vector has no way of knowing on what system you use it - it only knows it's maximum theoretical limit.

7

I would point out the following factors that make it impossible to allocate max_size amount of memory:

  • the available memory on your system could have changed between max_size was invoked and the memory was attempted to be allocated
  • there might not be large enough block of continuous memory available for allocation (i.e. there might be enough memory in total, but was fragmented and vector is guaranteed to store the memory in continuous block)
  • vector resizes when new elements are added to it (like you do with push_back); when it happens, the content of old vector is copied to new one - and there might not be enough memory to store both of them at the same time.
  • you might not have enough memory in your system in the first place. For example, on my system, max_size returns something like (maximum_value_of_ptrdiff_t/sizeof(vector_element)). While this number can be huge, the physical limits of a given machine may allow for something much more smaller
2
  • The fact that alloc+copy will fail won't stop you from allocating a large vector<> in the first place. It just calls new; it doesn't ask the allocator to check that there's room for another allocation of the same or double size. Or are you saying that the way the OP grows their vector with push_back instead of one big resize means that their testing will find a limit that's lower than if they'd just used resize() or reserve() on an initially-empty vector? Because yes, that's true. May 19, 2020 at 20:32
  • @PeterCordes Yeah, I meant that the latter. I certainly didn't mean that vector checks whether any future allocations are possible.
    – lukeg
    May 19, 2020 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.