Peter Siebel - Practical Common Lisp

To keep lists from stealing the show, in this chapter I'll focus on Common Lisp's other collection types: vectors and hash tables. [119] Once you're familiar with all the data types Common Lisp offers, you'll also see that lists can be useful for prototyping data structures that will later be replaced with something more efficient once it becomes clear how exactly the data is to be used. However, vectors and lists share enough characteristics that Common Lisp treats them both as subtypes of a more general abstraction, the sequence. Thus, you can use many of the functions I'll discuss in this chapter with both vectors and lists.

Vectors are Common Lisp's basic integer-indexed collection, and they come in two flavors. Fixed-size vectors are a lot like arrays in a language such as Java: a thin veneer over a chunk of contiguous memory that holds the vector's elements. [120] Vectors are called vectors , not arrays as their analogs in other languages are, because Common Lisp supports true multidimensional arrays. It's equally correct, though more cumbersome, to refer to them as one-dimensional arrays . Resizable vectors, on the other hand, are more like arrays in Perl or Ruby, lists in Python, or the ArrayList class in Java: they abstract the actual storage, allowing the vector to grow and shrink as elements are added and removed.

You can make fixed-size vectors containing specific values with the function VECTOR , which takes any number of arguments and returns a freshly allocated fixed-size vector containing those arguments.

(vector) ==> #()

(vector 1) ==> #(1)

(vector 1 2) ==> #(1 2)

The #(...)syntax is the literal notation for vectors used by the Lisp printer and reader. This syntax allows you to save and restore vectors by PRINT ing them out and READ ing them back in. You can use the #(...)syntax to include literal vectors in your code, but as the effects of modifying literal objects aren't defined, you should always use VECTOR or the more general function MAKE-ARRAY to create vectors you plan to modify.

MAKE-ARRAY is more general than VECTOR since you can use it to create arrays of any dimensionality as well as both fixed-size and resizable vectors. The one required argument to MAKE-ARRAY is a list containing the dimensions of the array. Since a vector is a one-dimensional array, this list will contain one number, the size of the vector. As a convenience, MAKE-ARRAY will also accept a plain number in the place of a one-item list. With no other arguments, MAKE-ARRAY will create a vector with uninitialized elements that must be set before they can be accessed. [121] Array elements "must" be set before they're accessed in the sense that the behavior is undefined; Lisp won't necessarily stop you. To create a vector with the elements all set to a particular value, you can pass an :initial-elementargument. Thus, to make a five-element vector with its elements initialized to NIL , you can write the following:

(make-array 5 :initial-element nil) ==> #(NIL NIL NIL NIL NIL)

MAKE-ARRAY is also the function to use to make a resizable vector. A resizable vector is a slightly more complicated object than a fixed-size vector; in addition to keeping track of the memory used to hold the elements and the number of slots available, a resizable vector also keeps track of the number of elements actually stored in the vector. This number is stored in the vector's fill pointer , so called because it's the index of the next position to be filled when you add an element to the vector.

To make a vector with a fill pointer, you pass MAKE-ARRAY a :fill-pointerargument. For instance, the following call to MAKE-ARRAY makes a vector with room for five elements; but it looks empty because the fill pointer is zero:

(make-array 5 :fill-pointer 0) ==> #()

To add an element to the end of a resizable vector, you can use the function VECTOR-PUSH . It adds the element at the current value of the fill pointer and then increments the fill pointer by one, returning the index where the new element was added. The function VECTOR-POP returns the most recently pushed item, decrementing the fill pointer in the process.

(defparameter *x* (make-array 5 :fill-pointer 0))

(vector-push 'a *x*) ==> 0

*x* ==> #(A)

(vector-push 'b *x*) ==> 1

*x* ==> #(A B)

(vector-push 'c *x*) ==> 2

*x* ==> #(A B C)

(vector-pop *x*) ==> C

*x* ==> #(A B)

(vector-pop *x*) ==> B

*x* ==> #(A)

(vector-pop *x*) ==> A

*x* ==> #()

However, even a vector with a fill pointer isn't completely resizable. The vector *x*can hold at most five elements. To make an arbitrarily resizable vector, you need to pass MAKE-ARRAY another keyword argument: :adjustable.

(make-array 5 :fill-pointer 0 :adjustable t) ==> #()

This call makes an adjustable vector whose underlying memory can be resized as needed. To add elements to an adjustable vector, you use VECTOR-PUSH-EXTEND , which works just like VECTOR-PUSH except it will automatically expand the array if you try to push an element onto a full vector—one whose fill pointer is equal to the size of the underlying storage. [122] While frequently used together, the :fill-pointer and :adjustable arguments are independent—you can make an adjustable array without a fill pointer. However, you can use VECTOR-PUSH and VECTOR-POP only with vectors that have a fill pointer and VECTOR-PUSH-EXTEND only with vectors that have a fill pointer and are adjustable. You can also use the function ADJUST-ARRAY to modify adjustable arrays in a variety of ways beyond just extending the length of a vector.

All the vectors you've dealt with so far have been general vectors that can hold any type of object. It's also possible to create specialized vectors that are restricted to holding certain types of elements. One reason to use specialized vectors is they may be stored more compactly and can provide slightly faster access to their elements than general vectors. However, for the moment let's focus on a couple kinds of specialized vectors that are important data types in their own right.

One of these you've seen already—strings are vectors specialized to hold characters. Strings are important enough to get their own read/print syntax (double quotes) and the set of string-specific functions I discussed in the previous chapter. But because they're also vectors, all the functions I'll discuss in the next few sections that take vector arguments can also be used with strings. These functions will fill out the string library with functions for things such as searching a string for a substring, finding occurrences of a character within a string, and more.

Literal strings, such as "foo", are like literal vectors written with the #()syntax—their size is fixed, and they must not be modified. However, you can use MAKE-ARRAY to make resizable strings by adding another keyword argument, :element-type. This argument takes a type descriptor. I won't discuss all the possible type descriptors you can use here; for now it's enough to know you can create a string by passing the symbol CHARACTER as the :element-typeargument. Note that you need to quote the symbol to prevent it from being treated as a variable name. For example, to make an initially empty but resizable string, you can write this: