Lists and Vectors
A data structure such as a list or a vector is not very useful on its own, because it needs operations for basic access such as adding and removing elements.
A Box With No Way In or Out
Imagine a box that can hold many objects but has no way to put an object in or take one out. The box exists, yet you cannot do anything useful with it. A list or a vector in a program works in a similar way when it is considered by itself. It can describe how a collection is organized, but the collection only becomes valuable once you can change it and ask questions about it.
What do you think happens?
A container can hold many objects, but it has no operation for adding or removing them. Is it useful to a program?
Reveal answer
No, not on its own, because it needs operations to change it and ask questions about it
A data structure such as a list or a vector is not very useful on its own. It needs operations for basic access such as adding and removing elements. Storing objects is the starting point; the operations let a program build up a collection and revise it as the work changes.
How Adding and Removing Change a Container
The source identifies two things that make a container practically usable. The first is the set of basic operations that let you add and remove elements. The second is the set of algorithms the standard library supplies for working with a container as a whole. We start with the first. Both lists and vectors provide operations for adding and removing elements, and this is why a list or vector is described as useful only when paired with such operations.
Trace the state of a small container through an add and a remove. Before the operations, the container holds three entries. Adding an entry increases what the container holds, and removing an entry decreases it. The diagram below uses generated, illustrative names to show the same container before and after both operations.
In the illustration, Banana is removed and Date is added. Each operation changes the contents of the container, and the program can then continue working with the updated collection. This is the point of the source's box analogy: operations are what turn a stored collection into one that a program can build up and revise.
Common Tasks Programs Perform on Collections
Programs rarely just store objects and leave them alone. The source points out that we usually sort them, print them, extract subsets from them, remove elements, and search for particular objects. Each of these is a task that applies to the container as a whole or to a meaningful part of it.
- Sorting: putting the objects in a chosen order
- Printing: displaying the objects held by the container
- Extracting subsets: pulling out a meaningful part of the collection
- Removing elements: taking objects out of the container
- Searching: looking for particular objects
Because these tasks are so common, the standard library provides the most common algorithms for containers, alongside the most common container types. An algorithm in this sense is a ready-made procedure that works on a container, so the programmer does not have to write each common task from scratch. The diagram below shows how the containers and these separate algorithm categories relate.
Tracing a Sort-and-Copy Task
The source gives a concrete task that combines several ideas at once. Suppose you have a vector holding a collection of entries. You want the entries in sorted order, and you also want a separate list that contains a copy of each unique element from that vector. The source says this can be done simply and efficiently with the standard library. The task uses a container operation, an algorithm, and a second container, so it is a good way to see how they work together.
Notice in the diagram that the vector is not replaced by the list. The list receives copies, so the vector remains the source collection that the algorithms worked on. The sort changes the order of the vector, and the copy step fills a second container with the unique elements.
Sorting a vector and copying its unique entries
A vector holds the entries 3, 1, 3, 2. Sort the vector, then copy each unique entry into a list.
- 1Start with the source vector
The vector holds 3, 1, 3, 2. The entry 3 appears twice.
- 2Apply the sort algorithm
The vector is put into sorted order, giving 1, 2, 3, 3. The vector is still the source collection.
- 3Copy the unique elements
Walking through the sorted vector, each distinct value is copied once into the list, giving 1, 2, 3.
- 4Check the two containers
The vector still holds all four entries in sorted order, and the list holds only the three unique values.
The vector is sorted as 1, 2, 3, 3, and the list receives copies of the unique values 1, 2, 3.
Mistakes When Thinking About Containers
Common mistake Believing a list or vector is useful just because it can store objects
Why it failsThe source says a data structure is not very useful on its own, because it needs operations for basic access such as adding and removing elements.
Do this insteadThink of storage and operations together. The operations are what let a program build up a collection and revise it.
Common mistake Writing common tasks such as sorting or searching from scratch every time
Why it failsThe standard library provides the most common algorithms for containers, so common tasks do not need to be written from scratch.
Do this insteadCheck for a ready-made algorithm before writing your own procedure for a common task.
Common mistake Assuming the copy step replaces the source vector with the list
Why it failsIn the sort-and-copy task the list receives copies, and the vector remains the source collection that the algorithms worked on.
Do this insteadKeep track of which container is the source and which is the destination when you trace a task.
Practice Tracing a Sort-and-Copy
A vector holds the entries 5, 2, 5, 9. Trace the sort-and-copy task: first state the vector after sorting, then state the list you get by copying its unique elements. Finally, say what the vector still holds after the task.
Hints
- Sorting changes the order of the entries in the vector, but the source collection is still the vector.
- The list receives one copy of each distinct value, so the repeated 5 appears only once.
- The vector is not replaced by the list, so it still holds all of its entries.
Key Takeaways
- A list or vector on its own is not very useful, because it needs operations such as adding and removing elements to build up and revise a collection.
- Programs commonly sort, print, extract subsets from, remove elements from, and search their collections.
- The standard library supplies ready-made algorithms for these common container tasks, so they do not need to be written from scratch.
- In a sort-and-copy task, the vector is sorted and the list receives copies of its unique elements, with the vector remaining the source collection.