【STL十二】适配器——迭代器适配器
- 一、迭代器
- 1、迭代器分类
- 2、迭代器定义
- 3、迭代器和迭代器适配器
- 二、迭代器适配器、流迭代器
- 1、简介
- 2、迭代器适配器
- 3、流迭代器
- 三、反向迭代器
- 1、简介
- 2、模板类
- 3、demo
- 四、插入迭代器
- 1、简介
- 2、模板类
- 3、demo
- 五、移动迭代器
- 1、简介
- 2、模板类
- 3、demo
- 六、流迭代器
- 1、简介
- 2、模板类
- 3、demo
- 七、流缓冲区迭代器
- 1、简介
- 2、模板类
- 3、demo
一、迭代器
无论是序列容器还是关联容器，它们本质上都是用来存储大量数据的。诸如数据的排序、查找、求和、插入等需要对数据进行遍历的操作方法应该是类似的。而实现此操作，多数情况会选用“迭代器（iterator）”来实现。
它除了要具有对容器进行遍历读写数据的能力之外，还要能对外隐藏容器的内部差异，从而以统一的界面向算法传送数据。
- 迭代器是一个“可遍历STL容器全部或部分元素”的对象.
1、迭代器分类
- 迭代器：输入迭代器、输出迭代器、正向迭代器、双向迭代器或者随机访问迭代器
STL 标准库为每一种标准容器定义了一种迭代器类型，这意味着，不同容器的迭代器也不同，其功能强弱也有所不同。
常用的迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种。本节主要介绍后面的这 3 种迭代器。
-
- 前向迭代器（forward iterator）
假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。
- 前向迭代器（forward iterator）
-
- 双向迭代器（bidirectional iterator）
双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）。
- 双向迭代器（bidirectional iterator）
-
- 随机访问迭代器（random access iterator）
随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
p+=i：使得 p 往后移动 i 个元素。
p-=i：使得 p 往前移动 i 个元素。
p+i：返回 p 后面第 i 个元素的迭代器。
p-i：返回 p 前面第 i 个元素的迭代器。
p[i]：返回 p 后面第 i 个元素的引用。
- 随机访问迭代器（random access iterator）
| 容器 | 对应的迭代器类型 |
|---|---|
| array | 随机访问迭代器 |
| vector | 随机访问迭代器 |
| deque | 随机访问迭代器 |
| list | 双向迭代器 |
| set / multiset | 双向迭代器 |
| map / multimap | 双向迭代器 |
| forward_list | 前向迭代器 |
| unordered_map / unordered_multimap | 前向迭代器 |
| unordered_set / unordered_multiset | 前向迭代器 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
2、迭代器定义
尽管不同容器对应着不同类别的迭代器，但这些迭代器有着较为统一的定义方式，具体分为 4 种，
| 迭代器定义方式 | 具体格式 |
|---|---|
| 正向迭代器 | 容器类名::iterator 迭代器名; |
| 常量正向迭代器 | 容器类名::const_iterator 迭代器名; |
以上每种容器对应的迭代器，我们基本都用过了，就不再重复的说了。
3、迭代器和迭代器适配器
- 从以下截图我们可以看到，输入迭代器、输出迭代器、正向迭代器、双向迭代器或者随机访问迭代器真正实现是在c++20中，
- vector::iterator ite;虽然我们平时这样定义也是返回一个随机访问迭代器。但是每个迭代器从字面区分开来，确是在c++20中。（同理同样方法定义的list、set、map返回的也确实是双向迭代器）
- 输入迭代器、输出迭代器，也是在c++20中实现。
以上这些问题就给初学者带来很多的困扰。
二、迭代器适配器、流迭代器
1、简介
本章将介绍
- 3种迭代器适配器：分别是反向迭代器适配器、插入型迭代器适配器、移动迭代器适配器。
- 2种流迭代器：流迭代器、流缓冲区迭代器、
2、迭代器适配器
| 迭代器定义方式 | 具体格式 |
|---|---|
| 反向迭代器 | 容器类名::reverse_iterator 迭代器名; |
| 插入型迭代器适配器 | insert_iterator |
| 移动迭代器适配器 | move_iterator |
3、流迭代器
| 迭代器定义方式 | 具体格式 |
|---|---|
| 流迭代器 | istream_iterator ostream_iterator |
| 流缓冲区迭代器 | istreambuf_iterator ostreambuf_iterator |
三、反向迭代器
1、简介
-
反向迭代器适配器（reverse_iterator），可简称为反向迭代器或逆向迭代器，常用来对容器进行反向遍历，即从容器中存储的最后一个元素开始，一直遍历到第一个元素。
-
值得一提的是，反向迭代器底层可以选用双向迭代器或者随机访问迭代器作为其基础迭代器。不仅如此，通过对 ++（递增）和 --（递减）运算符进行重载，使得：
- 当反向迭代器执行 ++ 运算时，底层的基础迭代器实则在执行 – 操作，意味着反向迭代器在反向遍历容器；
- 当反向迭代器执行 – 运算时，底层的基础迭代器实则在执行 ++ 操作，意味着反向迭代器在正向遍历容器。
2、模板类
template <class Iterator>class reverse_iterator;
注意，Iterator 模板参数指的是模板类中所用的基础迭代器的类型，只能选择双向迭代器或者随机访问迭代器。
这意味着，如果想使用反向迭代器实现逆序遍历容器，则该容器的迭代器类型必须是双向迭代器或者随机访问迭代器。
3、demo
当需要向容器的任意位置插入元素时，就可以使用 insert_iterator 类型的迭代器。
- 需要说明的是，该类型迭代器的底层实现，需要调用目标容器的 insert() 成员方法。但幸运的是，STL 标准库中所有容器都提供有 insert() 成员方法，因此 insert_iterator 是唯一可用于关联式容器的插入迭代器。
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {//创建并初始化一个 vector 容器std::vector<int> myvector{ 1,2,3,4,5,6,7,8 };//创建并初始化一个反向迭代器std::reverse_iterator<std::vector<int>::iterator> my_reiter(myvector.rbegin());//指向 8cout << *my_reiter << endl;// 8cout << *(my_reiter + 3) << endl;// 5cout << *(++my_reiter) << endl;// 7cout << my_reiter[4] << endl;// 3return 0;
}
输出
8
5
7
3
四、插入迭代器
1、简介
- 插入迭代器适配器（insert_iterator），简称插入迭代器或者插入器，其功能就是向指定容器中插入元素。值得一提的是，根据插入位置的不同，C++ STL 标准库提供了 3 种插入迭代器，。
| 迭代器适配器 | 功能 |
|---|---|
| back_insert_iterator | 在指定容器的尾部插入新元素，但前提必须是提供有 push_back() 成员方法的容器（包括 vector、deque 和 list）。 |
| front_insert_iterator | 在指定容器的头部插入新元素，但前提必须是提供有 push_front() 成员方法的容器（包括 list、deque 和 forward_list）。 |
| insert_iterator | 在容器的指定位置之前插入新元素，前提是该容器必须提供有 insert() 成员方法。 |
接下来我们以insert_iterator为例子讲解下
2、模板类
template< class Container >
class insert_iterator;
3、demo
当需要向容器的任意位置插入元素时，就可以使用 insert_iterator 类型的迭代器。
- 需要说明的是，该类型迭代器的底层实现，需要调用目标容器的 insert() 成员方法。但幸运的是，STL 标准库中所有容器都提供有 insert() 成员方法，因此 insert_iterator 是唯一可用于关联式容器的插入迭代器。
#include <iostream>
#include <iterator>
#include <list>
using namespace std;
int main() {//初始化为 {5,5}std::list<int> foo(2, 5);//定义一个基础迭代器，用于指定要插入新元素的位置std::list<int>::iterator it = ++foo.begin();//创建一个 insert_iterator 迭代器//std::insert_iterator< std::list<int> > insert_it(foo, it);std::insert_iterator< std::list<int> > insert_it = inserter(foo, it);//向 foo 容器中插入元素insert_it = 1;insert_it = 2;insert_it = 3;insert_it = 4;//输出 foo 容器存储的元素for (std::list<int>::iterator it = foo.begin(); it != foo.end(); ++it)std::cout << *it << ' ';return 0;
}
输出
5 1 2 3 4 5
五、移动迭代器
1、简介
它是一个迭代器适配器，其行为与底层迭代器完全相同。
2、模板类
template <class Iterator> class move_iterator;
3、demo
#include <iostream>
#include <iterator>
#include <vector>
#include <string>
#include <algorithm>
int main () {std::vector<std::string> foo (3);std::vector<std::string> bar {"sai","ram","krishna"};typedef std::vector<std::string>::iterator Iter;std::copy ( std::move_iterator<Iter>(bar.begin()),std::move_iterator<Iter>(bar.end()),foo.begin() );bar.clear();std::cout << "foo:";for (std::string& x : foo) std::cout << ' ' << x;std::cout << '\n';return 0;
}
输出
foo: sai ram krishna
六、流迭代器
1、简介
- 它是一个特殊的输入迭代器，可以读取输入流中的连续元素。
2、模板类
template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>class istream_iterator;
3、demo
#include <iostream>
#include <iterator>
int main () {double value1, value2;std::cout << "Please insert values: ";std::istream_iterator<double> eos; std::istream_iterator<double> iit (std::cin); if (iit!=eos) value1=*iit;++iit;if (iit!=eos) value2=*iit;std::cout << value1 << "*" << value2 << "=" << (value1*value2) << '\n';return 0;
}
输出
Please insert values: 11 11 2
11*11=121
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
int main () {std::vector<int> myvector;for (int i = 10; i > 1; i--) myvector.push_back(i*10);std::ostream_iterator<int> out_it (std::cout,", ");std::copy ( myvector.begin(), myvector.end(), out_it );return 0;
}
100, 90, 80, 70, 60, 50, 40, 30, 20,
七、流缓冲区迭代器
1、简介
- 它是一个特殊的输入迭代器，它从流缓冲区中读取连续的元素。
2、模板类
template <class charT, class traits = char_traits<charT> >class istreambuf_iterator;
3、demo
#include <vector>
#include <sstream>
#include <iostream>
#include <iterator>
int main() {std::istringstream in("Hello, world");std::vector<char> v( (std::istreambuf_iterator<char>(in)),std::istreambuf_iterator<char>() );std::cout << "v has " << v.size() << " bytes. ";v.push_back('\0');std::cout << "it holds \"" << &v[0] << "\"\n";std::istringstream s("abc");std::istreambuf_iterator<char> i1(s), i2(s);std::cout << "i1 returns " << *i1 << '\n'<< "i2 returns " << *i2 << '\n';++i1;std::cout << "after incrementing i1, but not i2\n"<< "i1 returns " << *i1 << '\n'<< "i2 returns " << *i2 << '\n';++i2;std::cout << "after incrementing i2, but not i1\n"<< "i1 returns " << *i1 << '\n'<< "i2 returns " << *i2 << '\n';
}
输出
v has 12 bytes. it holds “Hello, world”
i1 returns a
i2 returns a
after incrementing i1, but not i2
i1 returns b
i2 returns a
after incrementing i2, but not i1
i1 returns b
i2 returns c
参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container
5、哔哩哔哩——侠姐聊算法——8.2.1 适配器与迭代器
6、WIKI教程_C ++标准库_C++ Library - <iterator>
