"Arrays?" you ask yourself. I know what you're thinking. You wonder why an article on a powerful object-oriented programming language in the year 2000 is focusing on arrays. Well, that's a good question, with a good answer: arrays in Java are very different than arrays in C. In fact, they're much safer and easier to use than C arrays; although, as usual, you pay the price of increased overhead. In this article I discuss how arrays work in Java, and I also look at the array algorithms introduced to Java 2.
Like C, Only Different
Well, how different can Java arrays be? Like arrays in C, Java arrays are fixed-length, indexed sequences of objects of the same type. Furthermore, with Java arrays you use square brackets for indexing and indexes begin at zero. But that's where the similarity between Java and C arrays ends. The most important thing to remember about arrays in Java is:
Java arrays are run-time objects.
Arrays in Java are created at run time. Therefore, they always reside on the heap. Since arrays are objects, they can store their length and check indexing operations for out-of-bounds errors — and so they do. Array elements are also automatically zero/null-initialized when they are created. The following program excerpt creates an array of ints:
int[] a; // line 1 a = new int[3]; // line 2 a[0] = 1; a[1] = 2; a[2] = 3; for (int i = 0; i < a.length; ++i) System.out.println(a[i]); /* Output: 1 2 3 */
You can see from the first line above that you place the brackets with the type, not the array name, which makes sense, because a is an array of int, precisely what the expression int[] suggests. Java will allow you to use a C-style declarator (int a[]), but that's just to ease the transition from C to Java. "Real" Java programmers say int[].
The second thing to learn from line 1 above is that you never specify an array's dimension when you declare it — that comes later when you create it with the new operator. After line 1 executes, the variable a holds a null. After line 2, a points to heap space large enough to hold three contiguous ints, which have already been initialized to zero. (Feel free to insert a print loop to verify the zero-initialization.) The number of elements in an array is available in its read-only length member [1]. If you try to index outside of the range [0, length-1] you will get an IndexOutOfBoundsException.
Java allows C-style array initializers for typists who prefer to minimize keystrokes. A single line, for example, could replace the first five lines of the excerpt above:
int[] a = {1, 2, 3,};
Note that Java allows a benign, trailing comma, probably for those of us who occasionally change our intializers but forget to delete that last comma.
Java provides yet another initializer mechanism, which is particularly handy for those instances when an array doesn't need a name. If you wanted to pass the array {1, 2, 3} as an argument to a function, for example, you could create the array on-the-fly as follows [2]:
f(new int[]{1, 2, 3});
Since arrays are run-time objects (somewhat similar to using calloc in C, in fact), you can reassign an array variable to another array, as in:
// assume a is initialized,
// from above
...
a = new int[]{10, 20, 30, 40};
// now a.length == 4
The old array will be cleaned up when the garbage collector runs.
You can create arrays of any type, of course, not just primitives. To create an array of Integers, you can do something like the following [3]:
Integer[] a; a = new Integer[3]; a[0] = new Integer(1); a[1] = new Integer(2); a[2] = new Integer(3);
or if you prefer
Integer[] a = {new Integer(1),
new Integer(2),
new Integer(3)};
Since arrays of objects only hold object references, you can always store objects in an array of the objects' supertype, as in:
Object[] a = {new Integer(1),
new Integer(2),
new Integer(3)};
If you try to store an object that is not compatible with an array's element type you will get an ArrayStoreException.
Arrays as Objects
Each array type is a class that implicitly extends Object, as if declared like this:
class <ArrayType>
implements Cloneable
{
public final int length =
<system provided value>;
public Object clone()
{
try
{
return super.clone();
}
catch (CloneNotSupportedException x)
{
throw new
InternalError(e.getMessage());
}
}
}
Since the overridden clone method doesn't throw an exception, you don't have to worry about catching or declaring it in your code. Unfortunately, in this pseudo implementation, Object.equals() isn't overridden, so you can't use it to compare two arrays for equality. (It behaves the same as the == operator; in other words, it's useless.) There is an array algorithm discussed below that will do the job, however. The program in Figure 1 illustrates all of the above. Note the actual class name for an array of int. The length of an array is not part of its type name (it's a field, remember), so all arrays that hold the same type of element are instances of the same class. The class name of an array is not a valid Java token (because it contains a bracket) and it reveals the array's dimension (the number of braces).
The System class includes a handy algorithm for copying a subsequence of one array to another. The following program copies the array a into the middle of array b.
class ArrayCopy
{
public static void
main(String[] args)
{
int[] a = {1,2,3};
int[] b = new int[5];
System.arraycopy(a, 0, b, 1,
a.length);
for (int i=0; i < b.length;++i)
System.out.print(b[i] + " ");
}
}
/* Output:
0 1 2 3 0
*/
Of course all the indices need to be within range and the types of the two arrays must be compatible.
Multidimensional Arrays
Like C, Java interprets an array with multiple dimensions as an array of arrays. For example, the expression:
int[][] a;
declares a to be an array, each of whose elements is itself an array of int. Unlike in C, you can't specify the size of each element array — that has to wait until run time. If you want a to create a 3x4 array of ints, you again have three choices. You can allocate the space all at once, as in:
int[][] a = new int[3][4];
and then initialize each element individually (i.e., a[0][0] = 0, a[0][1] = 1, etc.). Or, you can use a shorthand C-style initializer, such as:
int a[][] = {{0, 1, 2, 3},
{4, 5, 6, 7},
{8, 9, 0, 1}};
Finally, you can allocate each row individually, like this:
// 1st dimension required
// in the next statement
int a[][] = new int[3][];
a[0] = new int[]{0, 1, 2, 3};
a[1] = new int[]{4, 5, 6, 7};
a[2] = new int[]{8, 9, 0, 1};
Whenever you create an array with the new operator without an initializer, you must always provide at least the first dimension specifier, so the compiler knows how many elements the array will hold. The latter two techniques emphasize the fact that each element of a is itself an array. If you wanted to, you could define a as a ragged array by giving each element a different length:
a[0] = new int[]{0, 1, 2, 3, 4};
a[1] = new int[]{5, 6, 7};
a[2] = new int[]{8, 9, 0, 1};
To print a row-wise requires using the length field for each element, as you can see in Figure 2. You can also define ragged arrays with a single initializer list, as the program in Figure 3 illustrates.
Since you can place the brackets in an array declaration either with the type or with the variable (C-style), declarations can sometimes be hard to decipher. For example, the following statement declares a as a T[] and b as a T[][].
T[] a, b[]; // b is T[][]
I think it's best not to mix the two declaration styles.
Array Algorithms
The class java.util.Arrays has some useful algorithms for processing arrays, namely:
- binarySearch
- equals
- fill
- sort
These algorithms come in the form of overloaded methods that take arrays of Object and also of every primitive data type. The program in Figure 4 uses all four algorithms on arrays of int. The binarySearch algorithm requires an ordered array, of course, so the first thing I do is call the sort algorithm with the statement:
Arrays.sort(array);
binarySearch returns the zero-based index of the element you're after, if it's there; otherwise it returns:
-pos - 1
Solving for pos by adding 1 and then changing sign will either give you the location before which the number should be inserted, or array.length, in case it should be appended to the array. Be aware that if the array contains multiple instances of a search object, there is no guarantee as to which one the search algorithm will find.
Unfortunately, when used with arrays of primitives, Arrays.sort puts things in ascending order only. If you want some other ordering scheme, you have to use arrays of Object and pass sort an extra comparator argument.
A comparator is an object that implements the following interface:
public interface Comparator
{
int compare(Object o1, Object o2);
}
The compare method must behave like C's strcmp function by returning a negative number if o1 precedes o2 in your ordering, zero if they are equal, or a positive number otherwise. The program in Figure 5 sorts an array of Integers in descending order by using the following comparator:
class Descending
implements Comparator
{
public int
compare(Object o1, Object o2)
{
Comparable c1 = (Comparable) o1;
Comparable c2 = (Comparable) o2;
return -c1.compareTo(c2);
}
}
A Comparable object implements the method int compareTo(Object o), which also behaves like C's strcmp. String, Date, and all the primitive wrapper classes implement Comparable, as do the new Java 2 collections (to be described in a future article). Arrays.sort uses Descending.compare to compare Integers in Figure 5.
Note that the definition of Descending above is totally generic — you can use it to reverse sort any collection of objects derived from Comparable. Since this is something you'll want to do quite often, the Java 2 library provides this comparator as the return value of Collections.reverseOrder, so you can replace the definition of desc in Figure 5 with the following one:
static Comparator desc = Collections.reverseOrder();
Since all Java 2 algorithms process instances of Object, it is easy to handle objects of any class. Figure 6 defines a Person class. Note that it implements Comparable, in case I want to sort an array of Persons. The fact that Person also implements Cloneable is a coincidence of my test program. I tried to implement hashCode and compareTo to insure that different Person objects will yield distinct results. The program in Figure 7 searches an array of Persons.
It is possible to order and search an array by a subset of the objects' fields by defining a suitable comparator. In Figure 8, I use a comparator that just looks at a Person's name. Unfortunately, I have to use a complete Person object as the search key, even though the last three fields are ignored. As far as I can tell, there is no way to define a comparator to use a Person as one argument and a string as the other, as you can with function objects in the Standard C++ library.
Conclusion
Because arrays are bona fide objects in Java, you have ample run-time support for handling them safely. The length field constitutes a run-time query for the number of elements in an array, so you don't have to pass it as a parameter as you do in C. If you accidentally use a bad index, the system will tell you instead of letting you march higgledy piggledy through memory on your merry way to an access violation. The java.util.Arrays class provides commonly-needed algorithms for processing arrays of any type. Naturally there is some overhead for all this safety and convenience, but unless you're building a performance-critical embedded system, the safety and ease of use is likely to be a winning proposition.
Notes
[1] Why length is a field and not a method is a great mystery known only to Java's designers.
[2] This feature became available with JDK version 1.1. This syntax is very similar to "compound literals" in C99. In the new C you can create a stack-based array on-the-fly in an expression like: F((int[]){1, 2, 3});
[3] An Integer is a class wrapper around an int.
Chuck Allison is Consulting Editor and a columnist with CUJ. He is the owner of Fresh Sources, a company specializing in object-oriented software development, training, and mentoring. He has been a contributing member of J16, the C++ Standards Committee, since 1991, and is the author of C and C++ Code Capsules: A Guide for Practitioners, Prentice-Hall, 1998. You can email Chuck at [email protected].
