W6: Containers and Iterators

Question 1

An array has _________ storage of _______ size

Answer 1

contiguous

fixed

Question 2

A vector has _________ storage of _______ size

Answer 2

contiguous

variable

Question 3

A deque has _________ storage of _______ size, and a ___________ queue

Answer 3

non-contiguous
variable
double-ended

Question 4

A forward_list has _________ storage of _______ size, and a __________ list

Answer 4

non-contiguous
variable
singly-linked

Question 5

A list has _________ storage of _______ size

Answer 5

non-contiguous
variable
doubly-linked

Question 6

vector(int n);

vector(int n, const T& t) ;

Answer 6

• creates a container with n elements

- creates a container with n elements, each initialized to value t

Question 7

vector(const vector& v);
vector& operator=(const vector& v);

vector(vector&& v) noexcept ;
vector& operator=(vector&& v) noexcept;

~vector();

Answer 7

• copies the contents of container v into the current object
• moves the contents of container v into the current object
• destroys the container

Question 8

size_t size() const;

size_t capacity() const;

bool empty() const;

Answer 8

• returns the number of elements in the current object
• returns the current capacity of the current object
• returns true if the current object has no elements

Question 9

T& operator;

const T& operator const;

T& at(size_t i);

const T& at(size_t i) const;

Answer 9

• returns a reference to element i
• returns an unmodifiable reference to element i
• returns a reference to element i and checks bounds - throwing an exception
• returns an unmodifiable reference to element i and checks bounds - throwing an exception

Question 10

T* data() noexcept;

const T* data() const noexcept;

Answer 10

• returns a pointer to the underlying array

- returns a pointer to the underlying unmodifiable array

Question 11

T& front();

const T& front() const;

T& back();

const T& back() const;

Answer 11

• returns a reference to the first element
• returns an unmodifiable reference to the first element
• returns a reference to the last element
• returns an unmodifiable reference to the last element

Question 12

void push_back(const T& t);

void pop_back();

void clear();

Answer 12

• adds element t after the last element in the container
• removes the last element from the container
• removes all elements from the container

Question 13

What will be the output?

 #include 
 #include 

 int main() {
     std::vector prices; // initially empty

 if(prices.empty())       // is prices empty?
     std::cout << "prices is empty" << std::endl; 
 prices.push_back(10.43); // add 10.43
 prices.push_back(20.54); // add 20.54
 prices.push_back(32.43); // add 32.43
 for(int i = 0; i < prices.size(); i++)
     std::cout << prices[i] << "  ";
 std::cout << std::endl;
 prices.front() = 54.11; // change 1st element 
 prices.pop_back();      // remove last element 
 for(int i = 0; i < prices.size(); i++)
     std::cout << prices[i] << "  ";
 std::cout << std::endl;  }

Answer 13

prices is empty

10. 43 20.54 32.43
11. 11 20.54

Question 14

How to get the pointer to point to the first element of vector object v

Answer 14

we can use either &v[0] or &v.front().

Question 15

A deque class can change in size from ______ end and have elements ordered in _______

Answer 15

either

sequence

Question 16

What member functions does the deque class include that vector doesn’t?

Answer 16

void pop_front() - removes the first element from the container

void push_front(const T& t) - adds element t before the first element in the container

Question 17

What will be the output?

 #include   // for deque template
 #include 

 int main() {
     std::deque prices(3, 10.50), costs; 

 prices.back() = 32.43; // reset last
 prices.pop_front();    // remove first
 for(int i = 0; i < prices.size(); i++) 
     std::cout << prices[i] << "  ";
 std::cout << std::endl;
 costs = prices;
 costs.push_front(5.64);  // add 5.64
 costs.push_front(20.31); // add 20.31
 costs.at(1) += 10.0;     // add 10.0
 for(int i = 0; i < costs.size(); i++)
     std::cout << costs[i] << "  ";
 std::cout << std::endl;  }

Answer 17

10. 5 32.43

20. 31 15.64 10.5 32.43

Question 18

Characteristics of the list class:

Answer 18

• doubly linked sequences that are optimized for insertion and removal of elements anywhere throughout the list
• sub-optimal for fast random access

Question 19

List class member functions:

iterator insert(iterator position, const T& t);

iterator erase(iterator position, const T& t);

Answer 19

• adds element T at the iterator position

- remove element T at the iterator position

Question 20

What member functions does the list class omit?

Answer 20

the subscripting operators and the at(int) member functions

Question 21

Standard library adapters

stack

queue

priority_queue

Answer 21

• last in, first out (LIFO) context
• first in, first out (FIFO) context
• first element is always the greatest

Question 22

What is the default container class defined by the stack, queue, and priority_queue adaptors?

Answer 22

deque

Question 23

Member functions of the stack class

Answer 23

explicit stack() - default - creates a stack with no elements
explicit stack(const Container& c) - creates a stack initialized to a copy of container c
stack& operator=(const stack& s) - copies the contents of s into the current object
~stack() - destroys the stack
size_t size() const - returns the number of elements in the current object
bool empty() const - returns true if the current object has no elements
T& top() - returns a reference to the top element of the stack
const T& top() const - returns an unmodifiable reference to the top element of the stack
void push(const T& t) - adds element t to the top of the stack
void pop() - removes the top element from the stack

Question 24

What will be the output?

 #include 
 #include 

 int main() {
     std::stack prices; // initially empty 

 prices.push(10.43); // add 10.43
 prices.push(20.54); // add 20.54
 prices.push(32.43); // add 32.43
 prices.top() = 5.41;
 while(!prices.empty()) {
     std::cout << prices.top() << "  ";
     prices.pop();
 }
 std::cout << std::endl;  }

Answer 24

5.41 20.54 10.43

Question 25

Additional member functions of the queue class T& front(); const T& front() const; T& back(); const T& back() const;

Answer 25

- returns a reference to the first element of the queue - returns an unmodifiable reference to the first element of the queue - returns a reference to the last element of the queue - returns an unmodifiable reference to the last element of the queue

Question 26

What will be the output? ``` #include #include ``` ``` int main() { std::queue tickets; // initially empty ``` tickets.push(10); // add 10 tickets.push(20); // add 20 tickets.push(32); // add 32 tickets.back() = 30; while(!tickets.empty()) { std::cout << tickets.front() << " "; tickets.pop(); } std::cout << std::endl; }

Answer 26

10 20 30

Question 27

What is an iterator?

Answer 27

an object that points to an element in a sequence

Question 28

Which standard library containers require iterators to access their elements?

Answer 28

classes that do not implement contiguous storage

Question 29

The definition of an iterator takes the form:

Answer 29

Container::iterator identifier;

Question 30

to define an iterator named iter for a vector of doubles, we write

Answer 30

std::vector::iterator iter;

Question 31

STL container classes include these member functions that return iterators:

Answer 31

iterator begin() noexcept - returns an iterator pointing to the first element in a sequence iterator end() noexcept - returns an iterator pointing to the element one past the end of a sequence const_iterator cbegin() const noexcept - returns an iterator pointing to the first element unmodifiable in a sequence const_iterator cend() noexcept - returns an iterator pointing to the element unmodifiable one past the end of a sequence

Question 32

What do these operators do on iterators? ++ -- *

Answer 32

point to next element point to previous element return value of element

Question 33

What will be the output? ``` #include #include ``` int main() { std: :vector prices; // initially empty std: :vector::iterator i; prices.push_back(10.43); // add 10.43 prices.push_back(20.54); // add 20.54 prices.push_back(32.43); // add 32.43 for(i = prices.begin(); i != prices.end(); i++) std::cout << *i << " "; std::cout << std::endl; }

Answer 33

10.43 20.54 32.43

Question 34

Iterator functions for inserting and removing elements anywhere within a collection

Answer 34

iterator insert(iterator position, const T& t) - inserts t at position p and returns an iterator pointing to the inserted element void insert(iterator position, size_t n, const T& t) - inserts t n times at position p void insert(iterator position, InIter f, InIter l) - inserts the range [f,l) at position p iterator erase(iterator p) - removes the element at position p and returns an iterator to the next element iterator erase(iterator f, iterator l) - removes the elements in the range [f,l) and returns an iterator to the next element

Question 35

What will be the output? ``` #include #include ``` ``` int main() { std::list prices; // initially empty ``` prices.push_back(10.43); // add 10.43 prices.push_back(20.54); // add 20.54 prices.push_back(32.43); // add 32.43 prices.insert(--prices.end(), 12.52); prices.erase(++prices.begin()); for(auto i = prices.begin(); i != prices.end(); i++) std::cout << *i << " "; std::cout << std::endl; }

Answer 35

10.43 12.52 32.43

Question 36

What will be the output?

Answer 36

10. 5 32.43 | 10. 5 15.64 32.43 20.31