More thoughts on Arrays

Friday, July 30, 2010
The more I work on collections in Tart, the more I realize how odd Arrays are.

For example, in my work in Java I almost never use an array type. Sequential containers are almost always ArrayList or ImmutableList. Pythons 'list' class (and 'array' class as well) are much more like Java's ArrayList, in that they can grow as needed.

At the same time, fixed length arrays are needed because the other container type - such as ImmutableList and ArrayList - are implemented in terms of arrays.

Arrays are also problematic in other ways as well. For one thing, there is the dreaded array-initialization problem: In a language where the use of null pointers is heavily discouraged, what do you use for the initial fill value of an array? Not all types have an obvious "default value" instance.

One idea that I have been toying with is the idea of making the basic array class more like fixed_vector: That is, a container with a fixed capacity, but variable length up to that capacity. You could grow the array up to it's maximum size, but in doing so you would have to provide either an explicit fill value, or a list of elements to copy into the array. From an implementation standpoint, this would require adding one extra field to the array, which is the current length. (And moreover, that field would disappear from ArrayList, since it could now use the length field of the underlying array.)

One problem with doing this is that "variable size with a maximum size" is a more complicated concept than just a fixed size. People might be surprised when their arrays start throwing capacity exceeded exceptions.

0 comments:

Post a Comment