Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 38 ยท Collections and Blocks

Arrays and Ordered Collections in Smalltalk

Work with Smalltalk sequences: Array, OrderedCollection, Interval and SortedCollection. Create, access, add, remove, search, slice and copy elements, with the 1-based indexing rules and common errors.

Collections are the data structures of Smalltalk, and they come as a rich, consistent family. This lesson covers the sequenceable ones, the collections whose elements have a position: fixed-size Array, growable OrderedCollection, the lazy Interval and the auto-ordering SortedCollection. The next lessons cover sets, dictionaries and the iteration protocol that works on all of them.

Smalltalk code here is read-only; the stand-ins run in JavaScript.

Indexing starts at 1

Smalltalk counts from 1, as people do. The first element is first or at: 1; the last is last or at: self size.

SMALLTALK
| a |
a := #(10 20 30 40).
a at: 1.        "-> 10"
a first.        "-> 10"
a last.         "-> 40"
a at: 5.        "-> error: Index 5 out of bounds"
a size.         "-> 4"

An out-of-range index raises SubscriptOutOfBounds, never silently reads garbage.

Array: fixed size, fast

SMALLTALK
#(1 2 3).                      "literal array"
{ 3 + 1. 'x' size. $a }.       "brace array: computed"
Array new: 3.                  "-> #(nil nil nil)"
Array new: 3 withAll: 0.       "-> #(0 0 0)"
Array with: 1 with: 2 with: 3. "-> #(1 2 3)"
(Array new: 3) at: 2 put: 'b'; yourself.   "-> #(nil 'b' nil)"

An Array cannot grow or shrink. add: on an Array raises shouldNotImplement. Its elements can be changed with at:put:, but never mutate a literal array that lives in a method (copy it first).

Useful messages:

SMALLTALK
#(3 1 2) reversed.          "-> #(2 1 3)"
#(3 1 2) , #(9).            "-> #(3 1 2 9): concatenation"
#(3 1 2) includes: 2.       "-> true"
#(3 1 2) indexOf: 2.        "-> 3"
#(3 1 2) copyFrom: 2 to: 3. "-> #(1 2)"
#(3 1 2) first: 2.          "-> #(3 1)"
#(3 1 2) allButFirst.       "-> #(1 2)"
#(3 1 2) isEmpty.           "-> false"
#(3 1 2) max.               "-> 3"
#(3 1 2) sum.               "-> 6"

OrderedCollection: growable

SMALLTALK
| oc |
oc := OrderedCollection new.
oc add: 'a'; add: 'b'; add: 'c'.
oc addFirst: 'z'.        "-> z a b c"
oc add: 'm' beforeIndex: 2.
oc removeFirst.          "-> 'z'"
oc removeLast.           "-> 'c'"
oc remove: 'a'.          "-> 'a' (error if absent)"
oc remove: 'q' ifAbsent: [ nil ].
oc addAll: #('x' 'y').
oc size.

OrderedCollection is the workhorse. It is implemented as a circular buffer with fast adds and removals at both ends, slower in the middle. add: returns the added element, not the collection (hence yourself in cascades). Create one from existing elements:

SMALLTALK
OrderedCollection withAll: #(1 2 3).
#(1 2 3) asOrderedCollection.

Interval: numbers on demand

SMALLTALK
(1 to: 5).                 "-> (1 2 3 4 5)"
(1 to: 10 by: 2).          "-> (1 3 5 7 9)"
(10 to: 1 by: -3).         "-> (10 7 4 1)"
(1 to: 5) asArray.         "-> #(1 2 3 4 5)"
(1 to: 1000000) size.      "-> 1000000, without storing the elements"
(1 to: 5) inject: 0 into: [ :sum :n | sum + n ].    "-> 15"

An Interval computes elements when asked. It is immutable and understands the whole collection protocol, so it makes loops tidy: (1 to: 5) collect: [ :i | i squared ].

SortedCollection: always ordered

SMALLTALK
| sc |
sc := SortedCollection new.
sc add: 5; add: 1; add: 3.
sc.                        "-> a SortedCollection(1 3 5)"
sc first.                  "-> 1"

#(3 1 2) asSortedCollection: [ :a :b | a >= b ].   "descending"
#('pear' 'fig') asSortedCollection: [ :a :b | a size <= b size ].

The sort block takes two elements and answers true when the first must come before the second (use <= or >=, not <, so the sort is stable). addFirst: is not allowed: the collection decides the position. Prefer sorting once at the end (asSortedCollection, or sorted: on any collection) to inserting one by one, because each add: to a SortedCollection costs time.

SMALLTALK
#(3 1 2) sorted.                      "-> #(1 2 3) (a new Array)"
#(3 1 2) sorted: [ :a :b | a > b ].   "-> #(3 2 1)"
#(3 1 2) sort.                        "sorts in place (Array is mutable)"

Choosing a collection

flowchart TD
    Q["Need an ordered sequence?"] -->|"fixed size, tiny, fast"| A["Array"]
    Q -->|"grows or shrinks"| O["OrderedCollection"]
    Q -->|"just a range of numbers"| I["Interval"]
    Q -->|"must stay sorted"| S["SortedCollection"]
    Q -->|"unique elements / key lookup"| N["Set, Dictionary: next lesson"]

Start with OrderedCollection when in doubt; use Array when the size is fixed and known.

Copying

Assignment copies the reference. Use copy for a shallow copy (a new collection with the same elements) and deepCopy when the elements must be copied too:

SMALLTALK
| a b |
a := OrderedCollection withAll: #(1 2).
b := a copy.
b add: 3.
a size.      "-> 2"

Common errors

Error Cause
Index 0 out of bounds Indexing from 0 like C or Java
nil does not understand #add: The collection was never created (missing initialize)
Instances of Array are not indexable... shouldNotImplement Using add: on an Array
Collection is empty / emptyCheck first, last, max on an empty collection
key not found remove: or indexOf: expectations; use the ifAbsent: forms
JS Stand-in: the sequence family

Press Run (or Ctrl + Enter) to see the console output here.

No output.

JS Stand-in: copy versus reference

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the first index of a Smalltalk Array?

    Smalltalk collections are 1-based; at: 1 answers the first element.
  2. 2. What does add: answer on an OrderedCollection?

    add: returns its argument, so use yourself at the end of a cascade to get the collection.
  3. 3. Which collection is best when the size is fixed and known?

    An Array is compact and fast, though it cannot grow.
  4. 4. In a sort block [ :a :b | a <= b ], what must the block answer?

    The sort block is a comparison answering true when the first argument should precede the second.
  5. 5. Why prefer sorted: once over adding to a SortedCollection repeatedly?

    Each add: to a SortedCollection has to find the right place, so bulk sorting is generally cheaper.

Summary

  • Smalltalk indexes from 1; out-of-range access raises an error.
  • Array has a fixed size; OrderedCollection grows and shrinks at both ends; Interval is a lazy number range; SortedCollection keeps order via a sort block.
  • add: answers its argument; end cascades with yourself.
  • copy is shallow; deepCopy copies elements too.
  • Prefer ifAbsent: forms when the item may not exist.

Next: Dictionaries, Sets and Bags