C++ Iterators Primer

The C++ “Standard Containers” are meant to be accessed through iterators, which are described in the course on this site as pointer-like objects which yield an element when dereferenced. Of course, programmers coming from other language backgrounds sometimes to prefer to use indexing, at least at first, however not all container types offer a subscript operator due to implementation issues (std::list does not, for example).

The Standard Containers have always provided member functions to provide first and one-past-last elements, however since C++11 non-member functions are also available within the std namespace, and it is these which allow the functionality for range-for loops, also since C++11. The full list of functions is summarized below:

Functions returning iterators which do not allow modification of the element (“const-iterators”) are also provided, named in the same way but with a preceding c, such as crbegin().

Something which is not possible with range-for loop syntax is traversing the elements backwards; this is able to be achieved as shown in the example program below:

#include <iostream>

int main() {
    const int arr[] = { 1, 2, 3, 4, 5, 6 };
    for (auto elem = std::crbegin(arr); elem != std::crend(arr); ++elem) {
        std::cout << *elem << ' ';
    }
    std::cout << '\n';
}

Note that for built-in arrays such as shown here, crbegin() returns the address of element [5], while crend() returns the address of element [-1]; this is legal because the end marker is never dereferenced. Also, use of test != is always correct for both forward and reverse markers, and prefix (not postfix) ++ should always be used.

It is technically possible to overload std::begin()/std::end() for structs or classes other than the built-in types, but this is not necessary: simply provide member functions with these names. (Adding to namespace std is, with very few exceptions, not good C++ practice.) The C++17 <filesystem> header uses iterators to provide listing of a directory, as shown in this example code:

#include <string>
#include <iostream>
#include <filesystem>

int main(const int argc, const char *argv[])
{
    if (argc != 2) {
        std::cerr << "Syntax: " << argv[0] << " directory-to-list\n";
        return 1;
    }
    std::string path = argv[1];
    std::cout << "Listing for directory: " << path << '\n';
    for (const auto &entry : std::filesystem::directory_iterator(path)) {
        std::cout << '\t' << entry.path() << std::endl;
    }
}

Orthogonal to the concept of const/non-const iterators are iterator categories, of which there are five. All iterators provide advance (++) and dereference (*), other operators are listed with their category in the table below:

When defining a class which uses iterators, these should be written as nested classes, for example: MyClass::iterator or MyClass::const_iterator. Iterator tags are defined by the Standard (in header <iterator>), for example std::reverse_iterator_tag, in order to provide algorithm selection based upon iterator type, see [TC++PL] 33.1.3. Interestingly, the rules for compatibility with range-for loops was relaxed in C++17, meaning that begin() and end() no longer have to have the same return type. This is how the Python range() example on this site is coded, not using iterators at all.

Defining a class which provides iterator access is not trivial, and you should try to use an iterator class derived from one of those in <iterator>, so reading the documentation and possibly even the header file itself may be necessary. This will pay off in producing solid, portable code which compiles without reams of template-related error messages when incorporated into a real project.