module 5

Question 1

Sequential Container Types:

Answer 1

• vector - flexible-size array with fast random access and slow insertion/deletion other than at the back
• deque - double-ended queue with fast random access and fast insertion/deletion at the front and the back
• list - doubly linked list with only bidirectional sequential access and fast insertion/deletion at any point in the list
• forward-list - singly linked list with sequential access in only one direction and fast insertion/deletion at any point in the list
• array - fixed-size array with fast random access but cannot add or remove elements
• string - a specialized container, similar to a vector, that contains characters, supports fast random access and fast insertion/deletion in the front and back

Question 2

common container operations

Answer 2

• c.size() - number of elements in the c (not valid for forward_list
• c.max_size() - max number of elements c can hold
• c.empty() - returns a bool, true if empty, otherwise false
• c.insert(args) - copy elements as specified by args into c
• c.emplace(inits) - use inits to construct an element in c
• c.erase(args) - remove all elements specified by args
• c.clear() - remove all elements from c

Question 3

Add elements to the vector using emplace_back():

struct Foo {
    Foo(int en, const string& ess) : n(en), s(ess) {}
    int n;
    string s;
};

int main() {
    vector<Foo> v;
		// add elements here
}

Answer 3

v.emplace_back(1, "one");
v.emplace_back(3, "three);
v.emplace_back(5, "five");

the same as v.push_back(Foo(1, "one"));

Question 4

Which functions return a const_iterator to the first and last element?

Answer 4

container.cbegin(), and containter.cend()

Question 5

Which functions return a reverse_iterator to the first and last element?

Answer 5

container.rbegin() and containter.rend()

Question 6

Which functions return a const_reverse_iterator to the first and last element?

Answer 6

container.crbegin() and containter.crend()

Question 7

Assign the values from the vector container to the list container:

list<string> names;
vector<const char*> oldstyle;

Answer 7

names.assign(oldstyle.cbegin(), oldstyle.cend());

Question 8

Specialized Containers

Answer 8

• stack
• queue
• priority_queue

Question 9

stack methods

Answer 9

• s.pop() - removes but does not return the top element of the stack
• s.push(item) - creates a new top element on the stack by copying or moving item
• s.emplace(args) - creates a new top item by constructing the element from the args
• s.top() - returns but does not remove the top element of the stack

Question 10

queue methods

Answer 10

• q.pop() - removes but does not return the front element of the queue
• q.front() - returns, but does not remove, the front element of the queue
• q.back() - returns, but does not remove, the back element of the queue
• q.push(item) - creates a new element at the back of the queue by copying or moving item
• q.emplace(args) - creates a new back item by constructing the element from the args

Question 11

priority_queue methods

Answer 11

• q.pop() - removes but does not return the front element of the priority_queue
• q.front() - returns, but does not remove, the front element of the priority_queue
• q.top() - returns, but does not remove, the highest-priority element of the priority_queue
• q.push(item) - creates a new element at the back of the priority_queue by copying or moving item
• q.emplace(args) - creates a new back item by constructing the element from the args

Question 12

Associative Containers with elements ordered by key

Answer 12

• map - associative array, holds key-value pairs
• set - container in which the key is the value
• mulitmap - map in which a key can appear multiple times
• mulitset - set in which a key can appear multiple times

use tree-based storage with O(logn) retrieval

Question 13

Associative Containers with unordered collections

Answer 13

• unordered_map - map organized by hash function
• unordered_set - set organized by hash function
• unordered_multimap - hashed map; keys can appear multiple times
• unordered_multiset - hashed set; keys can appear multiple times

containers are hash tables, O(1) retrieval complexity

Question 14

write a pair (defined in <utility>) that will hold an int and a string, then print the second value

Answer 14

#include <utility>
#include <string>
#include <iostream>

using namespace std;

int main() {
    pair<int, string> p1 {10, "ten"};
    cout << p1.second << endl;
}

Question 15

Erase Operations

Answer 15

• c.erase(k) - removes every element with key k from c, returns size_t indicating number of elements removed
• c.erase(p) - removes the element denoted by the iterator p from c. returns an iterator to the element after p or c.end() if p is the last element in c
• c.erase(b, e) - removes the elements in the range denoted by the iterator pair b, e. returns e

Question 16

Unordered Container Operations - Bucket Interface

Answer 16

• c.bucket_count() - number of buckets in use
• c.max_bucket_count() - largest number of buckets this container can hold
• c.bucket_size(n) - number of elements in the nth bucket
• c.bucket(k) - bucket in which elements with key k would be found

Question 17

Unordered Container Operations - Bucket Iteration

Answer 17

• local_iterator - iterator type that can access elements in a bucket
• const_local_iterator - const version of local_iterator
• c.begin(n), c.end(n) - Iterator to the first, and one past the last element in bucket n
• c.cbegin(n), c.cend(n) - returns const_local_iterator

Question 18

Unordered Container Operations - Hash Policy

Answer 18

• c.load_factor() - Average number of elements per bucket, returns float
• c.max_load_factor() - Average bucket size that c tries to maintain. c addds buckes to keep load_factor < max_load_factor. returns float
• c.rehash(n) - reorganize storage so that bucket_count > size / max_load_factor
• c.reserve(n) - reorganize so that c can hold n elements without rehash