Understanding C++ Iterators

iterators.md

C++'s iterators are a generalisation of pointers-into-arrays. So you can write this:

void sort_array() {
    int arr[10] = {4, 5, 1, 7, 6, 3, 9, 2, 8, 0};
    std::sort(arr, arr + 10); // std::sort<int*>
}

just as you can write

void sort_vector() {
    std::vector<int> v = {4, 5, 1, 7, 6, 3, 9, 2, 8, 0};
    std::sort(v.begin(), v.end()); // std::sort<std::vector<int>::iterator>
}

And in general you can write

template <Container C, Integral T> // not-yet-legal concepts syntax
sort_container() {
    C<T> c = {4, 5, 1, 7, 8, 3, 9, 2, 8, 0};
    std::sort(std::begin(c), std::end(c));
}

Note: template <Container C, Integral T> means template <typename C, typename T> requires Container<C> && Integral<T>, which roughly means template <typename C, typename T, std::enable_if_t<std::is_integral_v<T> && std::is_container_v<C>>, if std::is_container existed

std::sort, because it is a function template, works for both T* (the sort of iterator you use into a T[N]) and std::vector<T>::iterator (the sort of iterator you use for a std::vector<T>, obviously). This only works because iterators are designed to mimic how pointers work.

And you can write these:

for (auto x : A) {
    std::cout << x << std::endl;
}

which are transformed into this (basically):

auto __end = std::end(A);    
for (auto __it = std::begin(A); __it != __end; ++__it) {
    std::cout << (*__it) << std::endl;
}

Which works whether A is arr or v.

Note: While in C you use T * everywhere, in modern C++ you use unique_ptr<T> for a owning-pointer-to-T, T * for a non-owning-nullable-pointer-toT, T& for a non-owning-non-nullable-pointer-to-T, std::array<T,N>::iterator for a pointer-into-std::array<T,N> (the replacement for T[N]) and std::vector<T>::iterator for a pointer-into-std::vector<T> (the replacement for T[]).

But iterators don't have to have the semantics of pointers, otherwise we'd just use pointers.