CS106L(6): Arcade Toy Claw with Iterators

2020-11-25

language

C++

Enjoy Arcade Toy Claw Games?

I have tried that game some times ago, here is the evidence:

HAHAHAHAHAHAHA…..The shop owner will bankrupt soon 💸

Summary

Understand Iterators Concept: It’s like Arcade Toy Claw Game!
Iterator Practice: Example and Exercises
- Introduce different types of Iterators

std:vector Loop Example

std::vector<int> vector{3, 1, 4, 1, 5, 9};
for (size_t i = 0; i < vector.size(); i++) {
 const auto& elem = vector[i];
 cout << elem << endl;
}

Iterators

Iterators allow iteration over any container whether ordered or unordered.

Iterators (“the claw”) can:

move “forward”
- according to some order…
retrieve element
check if two claws are in the same place

Containers (“the machine”) provide:

the bounds (begin and end)

2020_11_25_2

Key idea: iterator has ordering over elements, it always knows what the “next” element is.

it (the reference)
*it; (dereference, the item)
(it == c.end())  //until

Examples

std::set<T> s;
auto iter = s.begin();
iter++;                     // increment; prefix operator is faster (why?)
++iter;
*iter;                      // dereference iter to get curr value
(iter != s.end());          // equality comparison
iter = another_iter         // copy construction

STL sets have the following operations:

s.begin(); // an iterator pointing to the first element
s.end()    // one `past` the last element

Why use ++iter and not iter++?

Answer: There’s no need to store the old value of the iterator, so ++iter returns the value after being incremented.

Iterator Practise

What type is it?

std::map<int, int> map {{1, 2}, {3, 4}};
auto it = map.first();      // what type is this?    My ans:  std::map::Iterator<int, int>
auto map_elem = *it;        // how about this?       My ans:  <int, int>

Quiz: Iterator Basics

Example Code:

std::map<int, int> map {{1, 2}, {3, 4}};     // note that dereferencing a std::map::iterator returns a std::pair
auto iter = map.begin(); // what is *iter?                       My ans:  <int, int>
++iter;                  // what is (*iter).second now?          My ans:  4
auto iter2 = iter;
++iter;                  // what does (*iter).first return?      My ans:  undefined

Notes:

++iter: go to the next element
*iter: retrieve what’s at iter’s position
copy constructor: create another iterator pointing to same thing

iter is a copy of begin iterator.

auto iter = map.begin();

*iter returns {1, 2}
++iter; : *iter incremented to next element
*iter.second is 4
auto iter2 = iter;: create an independent copy of iter pointing to same thing
last ++iter;: increment iter (iter2 not impacted…)
what does (*iter).first return?

undefined!, because (iter == map.end())

Recall the Loop Example

std::vector<int> vector{3, 1, 4, 1, 5, 9};
for (size_t i = 0; i < vector.size(); i++) {
 const auto& elem = vector[i];
 cout << elem << endl;
}

Iterator Example

std::set<int> set {3, 1, 4, 1, 5, 9};
for (auto iter = set.begin(); iter != set.end(); ++iter) {
 const auto& elem = *iter;
 cout << elem << endl;
}

std::map<int> map {{1, 6}, {1, 8}, {0, 3}, {3, 9}};
for (auto iter = map.begin(); iter != map.end(); ++iter) {
 const auto& [key, value] = *iter; // structured binding!
 cout << key << “:” << value << endl;
}

Exercise: print all elements in these collections

You discovered For-Each Loop!

std::set<int> set {3, 1, 4, 1, 5, 9};
for (const auto& elem : set) {
 cout << elem << endl;
}
std::map<int> map {{1, 6}, {1, 8}, {0, 3}, {3, 9}};
for (const auto& [key, value] : map) {
 cout << key << ":" << value << endl;
}

Thoughts: auto or auto&?

Seems that if it is value, auto& will be used to represent the dereference/or the content in that address, if it’s pointer/iterator, then auto will be used. Is it correct?

Iterator Shorthand

These are equivalent:

auto key = (*iter).first;
auto key = iter->first;

Types of Iterators

All iterators are incrementable (++)
Input iterators can be on the right side of =: auto elem = *it;
Output iterators can be on the left side of =: *elem = value;
Forward iterators can be traversed multiple times:

iterator a;
b = a;
a++; b++;
assert (*a == *b) // true

Q: Can you think of an example of an iterator that should not be a forward iterator?

Random access iterators support indexing by integers.

it += 3; // move forward 3
it -= 70; // move backwards by 70
auto elem = it[5]; // offset by 5

Haha, congrats, the 6th lecture finished! Wish you good luck next time when you see this:

2020_11_25_1

Famous Arcade Game!

fabbit