IteratorsIteratorsIterators
- 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.
Obtainable from standard containers
either with member functions:
container.begin()
→ @first_elementcontainer.end()
→ @one_behind_last_element
or with free-standing functions: C++11
std::begin(container)
→ @first_elementstd::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);
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;
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
Iterator-Based Loop
std::vector<int> v {1, 2, 3, 4, 5, 6};
for(auto i = begin(v); i != end(v); ++i) { cout << *i; }
Obtainable from (many, but not all) standard containers
either with member functions:
container.rbegin()
→ @last_elementcontainer.rend()
→ @one_before_first_element
or with free-standing functions: C++11
std::rbegin(container)
→ @last_elementstd::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
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;
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
Reverse Iterator-Based Loop
std::vector<int> v {1, 2, 3, 4, 5, 6};
for(auto i = rbegin(v); i != rend(v); ++i) { cout << *i; }
- 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
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
= 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
- …