David E. Goldschmidt, Ph.D.

Example 23: Erasing Elements from a Vector

// iterator-example-v1.cpp  <== click here for file

#include <iostream>
#include <vector>
using namespace std;

// this does not use an iterator (yet); just a pointer

int main()
{
  vector<string> courses;
  courses.push_back( "CSCI 1200" );
  courses.push_back( "CSCI 4210" );
  courses.push_back( "CSCI 1100" );
  courses.push_back( "CSCI 4430" );
  courses.push_back( "CSCI 4440" );

  for ( unsigned int i = 0 ; i < courses.size() ; i++ ) {
    cout << courses[i];
    if ( courses[i] == "CSCI 4210" ) {
      cout << " (hey, that's Operating Systems!)";
    }
    cout << '\n';
  }

  // find a course and cancel it
  string course_to_delete = "CSCI 4210";
  bool found = false;
  unsigned int loc = 0;
  while ( !found && loc < courses.size() )
  {
    found = ( courses[loc] == course_to_delete );
    if ( !found ) { loc++; }
  }

  if ( found ) {
    courses.erase( courses.begin() + loc );
    cout << "Course deleted: " << course_to_delete << '\n';
  }

  for ( unsigned int i = 0 ; i < courses.size() ; i++ ) {
    cout << courses[i] << '\n';
  }

  return 0;
}

Order Analysis:

• When items are constantly being inserted and removed, vectors are not a good choice of container. Such operations require (large) contiguous portions of the vector to be shifted, which result in O(n) algorithms.
• A different sequential container called a linked list (i.e. list) is better.
• A list has a linked structure that makes the cost of inserting and erasing independent of the size. Therefore, insertion and deletion operations (assuming we know which nodes we'd like to insert or delete) are O(1).
• We will move toward a list-based implementation of the program above in two steps:
  1. Rewriting our code using iterator operations.
  2. Replacing vector with list.

Example 24: Iterators

Defining Iterators:

• From the definition given in Koenig & Moo, an iterator:
  • Identifies a container and a specific element stored in the container.
  • Lets us examine and change (except for a const_iterator) the value stored at that element of the container.
  • Provides operations for moving (i.e. the iterator) between elements in the container.
  • Restricts the available operations in ways that correspond to what the container supports.
• Iterators for different container classes have many operations in common. This often makes the switch between containers fairly straightforward from the programmer's viewpoint.
• In many ways, iterators are generalizations of pointers: many operations and operators defined for pointers are also defined for iterators.

// iterator-example-v2.cpp  <== click here for file

#include <iostream>
#include <vector>
using namespace std;

// this DOES use an iterator (on vector)

int main()
{
  vector<string> courses;
  courses.push_back( "CSCI 1200" );
  courses.push_back( "CSCI 4210" );
  courses.push_back( "CSCI 1100" );
  courses.push_back( "CSCI 4430" );
  courses.push_back( "CSCI 4440" );

  // create an iterator
  vector<string>::iterator p = courses.begin();
  while ( p != courses.end() ) {
    cout << *p;
    if ( *p == "CSCI 4210" ) {
      cout << " (hey, that's Operating Systems!)";
    }
    cout << '\n';

    p++;   // Advance the iterator
  }

  // find a course and cancel it
  string course_to_delete = "CSCI 4210";
  bool found = false;
  vector<string>::iterator loc = courses.begin();
  while ( !found && loc != courses.end() )
  {
    found = ( *loc == course_to_delete );
    if ( !found ) { loc++; }
  }

  if ( found ) {
    courses.erase( loc );
    cout << "Course deleted: " << course_to_delete << '\n';
  }

  for ( p = courses.begin() ; p != courses.end() ; p++ ) {
    cout << *p << '\n';
  }

  return 0;
}

• As we have already seen with the vector<T> class and our own Vec<t> implementation, iterator types are declared by the container class, as in:

// define an uninitialized pointer p that will refer to
//   an element in a vector of string objects
vector<string>::iterator p;

// define an uninitialized pointer q that will refer to
//   an element in a vector of string objects, though
//   note that the element referred to CANNOT be changed
vector<string>::const_iterator q;

• The dereference operator is applied to an iterator to access the value stored at an element of the container. In particular, the following code changes the first entry in the given vector:

vector<string> courses;
vector<string>::iterator p;
p = courses.begin();
*p = "CSCI 1100";

• The dereference operator is combined with the dot operator tor access member functions of class objects stored in containers. Here is an example using the Student class:

vector<Student> students;
vector<Student>::iterator i = students.begin();

// Note that the parentheses are required
double gpa = (*i).get_gpa();

// Rewrite the line above using ->
double gpa = i->get_gpa();

• Just like pointers, iterators can be incremented and decremented using the ++ and -- operators, which move the iterator to the next or previous element of any container.
• Iterators can be compared using the == and != operators.
• Iterators can be assigned using the = operator.
• Since a vector uses an array for its internal implementation, we can compare iterators using the <, ≤, >, and ≥ operators. Further, pointer arithmetic is supported, as in:

courses.erase( courses.begin() + loc );

Example 25: Lists

// iterator-example-v3.cpp  <== click here for file

#include <iostream>
#include <list>
using namespace std;

// this DOES use an iterator (on list)

int main()
{
  list<string> courses;
  courses.push_back( "CSCI 1200" );
  courses.push_back( "CSCI 4210" );
  courses.push_back( "CSCI 1100" );
  courses.push_back( "CSCI 4430" );
  courses.push_back( "CSCI 4440" );

  // create an iterator
  list<string>::iterator p = courses.begin();
  while ( p != courses.end() ) {
    cout << *p;
    if ( *p == "CSCI 4210" ) {
      cout << " (hey, that's Operating Systems!)";
    }
    cout << '\n';

    p++;   // Advance the iterator
  }

  // find a course and cancel it
  string course_to_delete = "CSCI 4210";
  bool found = false;
  list<string>::iterator loc = courses.begin();
  while ( !found && loc != courses.end() )
  {
    found = ( *loc == course_to_delete );
    if ( !found ) { loc++; }
  }

  if ( found ) {
    courses.erase( loc );
    cout << "Course deleted: " << course_to_delete << '\n';
  }

  for ( p = courses.begin() ; p != courses.end() ; p++ ) {
    cout << *p << '\n';
  }

  return 0;
}

Lists:

• Lists are formed as a sequentially linked structure instead of the array-like random access indexing structure of vectors.
• Lists have push_front() and pop_front() functions in addition to the push_back() and pop_back() functions of vectors.
• Erase is very efficient for a list, independent of the size of the list.
• We cannot use the standard sort() function; we must use a special sorting function defined by the list type.
• Lists have no subscripting operation. Why not?
• Although the interface (public member functions) of lists and vectors and their iterators are quite similar, their implementations are substantially different.
• In particular, operations that differ include:
  • No indexing (subscripting) in lists.
  • No push_front() or pop_front() operations for vectors.
  • For vectors, the erase() function invalidates all iterators after the point of erasure.
  • Again for vectors, the push_back() function invalidates all iterators in a vector. Why?
  • Lists have their own specialized sorting functions. Why?