CS211: Vectors

Computer programming, in the form we're familiar with it, has been around for over eighty years. All of that time has come with advancements not just in technology, but also in the way that we think about and write compute programs. The main aspect we'll be concerned with throughout the rest of this course is in data structures. A data structure is a way to organize and orient data within a computer program. There have been many data structures theorized, formalized, and utilized throughout the long history of computing, so we can only focus on a few in a reasonable amount of time. We'll begin with a simple, intuitive data structure which acts as a useful supplement to a basic array.

Many of the remaining exercises will be having you implement the data structures in C yourself. This means the only code I will provide for the remainder of this course is pseudocode.

Arrays are incredibly useful for storing and retrieving a fixed number of elements. For example, if I'm writing software that catalogues all of the titles in a library, and I know the number of books contained within that library, it's trivial to represent every item as an element in an array, albeit a bit tedious. But what happens the moment a new book comes out and the library adds it to its physical collection? Already the old program is out of sync with reality and must be reworked to allow for the additional item. What we need is a data structure that can grow on demand without the programmer having to manage the resizing manually.

A vector is the exact response to the above problem. The idea is simple: combine the simplicity and contiguous behavior of arrays with automatic resizing logic. Vectors are often also called resize-able arrays.

Every data structure we will be discussing has historically been defined and implemented in one form or another. Regardless of particular historical machines/libraries, there are always key functions and behaviours the remain constant across all implementations. We call the relevant functions and their behaviors tied to a data structure its application programmer interface (API). We list the API for a vector below:

• init
  • Initializes a vector
• add
  • Appends an element to the vector
• get
  • Gets an element at a given index
• set
  • Sets an element at a given index
• size
  • Returns the number of elements in the vector
• capacity
  • Returns the underlying size of the vector
• is_empty
  • Indicates whether the vector is empty or not
• free
  • Frees the vector

There is no one, true way of implementing any data structure—there will always be differences depending on goals, target language quirks, and programming styles. When implementing a vector it is always advisable to use the target language's array data type as the underlying array that be resized. The essential logic is quite simple:

1: add(elem):
2:   if size = capacity:
3:     resize()
4:   array[size] ← elem
5:   size ← size + 1
6:   return

When adding elements to the array you must first check to see if there's any space. If so, the element can be added; if not, the array must be grown. The way the array is resized is down to implementation. What matters is that the original elements must be copied over into the new array.

I leave it as an exercise to the reader to further flesh out the Vector implementation in C.

Remember that if arrays are going to be passed around multiple functions you should make sure to allocate them on the heap!

The choice to use one data structure over another is always an engineering decision. It is up to the programmer to weight the pros and cons of all of the possible data structures that could be used for a given task. Here, we enumerate the pros and cons for vectors:

Pros:

• Random access

Cons:

• Must copy everything over on size up
• Wasted space if anomalous growth occurs

Vectors are very common throughout the standard libraries of programming languages, although they are often given different names. Java calls its vector an ArrayList, Python a list, Rust a Vec, Go a slice, and so on. C++ sticks to vector which is why I used that terminology here. Each of these language implement their vectors differently, although the core functionality remains. The major difference will come in the form of the default array size and the algorithm which determines the new resized array length.

1. Design a struct to represent a vector in C. It should contain at minimum an integer array pointer, a size field, and a capacity field. What type should the array pointer be and why? What initial values should size and capacity have after init?
2. Implement init and free_vec for your vector struct. init should allocate an initial array on the heap with a starting capacity of your choice and set size to 0. Run your init and free_vec under valgrind to confirm there are no memory leaks.
3. Implement size, capacity, and is_empty for your vector. These should be straightforward one-liners. Write a small main that calls init, then prints the result of all three functions before any elements are added.
4. Implement get and set for your vector. What should happen if the index provided is out of bounds? Add a bounds check and print an error message if the index is invalid.
5. Implement the resize helper function referenced in the pseudocode. It should allocate a new array of larger capacity, copy all existing elements over, free the old array, and update the capacity field. What factor should you grow by and why? Look up how Python and Java grow their dynamic arrays and compare.
6. Implement add using the pseudocode given in the lecture as a guide. Test it by adding 20 integers to a vector with an initial capacity of 4 and printing the size and capacity after each insertion. How many times does resize get called?
7. The lecture states that "the way the array is resized is down to implementation." Implement two versions of resize: one that doubles the capacity and one that grows by a fixed amount of 4. Add 100 elements to each and count the total number of copy operations performed. Which strategy results in fewer copies overall?
8. The lecture lists random access as a pro of vectors. Write a program that uses get to access the middle element of a vector containing 1000 integers. Then think about how you would find the middle element of a linked list — what would that require?
9. The lecture notes that wasted space is a con of vectors. Write a program that adds 5 elements to a vector with a doubling resize strategy and then prints size and capacity. How much space is wasted? Under what circumstances would this wasted space become a practical problem?
10. The lecture distinguishes between size and capacity as two separate concepts. Write a program that creates a vector with an initial capacity of 4 and adds elements one at a time, printing both size and capacity after each insertion until the vector has been resized at least three times. In your own words, explain the difference between what size and capacity represent and why a vector needs to track both.