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):

• Containers, Adaptors
• 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_frontand pop_front.

std::deque<int> deq{5, 6}; // {5, 6}
deq.push_front(3); // {3, 5, 6}
deq.pop_back(); // {3, 5}
deq[1] = -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

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

Live Code Demo: VecDecSpeed (measuring access speed in the middle of a container)

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.

Container Adaptors

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.

How about a queue?

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

Deep Dive Into std::stack documentation 🏊

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: 🕶

…🍌🍊🍇🥭🍋🍉…

References

• Lecture Note
• All lecture notes
• Module Website