# CS106L(5): Fruit Containers

Containers. This lecture brings me back to my university life when I was young, at that time, classmates were like the image shown below. 😀 As time goes by, now I shrink to…:

…🍌🍊🍇🥭🍋🍉…

## Core Idea

• Intro to Standard Template Library (STL)
• Sequence Containers - vector, deque, list 🎉
• Container Adaptors - queue, stack 🎉
• Associative Containers - set, map, type requirements 🎉

## Lecture 5: Containers - Note 📒

View Lecture Note

## Standard Template Library (STL) 🍉

Overview of STL (AKA Standard Template Library):

• Iterators
• Functions
• Algorithms

C++ details we will cover:

• std::vector
• std::deque/list
• std::map/unordered_map
• std::set/unordered_set
• std::stack/queue

Sequence Containers:

1. std::vector - Stanford vs. STL
2. std::vector - safety and efficiency
3. std::deque vs. std::vector

### 3 Types of STL Sequence Container 🌰🍊🍅

which are vector, deque, and list.

Summary of Sequence Containers

• vector: use for most purposes
• deque: frequent insert/remove at front
• list: very rarely - if need splitting/joining

### vector 🌰

``````vector<int> v;       // Create an empty vector
vector<int> v(n);	// Create a vector with n copies of zero
vector<int> v(n, k); 	// Create a vector with n copies of a value k
v.push_back(k);		// Add k to the end of the vector
v.clear();	// Clear vector

int k = v.at(i);     // Get the element at index i
int k = v[i]; (*)	// (* does not bounds check!)

if (v.empty()) ...   // Check if the vector is empty

v.at(i) = k;      // Replace the element at index i
v[i] = k; (*)	// (* does not bounds check!)
``````

InsertionSpeed: `std::vector` does not have a push_front function.

Recurring C++ pattern: don’t provide functions which might be mistaken to be efficient when it’s not.

Internally, a `std::vector` consists of an fixed-size array. The array is automatically resized when necessary.

### deque 🍊

std::deque provides fast insertion anywhere.

std::deque has the exact same functions as std::vector but also has `push_front`and `pop_front`.

``````std::deque<int> deq{5, 6}; // {5, 6}
deq.push_front(3); // {3, 5, 6}
deq.pop_back(); // {3, 5}
deq = -2; // {3, -2}
``````

### list 🍅

`std::list` is kinda like `std::stack` + `std::queue`

``````std::list<int> list{5, 6}; // {5, 6}
list.push_front(3);
list.pop_back(4);
``````

### When to use which sequence container

std::vector std::deque std::list
Indexed Access Super Fast Fast Impossible
Insert/remove front Slow Fast Fast
Insert/remove back Super Fast Very Fast Fast
Insert/remove elsewhere Slow Fast Very Fast
Memory Low High High
Splicing/Joining Slow Very Slow Fast
Stability * Poor Very Poor Good

Sidenote: vector might not look great, but remember that indexed access and inserting to the back are the most common uses of sequence containers.

### Summary from the ISO Standard

vector is the type of sequence that should be used by default…deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

### Best Practises 💖

#### if possible, reserve before insert

Reserve is to request that the vector capacity be at least enough to contain n elements.

Exp 1:

``````std::vector<int> vec;
for (size_t i = 0; i < 1000000; ++i) {
vec.push_back(i);  //Problem: internally the array is resized and copied many times.
}
``````

Exp 2:

``````std::vector<int> vec;
vec.reserve(1000000);   // Reserve the place for vector
for (size_t i = 0; i < 1000000; ++i) {
vec.push_back(i);
}
``````

#### Other best practices

• Consider using `shrink_to_fit` if you don’t need the memory.
• Call empty(), rather than check if size() == 0.
• Don’t use `vector<bool>` (“noble failed experiment”)
• Other Iterator Stuff

It’s easy to write inefficient code. Know about the common pitfalls - prevent as much resizing as much as possible.

A wrapper for an object changes how external users can interact with that object.

Container adaptors provide a different interface for sequence containers. You can choose what the underlying container is!

### Quiz Question ✍️

Which data structure should we use to implement a stack? (O_O)?

Noted that stack is LIFO (Last In First Out). Check the `Insert/remove back`, I think std::vector is faster. But in the lecture, it says deque would be preferred, there should be some reasons.

The queue is FIFO (First In First Out). So should be `Insert back` fast, `Remove Front` fast, so it will be std::deque.

``````std::stack<int> stack_d; // Container = std::deque
std::stack<int, std::vector<int>> stack_v; // Container = std::vector
std::stack<int, std::list<int>> stack_l; // Container = std::list
``````

documentation

### std::priority_queue

A priority queue is a container adaptor that provides `constant time lookup` of the largest (by default) element, at the expense of logarithmic insertion and extraction.

## Associative Containers 🍈🍇

1. `std::set` functions
2. `std::map` functions and auto-insertion
3. type requirements

Summary:

• set: membership
• map: key/value pairs
• set/map require comparison operator
• map stores std::pairs
• auto-insertion = useful but be careful
• unordered/multi stuff - know they exist

### std::set 🍈

``````set<int> s;
s.insert(k);		// Add k to the set
s.erase(k);			// Remove k from the set
if (s.count(k)) ...		// Check if k is in the set
if (s.contains(k))     //  Check if k is in the set, C++20
if (s.empty()) ...		// Check if the set is empty
``````

### std::map 🍇

``````map<int, char> m;

m.insert({k, v});	// Add key k with value v into the map
m[k] = v;	// Add key k with value v into the map

m.erase(k); 	// Remove key k from the map

if (m.count(k)) ...		// Check if k is in the map
if (m.contains(k)) 		// Check if k is in the map, C++ 20

if (m.empty()) 			// Check if the map is empty

char c = m.at(k);
m.at(k) = v;  // Retrieve or overwrite value associated with key k (error if does not exist)

char c = m[k];
m[k] = v;		// Retrieve or overwrite value associated with key k (auto-insert if DNE)

``````

STL maps stores `std::pairs`. The underlying type stored in a `std::map<K, V>` is a `std::pair<const K, V>`.

sidenote: why is the key const?

Sometimes the structure of a container is based on the value itself, so can’t be modified? so use `const`?

### STL sets + maps require comparison operator 🍈 + 🍇

By default, the type (for sets) or key-type (for maps) must have a comparison (<) operator defined.

``````std::set<std::pair<int, int>> set1; // OKAY - comparable
std::set<std::ifstream> set2; // ERROR - not comparable
std::map<std::set<int>, int> map1; // OKAY - comparable
std::map<std::function, int> map2; // ERROR - not comparable
``````

### Iterating over the elements of a STL set/map.

• The elements are ordered based on the operator `<` for element/key.
• Because maps store pairs, each element m is an `std::pair` that you can use structured binding on.
``````for (const auto& element : set) {
// do stuff with key
}
for (const auto& [key, value] : map) {
// do stuff with key, value
}
``````

### unordered_map and unordered_set

Each STL set/map comes with an unordered sibling. Their usage is the same, with two differences:

• Instead of a comparison operator, the element (set) or key (map) must have a hash function defined for it
• The `unordered_map/unordered_set` is generally faster than `map/set`

### multimap, multiset (+ unordered siblings)

Each STL set/map (+ unordered_set/map) comes with an multi-cousin. Their usage is the same, with two differences:

• You can have multiple of the same element (set) or key (map).
• insert, erase, and retrieving behave differently (since they may potentially have to retrieve multiple elements/values).

### a few problems with STL containers

Concrete things we haven’t been able to do yet…

• how to insert an element at a certain position in a vector?
• how do we create sublists of a vector? how about for a set?
• how do we iterate over all the elements in an associative container?

Ideas we want to move toward (we’ll know how to do these by the end of the class!)

• can I write a function that works for any container?
• can I operate over a container while completing ignoring the container?

## Summary 🍓

• `std::vector` indexing has [] and at() functions. only at() does error-checking
• `std::deque` is like vector, inserting to `front` is fast, other operations slower
• `std::stack` and `std::queue` adapt a `deque` to their unique interface
• `std::map`’s operator[] has auto-insertion, but at() does not
• `set/map` require a comparison operator (since they are internally sorted)

Noted that:

• you should practice using these containers yourself
• you should read the STL documentation for more details

??????? ☠️

Too many concepts need to practise….😿

Haha, congrats, the 5th lecture finished! Here are your takeaways: 🕶 …🍌🍊🍇🥭🍋🍉…