I didn't get this one published as early as usual, so I've extended the participation deadline by 24 hours to give a little extra flexibility.
This lecture covers a broad overview of containers as well as the fundamental approaches to implementing their underlying data structures.
Containers serve a variety of purposes. Here's a few containers from the C++ standard library as examples:
std::vector<double> could store datapoints for statistical analysisstd::set<string> could represent uniqnames of students registered for a coursestd::map<string, double> could allow us to look up the price of an item on a menu by providing its nameWe'll also take a look at the way the standard library uses iterators as the abstraction for locating and traversing through elements.
|
1: Introduction to Standard Library Containers
|
|
2: Sequential Containers with Contiguous Allocation
2.1
There are two fundamental approaches to data representation for containers. The first of these is to use a contiguous allocation (i.e. elements are stored in an underlying array).
2.1
Which of the following are true? |
|
3: Sequential Containers with Linked Structures
3.1
3.2
The second fundamental approach to data representation for containers is to use a linked structure (i.e. elements are stored in nodes that point to each other).
3.1 Exercise: Time Complexity
Determine the time complexity of each of the following operations on the given data structure. Using a worst-case analysis, determine whether each function has O(1) constant time complexity or O(n) linear time complexity. Updating the value of the first element in a Inserting a new element at the front (left) of a Inserting a new element at the back (right) of a Printing the value of the first element in a Inserting a new element at the front (left) of a Printing the element in the middle of a Assuming you already have a pointer to some node within a
3.2 Exercise: Binary Search
Recall the binary search algorithm, where we find a desired value in a sorted array by:
Using binary search, a lookup operation in a sorted array can be implemented in worst-case logarithmic time, O(log n). However, this isn't the case for a sorted linked list! Why not? Explain why binary search is not a good fit for a linked list. Sample solution…Binary search relies on efficient indexing to get the middle value in the array. In an array, this is possible via pointer arithmetic. But linked lists do not support efficient indexing! To take one step of the binary search algorithm, we'd need to traverse linearly through 50% of the list by following next pointers. This first step alone already puts us at linear time complexity (and rules out logarithmic time). |
|
4: Iterators and Traversal by Iterator
The C++ standard library uses the concept of an iterator to indicate the position of an element in a list and to facilitate traversal through elements. Note that traversal by iterator is analogous to traversal by pointer, which we've seen previously. (Although not all iterators are literally implemented as pointers.) |
|
5: The
auto Keyword
|
|
6: Range-based
for Loops
|
|
7: Iterator Interfaces
Iterator types are also used to specify the parameter or return types for many functions from the standard library. |
|
8: Sets and Maps
8.1
8.1
Select the item below for participation credit. |