David E. Goldschmidt, Ph.D.

Example 26: Iterator Operations

Iterator Operations:

• An iterator type is defined by each container class. For example:

vector<double>::iterator p;
list<string>::iterator q;

• There are also string iterators, which work just like vector iterators.
• An iterator is assigned to a specific location in a container. For example:

vector<double> v;
vector<double>::iterator p;
p = v.begin() + i;   // i-th location in the vector

list<string> r;
list<string>::iterator q;
q = r.begin();       // first entry in the list

• The contents of the specific entry referred to by an iterator are accessed using the * operator.

// use of *p and *q below are as l-values:
*p = 3.14;
*q = "Hello";

// use of *q below is as an r-value:
cout << *q << endl;

• Stepping through a container, either forward and backward, is done using the increment (++) and decrement (--) operators.

// move p to the next location in the vector
++p;

// move q to the previous location in the list
q--;

• When we have an iterator that references a list (or vector) of objects, the member functions of the object are accessed through the -> operator.

list<string> words;

// ... populate the list ...

// iterate through all elements of the list:
for ( list<string>::iterator p = words.begin() ; p != words.end() ; p++ ) {
  cout << *p << " " << p->size() << '\n';
}

// TO DO: change above for loop into a while loop

• We can change the container that an iterator p refers to as long as the types are the same.

vector<double> v;
vector<double>::iterator p;
p = v.begin();
*p = 3.14;   // changes entry 0 in v

vector<double> w;
p = w.begin() + 2;
*p = 2.78;   // changes entry 2 in w

vector<string> a;
p = a.begin();  // !!! compilation error due to type mismatch !!!

Vector Iterators:

Vector (and string) iterators have special capabilities that other container iterators (e.g. list) do not have, as described below.

• Initialization at an indexed spot in the vector:

p = v.begin() + i;

• Jumping around inside the vector through addition and subtraction of location counts:

p = p + 5;   // moves p exactly 5 locations further in the vector

• The above operators are allowed because vectors are really arrays and vector iterators are really just pointers.
• Neither of these is allowed for list iterators (and most other iterators, for that matter) because of the underlying linked structure of lists.
• Vector (and string) iterators may also be compared using <, <=, >, and >= operators. List (and other) iterators may only be compared using == and !=.

Iterators vs. Indexes for Vectors and Strings:

• Consider the following declarations:

vector<double> a( 10, 2.5 ), b( 20, 1.1 );
vector<string> c( 3, string( "hi" ) );
vector<double>::iterator p = a.begin() + 5;
unsigned int i = 5;

• Iterator p refers to location 5 in vector a. The value stored there is directly accessed through the * operator, as follows:

*p = 6.0;  // change the contents of vector a.

• We can also access the contents of vector a using subscripting. Using i as the subscript, we write:

// i is not "attached" to vector a in any way
cout << a[i] << endl;

Example 27: Lists vs. Vectors

Lists vs. Vectors:

• Lists are a chain of separate memory blocks, one block for each entry.
• Vectors are formed as a contiguous (and much bigger) block of memory.
• Therefore, lists support easy (and fast) insertions and deletions in the middle, but not indexing.
• Vectors support indexing (which "jumps around" inside the block of memory), but slow insertions and deletions in the middle (due to required shifting of elements and reindexing).

Erase:

• Lists and vectors each have a special member function called erase().

list<int> s;

// ... populate s ...

list<int>::iterator p = s.begin();
p++;

list<int>::iterator q = s.erase( p );

// after calling the function erase():
// – the integer stored in the second entry of the list has been removed
// – the size of the list has shrunk by one
// – iterator p does not refer to a valid entry
// – iterator q refers to the item that was the third entry and is now the second

• You will often see the code above rewritten without iterator q by reusing iterator p to refer to the entry after the entry that was erased:

list<int>::iterator p = s.begin();
p++;

p = s.erase( p );

• Even though the erase() function has the same syntax for both vectors and lists, the vector version is O(n), whereas the list version is O(1).

Insert:

• Given a list and an iterator p that refers to an item in the list, the insert() member function of the list class may be used to insert a new item before the item referred to by p.
• The insert() function returns an iterator referring to the new item that was inserted.

list<string>::iterator p = words.begin();

// insert string "Hello" at the beginning of the list
p = words.insert( p, string( "Hello" ) );

// ... populate the list ...

// refer to the element beyond the last element in the list
list<string>::iterator p = words.end();
p = words.insert( p, string( "Bye" ) );
p = words.insert( p, string( "Good" ) );

// the list ends with: ... "Good" "Bye"