简明STL

主要内容

迭代器及其分类、区间、辅助函数

迭代器是提供了访问容器中每个元素的方法，用于对一个对象群集的元素进行遍历。对象群集可能是容器，也可能是容器的一部分。

迭代器为容器提供一组公共接口，能够使程序非常快捷地实现对容器中内容的反复访问，反复访问意味着一次可以访问一个或多个元素。

迭代器是泛化的指针，提供了类似指针的操作（诸如++、*、->运算符）。

迭代器是算法和容器的桥梁

迭代器是算法和容器的桥梁

迭代器是用来访问容器中元素的；算法并不直接操作容器中的数据，而是通过迭代器间接操作。这就使得算法和容器相互独立：增加新的算法，无需影响容器的实现；增加新的容器，原有的算法也能适用。

迭代器的分类

STL定义了5种类型的迭代器，并根据其使用方法命名。每种容器都支持某种类别的迭代器。

常见的迭代器包括输入、输出、前向、双向和随机访问等类别。

分类
  • 输入迭代器主要用于为程序中需要的数据源（容器、数据流）提供输入接口。输入迭代器只能从一个序列中读取数值。
  • 输出迭代器主要用于输出程序中已经得到的数据结果（容器，数据流）。输出迭代器只能向一个序列写入数据。
  • 前向迭代器既可以用来读又可以用来写，并可以在一个方向上遍历。双向迭代器可以同时进行前向和后向元素操作。所有STL容器都提供了双向迭代器功能，这既有利于数据的写入和读出，又有利于提供更加灵活的数据操作。
  • 有的容器提供了随机访问迭代器。随机接人迭代器可以通过跳跃的方式访问容器中的任意数据，使数据的访问非常灵活。随机访问迭代器具有双向迭代器的所有功能，是功能最强大的迭代器类型。

迭代器的区间

STL算法常以迭代器的区间作为输入，传递输入数据。两个迭代器表示一个区间：[p1, p2)。

合法区间的定义：p1经过n次(n > 0)自增(++)操作后满足p1 == p2，也就是说：区间包含p1，但不包含p2。

迭代器的辅助函数

  1. advance(p, n)：对p迭代器执行n次自增操作

  2. distance(first, last)：计算两个迭代器first和last的距离，即对first执行多少次++操作后能够使得first == last

流迭代器

流迭代器是从流中读取的单通迭代器（输入迭代器 或 输出迭代器）。流迭代器只能传送给定类型的数据到流中或者从流中读取给定类型的数据。

和其他迭代器相比，流迭代器不同的是，递增一个流迭代器并不会将迭代器转移指向下一个数据项，而是会从流中读取或者插入一个值。

  • 输入流迭代器 istream_iterator<T>
    • 以输入流（如 cin）为参数构造
    • 可用 *(p++) 获得下一个输入的元素
  • 输出流迭代器 ostream_iterator<T>
    • 构造时需要提供输出流（如 cout）
    • 可用 (*p++) = x 将 x 输出到输出流
  • 二者都属于适配器
    • 适配器是用来为已有对象提供新的接口的对象
    • 输入流适配器和输出流适配器为流对象提供了迭代器的接口

例 从标准输入读入几个实数，分别将它们的平方输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;

// 求平方的函数
double square(double x) {
    return x * x;
}
int main() {
    // 从标准输入读入若干个实数，分别将它们的平方输出
    transform(istream_iterator<double>(cin), istream_iterator<double>(),
        ostream_iterator<double>(cout, "\t"), square);
    cout << endl;
    return 0;
}

例 综合运用几种迭代器的示例

程序涉及到输入迭代器、输出迭代器、随机访问迭代器这三个迭代器概念，并且以前两个概念为基础编写了一个通用算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <iterator>
#include <vector>
#include <iostream>
using namespace std;

// 将来自输入迭代器的n个T类型的数值排序，将结果通过输出迭代器result输出
template <class T, class InputIterator, class OutputIterator>
void mySort(InputIterator first, InputIterator last, OutputIterator result) {
    // 通过输入迭代器将输入数据存入向量容器s中
    vector<T> s;
    for (;first != last; ++first)
        s.push_back(*first);
    // 对s进行排序，sort函数的参数必须是随机访问迭代器
    sort(s.begin(), s.end());  
    copy(s.begin(), s.end(), result);   //将s序列通过输出迭代器输出
}

int main() {
    // 将s数组的内容排序后输出
    double a[5] = { 1.2, 2.4, 0.8, 3.3, 3.2 };
    mySort<double>(a, a + 5, ostream_iterator<double>(cout, " "));
    cout << endl;
    // 从标准输入读入若干个整数，将排序后的结果输出
    mySort<int>(istream_iterator<int>(cin), istream_iterator<int>(), ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}

运行结果：

1
2
3
0.8 1.2 2.4 3.2 3.3
2 -4 5 8 -1 3 6 -5
-5 -4 -1 2 3 5 6 8