Итераторы

Итак, мы можем работать с любым отдельным элементом коллекции. Как насчет того, чтобы перебрать все элементы? Тупой перебор в цикле for не поможет:

for (int i = 0; i < ... чего?

При выбранной реализации разреженного массива измерения не имеют верхней границы. Впрочем, даже если бы она и была, хотелось бы вам перебирать 1 000 000 000 всевозможных индексов в поисках какой-то тысячи используемых? Знаю, знаю, ваш RISC-компьютер прогоняет бесконечный цикл за семь секунд, но давайте мыслить реально. Если для коллекции существует оптимальный способ обращаться только к используемым элементам, мы должны предоставить его в распоряжение клиента.

Но помните, клиент ничего не знает о внутреннем строении наших коллекций; собственно, именно для этого мы изобретали курсоры. Добро пожаловать в удивительный и безумный мир итераторов (iterators) - классов, предназначенных для перебора коллекций! Удивительный - поскольку итераторы просто решают многие проблемы проектирования. Безумный - поскольку два программиста C++ ни за что не придут к общему мнению о том, какие же идиомы должны использоваться в реализации итераторов.