Lab 04 - Iterator (02/09/2022)

---

Classes defined inside another class are called nested classes. Nested classes are used in situations where the nested class has a close conceptual relationship to its surrounding class.

A class can be nested in any part of the surrounding class: in the public, protected or private sections, and is considered a member of the surrounding class. The normal access rules of classes apply to nested classes. If a class is nested in the public section of a class, it is visible outside the surrounding class. Likewise, if nested in the protected section, it is visible in subclasses, derived from the surrounding class and if nested in the private section, it is only visible for the members of the surrounding class. The surrounding class has no special privileges towards the nested class. The nested class has full control over the accessibility of its members by the surrounding class.

Since iterators are closely associated with the container upon which it iterates, iterators are most often implemented as nested classes in the public member section of the container. The container begin() and end() member functions instantiate and return a class iterator object.

The prefix and postfix versions of the unary increment and decrement operators can all be overloaded. To allow both unary prefix and postfix increment usage, each overloaded operator function must have a distinct signature (so that the compiler can determine which version of "++" is intended.)

When the compiler sees the pre-increment expression on a Data data type:

Data myData;
++myData;

the compiler generates the member function call:

Data myData;
myData.operator++();

The prototype for this operator function would be:

Data& operator++();

Overloading the postfix increment operator presents a challenge because the compiler must be able to distinguish between the signatures of the overloaded prefix and postfix increment operator functions.

The convention that has been adopted in C++ is that when the compiler sees the post-incrementing expression object++, it generates the member function call:

myData.operator++(0)

The argument 0 is strictly a "dummy value" that enables the compiler to distinguish between the prefix and postfix increment operator functions.

In summary:

// prefix (return by reference)
MyClass& operator++()
{
   // implement increment logic, return reference to it.
   return *this;
}

// postfix (return by value)
MyClass operator++(int) // the dummy int disambiguates
{
   MyClass tmp(*this);
   operator++();        // prefix-increment this instance
   return tmp;          // return value before increment
}

**NOTE: The return value of the overloaded postfix operator must be a non-reference, because we can’t return a reference to a local variable that will be destroyed when the function exits. Postfix operators are typically less efficient than the prefix operators because of the added overhead of instantiating a temporary variable and returning by value instead of reference.

The concept of an iterator is fundamental to understanding the C++ Standard Template Library (STL). Iterators provide a means for accessing data stored in container classes such a vector, map, list, etc.

Iterators are objects acting like pointers. You can think of an iterator as pointing to an item that is part of a larger container of items. All iterated containers support a function called "begin", which returns an iterator object pointing to the beginning of the container (the first element) and a function "end", which returns an iterator object corresponding to having reached the end of the container. You then can access the element by "dereferencing" the iterator with a "*", just as you would dereference a pointer.

The linked list iterator functions used in Lab 04 are as follows:

• Iterator begin();

  Returns an iterator pointing to the first element in the list container.

  Example:

  LinkedList::Iterator iter = linked_list.begin();

• Iterator end();

  Returns an iterator referring to the past-the-end element in the list container. The past-the-end element is the theoretical element that would follow the last element in the list container. It does not point to any element, and thus shall not be dereferenced. Because the ranges used by functions of the standard library do not include the element pointed by their closing iterator, this function is often used in combination with list::begin to specify a range including all the elements in the container.

  If the container is empty, this function returns the same as list::begin.

  Example:

  LinkedList<string>::Iterator iter = linked_list.begin();
  while (iter != linked_list.end())
  {
     cout << endl << " [" << *iter << "]";
     ++iter;
  }

• Iterator find(Iterator first, Iterator last, const T& value);

  Returns an iterator to the first element in the range [first,last) that compares equal to value. The range searched is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. If no elements match, the function returns last.

  Example:

  LinkedList::Iterator position;
  position = linked_list.find(linked_list.begin(), linked_list.end(), value);

• Iterator insert(Iterator position, const T& value);

  The container is extended by inserting a new element before the element at the specified position. The function returns an iterator pointing to the newly inserted element.

  Example:

  LinkedList::Iterator position;
  position = linked_list.find(linked_list.begin(), linked_list.end(), find_value);
  linked_list.insert(position, before_value);

• Iterator insert_after(Iterator position, const T& value);

  The container is extended by inserting a new element after the element at the specified position. The function returns an iterator pointing to the newly inserted element.

  Example:

  LinkedList::Iterator position;
  position = linked_list.find(linked_list.begin(), linked_list.end(), find_value);
  linked_list.insert_after(position, after_value);

• Iterator erase(Iterator position);

  Removes from the list container a single element (position) and returns an iterator pointing to the element that followed the element erased by the function call. This is the container end if the operation erased the last element in the sequence.

  Example:

  LinkedList::Iterator position;
  position = linked_list.find(linked_list.begin(), linked_list.end(), value);
  linked_list.erase(position);

• void replace(Iterator first, Iterator last, const T& old_value, const T& new_value);

  Assigns new_value to all the elements in the range [first,last) that compare equal to old_value. The function uses operator== to compare the individual elements to old_value.

  Example:

  linked_list.replace(linked_list.begin(), linked_list.end(), "too", "very");

Summary

So why use iterators? First, they're a flexible way to access the data in containers that don't have obvious means of accessing all of the data (for instance, maps). They're also quite flexible - if you change the underlying container, it's easy to change the associated iterator so long as you only use features associated with the iterator supported by both classes. Finally, the STL algorithms defined in <algorithm> use iterators.

The Good:

• The STL provides iterators as a convenient abstraction for accessing many different types of containers.
• Iterators for templated classes are generated inside the class scope with the syntax class_name::iterator.
• Iterators can be thought of as limited pointers (or, in the case of random access iterators, as nearly equivalent to pointers.)

The Bad:

• Iterators (like pointers) do not provide bounds checking; it is possible to overstep the bounds of a container, resulting in segmentation faults.
• Different containers support different iterators, so it is not always possible to change the underlying container type without making changes to your code.
• Iterators (like pointers) can be invalidated if the underlying container (the container being iterated over) is changed significantly.

See also Dr. Dobb's "STL & Generic Programming: Writing Your Own Iterators"