5

Array DS requires all its members to have the same time. Java throws ArrayStoreException when an attempt has been made to store the wrong type of object into an array of objects. Don't remember what C++ does.

Is my understanding correct that it's important to have all objects of the same type in array because it guarantees constant time element access through the following two operations:

1) element size * element index = offset
2) array pointer address + offset

If objects are of different types and consequently different size, the above mentioned formula won't work.

Max Koretskyi
  • 101,079
  • 60
  • 333
  • 488

3 Answers3

7

Because: we want it like this.

What I mean is: people using the Java language (probably the same for C++) are using a statically typed language for a purpose.

And when such people starting thinking in plurals; they typically think in plurals of "similar" things.

Caveat: in Java, everything is an Object, so you can always declare an Object[] and stuff anything into that. Strings, Numbers, whatever.

And that also leads to the other important aspect: in C++, your array represents an area in memory. And you better have same sized elements in that area; to avoid data corruption.

In Java on the other hand, an array is not pointing to raw memory.

Long story short: there are real differences between Java and C++ in this context (that one has to understand to make an informed decision); and then there is the "language" thing itself. In other words: this is not Ruby land, where you just put ducks, numbers, plants and quack sounds in the same "list" without further thinking.

Final thought, based on that joke in the last paragraph: in my eyes, an array is an implementation of the list concepts, thus it is about a collection of things of the same nature. If you want a collection of unrelated things, I would rather call that a tuple.

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • 1
    yeah, thanks, but since `JVM` is mostly implemented in `C++`, it still comes down to the underlying concepts. So my question is more why the array has to have the same type, rather than why it's so in `Java`. So I gather from your answer that it's not because of the constant time access, but rather because of constistency? – Max Koretskyi Apr 21 '17 at 09:08
  • @Maximus [this accepted answer might be worth a reading](http://stackoverflow.com/questions/12369957/dealing-with-an-arraystoreexception) – SomeJavaGuy Apr 21 '17 at 09:19
  • @SomeJavaGuy, yeah, thanks, but it's too `Java` specific. I realize now that I shouldn't have added `Java` tag. And someone removed `c++` tag – Max Koretskyi Apr 21 '17 at 09:23
4

Yes, you are right. All that is required for constant time random access.

Also, you can have an array of void pointers if you want to store different data types in a single array. For instance in c++, do

void * a[N]

a[i] = (void *)(&YourClass)

Similarly, use Object[] in java.

v78
  • 2,803
  • 21
  • 44
  • thanks, _if you want to store **different** data types in a single array_ - so does then the formula in my question work? – Max Koretskyi Apr 21 '17 at 09:12
  • 1
    yes, index of ith element = base_address + sum(element_sizes before the ith element). Not O(1) random access anymore. right!! – v78 Apr 21 '17 at 09:14
2

The C++ language (and compiler) requires the type of the elements to be stored in an array for various reasons, like pointer arithmetics and array subscription (e.g. x[i]), default initialisation of the elements, dealing with alignment restrictions, ...).

int x[3] = { 1,2,3 };  // array of 3 int values, each being properly aligned concerning processor architecture;
myObjectType objs[10]; // array of 10 objects of type myObjectType, each being default initialised (probably the default constructor), each being properly aligned
myObjectType *objs[10]; // array of 10 pointers to objects of type myObjectType (including subclasses of myObjectType; allowing dynamic binding and polymorphism). Note: all pointers have the same size, the object to which they point may differ insize.

int *intptr = x;
bool isEqual= (intptr[2] == x[2]); // gives true
intptr += 2; // increases the pointer by "2*sizeof(int)" bytes.

So, yes, you are right: one reason is because of calculating offsets; But there are other reasons as well, and other issues like alignment, array to pointer decay, default initialisation logic are probably more subtle but essential, too.

Stephan Lechner
  • 34,891
  • 4
  • 35
  • 58