Collapse All Levels Collapse Top Level Expand Top Level Expand All Levels
News Featured Articles Beginner's Guide to C++ Lists
@hackingcpp About Privacy Home
    Beginner's Guide
    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

    • 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.

    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:
    vector<int> v {1,2,3,4,5,6,7}
auto i = begin(v);  
auto e = end(v);
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    

    • i
    •  
    •  
    •  
    •  
    •  
    •  
    • e
    *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";
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 2

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 4

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 3

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    •  
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
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:
    vector<int> v {1,2,3,4,5,6,7}
auto i = rbegin(v);  
auto e = rend(v);
    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    

    • e
    •  
    •  
    •  
    •  
    •  
    •  
    • i
    *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";
    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 6

    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 4

    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
prints 5

    •  
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    
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 Example: Swap Adjacent Example

    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)   {
    swap(*i,*j);
  }
}
    vector<int> w {1,2,3,4,5,6};
swap_adjacent_pairs(v);
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    

    • 2
    • 1
    • 4
    • 3
    • 6
    • 5

    Iterator Ranges 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);
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      
→ 
      • 1
      • 2
      • 3
      • 7
      • 8
      • 9
    • 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

    #include <vector>
#include <iterator>  // std::distance
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
// size of entire container
auto m = distance(begin(v), end(v));          // int m = 9

    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

    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

    Comments