: : : : :
: : : : : No.
: : : : :
array[N][N][N] has n*n*n elements, so worst case is n*n*n and best case is still one if the element to search for is at array[0][0][0].
: : : : :
: : : :
: : : : Hi Eric
: : : :
: : : : I am not sure what three dimentional array is.
: : : : Is it the.. array[string length][column][row] though?
: : : :
: : : : In that case, if N=2, it would be array[2][2][2] I think.
: : : : Is one of the [N] is the length of the string, why would it take 2*2*2 = 8 times to search?
: : : :
: : : :
: : :
: : : A multi-dimensional array doesn't have a specific meaning. You use it whenever you think is appropriate.
: : : Think of it as follows:
: : : - A one-dimensional array is an array of elements;
: : : - A two-dimensional array is an array where each element is an array of elements;
: : : - A three-dimensional array is an array where each element is an array, of which each element is an array of elements;
: : : - A four-dimensional array is .....
: : : etc.
: : :
: : : An example:
: : : Suppose you want to store outside temperatures on a regular basis:
: : :
: : : //store temperatures by hour, for one day:
: : : int temperatures[24];
: : :
: : : //to get the temperature at noon:
: : : int temp = temperatures[12];
: : :
: : : Obvious, isn't it?
: : :
: : : Now you decide you want to keep track of the temperatures for a whole month:
: : :
: : : //store temperatures by hour, by day for one month:
: : : int temperatures[31][24];
: : :
: : : //to get the temperature at day 9, 07:00 AM:
: : : int temp = temperatures[8][7]; //note that I use 8, because array-indices are zero-based in C++
: : :
: : :
: : : Now you decide to keep track of the temperatures for a whole year:
: : :
: : : //store temperatures by hour, by day, by month for one year:
: : : int temperatures[12][31][24];
: : :
: : : //to get the temperature at May 23rd, 04:00 PM:
: : : int temp = temperatures[4][22][16];
: : :
: : :
: : : You can go even further and store the temperatures for a whole century. That requires a four-dimensional array:
: : :
: : : //store temperatures by hour, by day, by month for one year:
: : : int temperatures[100][12][31][24];
: : :
: : : //to get the temperature at May 23rd 1988, 04:00 PM:
: : : int temp = temperatures[88][4][22][16];
: : :
: : :
: : : Take this 4-dimensional array, and suppose you would want to know if the temperature raised above 100 degrees at some time.
: : : The array contains 100*12*31*24 = 892,800 temperatures. So you need 892,800 comparisons worst case, or one comparision best case:
: : :
: : :
: : : for (int y=0; y<100; y++)
: : : {
: : : for (int m=0; m<12; m++)
: : : {
: : : for (int d=0; d<31; d++)
: : : {
: : : for (int h=0; h<24; h++)
: : : {
: : : if (temperatures[y][m][d][h] > 100)
: : : {
: : : //found!
: : : }
: : : }
: : : }
: : : }
: : : }
: : :
: : :
: : : Greets,
: : : Eric Goldstein
: : :
http://www.gvh-maatwerk.nl
: : :
: : :
: :
: :
: : There are are some problems with multi-dimensional arrays that one should be aware of:
: :
: : 1) You must specify the size of every dimension except the first when writing a function taking them as parameter. So it is not easy to pass them to general purpose functions.
: :
: : 2) You can't typecast between multi-dimensional arrays and pointer-to-pointers. If you use dynamicly allocated arrays, this will cause lots of trouble, since they are always allocated using pointer-to-pointer. Meaning you can't typecast between staticly and dynamicly multi-dimensional arrays.
: :
: : If the above causes trouble in the implementation, skip the multi-dimensions and "mangle" the array to one dimension instead.
: :
: What Lundin probably means by 'mangling' is to store all elements in one dimension. Following my example:
:
: Store the temperatures for a whole century in a one-dimensional array:
:
: //store temperatures by hour, by day, by month for one year:
: int temperatures[100*12*31*24];
:
: //to get the temperature at May 23rd 1988, 04:00 PM:
: int temp = temperatures[88*12*31*24 + 4*31*24 + 23*24 + 4];
:
:
:
: Greets,
: Eric Goldstein
:
http://www.gvh-maatwerk.nl
:
:
:
Yep. Looks more inefficient at first sight, but the program would need to calculate that offset in runtime anyway, so the result should be the same.
(A smart compiler would optimize this particular example to an absolute address instead, since the offset is known at compile-time. But if we had variables instead of numbers, it would be force to do it in runtime)
