Vectors vs. Lists

At this point, you might be confused about why we need vectors if we have lists, and vice versa. Just remember the points that Brian brought up in lecture!

Lists Vectors
Implementation A series of pairs where the cdr of one pair points to the rest of the list. A single contiguous block of "memory cells" with a fixed length.
Accessing (set or get) the kth item Θ(k) repeated cdrs. Θ(1) direct access.
Inserting or deleting an item at the beginning Θ(1) cons or cdr. Θ(N) copy into a larger vector!
Inserting/deleting an item in general Θ(k) to get to the right place, then as above. Θ(N) copy into a larger vector.
Length Θ(N) counts the pairs. Θ(1) fixed when the vector is created.

Vector Operations

Lists Vectors Result
(list 1 2 3) (vector 1 2 3) (1 2 3)
#(1 2 3)
No corresponding function for
lists (easy to write)
(make-vector 4 'a) #(a a a a)
No corresponding function for
lists (not applicable)
(make-vector 4)
#(#[unbound]
#[unbound]
#[unbound]
#[unbound])
(car '(1 2 3)) (vector-ref '#(1 2 3) 0) 1
(cdr '(1 2 3)) No corresponding function for
vectors (would have to make
a new vector)
(2 3)
(list-ref '(1 2 3) 1) (vector-ref '#(1 2 3) 1) 2
(set-car! lst 'a) (vector-set! vec 0 'a) okay
(set-car! (cdr lst) 'a) (vector-set! vec 1 'a) okay
(length '(2 4 1)) (vector-length '#(2 4 1)) 3

There are no vector-map or vector-filter functions in STk by default, but they're not hard to write.

There are two interesting points about make-vector. One is the #[unbound] you get if you don't specify an initial value. You can test for this with unbound?, but if you aren't going to use the entire vector it's better style to just specify #f or something as the starting value. (#[unbound] is an STk-ism, not something in all Schemes.)

The other interesting point is that if you specify a pair as the initial element of a vector, it won't be copied. Same goes if you use another vector. So you'll end up with this:

> (define my-lst (list 1 2))
> (define my-vec (make-vector 3 my-lst))
> my-vec
#((1 2) (1 2) (1 2))
> (set-car! (vector-ref 0 my-vec) 0)
> my-vec
#((0 2) (0 2) (0 2))
> my-lst
(0 2)

This is all part of the equal? vs. eq? stuff you learned this week.

As with lists, you're not supposed to use vector-set! on quoted vectors, even though STk will let you do it.

And finally, don't solve vector problems by converting the vectors to lists and then back! Vectors and lists are good for different things, and you should use the right tool for the job.

Back to Jordy's home page | Course home page