Pointer Array vs multidimensional array | SoloLearn: Learn to code for FREE!

+1

Pointer Array vs multidimensional array

Below are advantages of multidimensional array over pointer array: 1. Input can be taken from user 2. Faster access 3. Predefined size (Edit : source link of above is https://interviewmania.com/discussion/40015-c-programming-c-pointers) As I have heard that pointer is preferred over array than why multi dimensional array wins!!!!? I don't understand second advantage related to faster access... Does pointer and multi dimensional array both don't store data linearly and row column storage is just a representation...? If storage is same , how come one is faster than other ? Related to input, why can't we take input in case of any scenario ? What is stopping us to take user input? At last , what is usage of predefined size? Understand that int a[2][3] will say that 2*3*4 = 24 byte is required for array where as int** would take only 4+4 = 8 size so where else we are storing data ? Any thoughts would be of help.. thanks in advance....!

7/6/2020 4:08:27 PM

Ketan Lalcheta

24 Answers

New Answer

+4

Ketan Lalcheta First up, good question bro 👍 Not sure where you read it, but if possible, it might be better to include link to it, so others can also review it, and say something Speculatively, I'm guessing they say "faster" due to the nature of predefined-size array were assumed to be created in stack (let's not to take VLA into this now). While pointer array, being dynamic in nature, would presumably be created in heap. So perhaps they were talking about stack based opposed to heap based memory. I didn't clearly understand your second to last paragraph about sizes. What's with that 4 + 4 = 8 anyway?

+3

Well I have no idea what a pointer array is. I've used arrays of pointers and I've accessed arrays using pointers. Once you start throwing arrays around and passing them to functions you end up using pointers anyway unless you stick with fixed size arrays. Here is an example of using a multidimensional dynamic array I created as an example for an earlier question. https://code.sololearn.com/cShrgY112B16/#cpp

+3

Ketan Lalcheta Thanks for adding source bro👌 Considering it was a quiz, and as I expected (since it's a quiz) the reason and rationale behind the quiz poster's statement/claim was untold. I feel uncertain now because of that. About sizes, as I understand it, an array simulated by pointer to pointer requires more memory, because there will also be memory needed for the pointers themselves, apart from the memory for the actual data. Seeing the reason for claim was missing from that page, Idk exactly what to say. I'm not sure how predefined size be considered an advantage. And I am even more unsure about what was meant by "input from user". At least to my understanding, the number of rows/columns can be user defined (at run time). Without a reason stated in that page, it is hard to argue the claims, as it is vague, unfortunately.

+3

An array in C/C++ is a continuous block of memory. An array of 4x4 ints takes up no more space than a one dimension array of 16 ints. The additional pointer that is used by the programmer to access it is no different to the pointer that the compiler creates on the fly to access a fixed size array. It's just that the programmer must do it explicitly. I've accessed C arrays using assembler by employing the same techniques.

+3

An int** is a pointer to a pointer, the indirect memory addressing I mentioned earlier. A pointer to a pointer is a variable that points to another pointer, so you need to dereference it to get the pointer then you need to dereference that to get the actual data. See: https://www.tutorialspoint.com/cprogramming/c_pointer_to_pointer.htm I have looked at the question posted by the OP and it makes no sense to me as I have never heard of the term pointer array before. I am assuming that they are referring to what I know as an array of pointers. I am more accustomed to using the terms "pointer to an array" and "array of pointers" since they are unambiguous. Any level of indirection is going to be slower than directly accessing data. The more levels of indirection you add the more time it takes to access your data.

+3

Martin Taylor Thank you for going even deeper 🙏 But Martin, if I may ask, in your perspecrive, do you find the statement/claim in the linked page to be credible? I mean about claim of "advantages" which kinda confused me TBH. Because it was a quiz, and there was no evidence or proof to support such statement.

+3

Historically, VLAs emerged in C99 to remedy C90's ugly hack regarding access to the elements of a dynamically allocated multidimensional array. The following article explains it in detail and clarifies possible misconceptions. https://www.drdobbs.com/the-new-cwhy-variable-length-arrays/184401444

+2

Ipang yup, i added link in question by editing the same... True... Seems faster access is due to heap memory vs stack memory... Regarding size , pointer size cannnot be computed (that's what I felt by example of double pointer ) as it is only four (in case of 32 bit) where as double pointer has fix size due to m*n* size of one data type... so does two and three point to same thing ? and still what is stopping user input mentioned in point 1?

+2

Martin Taylor "The additional pointer that is used by the programmer to access it is no different to the pointer that the compiler creates on the fly ..." Is that also true for the `int**` case mentioned by OP in the second to last paragraph of the original post? Because I was thinking, that way each pointer (row based) will be reassigned an address to another memory block allocated for the columns.

+2

AFAIK, Below is case(assume 32 bit system) : Int* -> 4 byte for the pointer on stack... Additional memory on heap for each new allocation Int [n] -> 4*n byte on stack... No heap memory... Name of array is nothing but pointer to the first element address... No additional variable i.e. memory int [m][n] -> 4*m*n byte on stack... No heap memory... Name of array is nothing but pointer to the first element address... No additional variable i.e. memory... Memory is not in terms of row / column... It's mere contiguous and second row starts just after first row... Int** -> 4+4 on stack as we need two pointer... Is above true ?

+2

@lpang, It depends on if we are talking about an array of pointers, or an array of primitives. A multidimensional array of primitive data types does not contain pointers. As I mentioned previously a 4x4 array of ints takes no more space than a 16x1 array of ints. A statements such as... print(myarray[2][1]); requires nothing more than pointer math. The base address of the array is myarray, multiply the row number by the number of columns then add the column number to obtain the offset from the starting address. That's how the pointer arithmetic is done. It's actually extremely efficient in assembly language, which the compiler generates. The base address is placed into a base register, the offset calculation is done in another register using the shift and add technique (much faster than multiplication). Then the data is accessed using a base address + offset register instruction, blindingly fast. So the rows do not contain pointers to other single dimension arrays. The array is a single block of memory. A good debugger should let you see it in memory. An array of strings would be different, single or multidimensional array. Each entry in the array would be a pointer to a character array representing a string. It would still be blindingly fast to access though. The processor just uses the same process as already mentioned but uses an indexed indirect addressing mode i.e. instead of fetching data in the first cycle it knows that it is fetching an address which must be used to access the data. Yes indexed indirect addressing is slower than indexed addressing at the machine cycle level as it involves an additional stage. However, unless you were accessing something in the tens of thousands I doubt it would be noticeable to most users. Either method compared with an interpreted language such as JavaScript or Python would be an order of magnitude quicker. I'm an embedded tech, I do assembly language and like to get down and dirty with my compiler.

+2

An array of pointers can be of fixed size. So perhaps the question is referring to dynamic arrays i.e. arrays that do not have a fixed size created by malloc and accessed using pointers. That's the only reason that they would state 'predefined size' as an advantage. I do not regard an array being a predefined size as an advantage. That would depend on the usage. Take the case of the command line arguments passed to main() as an example. A command line that can only take two parameters is not of much use in many situations. int main(int argc, char *argv[]); The character array argv[] is an array of pointers and it is of variable length, as specified by argc. It is certainly possible to accept user input and store it into a dynamic array, it wouldn't be much use otherwise. How do you think the command line arguments get into argv[]. They are entered on the command line by the user. About the only thing I would agree with in that question is that you have faster access. However, compared with the speed of user input that is negligible. I have already posted a link to my C++ example of using dynamic arrays. That is arrays created using malloc and accessed using pointers. To reiterate it can be found here: https://code.sololearn.com/cShrgY112B16/#cpp Modern C compilers actually have variable length arrays. Here is the same problem solved using variable length arrays in C: https://code.sololearn.com/cYSrlNBtF34S/#c as you can see this is very easy to read and understand and works very much like using fixed size arrays with none of their limitations of size. The C++ standard does not have variable length arrays, but I think g++ may be able to use them (don't quote me on that though). Instead the C++ standard has the Vector class: https://code.sololearn.com/cNMf27IpHsnt/#cpp You have to remember that the name of an array is a pointer... char str[] = "Hello World"; char * pstr = str; printf("%s\n%s\n", str, pstr); char str[] = "Hello World"; char * pstr = str; cout << str <

+2

Martin Taylor Huge Thanks for the contributions 🙏 In a short summary (cmiiw please) I guess it comes to a conclusion that "advantage" is a contextual statement, depending on what is actually referred to by the terms mentioned. Considering it was a quiz, obviously there was not much covered to be conclusive, however. Speed comparison there (linked page) also was missing details, but I agree that perhaps they referred to dynamic arrays. Actually, I did not know, before now, that indexed indirect addressing has a penalty, good to learn : )

+2

"The C++ standard does not have variable-length arrays, but I think g++ may be able to use them (don't quote me on that though)." test prototype: void vlaCheck(size_t n, int a[n]); ~~~~~~~~~~~ g++ 7.4.0: g++ -Wall -Wpedantic -std=c++17 -O2 -o a.out source_file.cpp Diagnostic: "error: use of parameter outside function body before ‘]’ token void vlaCheck(size_t n, int a[n]);" ~~~~~~~~~~~ clang 6.0.0: clang++ -Wall -Weverything -std=c++17 -stdlib=libc++ -O2 -o a.out source_file.cpp Diagnostic: "warning: variable length arrays are a C99 feature [-Wvla-extension] void vlaCheck(size_t n, int a[n]);" ~~~~~~~~~~~ Microsoft (R) C/C++ Optimizing Compiler Version 19.00.23506 for x64: CL source_file.cpp /Wall -o a.exe /EHsc /MD Diagnostic: "error C2131: expression did not evaluate to a constant" "note: failure was caused by non-constant arguments or reference to a non-constant symbol" "note: see usage of 'n'"

+2

@Babak "But C++ standard (till C++11) doesn’t support variable sized arrays. The C++11 standard mentions array size as a constant-expression See (See 8.3.4 on page 179 of N3337). So the above program may not be a valid C++ program. The program may work in GCC compiler, because GCC compiler provides an extension to support them." See: https://www.geeksforgeeks.org/variable-length-arrays-in-c-and-c/ From my personal experience, the Embercadaro C++ compiler supports VLAs but the MSVC compiler in Visual Studio 2019 doesn't, unless there is a compiler option I haven't looked at. I haven't used VLAs in C++ other than once for testing them. Edit: VLAs use stack memory to allocate the array. This can blow your stack and cause segmentation faults. use with caution.

+2

Pointers and Arrays in Depth (Part II) ====================================== Related code at: https://code.sololearn.com/cO9eH0C5poj1/#cpp While in scope the compiler is smart enough to figure out how to access either array in the same manner... cout << myarray[5][3] << endl; and cout << ptrarray[5][3] << endl; as demonstrated in the main() function. However, you cannot pass both arrays to the same function in the same manner. If we have a function showarray... void showarray(int arr[][10]); void showarray(int arr[10][10]); // alternative syntax we can call showarray(myarray) but not showarray(ptrarray), because ptrarray is not an integer array and will throw an error at compile time. A different function has to be used for ptrarray... void showptrarray(int *arr[]); void showptrarray(int *arr[10]); // alternative syntax

+2

Pointers and Arrays in Depth (Part IV) ====================================== Related code at: https://code.sololearn.com/cO9eH0C5poj1/#cpp So why are we doing all of this? Well, if you are just using a fixed size array and that's it we don't need to worry about it. Just go with.. int myarray[10][10]; and pass it to somefunction(myarray). However, if you are going to be using different sized arrays that need to be processed in the same way then writing a separate function for each size of array is going to become tedious, inefficient, and error prone very quickly. Having the ability to pass an array as a pointer and pass the dimensions of that array means we can use the same function to handle arrays of different sizes. Think about an array of pixel data for an image stored as 32-bit rgba values. It would not be possible to write a different function for every possible image size. A typical case where an array of pointers is used is in what are known as 'ragged arrays'. These are arrays with a fixed number of rows but a variable number of columns. These are often used to handle strings (character arrays). Each row entry is a pointer to a character array. Since each row is only large enough to store the data that is required this is efficient use of memory. The alternative is to create each row long enough to hold the maximum allowable data set. Note that these techniques originated in C. Modern C++ compilers offer container classes that can hold objects, such as C++ strings, which simplify your code and remove the risk of the potential errors that can occur when using pointers. I've had fun writing this, so I hope it can be of some use to somebody.

+2

@Martin "But C++ standard (till C++11) doesn’t support variable sized arrays" I'm afraid, the above quote (till C++11) is simply incorrect. Consulting to my 2019 working draft (n4800), I couldn't find any paragraph or even a footnote about VLAs. To make sure, I also got a copy of n3337 (2012 working draft) and couldn't find anything either there. The last place to visit was SO which I found a confirmation there. https://stackoverflow.com/questions/8593643/does-c-support-variable-length-arrays However, we can tell that this C99 feature has been adopted as an extension for some compatibility reasons; then again, the C++ standard hasn't mentioned anything about it and as summarized by @Johannes Schaub - litb "[...] doesn't mean that any and everything in C99 is in C++11." ~~~~~~~~~~~~~~~~~~~ "VLAs use stack memory to allocate the array. This can blow your stack and cause segmentation faults. use with caution." Most certainly. There are two options as far as I can tell. Use it if 1. The number and size of each element of the list are small enough that the product of them (n * s) cannot reach the default size of the stack frame (of GCC* for example) in each environment (~1MB in Win and ~8MB in Linux for example). 2. You plan to increase the size of the stack to something higher than usual through passing a linker option** as gcc/g++ -Wl,--stack, reserve [...other regular options] for example, to reserve 64MB, we type in --stack, 64000000. Suffice it to say, having 64MB of memory shouldn't lure us to do something reckless! _______ * https://cs.nyu.edu/exact/core/doc/stackOverflow.txt ** https://sourceware.org/binutils/docs-2.16/ld/Options.html

+1

Martin Taylor Appreciated your time for the lengthy response. Back the OP's question, and OP's recent reply, how was that for an answer? and in particular to second to last paragraph where int** was mentioned. As I see it from my naive prespective, the doubt is still uncleared. Good to know about you being an embedded tech, must be a wonderful job 👍

+1

If anyone is interested in seeing the assembly code generated by their compiler the relevant command line switches are.. GNU Compiler -S https://gcc.gnu.org/onlinedocs/gcc/Overall-Options.html#Overall-Options Microsoft Visual C /FA https://docs.microsoft.com/en-us/cpp/build/reference/fa-fa-listing-file?view=vs-2019 Borland/Embarcadero 32-bit Compiler -B Compile to .ASM (-S), then assemble to .OBJ -S Compile to assembly (See manual) Open Watcom The Open Watcom compiler does not have a command line switch for generating the assembly listing. Instead it uses the Open Watcom Disassembler (wdis) which takes as input an object file (a file with extension ".obj") and produces, as output, the Intel assembly language equivalent. (See manual) Java Compiler The javap command disassembles one or more class files. https://docs.oracle.com/javase/7/docs/technotes/tools/windows/javap.html Most decent compilers are also capable of producing a list file (.lst) which also helps in understanding the layout and memory usage of a program.