Pointer Array vs multidimensional array

Question

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....!

Answer 1

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?

Answer 2

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.

Answer 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.

Answer 4

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

Answer 5

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?

Answer 6

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.

Answer 7

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 ?

Answer 8

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 : )

Answer 9

"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'"

Answer 10

@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

Answer 11

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 👍