Object-Oriented Programming

Iterators

Michael L. Collard, Ph.D.

Department of Computer Science, The University of Akron

Credits

Based on On Iteration by Andrei Alexandrescu

Iterator Beginnings

  • LISP - singly-linked lists (S-lists) primary data type
    • Forward iterator only
    • Indexing makes no sense with lists
  • C-pointers
  • Data structures where indexing can be expensive, but accessing the next element (or previous element) is not, e.g., a linked list

Iterator Design Pattern

Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation

GoF Iterator

  • Often First() is replaced by a copy
  • Forward iteration only
  • Has been generalized to many related situations

C++ Library

C++ Sequence Containers

C++ Algorithms

C++ Iterators

Iterators tie data structures and algorithms together *

  • Problem:
    • m algorithms
    • n containers
    • = m × n implementations
  • Problem: User-defined containers
  • Solution: Common algorithm implementation for as many containers as possible, defined so that users can create new containers
  • Focus on algorithms and make containers adapt
  • Inspired by a c-array pointers

C-Array Operators

C-Array Pointers Description C++ Iterator term
int* p = ar; Start at the beginning initialize
++p Advance to the next item increment
p < ar + ARSIZE Keep going? comparison
*p Get current item dereference

Iterator Operations based on Pointers (C++)

Name C/C++ C++11
dereference *p  
increment/decrement ++p, (p++) / --p, (p--)  
copy curp = p  
comparison p != end  
addition n p + n std::next(p, n)
subtraction n p - n std::prev(p, n)
increment n p += n std::advance(p, n)
decrement n p -= n  
indexing p[n]  
distance p - begin std::distance(begin, p)

Use of C++ Iterators

  • begin is an iterator to the first element
  • end is an iterator pass the last element
  • Uses != instead of < because sequential elements may not be adjacent
  • Uses auto to make declaration easier
  • Use of auto also makes the code adaptable to multiple sequence containers
  • For this code, the iterator requirements are assignment, comparison, increment, dereference

C++ Iterator Operation

  • Iterators are separate objects from the container object
  • We can have multiple, simultaneous iterators for the same container object
  • Iterators are small and typically have just couple of fields/data members
  • Often passed by value and not const reference
  • The C++ standard algorithms are implemented using iterators

Pre and Post

Term C/C++ Order of Operations
pre-increment ++p Step 1: p += 1
    Step 2: Return value
post-increment p++ Step 1: Return value
    Step 2: p += 1
pre-decrement --p Step 1: p -= 1
    Step 2: Return value
post-decrement p-- Step 1: Return value
    Step 2: p -= 1

Class Pre and Post Implementation

  • Post-increment can be implemented using pre-increment

  • Post-increment requires an additional copy

  • Post-increment is never more efficient than pre-increment

  • Post-increment is more difficult to understand than pre-increment

  • Decrement has the same issues

  • Prefer ++p over p++
  • Prefer --p over p--

Container Support for Iterators: std::vector

Description Method
Iterator to first element v.begin()
Iterator past the end of the vector v.end()
const Iterator form of v.begin() v.cbegin()
const Iterator form of v.end() v.cend()
Reverse iterator to the element preceding the first element v.rbegin()
Reverse iterator to the last element in the vector v.rend()
const Iterator form of v.rbegin() v.crbegin()
const Iterator form of v.rend() v.crend()

Common Interface

  • Consistent usage helps in comprehension of the code

  • Can change the data structure without changing the algorithm

  • Easy to learn new data structures

  • Can create user-defined data structures that work with the existing algorithms

  • Can create new algorithms that work with existing containers

C++ Iterator Hierarchy

  • input iterators - one-pass input from streams
  • output iterators - one-pass output to streams
  • forward iterators - models access to singly-linked lists
    • *p, ++p, (p++), curp = p, p != end
  • bidirectional iterators - models access to double-linked lists
    • *p, ++p, (p++), curp = p, p != end, --p, (p--)
  • random-access iterators models array access
    • *p, ++p, (p++), curp = p, p != end, --p, (p--), p += 5, p[5], p - begin
  • All of these primitives are constant time O(1).
  • Pointers in C are random-access iterators

C++ Container Types