# CS106L(6): Arcade Toy Claw with Iterators

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

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>
``````

### 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
1. iter is a `copy` of begin iterator.
``````auto iter = map.begin();
``````
1. `*iter` returns {1, 2}

2. `++iter;` : `*iter` incremented to next element

3. `*iter.second` is 4

4. `auto iter2 = iter;`: create an independent copy of iter pointing to same thing

5. last `++iter;`: increment iter (iter2 not impacted…)

6. 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: