Iterators

Some data structures in C++ implement iterators - used to iterate over elements of the data structure (especially if random access is not supported). Iterators can be advanced by moved forward (++) and backward (--) by one step. To get the value of the element being pointed to, dereference it like a pointer (*).

Usually the data structure d will provide two methods:

• d.begin() - points to the first element
• d.end() - points to the position after the last element

Insert and erase methods usually accept iterators.

Vector

vector<int> v{ 3, 4, 5, 6, 7 };
//             ^ v.begin()   ^ v.end()
for (auto it = v.begin();  // let the iterator point to the first element
     it != v.end();        // check if iterator reached the end of the vector
     it++) {               // advance the iterator
    cout << *it << " ";  // dereference the iterator using *
}
cout << "\n";  // 3 4 5 6 7

Because vector supports random access, it is possible to add an integer to it directly (not possible for set):

v.insert(v.begin() + 2, 10);  // 3 4 10 5 6 7

find from <algorithm> also returns an iterator:

auto it = find(v.begin(), v.end(), 10);   // iterator pointing to position of 10 (== v.begin() + 2)
v.erase(it);  // 3 4 5 6 7

Set

set<int> s{3, 4, 5, 6, 7};
for (auto it = s.begin(); it != s.end(); it++) {
    cout << *it << " ";
}
cout << "\n";  // 3 4 5 6 7

s.find(x) returns an iterator pointing to x if found, otherwise it returns s.end().

Since set iterates over its elements in ascending order, we can find the min and max using:

int smin = *s.begin();
int smax = *(--s.end());  // equivalent to: auto it = s.end(); it--; int smax = *it;
                          // alternatively: int smax = *s.rbegin();  // reverse iterator, cannot be used with erase

Multiset

Multiset (from <set>) is just a set supporting duplicate elements.

multiset<int> s;
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n";  // 2

Caveat: be careful with erase!

s.erase(5);  // erases all instances of 5
cout << s.count(5) << "\n";  // 0

To erase the first occurrence, pass an iterator:

s.erase(s.find(5));
cout << s.count(5) << "\n";  // 1