Iterators Iterators Iterators

objects that point to a location
may point to a readable memory address / object
used to iterate over container elements in a data-layout-agnostic way
also used to specify positions and ranges in containers (for insertion, deletion, etc.)

In the following chapters the notation @name will be used to denote an iterator object / parameter / return value. Note that @ is neither an allowed operator nor does it have any other meaning in C++.

Default Iterators Default

Obtainable from standard containers

either with member functions:

container.begin()→ @first_element
container.end()→ @one_behind_last_element

or with free-standing functions: C++11

std::begin(container)→ @first_element
std::end(container)→ @one_behind_last_element

An iterator refers to a position in a container:

#include <vector>
#include <iostream>

int main () {std::vector<int> v {1,2,3,4,5,6,7};
auto i = begin(v);  
auto e = end(v); 

std::cout << *i << '\n';
std::cout << *(i+2) << '\n';
// std::cout << *e << '\n'; // undefined behavior!

++i;
std::cout << *i << '\n';

i += 2;
std::cout << *i << '\n';

--i;
std::cout << *i << '\n';

i += 5;
if (i == end(v)) std::cout << "at end\n";
}

`*i` accesses the element at `i`'s position

cout << *i;
cout << *(i+2);
cout << *e;

prints 1
prints 3
 UNDEFINED BEHAVIOR

The end iterator is only intended to be used as position indicator, it must not be used to access an element.

++i goes 1 toward end
--i goes 1 towards begin

i += 2 goes forward by 2
i -= 3 goes backwards by 3

++i;

cout << *i;
i += 2;

cout << *i;
--i;

cout << *i;
i += 5;
if (i == end(v)) 
  cout << "at end";

Reverse Iterators Reverse

Obtainable from (many, but not all) standard containers

either with member functions:

container.rbegin()→ @last_element
container.rend()→ @one_before_first_element

or with free-standing functions: C++11

std::rbegin(container)→ @last_element
std::rend(container)→ @one_before_first_element

A reverse iterator refers to a position in a container:

#include <vector>
#include <iostream>

int main () {std::vector<int> v {1,2,3,4,5,6,7};
auto i = rbegin(v);  
auto e = rend(v); 

std::cout << *i << '\n';
std::cout << *(i+2) << '\n';
// std::cout << *e << '\n'; // undefined behavior!

++i;
std::cout << *i << '\n';

i += 2;
std::cout << *i << '\n';

--i;
std::cout << *i << '\n';

i += 5;
if (i == rend(v)) std::cout << "at rend\n";
}

`*i` accesses the element at `i`'s position

cout << *i;
cout << *(i+2);
cout << *e;

prints 7
prints 5
 UNDEFINED BEHAVIOR

The rend iterator is only intended to be used as position indicator, it must not be used to access an element.

++i goes 1 towards begin
--i goes 1 towards end

i += 2 goes backwards by 2
i -= 3 goes forward by 3

++i;

cout << *i;
i += 2;

cout << *i;
--i;

cout << *i;
i += 5;
if (i == rend(v)) 
  cout << "at rend";

`ri.base()` returns the corresponding normal (non-reverse) iterator

reverse position = normal position - 1
normal position = reverse position + 1

vector<int> v {1,2,3};
auto re = rbegin(v);
auto fw = re.base();

re 

   1
2
3
 
fw

Iterator-Based Loops Loops

Forward Direction

works for all standard sequence containers
out-of-bounds access bugs possible
verbose

std::vector<int> v {1, 2, 3, 4, 5, 6};
for (auto i = begin(v); i != end(v); ++i) {   cout << *i; }

Reverse Direction

works for all bidirectional containers
out-of-bounds access bugs possible
verbose

std::vector<int> v {1, 2, 3, 4, 5, 6};
for (auto i = rbegin(v); i != rend(v); ++i) {   cout << *i; }

Example: Swap Adjacent Pairs

#include <iostream>
#include <vector>
void swap_adjacent_pairs (std::vector<int>& v) {
  if (v.size() < 2) return;
  for (auto i=begin(v), j=i+1, e=end(v);      j < e; i+=2, j+=2)   {
    std::swap(*i,*j);
  }
}

int main() {
  std::vector<int> v {1,2,3,4,5,6};
  swap_adjacent_pairs(v);
  for (int x : v) { std::cout << x << ' '; }
  std::cout << '\n';
}

vector<int> v {1,2,3,4,5,6};
swap_adjacent_pairs(v);

Iterator Ranges

= pair `p,q` of iterators

end-of-range iterator q points one behind the last element in the range

Used for specifying ranges of elements

to be erased from a container

std::vector<int> v {1,2,3,4,5,6,7,8,9};  
v.erase(begin(v)+3, begin(v)+6);

to be inserted into a container
to be assigned to a container
to be processed by a standard algorithm
…

Element Count of Iterator Range Size of Iterator Range distance

returns the size of an iterator range

distance(@range_begin, @element_in_range) → index_of_element_in_range

cppreference

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>  // std::distance

int main() {
std::vector<int> v {0,1,2,3,4,5,6,7,8};
// size of subrange (as shown in image)
auto n = distance(begin(v)+2, begin(v)+7);    // int n = 5
std::cout << "n: " << n << '\n';
// size of entire container
auto m = distance(begin(v), end(v));          // int m = 9
std::cout << "m: " << m << '\n';

std::vector<int> w {4,5,1,9,8};
// get index of smallest element in w:
auto argmin = distance(     begin(w), min_element(begin(w),end(w)) );  
// int argmin = 2
std::cout << "argmin: " << argmin << '\n';
}

Avoid using distance with iterators into non-random access containers like std::list, because the runtime will be proportional to the size of the input range!

Summary: Iterators

valgrind

Beginner's Guide / Std.Library 1

Sequ.Containers

Last updated: 2020-09-20

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics

Iterators Iterators Iterators

Default Iterators Default

Obtainable from standard containers

An iterator refers to a position in a container:

`*i` accesses the element at `i`'s position

`++i` goes 1 toward end

`--i` goes 1 towards begin

`i += 2` goes forward by 2

`i -= 3` goes backwards by 3

Reverse Iterators Reverse

Obtainable from (many, but not all) standard containers

A reverse iterator refers to a position in a container:

`*i` accesses the element at `i`'s position

`++i` goes 1 towards begin

`--i` goes 1 towards end

`i += 2` goes backwards by 2

`i -= 3` goes forward by 3

`ri.base()` returns the corresponding normal (non-reverse) iterator

Iterator-Based Loops Loops

Forward Direction

Reverse Direction

Example: Swap Adjacent Pairs

Iterator Ranges

= pair `p,q` of iterators

Used for specifying ranges of elements

Element Count of Iterator Range Size of Iterator Range distance

Summary: Iterators

Comments…

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics

Default Iterators Default

Obtainable from standard containers

An iterator refers to a position in a container:

*i accesses the element at i's position

++i goes 1 toward end

--i goes 1 towards begin

i += 2 goes forward by 2

i -= 3 goes backwards by 3

Reverse Iterators Reverse

Obtainable from (many, but not all) standard containers

A reverse iterator refers to a position in a container:

*i accesses the element at i's position

++i goes 1 towards begin

--i goes 1 towards end

i += 2 goes backwards by 2

i -= 3 goes forward by 3

ri.base() returns the corresponding normal (non-reverse) iterator

Iterator-Based Loops Loops

Forward Direction

Reverse Direction

Example: Swap Adjacent Pairs

Iterator Ranges

= pair p,q of iterators

Used for specifying ranges of elements

Element Count of Iterator Range Size of Iterator Range distance

Summary: Iterators

Comments…

`*i` accesses the element at `i`'s position

`++i` goes 1 toward end

`--i` goes 1 towards begin

`i += 2` goes forward by 2

`i -= 3` goes backwards by 3

`*i` accesses the element at `i`'s position

`++i` goes 1 towards begin

`--i` goes 1 towards end

`i += 2` goes backwards by 2

`i -= 3` goes forward by 3

`ri.base()` returns the corresponding normal (non-reverse) iterator

= pair `p,q` of iterators