Файл: Programming_in_Scala,_2nd_edition.pdf

Mutable sets have methods that add, remove, or update elements, which are summarized in Table 24.6:

Table 24.6 · Operations in trait mutable.Set

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Table 24.6 · continued

Just like an immutable set, a mutable set offers the + and ++ operations for element additions and the - and -- operations for element removals. But these are less often used for mutable sets since they involve copying the set. As a more efficient alternative, mutable sets offer the update methods += and -=. The operation s += elem adds elem to the set s as a side effect, and returns the mutated set as a result. Likewise, s -= elem removes elem from the set, and returns the mutated set as a result. Besides += and -= there are also the bulk operations ++= and --=, which add or remove all elements of a traversable or an iterator.

The choice of the method names += and -= means that very similar code can work with either mutable or immutable sets. Consider first the following interpreter dialogue that uses an immutable set s:

scala> var s = Set(1, 2, 3)

s: scala.collection.immutable.Set[Int] = Set(1, 2, 3) scala> s += 4; s -= 2

scala> s

res9: scala.collection.immutable.Set[Int] = Set(1, 3, 4)

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

In this example, we used += and -= on a var of type immutable.Set. As was explained in Step 10 in Chapter 3, a statement such as s += 4 is an abbreviation for s = s + 4. So this invokes the addition method + on the set s and then assigns the result back to the s variable. Consider now an analogous interaction with a mutable set:

scala> val s = collection.mutable.Set(1, 2, 3)

s: scala.collection.mutable.Set[Int] = Set(1, 2, 3)

scala> s += 4

res10: s.type = Set(1, 4, 2, 3)

scala> s -= 2

res11: s.type = Set(1, 4, 3)

The end effect is very similar to the previous interaction; we start with a Set(1, 2, 3) and end up with a Set(1, 3, 4). However, even though the statements look the same as before, they do something different. The s += 4 statement now invokes the += method on the mutable set value s, changing the set in place. Likewise, the s -= 2 statement now invokes the -= method on the same set.

Comparing the two interactions shows an important principle. You often can replace a mutable collection stored in a val by an immutable collection stored in a var, and vice versa. This works at least as long as there are no alias references to the collection through which you can observe whether it was updated in place or a new collection was created.

Mutable sets also provide add and remove as variants of += and -=. The difference is that add and remove return a boolean result indicating whether the operation had an effect on the set.

The current default implementation of a mutable set uses a hash table to store the set’s elements. The default implementation of an immutable set uses a representation that adapts to the number of elements of the set. An empty set is represented by just a singleton object. Sets of sizes up to four are represented by a single object that stores all elements as fields. Beyond that size, immutable sets are implemented as hash tries.2

A consequence of these representation choices is that for sets of small sizes, up to about four, immutable sets are more compact and more efficient

2Hash tries are described in Section 24.9.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

than mutable sets. So if you expect the size of a set to be small, try to make it immutable.

Two Set subtraits are SortedSet and BitSet. These are explained in the following subsections.

Sorted sets

A SortedSet is a set where, no matter what order elements were added to the set, the elements are traversed in sorted order. The default representation of a SortedSet is an ordered binary tree maintaining the invariant that all elements in the left subtree of a node are smaller than all elements in the right subtree. That way, a simple in-order traversal can return all tree elements in increasing order. Scala’s class immutable.TreeSet uses a red-black tree implementation to maintain this ordering invariant, and at the same time keep the tree balanced—meaning that all paths from the root of the tree to a leaf have about the same length.

To create an empty tree set, you could first specify the desired ordering. For example, here is an ordering that puts strings in reverse order:

scala> val myOrdering = Ordering.fromLessThan[String](_ > _)

myOrdering: scala.math.Ordering[String] = ...

Then, to create an empty tree set with that ordering, use:

scala> import scala.collection.immutable.TreeSet import scala.collection.immutable.TreeSet

scala> TreeSet.empty(myOrdering)

res12: scala.collection.immutable.TreeSet[String] = TreeSet()

Or you can leave out the ordering argument but give an element type or the empty set. In that case, the default ordering on the element type will be used:

scala> val set = TreeSet.empty[String]

set: scala.collection.immutable.TreeSet[String] = TreeSet()

If you create new sets from a tree set (for instance by concatenation or filtering), they will keep the same ordering as the original set. For example:

scala> val numbers = set + ("one", "two", "three", "four") numbers: scala.collection.immutable.TreeSet[String] =

TreeSet(four, one, three, two)

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Sorted sets also support ranges of elements. For instance, the range method returns all elements from a starting element up to, but excluding, an end element. Or, the from method returns all elements greater than or equal to a starting element in the set’s ordering. The result of calls to both methods is again a sorted set. Here are some examples:

scala> numbers range ("one", "two")

res13: scala.collection.immutable.TreeSet[String] = TreeSet(one, three)

scala> numbers from "three"

res14: scala.collection.immutable.TreeSet[String] = TreeSet(three, two)

Bit sets

Bit sets are sets of non-negative integer elements that are implemented in one or more words of packed bits. The internal representation of a bit set uses an array of Longs. The first Long covers elements from 0 to 63, the second from 64 to 127, and so on.3 For every Long, each of its 64 bits is set to 1 if the corresponding element is contained in the set, and is unset otherwise. It follows that the size of a bit set depends on the largest integer that’s stored in it. If N is that largest integer, then the size of the set is N/64 Long words, or N/8 bytes, plus a small number of extra bytes for status information.

Bitsets are hence more compact than other sets if they contain many small elements. Another advantage of bit sets is that operations such as membership test with contains, or element addition and removal with += and -=, are all extremely efficient.

24.7 Maps

Maps are Iterables of pairs of keys and values (also named mappings or associations). As explained in Section 21.4, Scala’s Predef class offers an implicit conversion that lets you write key -> value as an alternate syntax for the pair (key, value). Therefore, Map("x" -> 24, "y" -> 25, "z" -> 26)

3Immutable bit sets of elements in the range of 0 to 127 optimize the array away and store the bits directly in a one or two Long fields.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

means exactly the same as Map(("x", 24), ("y", 25), ("z", 26)), but reads better.

The fundamental operations on maps, summarized in Table 24.7, are similar to those on sets. Mutable maps additionally support the operations shown in Table 24.8. Map operations fall into the following categories:

Lookups apply, get, getOrElse, contains, and isDefinedAt. These operations turn maps into partial functions from keys to values. The fundamental lookup method for a map is:

def get(key): Option[Value]

The operation “m get key” tests whether the map contains an association for the given key. If so, it returns the associated value in a Some. If no key is defined in the map, get returns None. Maps also define an apply method that returns the value associated with a given key directly, without wrapping it in an Option. If the key is not defined in the map, an exception is raised.

Additions and updates +, ++, and updated, which let you add new bindings to a map or change existing bindings.

Removals - and --, which remove bindings from a map.

Subcollection producers keys, keySet, keysIterator, valuesIterator, and values, which return a map’s keys and values separately in various forms.

Transformations filterKeys and mapValues, which produce a new map by filtering and transforming bindings of an existing map.

Table 24.7 · Operations in trait Map

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index