W6: Containers and Iterators Flashcards
An array has _________ storage of _______ size
contiguous
fixed
A vector has _________ storage of _______ size
contiguous
variable
A deque has _________ storage of _______ size, and a ___________ queue
non-contiguous
variable
double-ended
A forward_list has _________ storage of _______ size, and a __________ list
non-contiguous
variable
singly-linked
A list has _________ storage of _______ size
non-contiguous
variable
doubly-linked
vector(int n);
vector(int n, const T& t) ;
- creates a container with n elements
- creates a container with n elements, each initialized to value t
vector(const vector& v);
vector& operator=(const vector& v);
vector(vector&& v) noexcept ;
vector& operator=(vector&& v) noexcept;
~vector();
- copies the contents of container v into the current object
- moves the contents of container v into the current object
- destroys the container
size_t size() const;
size_t capacity() const;
bool empty() const;
- 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
- 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
T* data() noexcept;
const T* data() const noexcept;
- returns a pointer to the underlying array
- returns a pointer to the underlying unmodifiable array
T& front();
const T& front() const;
T& back();
const T& back() const;
- 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
void push_back(const T& t);
void pop_back();
void clear();
- adds element t after the last element in the container
- removes the last element from the container
- removes all elements from the container
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; }
prices is empty
- 43 20.54 32.43
- 11 20.54
How to get the pointer to point to the first element of vector object v
we can use either &v[0] or &v.front().
A deque class can change in size from ______ end and have elements ordered in _______
either
sequence
What member functions does the deque class include that vector doesn’t?
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
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; }
- 5 32.43
20. 31 15.64 10.5 32.43
Characteristics of the list class:
- doubly linked sequences that are optimized for insertion and removal of elements anywhere throughout the list
- sub-optimal for fast random access
List class member functions:
iterator insert(iterator position, const T& t);
iterator erase(iterator position, const T& t);
- adds element T at the iterator position
- remove element T at the iterator position
What member functions does the list class omit?
the subscripting operators and the at(int) member functions
Standard library adapters
stack
queue
priority_queue
- last in, first out (LIFO) context
- first in, first out (FIFO) context
- first element is always the greatest
What is the default container class defined by the stack, queue, and priority_queue adaptors?
deque
Member functions of the stack class
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
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; }
5.41 20.54 10.43
Additional member functions of the queue class
T& front();
const T& front() const;
T& back();
const T& back() const;
- 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
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; }
10 20 30
What is an iterator?
an object that points to an element in a sequence
Which standard library containers require iterators to access their elements?
classes that do not implement contiguous storage
The definition of an iterator takes the form:
Container::iterator identifier;
to define an iterator named iter for a vector of doubles, we write
std::vector::iterator iter;
STL container classes include these member functions that return iterators:
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
What do these operators do on iterators?
*
point to next element
point to previous element
return value of element
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; }
10.43 20.54 32.43
Iterator functions for inserting and removing elements anywhere within a collection
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
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; }
10.43 12.52 32.43
What will be the output?
- 5 32.43
10. 5 15.64 32.43 20.31
