Take the 2-minute tour ×

I want to use the code below and I want to use it for "unknown size of input". For example there is an array int cac[1000][1000]. I can use vector<vector<int> > array;, then how can i initialize it with -1 ? Any suggestions?

#include <sstream>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <memory.h>

using namespace std;

int cac[1000][1000];
string res[1000][1000];
vector<string> words;
int M;

int go(int a, int b){
 if(cac[a][b]>= 0) return cac[a][b];
 if(a == b) return 0;

 int csum = -1;
 for(int i=a; i<b; ++i){
  csum += words[i].size() + 1;
 if(csum <= M || a == b-1){
  string sep = "";
        sep = " ";
  return cac[a][b] = (M-csum)*(M-csum);

 int ret = 1000000000;
 int best_sp = -1;
 for(int sp=a+1; sp<b; ++sp){
 int cur = go(a, sp) + go(sp,b);
 if(cur <= ret){
    ret = cur;
    best_sp = sp;
 res[a][b] = res[a][best_sp] + "\n" + res[best_sp][b];
 return cac[a][b] = ret;

int main(int argc, char ** argv){
memset(cac, -1, sizeof(cac));
M = atoi(argv[1]);
string word;
while(cin >> word) words.push_back(word);
go(0, words.size());
cout << res[0][words.size()] << endl;
share|improve this question
What semantics would you expect -1 to have? –  ildjarn May 3 '12 at 18:55
I'm confused, can you maybe explain what you're looking to do in a little more depth? –  pg1989 May 3 '12 at 18:56
An infinite array is a linked list. That is what it sounds like you want. –  Tejs May 3 '12 at 18:56
std::map<int, std::vector<int>> That will work better for you I think. –  andre May 3 '12 at 19:06
@vk7x : if (cac[i].empty()) { /*not initialized*/ }... –  ildjarn May 3 '12 at 19:07
show 8 more comments

2 Answers

What you can do is to use a associative array, where the key is a pair (rowPosition, ColumnPosition). When you want to set array[i][j] you just add or update the value assoArray[Pair(i,j)]. You can assume that any element which is not in the associative array has the initial value.

In general infinite multidimensional arrays are used for theoretical purpose.I hope i didn't misunderstood the question.

share|improve this answer
add comment

Using std::vector from the STL is much more straightforward than the following solution, which was pointed out in the comments for this post. I find that this site explains that topic effectively: http://www.learncpp.com/cpp-programming/16-2-stl-containers-overview/

An array of infinite size is not actually possible. However, you can achieve basically that effect using dynamic allocation. Here's some sample code:

int counter = 0;
int* myArray = new int[1000];

Fill the array with data, incrementing counter each time you add a value. When counter reaches 1000, do the following:

int* largerArray = new int[2000];
    largerArray[i] = myArray[i];
delete[] myArray;
myArray = largerArray;

With this method, you create the closest thing possible to an infinitely sized array, and I don't believe performance will be an issue with the copy piece

share|improve this answer
I don't believe that type of mistake is deserving of a downvote for my post. You are correct though, good suggestion –  TheResolute May 4 '12 at 1:00
My downvote was incentive for you to change your post. And it will be withdrawn once you have done so. –  Nicol Bolas May 4 '12 at 1:58
I didn't realize that was possible. That's pretty funny, thanks for the tip XD . –  TheResolute May 4 '12 at 6:48
add comment

Your Answer


