collections

A number of commonly useful collection classes have been added to the utils package. Here is a quick rundown:

  • Array An ordered, resizable array of objects. This can be used in place of ArrayList. This class is a tiny bit more efficient than ArrayList for get/put and exposes the size and underlying items array. The items array can be typed, which facilitates System.arraycopy. It can be used with the enhanced for loop syntax without allocation (it caches a single instance of an iterator, so this isn’t thread safe). The methods indexOf, contains, and removeValue can either use equals() or identity (==).
  • Bag An unordered, resizable array of objects. All the same features as Array, except when an element is removed, it is simply swapped with the last element in the bag. This avoids the memory copy that occurs when an element is removed from an Array.
  • ArrayPool and BagPool These are the same as Array and Bag respectively, except instead of giving the object to add, add() is called without parameters and returns a new object. The pool knows how to create the object via an abstract newObject() method. This allows elements in the pool to be reused to avoid garbage generation. The pool can be used as a simple store for objects used elsewhere, or can be used itself as a collection of objects.
  • IntArray, FloatArray, and LongArray These are the same as Array, except store primitives. This avoids the boxing that would happen with ArrayList while still providing the convenience of an automatically resizing collection.
  • IntBag, FloatBag, and LongBag These are the same as Bag, except store primitives. Again, this avoids boxing.
  • IntHashMap and LongHashMap These are hash maps that use an int or long as the key. This is more efficient than using object keys and avoids boxing. The entries, keys, or values can be iterated without allocation and remove() is supported. The containsValue method can use equals() or identity (==).

6 thoughts on “collections

  1. You might also want to add a sorting utility – Collections.sort() and Arrays.sort() create garbage on android :-/

  2. @Dave, while iteration can be very slightly more efficient, there are different reasons for each class. For Array, it isn’t much different than ArrayList, unless you need direct access to the underlying array. Bag, is best when you don’t care about order, because you avoid a memory copy when items are removed. The pools are for object pooling. The primitive collections avoid allocation caused by boxing.

    @Ryanm, good idea, I’ll check it out.

  3. I probably should have mentioned, BagPool is a great class to use for object pooling.

    I looked at sorting yesterday and will probably add a timsort to libgdx, giving us control of allocation.

  4. Ok, I added a Sort class for sorting arrays of Objects without allocation. It is the same thing Android does (timsort) but allows the working memory to be reused. Go ahead and use Arrays.sort for primitive arrays, as it doesn’t allocate.

Leave a Reply

Your email address will not be published.