1

I want to have an array, grid[50000][50000], i tried to do with vector but when i run the code, it stops. No error. Just waits.Any suggestions?

#include <iostream>
#include <vector>

using namespace std;

typedef std::vector<int> IntVec;
typedef std::vector<IntVec> IntGrid;
IntGrid grid(50000, IntVec(50000));

int main(){
  grid[0][0]=3;
  cout<<grid[0][0]<<endl;
}
vkx
  • 424
  • 1
  • 7
  • 17
  • 1
    *"I want to have an array, grid[50000][50000],"* - why? Is this an actual requirement or a perceived requirement based on you proposed implementation? That's way too much memory to grab up, there may be a better approach, but you need to tell us the problem you are trying to solve. – Ed S. May 03 '12 at 23:27
  • @EdS. Could you look here : http://stackoverflow.com/questions/10437622/how-to-implement-infinite-multidimensional-array/10438688#10438688 i want to use that code for at least 50k input. cac[50k][50k]. – vkx May 03 '12 at 23:29
  • 2
    @vk7x: Wanting things won't make them happen. You should look up sparse matrices and such. – Nicol Bolas May 03 '12 at 23:34
  • 1
    Suggestions from the linked question tend to point you towards something like `std::map>` or any other form of sparse storage scheme. Holding this much memory at once is almost impossible (unless you own a high end machine and you are optimistic about your OS's resource management). – Alexandre C. May 03 '12 at 23:37
  • @AlexandreC. Okay. I understand. Now, how can i deal with that? Implementing word wrapping algorithm with 50k words? – vkx May 03 '12 at 23:41
  • 2
    @vk7x: I don't know precisely about word wrapping algorithms, so I cannot help here. Would you mind asking another question, describing what you *want to do* precisely (ie. word wrapping, if possible with a layman's description of the algorithm you intend to use), and the input size requirements you have ? You'll likely get more useful answers than the ones here, since you will be asking about your actual problem, which may have many solutions you did not think about. – Alexandre C. May 03 '12 at 23:47
  • @vk7x: Also, see http://stackoverflow.com/questions/17586/best-word-wrap-algorithm – Alexandre C. May 03 '12 at 23:49

1 Answers1

3

As a very rough calculation,

50,000 rows × 50,000 columns × 4 bytes/integer = 10,000,000,000 bytes.

Unless your computer has more than 10 GB of RAM, you've run out of memory.

Can you rewrite your program to work with smaller chunks of data, or to use a file to store the parts of the array that don't require immediate access?

Adam Liss
  • 47,594
  • 12
  • 108
  • 150
  • Could you look here : http://stackoverflow.com/questions/10437622/how-to-implement-infinite-multidimensional-array/10438688#10438688 i want to use that code for at least 50k input. cac[50k][50k]. – vkx May 03 '12 at 23:29
  • 1
    Why don't you tell us what you're trying to accomplish? Maybe we can come up with a more efficient solution. – Adam Liss May 03 '12 at 23:48
  • Actually, any normal x86-64 Linux setup should be able to allocate that much memory, using swap space. But that is very slow compared to RAM. – leftaroundabout May 03 '12 at 23:48
  • It's actually probably at least twice that when you factor in the storage for the vector iterators ... – AJG85 May 03 '12 at 23:57
  • 3
    @AJG85: no, the space overhead of `std::vector` is constant so for a nested one that overhead is _O_ (_n_), which is completely neglectable vs the _O_ (_n_ ²) data amount when n is as large as 50000. – leftaroundabout May 04 '12 at 00:02
  • 1
    @leftaroundabout Do nested vectors not maintain their own begin and end pointers etc? I suppose it would only add a few hundred MB which is relatively small in comparison even if that was the case. – AJG85 May 04 '12 at 00:12
  • 1
    @AJG85 `vector` probably has three words: pointer, size, and capacity. On a 64-bit implementation that's 24 bytes/vector. 50K * 24 is about 1MB overhead for the struct vector. Maybe that much again for the malloc overhead, so we've got a few MB, not hundreds. – Robᵩ May 04 '12 at 03:27