Converting a generic List to an Array. Why do I need use clone?

Question

I faced a problem yesterday, when I was writing my homework. I finished the homework, but I still don't really understand why my code works. I had to write a sort function that takes an varargs of any comparable generic object as an argument and return the argument. The problem was that I had to return an array of sorted objects. So I had to learn more about varargs lists and arrays.

The function was defined like this.

public <T extends Comparable<T>> T[] stableSort(T ... items)

and inside the function I made a list, which I would sort and do all the work on.

List<T> list = new ArrayList<T>(Arrays.asList(items));

and at the end of the function I was returning list toArray so that it matched the output type T[].

list.toArray(items.clone());

My question is since I already made the list from the varargs, why do I have to do items.clone() inside the toArray function. That seemed like doing two same things to me. I thought arrays.asList() would clone the values of array to list and I don't get why am I doing it again at the end of the code in toArray(). I know that this was the correct way to write it, because I finished the homework yesterday and found out this way from forums of the class, but I still don't understand why.

EDIT

The task required me to create a new array with sorted files and return it instead. Due to Type Erasure, it is not possible to instantiate an array of a generic type without a reference to a class that fits the generic. However, the varargs array has type T, so I should have cloned an array of a type which fits the generic constraints. Which I didn't know how to do in time. So I decided to use list to make my time easier till the deadline.

Answer 1

By the way, you didn't have to use return list.toArray(items.clone()); You could have used, for example, return list.toArray(Arrays.copyOf(items, 0));, where you are passing to list.toArray() an empty array that contains none of the arguments from items.

The whole point of passing an argument to the version of list.toArray() that takes an argument, is to provide an array object whose actual runtime class is the actual runtime class of the array object it wants to return. This could have been achieved with items.clone(), or with items itself (though that would cause list.toArray() to write the resulting elements into the original array pointed to by items which you may not want to happen), or with, as I showed above, an empty array that has the same runtime class.

By the way, the need to pass the argument to list.toArray() is not a generics type issue at all. Even if you had written this with pre-generics Java, you would have had to do the same thing. This is because the version of List::toArray() that took no arguments always returns an array object whose actual runtime class is Object[], as the List doesn't know at runtime what its component type is. To have it return an array object whose actual runtime class is something different, you had to give it an example array object of the right runtime class to follow. That's why pre-generics Java also had the version of List::toArray() that took one argument; even though in pre-generics, both methods were declared to return Object[], they are different as the actual runtime class returned is different.

Answer 2

It seems to me there are a few questions here, that may have come together to create some confusion as to why what needs to be done.

I thought arrays.asList() would clone the values of array to list and I don't get why am I doing it again at the end of the code in toArray().

This is probably just the way it is typed, but it should be made clear that you don't clone the objects in the array, but only make a new List with the references to the objects in the array. The objects themselves will be the same ones in the array as in the List. I believe that is probably what you meant, but terminology can be tricky here.

I thought arrays.asList() would clone the values of array to list...

Not really. Using Arrays.asList(T[] items) will provide a view onto the array items that implements the java.util.List interface. This is a fixed-size list. You can't add to it. Changes to it, such as replacing an element or sorting in-place, will pass through to the underlying array. So if you do this

List<T> l = Arrays.asList(T[] items);
l.set(0, null);

... you've just set the element at index 0 of the actual array items to null.

The part of your code where you do this

List<T> list = new ArrayList<T>(Arrays.asList(items));

could be written as this:

List<T> temp = Arrays.asList(items);
List<T> list = new ArrayList<T>(temp);

The first line is the "view", the second line will effectively create a new java.util.ArrayList and fill it with the values of the view in the order they are returned in by their iterator (which is just the order in the array). So any changes to list that you make now don't change array items, but keep in mind that it's still just a list of references. items and list are referencing the same objects, just with their own order.

My question is since I already made the list from the varargs, why do I have to do items.clone() inside the toArray function.

There could be two reasons here. The first is as CKing said in his/her answer. Because of type erasure and the way arrays are implemented in Java (there are separate array types depending on whether it's an array of primitives or references) the JVM would not know what type of array to create if you just called toArray() on the list, which is why that method has a return type of Object[]. So in order to get an array of a specific type, you must provide an array to the method that can be used at run-time to determine the type from. This is a piece of the Java API where the fact that generics work via type-erasure, aren't retained at run-time and the particular way in which arrays work all come together to surprise the developer. A bit of abstraction is leaking there.

But there might be a second reason. If you go check the toArray(T[] a) method in the Java API, you'll notice this part:

If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.

Suppose some code by another dev is using your stableSort method like this:

T[] items;
// items is created and filled...
T[] sortedItems = stableSort(items);

If you didn't do the clone, what would happen in your code would be this:

List<T> list = new ArrayList<T>(Arrays.asList(items));
// List is now a new ArrayList with the same elements as items
// Do some things with list, such as sorting
T[] result = list.toArray(items);
// Seeing how the list would fit in items, since it has the same number of elements,
// result IS in fact items

So now the caller of your code gets sortedItems back, but that array is the same array as the one he passed in, namely items. You see, varargs are nothing more than syntactic sugar for a method with an array argument, and are implemented as such. Perhaps the caller didn't expect the array he passed in as an argument to be changed, and might still need the array with the original order. Doing a clone first will avoid that and makes the effect of the method less surprising. Good documentation on your methods is crucial in situations like this.

It's possible that code testing your assignment's implementation wants a different array back, and it's an actual acquirement that your method adheres to that contract.

EDIT:

Actually, your code could be much simpler. You'll achieve the same with:

T[] copy = items.clone();
Arrays.sort(copy);
return copy;

But your assignment might have been to actually implement a sorting algorithm yourself, so this point may be moot.

Answer 3

You need to use this:

List<T> list = new ArrayList<T>(Arrays.asList(items));

when you want to do an inline declaration.

For example:

List<String> list = new ArrayList<String>(Arrays.asList("aaa", "bbb", "ccc"));

Answer 4

My question is since I already made the list from the varargs, why do I have to do items.clone()

You are right. Unfortunately, the compiler will be unable to determine the type of the array if you simply use the toArray() method. You should get a compilation error saying Cannot convert from Object[] to T[]. The call to item.clone() is required to assist the compiler in type-inference. An alternate approach would be to say return (T[])list.toArray

That said, I would not recommend either of the approaches. It doesn't really make sense to convert an array to a list and convert it back to an array in the first place. I don't see any significant take-aways that you would even understand from this code.