CODEWITHSUNDEEP
c++gccvectorstldeque
lucent
lucent

Reputation: 124

Why did I get deque's max_size() less than vector's max_size()?

While learning (& experimenting) with STL containers I found out that the vector max_size = 4611686018427387903 and deque max_size = 2305843009213693951 on my system(gcc version 4.7.2, x86_64). From my (limited) understanding deques are usually implemented internally as list of vectors(or vector of vectors?). If that is the case then why is deque's max_size lesser than that of a vector which(vector) would actually require contiguous block of memory and a deque may be able to work with multiple contiguous blocks? Does it have anything to do with my system configuration, current state or it is the way it has to be?

Upvotes: 1

Views: 269

Answers (2)

Arne Mertz
Arne Mertz

Reputation: 24576

I am missing one detail in your question: Which types did you test the max_sizes with? Ideone's gcc 4.7.2 (on 32bit) says that both have the same max_size - if given the same element type. For int its 2^30-1 - which means the maximum size of stored data is (2^32 - 4) bytes, since sizeof(int) == 4 on that system.

This is a wild guess here: have you compared vector<T>::max_size vs. deque<U>::max_size with sizeof(T) == 4 and sizeof(U) == 8? that would explain the approximate factor 2.

Be that as it may, your experiment shows, that the max_size returns only a very theoretic number, since you surely can't get 2^62-1 ints into memory. The -1 stems from the fact that the "first" 4 bytes have to be left empty, or else &vec[0] == NULL. You could not have any other data in that program than the ints stored in the vector - that includes the vector itself!

Upvotes: 1

congusbongus
congusbongus

Reputation: 14622

As you may have noticed, 4611686018427387903 is 2^62 - 1 and 2305843009213693951 is 2^61 - 1, which should give you a hint to where those numbers come from (hint: nothing to do with your system configuration).

I don't know the real reason, but I would guess that it's very academic and has nothing to do with how vectors or deques are implemented. Perhaps GCC's deque uses an extra bit to keep track of something else. Someone familiar with GCC can probably chime in here. Anyway the language standard says nothing about what max_size should be, so it's fully up to library/compiler implementers.

Those numbers are very large, and in practice you'll see other things blow up way before you approach max_size. Perhaps there are wacky STL implementations where max_size is very small, but at least for GCC you don't need to worry about it.

Upvotes: 0

Related Questions