EugeneJudo's blog

By EugeneJudo, history, 5 weeks ago, In English

There are many methods of ensuring that you don't write beyond your arrays bounds, i'm wondering which others have found to be best.

For instance, I just went through a simple problem which was solvable via recursion, and handled bounds like this:

bool inBounds(vector<vector<int>> &G,int i,int j){
    return (i >= 0) && (j >= 0) && (i < G.size()) && (j < G[0].size());
}
 
void fill(vector<vector<int>> &G,int i,int j){
    if(!inBounds(G,i,j) || !G[i][j]) return;
    G[i][j] = 0;
    fill(G,i-1,j); fill(G,i+1,j);
    fill(G,i,j-1); fill(G,i,j+1);
}

Instead of this, I could have handled bounds like this:

void fill(vector<vector<int>> &G,int i,int j){
    if(!G[i][j]) return;
    G[i][j] = 0;
    if(i-1 >= 0) fill(G,i-1,j); 
    if(i+1 < G.size()) fill(G,i+1,j);
    if(j-1 >= 0) fill(G,i,j-1); 
    if(j+1 < G[0].size()) fill(G,i,j+1);
}

but the second approach seems more susceptible to bugs! i.e. it relies on picking the right bound to check, instead of blanket checking every one of them.

There's also a third approach I sometimes use, which here would be to modify G in the following way

void preprocess(vector<vector<int>> &G){
    G.insert(G.begin(),vector<int>(G[0].size()+2,0));
    for(int i=1;i<G.size();i++){
        G[i].insert(G[i].begin(),0);
        G[i].push_back(0);
    }
    G.push_back(vector<int>(G[0].size(),0));
}

void fill(vector<vector<int>> &G,int i,int j){
    if(!G[i][j]) return;
    G[i][j] = 0;
    fill(G,i-1,j); fill(G,i+1,j);
    fill(G,i,j-1); fill(G,i,j+1);
}

Then no bounds checking is needed! As long as we never start at an edge, since our preprocessing adds a boundary of 0's around G, and part of the problem already involved terminating when we hit a 0.

Are there other method/tricks for making this process easier? It's usually not that big of a consideration, but when a bug appears because of it, it can sometimes lead to 30 minutes of fruitless debugging. How do you handle this?

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

First is best

It's usually not that big of a consideration

It isnt.

How do you handle this?

By working on debugging skills.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Well I thought it was an interesting question. After some reading, adding the flag -fsanitize=address to g++ looks to be what I was looking for in helping find out of bound writes, before they lead to notorious undefined behavior.