Test for first empty value of array

Question

Is there anyway to test for the first empty value of a 2 dimensional int array in c?

In my current program, I used 2 for loops before the main program(while loop) to set all the values of my 2 dimensional array to -9999. Then inside my main while loop, I test for the first -9999 value and set it to a value, and then use break to exit from it.

Using this I managed to do my assignment, but I'm not very satisfied, as I think there might be a better solution.

Is there one?

EDIT: Code since you asked for it.

For loop outside while loop:

for(int x=0;x<ctr-1;x++)
{
    for(int y=0;y<maxtrips;y++)
    {
        EmployeeKilos[x][y] = -9999; // Set all the kilos to -9999 to signify emptiness.
    }
}

Inside my main while loop:

for(int x=0;x<ctr-1;x++)                                                              // and set it to the log kilometers 
{
  if(employeenames[x].EmployeeNumber == log.Record)
  {
    for(int y=0;y<maxtrips;y++)
    {
      if(EmployeeKilos[x][y] == -9999)
      {
        EmployeeKilos[x][y] = log.Kilometers;
        break;
      }
    }
  }
}

All my code: http://pastebin.com/Zb60mym8

nope. There is no code (I don't see it), so we cannot propose a better version of non-existing code :). — sehe, Nov 28 '11 at 07:47
Might be a better fit for http://codereview.stackexchange.com ? — Paul R, Nov 28 '11 at 07:52

score 1 · Answer 1 · edited May 23 '17 at 12:20

As Dave said, checking for empty values cannot be made more efficient than linear time (O(n)), but my answer focuses on a solution that can prevent having to look for it in the first place.

In general you could iterate the matrix in row-major or column-major mode.

Effectively, you can use a single index that translates to a matrix cell like so

for (size_t i=0; i<ROWS*COLS; ++i)
{
     int row = i / ROWS;
     int col = i % ROWS;

     // work with matrix[row][col]
}

This way you could just store and remember the value of i where you last found the first empty cell, so you don't have to restart from the beginning.

If you're not actually interested in row/col addressing, you could forget about those and just use an output iterator to track your current output location.

Here's a demo using 'iterator' style (borrowing from c++ but perfectly C99)

typedef int data;
typedef data* output;

output add_next(data matrix[ROWS][COLS], output startpoint, data somevalue)
{
    if (output < (matrix + ROWS*COLS))
         *(output++) = somevalue;
    return output;
}

Now you can just say:

add_next(matrix, 42);
add_next(matrix, 9);

NOTE the output iterator thing assumes contiguous storage and therefore cannot be used with so-called jagged arrays

HTH

Wow, seems pretty complicated, but I'll read up on it. Thanks :) — Amir, Nov 28 '11 at 07:57
@lelouch: As Dave said, checking for empty values cannot be made more efficient than linear time (O(n)), but my answer focuses on a solution that can _prevent_ having to look for it in the first place. If you are filling these values in a sequential loop, this would mean the difference between linear and quadratic (`O(n*n)`) time). Note that quadratic time quickly becomes a noticeable performance bottleneck in often-used code (or for large _`n`_) — sehe, Nov 28 '11 at 08:01

score 0 · Answer 2 · answered Nov 28 '11 at 07:53

0

You can use memset to initialise arrays to a fixed value - it's a bit more efficient and cleaner looking than iterating over the array.

Checking for your 'empty' value can't be done much faster than you are doing it, though. :)

answered Nov 28 '11 at 07:53

Dave

556
1
6
17

score 0 · Answer 3 · answered Nov 28 '11 at 10:55

This sounds like you should think about your datatype. Since you are already using structs. why don't you add another int for the last unassigned value so you just loop to it. something like e.g:

struct t_EmployeeKilos{
 int kilos[maxtrips];
 int nlast;
} EmployeeKilos[N];

and set nlast whenever you assign a new element in kilos. This way it is O(1).

for(int x=0;x<ctr-1;x++)                                                              // 
{
  if(employeenames[x].EmployeeNumber == log.Record)
  {
        EmployeeKilos[x].kilos[EmployeeKilos[x].nlast] = log.Kilometers;
        EmployeeKilos[x].nlast++;
  }
}

Test for first empty value of array

3 Answers3