Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 38 ยท Collections and Blocks

Dictionaries, Sets and Bags in Smalltalk

Use Smalltalk's unordered collections: Dictionary and Association, Set, Bag and IdentityDictionary. Learn at:put:, at:ifAbsent:, keysAndValuesDo:, counting with Bag and how = and hash decide membership.

When you care about what is in a collection or which key maps to a value more than where something sits, you reach for hashed collections: Set for unique elements, Bag for counting, and Dictionary for key-value lookup. They answer questions like "have I seen this?", "how many of each?" and "what is the price of this product?" in near-constant time.

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

Set: unique elements

SMALLTALK
| s |
s := Set new.
s add: 3; add: 5; add: 3.
s size.               "-> 2: the second 3 was ignored"
s includes: 5.        "-> true"
s remove: 5.
#(1 2 2 3 3 3) asSet. "-> a Set(1 2 3), in no guaranteed order"

A Set stores each distinct element once. "Distinct" means =, with hash consistent with it (see Initialize and creating instances). Sets have no order and no index: s at: 1 is an error, and printing order may vary. Use asSortedCollection or sorted if you need order.

Set operations:

SMALLTALK
| a b |
a := #(1 2 3 4) asSet.
b := #(3 4 5) asSet.
a select: [ :x | b includes: x ].   "intersection -> Set(3 4)"
a union: b.                         "-> Set(1 2 3 4 5)"
a reject: [ :x | b includes: x ].   "difference -> Set(1 2)"
a includesAll: #(1 2).              "-> true"

The select: and reject: forms work in every version. Dedicated set-algebra messages such as union: exist in some versions and not others, so check the browser before relying on them.

Bag: counting

A Bag is a Set that remembers how many times each element was added:

SMALLTALK
| bag |
bag := Bag new.
bag add: 'apple'; add: 'pear'; add: 'apple'; add: 'apple' withOccurrences: 2.
bag occurrencesOf: 'apple'.     "-> 4"
bag size.                       "-> 5"
bag asSet size.                 "-> 2 distinct"
bag sortedCounts.               "-> pairs count -> element, largest first"

Counting words, votes or dice outcomes is a Bag's job.

Dictionary: key to value

SMALLTALK
| prices |
prices := Dictionary new.
prices at: #apple put: 3; at: #pear put: 5.
prices at: #apple.                      "-> 3"
prices at: #kiwi.                       "-> error: key not found"
prices at: #kiwi ifAbsent: [ 0 ].       "-> 0"
prices at: #fig ifAbsentPut: [ 7 ].     "adds fig -> 7 and answers 7"
prices includesKey: #apple.             "-> true"
prices keys.                            "-> a Set or sorted collection, depending on version"
prices values.                          "-> an OrderedCollection or Array"
prices removeKey: #pear.
prices size.

Literal-like creation: { #a -> 1. #b -> 2 } asDictionary, or the Pharo short form Dictionary newFrom: { #a -> 1 }.

key -> value creates an Association, a pair object. A Dictionary is, conceptually, a set of associations:

SMALLTALK
(#apple -> 3) key.     "-> #apple"
(#apple -> 3) value.   "-> 3"

Iterating a dictionary

SMALLTALK
prices keysAndValuesDo: [ :k :v |
    Transcript show: k asString, ' costs ', v printString; cr ].
prices do: [ :v | ... ].                      "iterates the values"
prices keysDo: [ :k | ... ].
prices associationsDo: [ :assoc | ... ].
prices collect: [ :v | v * 2 ].               "-> a Bag of the new values"
prices select: [ :v | v > 3 ].                "-> a Dictionary of matches"
prices keyAtValue: 5 ifAbsent: [ nil ].       "reverse lookup (first match)"

Note the odd detail: collect: on a Dictionary answers a Bag of values, whereas select: answers a Dictionary. To transform values and keep keys, use collect: on associations or build a new dictionary.

Order

A plain Dictionary has no guaranteed order. For insertion order use OrderedDictionary (available in Pharo). To list in key order: prices keys sorted do: [ :k | ... ] or prices associations sorted: [ :a :b | a key <= b key ].

Keys: symbols, strings and identity

Symbols are the usual keys because they are unique and fast to compare. Strings work too (compared by =). IdentityDictionary and IdentitySet compare with == instead of =: faster, but only right when keys are unique objects such as symbols or small integers.

Grouping and counting patterns

SMALLTALK
"Count words"
| counts |
counts := Dictionary new.
#('a' 'b' 'a') do: [ :w | counts at: w put: (counts at: w ifAbsent: [ 0 ]) + 1 ].

"Group by length"
| groups |
groups := Dictionary new.
#('fig' 'pear' 'kiwi' 'plum') do: [ :w |
    (groups at: w size ifAbsentPut: [ OrderedCollection new ]) add: w ].

The at:ifAbsentPut: idiom is the Smalltalk "default dict". Collection >> groupedBy: and asBag occurrencesOf: shorten common cases.

Choosing

Need Use
Unique items, fast membership Set
Counts of items Bag
Lookup by key Dictionary (symbols/strings/numbers as keys)
Insertion-ordered lookup OrderedDictionary
Keys compared by identity IdentityDictionary, IdentitySet
JS Stand-in: Set, Bag and Dictionary

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

No output.

JS Stand-in: grouping with atIfAbsentPut

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 does #(1 2 2 3 3 3) asSet contain?

    A Set stores each distinct element once, in no guaranteed order.
  2. 2. Which collection tells you how many times each element occurs?

    A Bag counts occurrences: occurrencesOf: answers the count.
  3. 3. What does prices at: #kiwi ifAbsent: [ 0 ] answer if #kiwi is not a key?

    The block is evaluated when the key is missing and its value is answered.
  4. 4. What does key -> value create?

    The binary message -> answers an Association object holding a key and a value.
  5. 5. Why must = and hash be overridden together for elements stored in a Set?

    Hash chooses the bucket and = confirms the match; breaking either rule makes lookups fail.

Summary

  • Set keeps unique elements, Bag counts occurrences, Dictionary maps keys to values; none is indexed by position.
  • Use at:ifAbsent: and at:ifAbsentPut: to handle missing keys, and keysAndValuesDo: to iterate.
  • key -> value is an Association; a Dictionary's collect: answers a Bag while select: answers a Dictionary.
  • Use OrderedDictionary when insertion order matters and sort keys for display.
  • Hashed collections rely on = and hash being consistent.

Next: Iteration and Enumeration