1. Definition
An iterator is a data type that examines and traverses the elements within a container.
[Quoted from: C++ iterator (iterator)_c++ iterator_NiUoW’s blog-CSDN blog]An iterator is a variable, which is equivalent to the intermediary between the container and the algorithm that manipulates the container. C++ tends to use iterators rather than array subscript operations because the standard library defines an iterator type for each standard container (such as vector, map, list, etc.), and only a few containers (such as vector) Supports array subscript operations to access container elements. You can use the iterator to point to the element address of the container you want to access, and use *x to print out the element value. This is very similar to the pointers we are familiar with.
C language has pointers, which are very flexible and efficient to use. The C++ language has iterators, which are more versatile than pointers.
Vector is implemented by an array, which means that as long as you know the first address of the array, you can access subsequent elements. Therefore, we can traverse the vector container elements by accessing the vector’s iterator.
List is implemented by a linked list. We know that the elements of the linked list are stored in a non-continuous address space. We need to access the next element through the next pointer. Then, we can also traverse the list container elements by accessing the iterator of the list.
It can be seen that iterators and containers are inseparable and closely connected. Different containers have different iterators, but their iterator functions are the same. If there is no iterator, due to the storage characteristics of vector and list containers, you need two algorithms to implement the function of traversing vector and list containers, which is complex and inefficient. With iterators, the efficiency of traversing containers will be greatly improved.
2. Why use iterators
Using iterators in STL (Standard Template Library) has the following benefits:
1. Unified access method: STL’s iterator provides a unified way to access container elements. Whether it is an array, linked list, collection or mapping, it can be traversed and accessed through the same iterator interface. This uniformity simplifies writing code and improves code readability and maintainability.
2. Safe access operations: The iterator is designed with the boundary conditions of the container in mind to ensure that it will not cause a crash due to out-of-bounds access or access to illegal memory. Iterators provide increment, decrement and other operators, making it easy and safe to move forward or backward a position in the container.
3. Flexible traversal methods: Iterators support forward traversal, reverse traversal, and jump traversal, making it convenient to choose the appropriate traversal method in different situations. For example, you can use a reverse iterator to traverse forward from the end of the container, or use a skip iterator to skip some elements according to certain rules.
4. Algorithmizable processing: STL provides a wealth of algorithms, such as sorting, searching, copying, deleting, etc. These algorithms can directly operate iterators without caring about the implementation of specific containers. Using iterators as parameters of the algorithm makes the code more reusable, and the same set of algorithms can be applied to different types of containers.
5. Composable operations: Iterator operations can be combined, and chain calls can be made between different operations to form a more complex sequence of operations. This composability makes the code more flexible, and iterator operations can be freely combined and customized according to needs to achieve more diverse functions.
In short, iterators in STL provide an abstract and unified way to access container elements, allowing us to handle various types of containers in a common way. Doing so can improve the reusability, readability and maintainability of the code, while also making full use of the rich algorithms provided by STL, simplifying the development process and improving efficiency.
Another explanation: [Detailed explanation of iterator (iterator) taken from C++ STL_c++ iterator-CSDN blog]
(1) STL provides different implementation principles for each container. Without iterators, we need to remember the access methods of objects in each container. Obviously, this will become very troublesome.
(2) Each container implements an iterator for accessing objects in the container. Although the implementation of the iterator in each container is different, the operation method for users is Consistent, that is to say, the access method to all containers is unified through iterators.
(3) The use of iterators can improve programming efficiency.
3. Use of iterators
3.1 Basic usage
(1) First, define an iterator type variable (here, take vector container as an example).
The definition method is as follows: container class name::iterator iterator name;
If you want to define the iterator of the vector container: vector
(2) Next, we need to use iterators to access container data
First, you need to understand several member functions, as shown in the following table.
| < strong>Member functions | Function |
| begin() | Returns the forward direction pointing to the first element in the container Iterator; if it is a const type container, the function returns a constant forward selector. |
| end() | Returns a forward iterator pointing to a position after the last element of the container. If it is an onst type container, this function returns a constant forward iterator. This function is usually used in conjunction with begin(). |
| rbegin() | Returns a reverse iterator pointing to the last element. If it is a const type container, this function returns a constant reverse iterator. |
| rend() | Returns a reverse iterator pointing to the position before the first element. If it is a const type container, the function returns a constant reverse iterator. This function is usually used in conjunction with begin(). |
Please note that the end() and rend() functions here do not point to the last element of the container, but to the subsequent position (See picture)
(3) Example
#include<iostream>
#include<vector>
int main() {
std::vector <int> vec; // define vector object vec
vec.push_back(2);
vec.push_back(3);
vec.push_back(5);
vec.push_back(9);
// At this point, the vector vec contains four elements, namely 2, 3, 5, and 9
std::vector<int>::iterator iter; // Define iterator type variable iter
iter = vec.begin(); // The variable is assigned an iterator pointing to the first element
std::cout << *iter << std::endl;
iter + + ; // You can use the auto-increment operation to make iter point to the next element
std::cout << *iter << std::endl;
iter = vec.begin() + 2; // Let iter point to the third position in the container
std::cout << *iter << std::endl;
}
Output results:
2 3 5
Note: The vector container iterator is a random access iterator and can move multiple positions at one time, such as iter=v1.begin() + 2;
You can also use iter=iter + 2;
3.2 Container data traversal
3.2.1 Common methods (forward order traversal)
for (auto it = container.begin(); it != container.end(); + + it) {
// process element *it
}
3.2.2 Common methods (reverse order traversal)
for (auto it = container.rbegin(); it != container.rend(); + + it) {
// process element *it
}
Among them, auto is a keyword in C++11, which can automatically deduce the iterator type. In the loop, first use the begin() function to obtain the iterator at the starting position of the container, and then use the increment operator to advance one position each time until the iterator is equal to end() The iterator returned by the function ends the loop.
3.2.3 Attention issues
It should be noted that when dealing with empty containers or containers with only one element, the iterators returned by the begin() and end() functions are the same, so in the loop The != operator cannot be used for comparison. Instead, the < or > operator should be used to determine whether it is out of bounds.
When a container is empty or has only one element, the iterators returned by the `begin()` and `end()` functions are at the same position, so comparison using the `!=` operator may give incorrect results.
For an empty container, both the `begin()` and `end()` functions return iterators pointing to the end, since there are no elements to traverse. In this case, you should directly determine whether the iterator is equal to the last iterator, as follows:
std::vector<int> v;
if (v.begin() == v.end()) {
// Handle the case of empty containers
}
For a container with only one element, although the `begin()` and `end()` functions will return different iterators, they point to the same position, which is the only element in the container. In this case, the comparison should be done using the `<` or `>` operators, as shown below:
std::vector<int> v{1};
for (auto it = v.begin(); it < v.end(); + + it) { // Note the use of < here
std::cout << *it << std::endl;
}
Similarly, you can also use the `>=` or `<=` operator in a loop to determine whether it is out of bounds, but a better approach is to use the iterator equality function `std::equal()`, ` provided by the standard library std::lexicographical_compare()`, etc. These functions automatically handle the case of empty containers and containers with only one element, and provide better readability and code robustness.
3.2.4 Traversal application example
#include<iostream>
#include<vector>
int main() {
std::vector <int> vec; // define vector object vec
vec.push_back(2);
vec.push_back(3);
vec.push_back(5);
vec.push_back(9);
// At this point, the vector vec contains four elements, namely 2, 3, 5, and 9
// Traverse all elements in vector vec
for (auto iter = vec.begin(); iter != vec.end(); iter + + ) {
std::cout << *iter << " ";
}
std::cout << std::endl;
}
Note: As mentioned above, the end() function points to the next position of the last element of the container, so when the iterator points to the last position, the traversal ends and all container elements can be accessed.
Output result:
2 3 5 9
4. Functions of iterators in different containers
vector random access
deque random access
list bidirectional
set / multiset bidirectional
map / multimap bidirectional
stack does not support iterators
queue does not support iterators
priority_queue does not support iterators
References
Detailed explanation of iterator in C++ STL_c++ iterator-CSDN blog
C++ iterator (iterator)_c++ iterator_NiUoW's blog-CSDN blog
Several situations about iterator failure-CSDN Blog (worth reading)