cniks117's blog

maximum array size
By cniks117, 12 years ago, In English

what is the maximum size of array that is permissible in c++?? can't we use an array of size 10^9 ..plz reply

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
12 years ago, # |
← Rev. 5   Vote: I like it +19 Vote: I do not like it

In theory, the maximum possible array size is std::numeric_limits<std::size_t>::max(). The maximum possible array length is the above value divided by the size of the array's element.

In practice, the maximum array size you can allocate is limited by available memory and OS restrictions.

In programming competitions, the maximum array size in bytes is limited by memory limit that is specified in the problem. Since most recent problems on Codeforces have a memory limit of 256M = 268435456 bytes, which is less than 109 bytes, you probably can't allocate such an array. Check the memory limit of your problem to be sure.

EDIT: I forgot to mention that if you want an array of bools, then you can save space by packing 8 bools¹ into each byte, which will reduce memory usage by 8 times. You can do it either using manual bit operations or with std::bitset<> (link).

¹Formally, CHAR_BIT elements.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Depends. for win 32 there are theoretical limit 4 GB (2^32 bytes) memory for all application. In practice there are 2 GB for user (programmer) and 2 GB for system (memory where loaded system dll's, file descriptors, etc). particular app can be tuned to use 3 GB for user, and 1 GB for system. For the 64-bit OS I don't know the limits, but i think they are very large, theoretically 2^64 bytes. In practice there are no hardware can operate 2^64 bytes of RAM.
A few days ago my friend has optimized memory usage of his application, when replaced dynamically allocated string class by ui32. His application works on the server powered by 64-bit unix, and uses 20-40 GB of memory. Data was divided into several blocks with the total size of string's of 2^32, and instead char* (8 bytes) was used ui32 (4 bytes) — 'pointer' in the array char[(size_t)1 << 32] where strings are placed one after another with terminating null character. The average size of used strings is less than a hundred, and because of dynamically allocated memory there was sufficient overhead. So, now it's normal to use array of size 2^32 :)

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"10^9"　means "O(n) algorithm is not allowed" in programming contest. So you should think the other way to solve the problem!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    On codeforces, O (n), where n <= 10 ^ 9 passes tests with ~2 sec. On topcoder 4 * 10 ^ 9 passes within 2 seconds.

    → Reply