Section 24.12

Chapter 24 · The Scala Collections API

583

What happened here is that the evenElems demands a class manifest for the type parameter U, but none was found. The solution in this case is, of course, to demand another implicit class manifest for U. So the following works:

scala> def wrap[U: ClassManifest](xs: Vector[U]) = evenElems(xs)

wrap: [U](xs: Vector[U])(implicit evidence$1: ClassManifest[U])Array[U]

This example also shows that the context bound in the definition of U is just a shorthand for an implicit parameter named here evidence$1 of type

ClassManifest[U].

In summary, generic array creation demands class manifests. Whenever you create an array of a type parameter T, you also need to provide an implicit class manifest for T. The easiest way to do this is to declare the type parameter with a ClassManifest context bound, as in [T: ClassManifest].

24.12 Strings

Like arrays, strings are not directly sequences, but they can be converted to them, and they also support all sequence operations. Here are some examples of operations you can invoke on strings:

scala> val str = "hello"

str: java.lang.String = hello

scala> str.reverse res6: String = olleh

scala> str.map(_.toUpper) res7: String = HELLO

scala> str drop 3 res8: String = lo

scala> str slice (1, 4) res9: String = ell

scala> val s: Seq[Char] = str

s: Seq[Char] = WrappedString(h, e, l, l, o)

These operations are supported by two implicit conversions, which were explained in Section 21.7. The first, low-priority conversion maps a String

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

Section 24.13

Chapter 24 · The Scala Collections API

584

to a WrappedString, which is a subclass of immutable.IndexedSeq. This conversion was applied in the last line of the previous example in which a string was converted into a Seq. The other, high-priority conversion maps a string to a StringOps object, which adds all methods on immutable sequences to strings. This conversion was implicitly inserted in the method calls of reverse, map, drop, and slice in the previous example.

24.13Performance characteristics

As the previous explanations have shown, different collection types have different performance characteristics. That’s often the primary reason for picking one collection type over another. You can see the performance characteristics of some common operations on collections summarized in two tables, Table 24.10 and Table 24.11.

The entries in these two tables are explained as follows:

CThe operation takes (fast) constant time.

eC	The operation takes effectively constant time, but
	this might depend on some assumptions such as the
	maximum length of a vector or the distribution of
	hash keys.
aC	The operation takes amortized constant time. Some
	invocations of the operation might take longer, but
	if many operations are performed on average only
	constant time per operation is taken.
Log	The operation takes time proportional to the loga-
	rithm of the collection size.

LThe operation is linear, that is it takes time proportional to the collection size.

-The operation is not supported.

Table 24.10 treats sequence types—both immutable and mutable—with the following operations:

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

Section 24.14

Chapter 24 · The Scala Collections API

585

head	Selecting the first element of the sequence.
tail	Producing a new sequence that consists of all ele-
	ments except the first one.
apply	Indexing.
update	Functional update (with updated) for immutable
	sequences, side-effecting update (with update) for
	mutable sequences.
prepend	Adding an element to the front of the sequence.
	For immutable sequences, this produces a new se-
	quence. For mutable sequences it modifies the exist-
	ing sequence.
append	Adding an element at the end of the sequence.
	For immutable sequences, this produces a new se-
	quence. For mutable sequences it modifies the exist-
	ing sequence.
insert	Inserting an element at an arbitrary position in the
	sequence. This is only supported directly for muta-
	ble sequences.

Table 24.11 treats mutable and immutable sets and maps with the following operations:

lookup	Testing whether an element is contained in set, or
	selecting a value associated with a key.
add	Adding a new element to a set or a new key/value
	pair to a map.
remove	Removing an element from a set or a key from a
	map.
min	The smallest element of the set, or the smallest key
	of a map.

24.14Equality

The collection libraries have a uniform approach to equality and hashing. The idea is, first, to divide collections into sets, maps, and sequences. Collections in different categories are always unequal. For instance, Set(1, 2, 3) is unequal to List(1, 2, 3) even though they contain the same elements. On the other hand, within the same category, collections are equal if and

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

Section 24.14

Chapter 24 · The Scala Collections API

586

head

tail

apply

update

prepend

append

insert

immutable

C

C

L

L

C

L

-

List

Stream

C

C

L

L

C

L

-

Vector

eC

eC

eC

eC

eC

eC

-

Stack

C

C

L

L

C

L

-

Queue

aC

aC

L

L

L

C

-

Range

C

C

C

-

-

-

-

String

C

L

C

L

L

L

-

mutable

C

L

C

C

L

aC

L

ArrayBuffer

ListBuffer

C

L

L

L

C

C

L

StringBuilder

C

L

C

C

L

aC

L

MutableList

C

L

L

L

C

C

L

Queue

C

L

L

L

C

C

L

ArraySeq

C

L

C

C

-

-

-

Stack

C

L

L

L

C

L

L

ArrayStack

C

L

C

C

aC

L

L

Array

C

L

C

C

-

-

-

Table 24.10 · Performance characteristics of sequence types

	lookup		add		remove		min
immutable	eC		eC		eC		L
HashSet/HashMap
TreeSet/TreeMap	Log		Log		Log		Log
BitSet	C		L		L		eCa
ListMap	L		L		L		L
mutable	eC		eC		eC		L
HashSet/HashMap
WeakHashMap	eC		eC		eC		L
BitSet	C		aC		C		eCa

Table 24.11 · Performance characteristics of set and map types

aAssuming bits are densely packed.

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