23 迭代器
23.1.1 为什么要有泛型编程
STL是泛型编程的一个例子，面向对象编程专注于数据方面的编程，而泛型编程专注于算法。 泛型编程的目标就是 代码独立于数据类型。 就如template使得算法独立于数据类型的存储，迭代器使得算法独立于不同的容器类型。 比如：
23.1.2 数组的寻找元素函数
double * find_ar(double * ar, int n, const double & val)
{
for (int i = 0; i < n; i++)
if (ar[i] == val)
return &ar[i];
return 0; // or, in C++11, return nullptr;
}
23.1.3 链表的寻找元素函数
struct Node
{
double item;
Node* p_next;
};
Node* find_ll(Node* head, const double& val)
{
Node* start;
for (start = head; start != 0; start = start->p_next)
if (start->item == val)
return start;
return 0;
}
数组和链表的寻找元素函数在算法上是一样的，但是在遍历时指针的处理不一样，泛型的目的就是使得函数不仅独立于存储的数据类型，还要独立于容器的数据结构。
23.2 迭代器
所有迭代器应该具备以下属性： (1)支持解引用 * p (2)重载赋值操作符 = (3)重载 == != 操作符 (4)重载前向和后向 ++操作符
23.3 容器中的迭代器
(1)每个容器都定义了一个适合自己的迭代器，迭代器会重载 * ++ (...) (2)每个容器都有结尾的标志---指向了最后一个元素地址的后一个地址 (3)每个容器都要begin()和end()方法，返回第一个元素的迭代器和结尾的标志
vector::iterator pr;
for (pr = scores.begin(); pr != scores.end(); pr++)
cout << *pr << endl;
上述代码中，pr是vector类型的一个迭代器，可以用其访问所有的元素 还可以使用auto关键字简化上述代码：
for (auto pr = scores.begin(); pr != scores.end(); pr++)
cout << *pr << endl;
注意事项：一般还是不要直接使用iterator类型，建议直接使用STL中的相关函数比如：for_each()。如果迭代器相同，则其指向的内容也相同。
23.4 迭代器的分类
23.4.1 输入迭代器 InputIterator
定义：就是程序可以读取到容器中的数据，但是不修改容器中的数据 特征： 允许获取容器中的所有数据 重载了++(前向and后向) 它只能单向访问数据，只能++，不能--(返回) 不能保证使用输入迭代器第二次遍历容器时，会以相同的顺序遍历值 在输入迭代器递增后，也不能保证其先前的值仍然可以被解引用
23.4.2 输出迭代器 Output Iterators
定义：迭代器可以从程序给容器传递信息(只可写) 特征： 重载了++(前向and后向) 它只能单向访问数据，只能++，不能--(返回) 不能保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值 在输出迭代器递增后，也不能保证其先前的值仍然可以被解引用
23.4.3 正向迭代器：Forward Iterators
定义：迭代器可读可写 特征： 重载了++(前向and后向) 允许多向访问数据，只能++，不能--(返回) 保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值 在输出迭代器递增后，能保证其先前的值仍然可以被解引用(前提是存储了先前的值) 可指定可读可写和可读
int * pirw; // read-write iterator
const int * pir; // read-only iterator
23.4.4 双向迭代器 Bidirectional Iterators
定义：迭代器可读可写，允许从两个方向访问容器 特征： 重载了++，--(前向and后向) 允许多向访问数据 保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值 在输出迭代器递增后，能保证其先前的值仍然可以被解引用(前提是存储了先前的值) 可指定可读可写或可读
int * pirw; // read-write iterator
const int * pir; // read-only iterator
23.4.5 随机访问迭代器 Random Access Iterators
定义：迭代器可读可写，允许从两个方向访问容器，并且允许跳跃着访问 特征： 重载了++，--(前向and后向)，+,-还有关系运算符 允许多向访问数据 保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值 在输出迭代器递增后，能保证其先前的值仍然可以被解引用(前提是存储了先前的值) 可指定可读可写或可读
int * pirw; // read-write iterator
const int * pir; // read-only iterator
比双向迭代器增加的内容：a和b是迭代器,n是整型，r是随机访问迭代器
| a + n | Points to the nth element after the one a points to |
|---|
| n + a | Same as a + n |
| a - n | Points to the nth element before the one a points to |
| r += n | Equivalent to r = r + n |
| r -= n | Equivalent to r = r - n |
| a[n] | Equivalent to *(a + n) |
| b - a | The value of n such that b == a + n |
| a < b | True if b - a > 0 |
| a > b | True if b < a |
| a >= b | True if !(a < b) |
| a <= b | True if !(a > b) |
23.5 各迭代器的功能总结
| Iterator Capability | Input | Output | Forward | Bidirectional | Random Access |
|---|
| Dereferencing read | Y | N | Y | Y | Y |
| Dereferencing write | N | Y | Y | Y | Y |
| Fixed and repeatable order | N | N | Y | Y | Y |
| ++i i++ | Y | Y | Y | Y | Y |
| --i i-- | N | N | N | Y | Y |
| i[n] | N | N | N | N | Y |
| i + n | N | N | N | N | Y |
| i - n | N | N | N | N | Y |
| i += n | N | N | N | N | Y |
| i -=n | N | N | N | N | Y |
23.6 迭代器的优先级
输入迭代器 and 输出迭代器 < 正向迭代器 < 双向迭代器 < 随机访问迭代器
23.7 使用迭代器的原则
功能越少的迭代器，使用的范围越多。
注意事项：迭代器不是C++定义好的数据类型，而是一种理论，是一种需求。
这种理论需求可以有一种继承的关系，但是不能真的将C++的继承关系运用到各类迭代器，这种继承称为改进(refinement).
一个理论的特定实现称为模型(model),比如一个普通的int指针是随机访问迭代器概念的模型。
23.8 把指针看作迭代器
sort(start,end)---将start和end范围内的数据升序排序。 迭代器是指针的泛化，指针满足迭代器的所有需求。迭代器是STL算法的接口，指针也是迭代器，因此STL算法可以使用指针去操作那些基于指针的非STM容器。
23.9 copy(), ostream_iterator, and istream_iterator
copy(start,end,loc)---将strat和end范围内的数据复制到loc,start和end是迭代器。copy不会自动调整容器的大小。 可以将一个容器的数据复制到另一个容器，是将已知数据重写到指定目的地，要求目的地容器有足够的空间容纳数据。 start和end必须是输入迭代器(或更好)，loc必须是输出迭代器(或更好)
ostream_iterator是一个输出迭代器，也是一个适配器(将其他接口转换为STL接口的类或函数) 它在iterator头文件中。 声明格式： 1.ostream_iterator out_iter(cout, " "); 第一个模板参数(此处为int)指示了传递给输出流数据类型，第二个模板参数(此处为char)指示输出流使用的字符类型; 第一个构造参数(此处为cout)标识正在使用的输出流，最后一个字符串参数是在发送到输出流的每个元素后显示的分隔符。 2.匿名ostream_iterator copy(dice.begin(), dice.end(), ostream_iterator(cout, " ") );
istream_iterator是一个输入迭代器，也是一个适配器。 它在iterator头文件中。
声明格式： copy(istream_iterator(cin),istream_iterator(), dice.begin()); ---表示从输入流中读取，直到文件结束、类型不匹配或其他输入失败。 第一个模板参数(此处为int)指示了读取的数据类型，第二个模板参数(此处为char)指示输入流使用的字符类型; 使用cin的构造函数表示由cin管理输入流，省略构造参数表示输入失败。
23.10 reverse_iterator back_insert_iterator front_insert_iterator and insert_iterator
递增反向迭代器会导致其递减。 vector类的rbegin()成员函数可以返回一个指向past-the-end的反向迭代器(值和end()返回值一样)，rend()成员函数能返回一个指向第一个元素的反向迭代器(值和begin()返回值一样)。 由于past-the-end是指向最后一个元素的后一个元素，因此不可以直接解引用*;同样，如果 rend()确实是第一个元素的位置，则copy()会提前停止一个位置，因为范围的末尾不在范围中。 反向指针通过先递减，然后取消引用来解决这两个问题。也就是说,如果rp指向位置6，则 * rp是位置5的值，依此类推。 由于copy()不会自动调整容器的大小，但是使用插入过程可以调整容器大小。 插入添加新元素而不覆盖已有的元素，它使用动态内存分配保证适配新内容。 back_insert_iterator---在容器末尾添加元素，前提是相关的容器类型允许在容器末尾快速插入(常量时间算法)元素，vector满足要求 front_insert_iterator---在容器开头添加元素，前提是相关的容器类型允许在容器开头快速插入(常量时间算法)元素，vector不满足要求，单queue满足要求 insert_iterator---在指定位置前添加元素，没有快速插入的前提，可以设置参数在开头或末尾插入，但是速度没有back_insert_iterator和front_insert_iterator快
格式：
back_insert_iterator > back_iter(dice);
front_insert_iterator > back_iter(dice);
insert_iterator > insert_iter(dice, dice.begin() );
---将容器类型作为模板参数，将容器对象作为构造函数参数；使用容器类型的原因是要充分利用容器方法。 ---insert_iterator多一个构造函数参数是为了指定插入的位置。 总结：这些迭代器使得一个算法更泛化了，可以将一个容器的内容复制给另一个容器，也可以将容器中给的内容复制给输出流，也可以将输入流复制给容器。
23.11 举例
代码：
/*
Project name : _22Iterator
Last modified Date: 2022年4月6日16点34分
Last Version: V1.0
Descriptions: 泛型编程---各种迭代器
*/
/*
泛型编程：
1.为什么要有泛型编程
STL是泛型编程的一个例子，面向对象编程专注于数据方面的编程，而泛型编程专注于算法。
泛型编程的目标就是 代码独立于数据类型。
就如template使得算法独立于数据类型的存储，迭代器使得算法独立于不同的容器类型。
比如：
数组的寻找元素函数：
double * find_ar(double * ar, int n, const double & val)
{
for (int i = 0; i < n; i++)
if (ar[i] == val)
return &ar[i];
return 0; // or, in C++11, return nullptr;
}
和链表的寻找元素函数：
struct Node
{
double item;
Node* p_next;
};
Node* find_ll(Node* head, const double& val)
{
Node* start;
for (start = head; start != 0; start = start->p_next)
if (start->item == val)
return start;
return 0;
}
数组和链表的寻找元素函数在算法上是一样的，但是在遍历时指针的处理不一样，泛型的目的就是使得函数不仅独立于存储的数据类型，还要独立于容器的数据结构。
2.迭代器
所有迭代器应该具备以下属性：
(1)支持解引用 *p
(2)重载赋值操作符 =
(3)重载 == != 操作符
(4)重载前向和后向 ++操作符
3.容器中的迭代器
(1)每个容器都定义了一个适合自己的迭代器，迭代器会重载* ++ (...)
(2)每个容器都有结尾的标志---指向了最后一个元素地址的后一个地址
(3)每个容器都要begin()和end()方法，返回第一个元素的迭代器和结尾的标志
vector::iterator pr;
for (pr = scores.begin(); pr != scores.end(); pr++)
cout << *pr << endl;
上述代码中，pr是vector类型的一个迭代器，可以用其访问所有的元素
还可以使用auto关键字简化上述代码：
for (auto pr = scores.begin(); pr != scores.end(); pr++)
cout << *pr << endl;
注意事项：一般还是不要直接使用iterator类型，建议直接使用STL中的相关函数比如：for_each()
如果迭代器相同，则其指向的内容也相同。
4.迭代器的分类
(1)输入迭代器 InputIterator
定义：就是程序可以读取到容器中的数据，但是不修改容器中的数据
特征：
允许获取容器中的所有数据
重载了++(前向and后向)
它只能单向访问数据，只能++，不能--(返回)
不能保证使用输入迭代器第二次遍历容器时，会以相同的顺序遍历值
在输入迭代器递增后，也不能保证其先前的值仍然可以被解引用
(2)输出迭代器 Output Iterators
定义：迭代器可以从程序给容器传递信息(只可写)
特征：
重载了++(前向and后向)
它只能单向访问数据，只能++，不能--(返回)
不能保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值
在输出迭代器递增后，也不能保证其先前的值仍然可以被解引用
(3)正向迭代器：Forward Iterators
定义：迭代器可读可写
特征：
重载了++(前向and后向)
允许多向访问数据，只能++，不能--(返回)
保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值
在输出迭代器递增后，能保证其先前的值仍然可以被解引用(前提是存储了先前的值)
可指定可读可写和可读
int * pirw; // read-write iterator
const int * pir; // read-only iterator
(4)双向迭代器 Bidirectional Iterators
定义：迭代器可读可写，允许从两个方向访问容器
特征：
重载了++，--(前向and后向)
允许多向访问数据
保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值
在输出迭代器递增后，能保证其先前的值仍然可以被解引用(前提是存储了先前的值)
可指定可读可写或可读
int * pirw; // read-write iterator
const int * pir; // read-only iterator
(5)随机访问迭代器 Random Access Iterators
定义：迭代器可读可写，允许从两个方向访问容器，并且允许跳跃着访问
特征：
重载了++，--(前向and后向)，+,-还有关系运算符
允许多向访问数据
保证使用输出迭代器第二次遍历容器时，会以相同的顺序遍历值
在输出迭代器递增后，能保证其先前的值仍然可以被解引用(前提是存储了先前的值)
可指定可读可写或可读
int * pirw; // read-write iterator
const int * pir; // read-only iterator
比双向迭代器增加的内容：a和b是迭代器,n是整型，r是随机访问迭代器
a + n Points to the nth element after the one a points to
n + a Same as a + n
a - n Points to the nth element before the one a points to
r += n Equivalent to r = r + n
r -= n Equivalent to r = r - n
a[n] Equivalent to *(a + n)
b - a The value of n such that b == a + n
a < b True if b - a > 0
a > b True if b < a
a >= b True if !(a < b)
a <= b True if !(a > b)
各迭代器的功能总结：
Iterator Capability Input Output Forward Bidirectional Random Access
Dereferencing read Yes No Yes Yes Yes
Dereferencing write No Yes Yes Yes Yes
Fixed and repeatable order No No Yes Yes Yes
++i i++ Yes Yes Yes Yes Yes
--i i-- No No No Yes Yes
i[n] No No No No Yes
i + n No No No No Yes
i - n No No No No Yes
i += n No No No No Yes
i -=n No No No No Yes
5.迭代器的优先级
输入迭代器 and 输出迭代器 < 正向迭代器 < 双向迭代器 < 随机访问迭代器
6.使用迭代器的原则：功能越少的迭代器，使用的范围越多。
注意事项：迭代器不是C++定义好的数据类型，而是一种理论，是一种需求。
这种理论需求可以有一种继承的关系，但是不能真的将C++的继承关系运用到各类迭代器，这种继承称为改进(refinement).
一个理论的特定实现称为模型(model),比如一个普通的int指针是随机访问迭代器概念的模型。
*/
// 指针可以满足迭代器的要求：
typedef double* iterator1;
iterator1 find_ar(iterator1 begin, iterator1 end, const double& val)
{
iterator1 ar;
for (ar = begin; ar != end; ar++)
if (*ar == val)
return ar;
return end; // indicates val not found
}
//也可以定义迭代器类，为该类重载各类操作符
//注意事项：iterator& operator++();和iterator operator++(int):是C++指定的++的前向和后向操作符重载
struct Node
{
double item;
Node* p_next;
};
class iterator
{
Node* pt;
public:
iterator() : pt(0) {}
iterator(Node* pn) : pt(pn) {}
double operator*() { return pt->item; }
iterator& operator++() // for ++it 重载前向++操作符
{
pt = pt->p_next;
return *this;
}
iterator operator++(int) // for it++ 重载后向++操作符
{
iterator tmp = *this;
pt = pt->p_next;
return tmp;
}
bool operator!=(int)
{
return true;
}
// ... operator==(), operator!=(), etc.
};
iterator find_ll(iterator head, const double& val)
{
iterator start;
for (start = head; start != 0; ++start)
if (*start == val)
return start;
return 0;
}
/*
现在的问题是如何使得函数 find_ar()和find_ll() 决定是否到达末尾数据的方式一致
find_ar()使用了读取 one-past-the-end，find_ll()使用了空值
---可以在列表末尾添加一个额外的元素即可解决
这样的话find_ar()和find_ll()就相等啦
*/
/*
7 把指针看作迭代器
sort(start,end)---将start和end范围内的数据升序排序。
迭代器是指针的泛化，指针满足迭代器的所有需求。迭代器是STL算法的接口，指针也是迭代器，因此STL算法可以使用指针去操作那些基于指针的非STM容器。
8 copy(), ostream_iterator, and istream_iterator
copy(start,end,loc)---将strat和end范围内的数据复制到loc,start和end是迭代器。copy不会自动调整容器的大小。
可以将一个容器的数据复制到另一个容器，是将已知数据重写到指定目的地，要求目的地容器有足够的空间容纳数据。
start和end必须是输入迭代器(或更好)，loc必须是输出迭代器(或更好)
ostream_iterator是一个输出迭代器，也是一个适配器(将其他接口转换为STL接口的类或函数)
它在iterator头文件中。
声明格式：
1.ostream_iterator out_iter(cout, " ");
第一个模板参数(此处为int)指示了传递给输出流数据类型，第二个模板参数(此处为char)指示输出流使用的字符类型;
第一个构造参数(此处为cout)标识正在使用的输出流，最后一个字符串参数是在发送到输出流的每个元素后显示的分隔符。
2.匿名ostream_iterator
copy(dice.begin(), dice.end(), ostream_iterator(cout, " ") );
istream_iterator是一个输入迭代器，也是一个适配器。
它在iterator头文件中。
声明格式：
copy(istream_iterator(cin),istream_iterator(), dice.begin());
---表示从输入流中读取，直到文件结束、类型不匹配或其他输入失败。
第一个模板参数(此处为int)指示了读取的数据类型，第二个模板参数(此处为char)指示输入流使用的字符类型;
使用cin的构造函数表示由cin管理输入流，省略构造参数表示输入失败。
9 reverse_iterator back_insert_iterator front_insert_iterator and insert_iterator
递增反向迭代器会导致其递减
vector类的rbegin()成员函数可以返回一个指向past-the-end的反向迭代器(值和end()返回值一样)，rend()成员函数能返回一个指向第一个元素的反向迭代器(值和begin()返回值一样)。
由于past-the-end是指向最后一个元素的后一个元素，因此不可以直接解引用*;同样，如果 rend()确实是第一个元素的位置，则copy()会提前停止一个位置，因为范围的末尾不在范围中。
反向指针通过先递减，然后取消引用来解决这两个问题。也就是说,如果rp指向位置6，则*rp是位置5的值，依此类推。
由于copy()不会自动调整容器的大小，但是使用插入过程可以调整容器大小。
插入添加新元素而不覆盖已有的元素，它使用动态内存分配保证适配新内容。
back_insert_iterator---在容器末尾添加元素，前提是相关的容器类型允许在容器末尾快速插入(常量时间算法)元素，vector满足要求
front_insert_iterator---在容器开头添加元素，前提是相关的容器类型允许在容器开头快速插入(常量时间算法)元素，vector不满足要求，单queue满足要求
insert_iterator---在指定位置前添加元素，没有快速插入的前提，可以设置参数在开头或末尾插入，但是速度没有back_insert_iterator和front_insert_iterator快
格式：back_insert_iterator > back_iter(dice);
front_insert_iterator > back_iter(dice);
insert_iterator > insert_iter(dice, dice.begin() );
---将容器类型作为模板参数，将容器对象作为构造函数参数；使用容器类型的原因是要充分利用容器方法。
---insert_iterator多一个构造函数参数是为了指定插入的位置。
总结：这些迭代器使得一个算法更泛化了，可以将一个容器的内容复制给另一个容器，也可以将容器中给的内容复制给输出流，也可以将输入流复制给容器。
*/
#include
#include
#include
#include
#include
void output(const std::string& s) { std::cout << s << " "; }
int main()
{
using namespace std;
const int SIZE = 100;
double Receipts[SIZE] = {9.9,9.99,11,999,888};
sort(Receipts, Receipts + SIZE);//此处就是将指针当作迭代器在用，是7的举例
cout << "把指针看作迭代器******************************************************" << endl;
cout << "对Receipts的排序******************************************************" << endl;
for (int i = 0; i < SIZE; i++)
cout << Receipts[i] << " ";
cout << endl;
cout << "copy() and ostream_iterator******************************************************" << endl;
int casts[10] = { 6, 7, 2, 9 ,4 , 11, 8, 7, 10, 5 };
vector dice(10);
// copy from array to vector
copy(casts, casts + 10, dice.begin());
cout << "Let the dice be cast!\n";
// create an ostream iterator
ostream_iterator out_iter(cout, "\n");
// copy from vector to output
*out_iter++ = 15; // works like cout << 15 << "\n";
ostream_iterator out_iter1(cout, " ");
copy(dice.begin(), dice.end(), out_iter1);
cout << endl;
cout << "istream_iterator******************************************************" << endl;
cout << "请输入数字（后输入模拟EOF）：" << endl;
//cin.get();
copy(istream_iterator(cin), istream_iterator(), dice.begin());
copy(dice.begin(), dice.end(), out_iter1);
cout << endl;
cout << "reverse_iterator******************************************************" << endl;
cout << "Implicit use of reverse iterator.\n";
copy(dice.rbegin(), dice.rend(), out_iter1);
cout << endl;
cout << "Explicit use of reverse iterator.\n";
vector::reverse_iterator ri;
for (ri = dice.rbegin(); ri != dice.rend(); ++ri)
cout << *ri << ' ';
cout << endl;
cout << "back_insert_iterator front_insert_iterator and insert_iterator*************" << endl;
string s1[4] = { "fine", "fish", "fashion", "fate" };
string s2[2] = { "busy", "bats" };
string s3[2] = { "silly", "singers" };
vector words(4);
copy(s1, s1 + 4, words.begin());
for_each(words.begin(), words.end(), output);
cout << endl;
// construct anonymous back_insert_iterator object
copy(s2, s2 + 2, back_insert_iterator >(words));
for_each(words.begin(), words.end(), output);
cout << endl;
// construct anonymous insert_iterator object
copy(s3, s3 + 2, insert_iterator >(words,words.begin()));
for_each(words.begin(), words.end(), output);
cout << endl;
return 0;
}
运行结果：
把指针看作迭代器******************************************************
对Receipts的排序******************************************************
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9.9 9.99 11 888 999
copy() and ostream_iterator******************************************************
Let the dice be cast!
15
6 7 2 9 4 11 8 7 10 5
istream_iterator******************************************************
请输入数字（后输入模拟EOF）：
1 2 3 4 5 ^Z
1 2 3 4 5 11 8 7 10 5
reverse_iterator******************************************************
Implicit use of reverse iterator.
5 10 7 8 11 5 4 3 2 1
Explicit use of reverse iterator.
5 10 7 8 11 5 4 3 2 1
back_insert_iterator front_insert_iterator and insert_iterator*************
fine fish fashion fate
fine fish fashion fate busy bats
silly singers fine fish fashion fate busy bats
D:\Prj\_C++Self\_1已统计代码\_22Iterator\Debug\_22Iterator.exe (进程 22020)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .