In addition to regular iterators, C++ also provides three additional types of iterators, which are all defined in the
- Insert iterator: used to bind to the container to write data to the container
- iostream iterator (iostream iterator): bound to IO stream
- Reverse iterator: implements reverse order traversal
1. Insert iterator
The adapter pattern adopted by the insertion iterator receives a container as a constructor parameter, and the interface definition conforms to the iterator standard, thereby enabling the use of iterators to dynamically insert data. There are three types of insertion iterators depending on the insertion location:
- back_inserter, use push_back to write to the container
- front_inserter, use push_front to write to the container
- inserter, use insert to insert at the specified position. The constructor requires an additional input parameter for the specified position.
1.back_inserter
back_inserter receives a container object and uses the container’s push_back to write data into the container.
void test_back_inserter() {
vector<string> v1;
v1.push_back("1");
v1.push_back("2");
v1.push_back("3");
vector<string> v2;
std::copy(v1.begin(), v1.end(), std::back_inserter(v2));
cout << "v2: " << to_str(v2,",") << std::endl; // print: v2: 1,2,3
std::copy(v1.rbegin(), v1.rend(), std::back_inserter(v2));
cout << "v2: " << to_str(v2, ",") << std::endl; // print: v2: 1,2,3,3,2,1
}
2.front_inserter
Unlike back_inserter, front_inserter implements insertion by using push_front. Using the code from the previous example, vector
void test_front_inserter() {
vector<string> v1;
v1.push_back("1");
v1.push_back("2");
v1.push_back("3");
list<string> v2;
std::copy(v1.begin(), v1.end(), std::front_inserter(v2));
cout << "v2: " << to_str(v2, ",") << std::endl; // print v2: 3,2,1,
std::copy(v1.rbegin(), v1.rend(), std::front_inserter(v2));
cout << "v2: " << to_str(v2, ",") << std::endl; // v2: 1,2,3,3,2,1,
}
3.inserter
Receives a container, and a positional parameter to specify the position to insert. What’s special is that after inserting an element, the next insertion position is next to the last insertion position.
void test_inserter() {
vector<string> v1;
v1.push_back("a");
v1.push_back("b");
v1.push_back("c");
v1.push_back("d");
vector<string>::iterator it = std::find(v1.begin(), v1.end(), string("c")); // Get the iterator pointing to "c"
vector<string> v2;
v2.push_back("1");
v2.push_back("2");
v2.push_back("3");
std::copy(v2.begin(), v2.end(), inserter(v1, it)); // Insert the content of v2 at the position of "c", move "c" backward, and the content of v2 is as before iterator output
cout << "v2: " << to_str(v2,",") << std::endl; // print v2: 1,2,3
cout << "v1: " << to_str(v1,",") << std::endl; // print v1: a,b,1,2,3,c,d
}
front_inserter will cause the content to be written to be inserted into the front of the container in reverse order. Using inserter + the starting position of the iterator, we can write the elements to the actual position of the container while retaining their original order. If you want to use inserter to simulate the effect of front_inserter, you need to select the insertion position as begin and iterate the elements to be inserted in reverse order.
void test_inserter_as_front_inserter() {
list<string> v1;
v1.push_back("a");
v1.push_back("b");
v1.push_back("c");
v1.push_back("d");
vector<string> v2;
v2.push_back("1");
v2.push_back("2");
v2.push_back("3");
std::copy(v2.rbegin(), v2.rend(), inserter(v1, v1.begin())); // print: v1: 3,2,1,a,b,c,d,
//std::copy(v2.begin(), v2.end(), std::front_inserter(v1)); // print: v1: 3,2,1,a,b,c,d,
cout << "v2: " << to_str(v2, ",") << std::endl;
cout << "v1: " << to_str(v1, ",") << std::endl;
}
2. iostream iterator
The standard library provides istream_iterator for reading input streams and ostream_iterator for writing output streams. Adapt iostream to an iterator to support some functions of generic algorithms.
|
Constructor |
illustrate |
|
istream_iterator |
Create an istream_iterator that reads objects of type T from the input stream stream |
|
istream_iterator |
istream_iterator pointing beyond the end |
|
ostream_iterator |
ostream_iterator that writes T objects to stream |
|
ostream_iterator |
Write the T object to the ostream_iterator of the stream, and use delim as the delimiter for multiple outputs. |
Stream iteration only provides the most basic functions, assignment, increment, and dereference. istream_iterator additionally provides an equality (==) comparison capability.
1.istream_iterator
istream_iterator prompts that the stream has been iterated through the return value of the default constructor. Let’s take a simple example and use istream_iterator to read strings from istringstream and save them into vectors.
#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
string to_str(const vector<string> & amp; ivec, const char* deli) {
std::ostringstream os;
std::copy(ivec.begin(), ivec.end() - 1, std::ostream_iterator<string>(os, deli));
os << ivec.back();
return os.str();
}
void test_istream_iterator() {
std::istringstream iss("the quick red fox jumps over the slow red turtle");
std::istream_iterator<string> it(iss);
std::istream_iterator<string> eof;
vector<string> v1;
std::copy(it, eof, std::back_inserter(v1)); // Limit the end position of the iterator through eof
cout << "v1: " << to_str(v1, ",") << endl;
}
In this example, the range specified by it and eof is used to insert into the vector. In fact, a more efficient way to write it is to pass it directly to the constructor of the vector.
void test_vector() {
std::istringstream iss("the quick red fox jumps over the slow red turtle");
string s1;
std::istream_iterator<string> it(iss);
std::istream_iterator<string> eof;
vector<string> v1(it, eof);
cout << "v1: " << to_str(v1, ",") << endl;
}
2. ostream_iterator
ostream_iterator outputs the content assigned to the iterator to the bound output stream. We use cout to initialize ostream_iterator, and each output is followed by a delimiter “\
“.
void test_ostream_iterator() {
std::istringstream iss("the quick red fox jumps over the slow red turtle");
std::istream_iterator<string> it(iss);
std::istream_iterator<string> eof;
std::ostream_iterator<string> it_out(cout, "\
");
while (it != eof) {
*it_out + + = *it + + ;
}
}
3. Reverse iterator
Similar to the begin and end functions provided by containers, many containers also provide rbegin and rend functions. rbegin points to the last element of the container before rbegin, and rend points to the previous position of the first element of the container.
Let’s take a look at a simple example to output the data in the vector in reverse order through a reverse iterator.
void test_reverse_iterator() {
std::vector<int> v1;
for (int i = 0; i < 10; i + + ) {
v1.push_back(i);
}
cout << "v1: " << to_str(v1, ",") << endl; // print v1: 0,1,2,3,4,5,6,7,8,9
vector<int>::reverse_iterator rit;
for (rit = v1.rbegin(); rit != v1.rend(); rit + + ) {
cout << *rit << endl; // print 9 8 7 ...
}
}
We have learned the sort function before, which is used to arrange elements in dictionary order. If we want to arrange them in reverse order, one way is to provide a custom predicate function, and the other is to pass in a reverse iterator.
bool compare(string i1, string i2) {
return i2 < i1;
}
void test_reverse_sort() {
vector<string> v1;
v1.push_back("1");
v1.push_back("3");
v1.push_back("2");
//std::sort(v1.begin(), v1.end()); // print: v1: 1,2,3
std::sort(v1.rbegin(), v1.rend()); // print: v1: 3,2,1
//std::sort(v1.begin(), v1.end(), compare); // print: v1: 3,2,1
cout << "v1: " << to_str(v1,",") << endl;
}
The containers provided by the standard library all support forward and reverse iteration, but the iostream iterator does not support reverse iteration.
1. Forward and reverse iterator conversion
When we use a reverse iterator, the iterator outputs the elements in reverse. Let us give an example to illustrate this problem
void test_reverse() {
string s1("123,456,789");
string::iterator it = find(s1.begin(), s1.end(), ',');
cout << "Forward sequence, first one, previous content: " << string(s1.begin(), it) << endl; // print 123
string::reverse_iterator rit = find(s1.rbegin(), s1.rend(), ',');
cout << "Reverse order, first one, content after: " << string(s1.rbegin(), rit) << endl; // print 987
cout << "Output in reverse order, the first one, and the content after that in forward order: " << string(rit.base(), s1.end()) << endl; // print 789
}
The first output is used to display the content before the first “,” in the positive sequence. There is no problem with outputting 123. The second output displays the content after the last “,”. It does not display 789 in the original order in s1, but displays 987. The reverse iterator provides a base function for converting the reverse iterator into a forward iterator. In the third output, we convert rit through the base function and output the content at the end position. The displayed content is 789 as we expected.
4. Iterator classification
Different iterators support different operations. For example, ostream_iterator only supports assignment, increment, and dereference, while vector’s iterator also supports decrement, relational, and arithmetic operations. According to the requirements of generic algorithms for iterators, iterators can be divided into 5 categories
|
iterator type |
Supported operations |
|
input iterator |
Read-only; only supports auto-increment operations |
|
output iterator |
Write only; only supports auto-increment operations |
|
forward iterator |
Read and write; only supports auto-increment operations |
|
bidirectional iterator |
Read and write; supports auto-increment and auto-decrement operations |
|
Random access iterator |
Read and write; supports full arithmetic operations |
1. Input iterator
Input iterators can be used to read container elements and need to support at least the following operations
- Equality and inequality (==, !=), comparing two iterators
- Pre- and post-increment operations ( + + ) move the iterator to the next element
- Dereference operation for reading elements
- Arrow operation (->), calling member functions and data of elements
Generic algorithms that support this level include find, accumulate, etc. The istream_iterator of the standard library is a type of input iterator.
2. Output iterator
Used to write elements to the container, at least the following operations need to be supported
- Pre- and post-increment operations ( + + ) point the iteration to the next element
- Dereference operation as left operand
The output iterator is generally used as the third parameter of the generic algorithm and is used as the target position of the output. The standard library ostream_iterator is a type of output iterator.
3. Forward iterator
Forward iterators can only traverse in one direction and support all operations of input iterators and output iterators. At the same time, it supports multiple reading and writing of an element. The standard library replace function requires at least this level of iterators.
4. Bidirectional iterator
Supports all operations of forward iterators, and additionally supports the ability to decrement (–). The standard library reverse function requires at least this level of iterators. The iterators provided by the standard library container at least meet the requirements of bidirectional iterators.
5. Random access iterator
Provides the function of accessing any location within constant time. The function of supporting bidirectional iterators is as follows. The following additional operations are provided:
- Relational operators (<, <=, >, >=), compare the relative positions of two iterators
- Supports arithmetic operations, supports iterators and addition and subtraction operations of integer values n
- Supports the subtraction operation of two iterators to obtain the distance between them
- The subscript operator iter[n] is a synonym for *(iter + n)
Sort in a generic algorithm requires this level of iterators. Iterators of vector, deque, string, and array pointers are all random access iterators. Map, set, and list all provide bidirectional iterators. istream_iterator is the input iterator, and ostream_iterator is the output iterator. 5 types of iterators output iterators, and the remaining 4 types form a set of inheritance structures. In algorithms that require lower-level iterators, higher-level iterators can be passed in. For example, find requires input iterators. We can pass in an input iterator or a forward iterator.