Do Jagged Arrays Exist in C/C++

What array structure is in C# but not in C/C++/Java?

C++

• So this suggests that there's no jagged arrays in C++

By the same reading, the block of text suggests that C++ doesn't have single dimensional arrays. This is clearly absurd!

C++ has both... You clearly can make a int**, that is a pointer to a pointer (so an "array" of pointers, so an "array" of "arrays"), like in C# you can have a int[][], that is an array of int[]. For C++ see various examples here. Note that this syntax is more C than C++... In C++ you should use std::array, like here.

• Another thing is that just C# can have non-zero array lower-bound(like a[-1,3] or a[4,9])

This doesn't exist in C++... They are internally implemented in C# by the same code that implements multi dimensional arrays, and exist for historical reasons (pseudo-compatibility with old versions of VB)

Java

Java doesn't have multi-dimensional arrays (see here). It does have jagged arrays, with a trick: if you want you can initialize a jagged array that has all the elements of the same size in a single command or if they have different sizes/some of them can be null, you can initialize them manually.

int[][] num = new int[4][2];

vs

int[][] num = new int[4][];
num[0] = new int[1];
num[1] = new int[2];
num[2] = new int[3];
num[3] = new int[4];

So in the end

                            C#    Java  C++   
single-dimensional array    x     x     x
multi-dimensional array     x           x
si.di. non-zero based array x
mu.di. non-zero based array x
jagged array                x     x     x

How to compare jagged array to another array in C?

You have the (inner) loop:

int *ptr = result[i];
for (int j = 0; j < size[k]; j++)
{
     if(ptr[j] == aux[j])
     {
       printf("%d\n",ptr[j]);
     }
     ptr++;
}

Since you increment both j and ptr, you're doing far too much incrementing. It's probably best to remove the ptr++; line.

How to declare a jagged array in a header file?

NOTE: Deviating from the requested array-of-pointers-to-rows syntax and pointing to the rows directly in the array, as proposed by @Someprogrammerdude, allows to obtain the same result, but with one less indirection and with a more clear access syntax.

direct array of rows solution

definition

unsigned jagged_row0[] = { 0, 1, 99 };
unsigned jagged_row1[] = { 1, 2, 3, 4, 5, 6, 99 };

unsigned *jagged[] = (unsigned *[]){ jagged_row0, jagged_row1 };

or in general:

type jagged_row0[] = { ... };
type jagged_row1[] = { ... };
...

type *jagged[] = (type *[]){ jagged_row0, jagged_row1, ... };

declaration

extern unsigned *jagged[];

or in general:

extern type *jagged[];

usage

unsigned v_i_j = jagged[i][j];

or in general:

type v_i_j = jagged[i][j];

original answer

The following solution addresses the definition given in the cited answer by @FaisalVasi, where the jagged array stores explicit pointers to the jagged rows.

definition (in some .c file)

unsigned jagged_row0[] = {0,1};
unsigned jagged_row1[] = {1,2,3};

unsigned (*jagged[])[] = { &jagged_row0, &jagged_row1 }; /* note the ampersand */

/* or alternatively, since compound literals are lvalues ... */
unsigned (*jagged[])[] = { &(int[]){0,1}, &(int[]){1,2,3} };  

declaration

extern unsigned (*jagged[])[];

usage

unsigned *jagged_row;
...
jagged_row = *jagged[i];
unsigned v_i_j = jagged_row[j];  /* value at [i][j] */

or more compactly:

unsigned v_i_j = (*jagged[i])[j];  /* value at [i][j] */

explanation

A jagged row is an array of some basic type, in our case an array (of length determined by the static initialization) of unsigned (unsigned[]), which can be thought of, with some caveats, as a pointer to unsigned (unsigned *).

With the proposed definition, the jagged array is an array of pointers to jagged rows, which, with the same simplification, can be though of as an array of unsigned **.

When you index the first dimension, you are getting the pointer to the jagged row (an array), then you have to dereference this pointer to get to the array itself that is the jagged row, than you have to index this array to get to the final value.

Jagged Array in C (3D)

In modern C there is a tool call compound literal to achieve at least partially what you seem to want:

double (*(layer1[])) = {
  (double[]){0.1,0.1,0.8},
  (double[]){0.1,0.1,0.8},
  (double[]){0.1,0.1,0.8},
  (double[]){0.1,0.1,0.8}
};
double (*(layer2[])) = {
    (double[]){0.1,0.1,0.1,0.1,0.8}
};
double (*(*(upper[]))) = {layer1, layer2};

I have put in () to the types to show you the rules of bindings for the types. But beware that with this type of programming you'd always have to remember the array bounds by yourself.

Edit: A construct as (double[]){ 0.0 } is called a compound literal and as the same effect as your temporary arrays that you had declared in your second version. The advantage is that you don't have to invent a naming convention for them and that the only way to access these temporary variables is then through the bigger array. Maybe it would be better to put in const into all of this so you wouldn't accidentally change the pointers:

double (*const(layer1[])) = {
  (double[]){0.1,0.1,0.8},
  (double[]){0.1,0.1,0.8},
  (double[]){0.1,0.1,0.8},
  (double[]){0.1,0.1,0.8}
};
double (*const(layer2[])) = {
    (double[]){0.1,0.1,0.1,0.1,0.8}
};
double (*const(*const(upper[]))) = {layer1, layer2};

This still lets you change the contents (all the doubles) but not the pointers. If you know that the doubles themselves don't change during the whole program, change double into double const everywhere.

MIPS Assembly for two-dimensional array and jagged array

These aren't C code, this looks like C#.

int[][] A; // C# declaration for jagged multidimensional array
int[,] B;  // C# declaration for rectangular multidimensional array

---

First, let's look at the simpler and more regular rectangular array.

C code for rectangular multidimensional array would be:

int B[5][10];  // C declaration for rectangular array

This fragment request a total of 50 integer elements, structed as 5 rows, where the row size is 10 elements.

Because the logical data structure is two dimensional yet physical memory is only one dimensional, we must map the 2D structure onto 1D.  There are two ways of doing this, one is row-major and the other column-major.  If we consider the index having the 5 to be row and 10 the column, then we can say that the C language uses row-major ordering.

(That there are two choices in mapping the array is similar to the idea that there are two reasonable orderings for individual bytes in multi-byte (i.e. word) items: big endian and little endian.)

The array is immediate in some sense: there are no pointers or references stored in this structure, only the 50 integer elements.

Access to an element is by address computation:

In B[r][c] we compute addr = B + (r * 10 + c) * 4, where the 10 represents the size of the row, and the 4 is the size of one integer element.  The multiplications are what are called scaling.  Because each row refers to 10 elements, then row 1 starts 10 positions further down than row 0.  Because each element takes 4 bytes, and each of the 4 bytes takes a memory address, then column 1 starts 4 bytes further down than column 0.  In summary, element 0,0 is at B + (0*10+0)*4, which is the same address value as B, and element 1,2 is at B + (1*10+2)*4, which is B + 48 — the 3rd element (+8) of the 2nd row (+10*4).

That addr can be dereferenced to load the r,c element from the array, or to store an updated value at r,c.

(If we were to chose column-major ordering, then the formula would be addr = B + (c * 5 + r) * 4.  Row major ordering is better if the column index varies faster, i.e. if we use for ( r = .. ) for ( c = .. ) { }, while for column-major we would prefer the inverse, varying the row index faster — the index for an inner loop varies faster than the index for an outer loop.  The difference between them has to do with cache utilization (without a cache it wouldn't matter much).)

---

Jagged arrays are arrays of arrays.  Each array involved is one-dimensional, so while there is still a rectangular shape to each individual array, the rectangular shape does not apply to the two dimensional structure of the overall "2D" array.

In C a jagged array is declared as an array of pointers, where the pointers themselves are references to individual arrays of zero or more integer elements (or are null).

int *A[10];

This declares an array (the [] take precedence over the *, so this is taken as int *(A[10]), the type of each array element is pointer to int.

The total storage size of this array is 40 bytes, 10 * size of pointer, 4, on MIPS 32-bit system.  Each element of the array is a pointer type.  There are no integers reserved by this array declaration!  There are positions for 10 pointers to integer (arrays), and each of 10 for each position must be further specified, by an initializer or by allocation.  Because the elements of this array are pointers to integer, each such pointer can be null or refer to storage of a different number of integers.  If you wanted to know how many integers each one (row) had/has, you will have to store that information separately, because there is no built in mechanism to store that with this declaration.

In summary, jagged arrays in C have the following issues:

• Only storage for the pointer array (array of pointer) is allocated by this declaration.
• The storage (the pointer elements) will be initialized to zero, for a global declaration, and also when using calloc, but using malloc or as a local variable declaration, those pointers will be uninitialized (i.e. garbage).
• Even when we populate the individual pointers with storage, there is no inherent recording of the length of the storage (the count of how many integer) are referred to by each element position.  The array can be jagged, but you would have to remember that shape in some other way (i.e. in other data structure, like a simple array of integer of the same element count as the pointer array.)

Accessing an element of a jagged array means obtaining the pointer element from the first array, and using that to compute the address of an integer element.  Both of these operations involve one-dimensional arrays, so in at least that sense, is conceptually simpler: there is no issue of row vs. column major ordering.

An element's address, A[r][c] is computed as follows:

addr = (*(A + r * sizeof(pointer))) + c * sizeof(int)

where the first * is indirection that fetches the pointer at index r.  This addr can be used the same as in the description after addr for rectangular array above.

---

The MIPS implementation of either of these is then fairly straightforward.  For global storage, reserve the appropriate amount.  In code, compute element addresses and use lw or sw once you've computed an addr.

Memory allocation of Jagged arrays in C# vs 2d arrays memory allocation in C++

Yes you are right. A Jagged array in C# is basically an single dimension array in memory where each element is just an reference. When you initialize the array in the for loop, it creates a new array somewhere else in memory and the reference points to it.

In case of multidimensional arrays ([,]), the situation is very different. When you initialize such array, a single block of memory is created and it's size is equal to the product of all dimensions of the array. Technically having a multidimensional array of size [M,N] is represented in memory the same way as a simple array of size [M * N]. The access by multiple indices is basically just a syntactic sugar where the framework calculates the actual position of the element by multiplication of the dimensions.

Creating a 2-dimensional array with different sizes within a loop

C++ doesn't support jagged 2d arrays. A 2d array needs to have a size of N x M where N and M are both greater than zero.

Instead of using a 2d array, you can use a 2d vector to get this behavior like

std::vector<std::vector<int>> table;
for (auto size : sizes)
    table.push_back(std::vector<int>(size));

What is a jagged array?

A jagged array is an array of arrays.

string[][] arrays = new string[5][];

That's a collection of five different string arrays, each could be a different length (they could also be the same length, but the point is there is no guarantee that they are).

arrays[0] = new string[5];
arrays[1] = new string[100];
...

This is different from a 2D array where it is rectangular, meaning each row has the same number of columns.

string[,] array = new string[3,5];

---

Related Topics