4.2.4 Random Access Iterators

In addition to bidirectional iterators, random access iterators satisfy the following requirements:

Random Access Iterator Requirements (additional to bidirectional iterators'):

• operator+ (int)
• operator+= (int)
• operator- (int)
• operator-= (int)
• operator- (random access iterator)
• operator[] (int)
• operator < (random access iterator)
• operator > (random access iterator)
• operator >= (random access iterator)

• operator <= (random access iterator)

Random access iterators allow algorithms to have random access to elements stored in a container which has to provide random access iterators, like the vector.

vector<int> v (1, 1);
v.push_back (2); v.push_back (3); v.push_back (4); // vector v: 1 2 3 4

vector<int>::iterator i = v.begin();
vector<int>::iterator j = i + 2; cout << *j << " ";
i += 3; cout << *i << " ";
j = i - 1; cout << *j << " ";
j -= 2;
cout << *j << " ";
cout << v[1] << endl;

(j < i) ? cout << "j < i" : cout << "not (j < i)"; cout << endl;
(j > i) ? cout << "j > i" : cout << "not (j > i)"; cout << endl;

i = j;
i <= j && j <= i ? cout << "i and j equal" : cout << "i and j not equal"; cout << endl;
j = v.begin();
i = v.end();
cout << "iterator distance end - begin =^ size: " << (i - j);

Output: 3 4 3 1 2

Output: j < i

Output: not (i > j)

Output: i and j equal

Output: iterator distance end - begin =^ size: 4

An algorithm that needs random access to container elements to work with O(ld n) is the binary search algorithm. In section 4.3 algorithms and function objects are explained and it is shown how they work together in a very advantageous way.

Continue with section 4.2.5

Back to index