The C++ Standard Library 学习笔记（一）第7章

7. 迭代器

7.2 迭代器分类

7.2.1 输入迭代器（Input Iterator）

输入迭代器只能逐位向前读取元素，且只能读取一遍，例如：istream,，ifstream。

7.2.2 输出迭代器（Output Iterator）

它与输入迭代器正好相反，它只能逐位向前写元素，也只能写一遍，例如：ostream，ofstream，inserter。

7.2.3 前向迭代器（Forward Iterator）

它是输出迭代器和输入迭代器的组合，它拥有输入迭代器的所有能力和几乎所有的输出迭代器的能力

7.2.4 双向迭代器（Bidirectional Iterator）

双向迭代器是前向迭代器加上向后迭代的能力，它的移动操作只有++和--，例如：list，set，multiset，map，multimap提供的迭代器。

7.2.5 随机访问迭代器（Random Access Iterator）

它可以随机存取元素，并且迭代器可以做算数运算，和关系运算（< 和 >）。例如：vector，deque，string，array提供的迭代器。

7.2.5 vector string迭代器的递增递减操作的问题

由于vector和string的迭代器通常用元素类型的指针来实现，对于指针你又不能改变它的临时值，因此很多情况下，编译会通不过。这时你需要一个临时的迭代器，例如：

std::vector<int> coll;

...

//sort, starting with the second element

// - PORTABLE version

if (coll.size() > 1) {

std::vector<int>::iterator beg = coll.begin();

coll.sort (++beg, coll.end());

}

7.3 迭代器辅助函数

#include <iterator> //头文件

void advance(InputIterator& pos, Dist n); //将迭代器向前移动n个位置，对所有迭代器适用。

Dist distance(InputIterator pos1, InputIterator pos2); //计算两个迭代器之间的距离，对所有迭代器适用。

#include <algorithm> //头文件

void iter_swap (ForwardIterator1 pos1, ForwardIterator2 pos2)；//交换两个迭代器的值，两个迭代器不需要为同一类型，但是必须可以复制。

7.4 迭代器适配器（Iterator Adapters）

7.4.1 反向迭代器（reverse iterator）

反向迭代器可以以相反的顺序访问元素。容器的rbegin()和rend()返回一对反向迭代器。

Container<T>::reverse_iterator rpos(pos);可以获得pos的反向迭代器，但rpos的值指向pos的前一个位置。

可以用reverse_iterator.base();得到反向迭代器的正向迭代器。

例子:

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

vector<int> ivec;

for (int i = 1; i < 9; ++i)

{

ivec.push_back(i);

}

vector<int>::iterator pos;

pos = find(ivec.begin(), ivec.end(), 5);

if (pos != ivec.end())

{

cout << "pos=" << *pos << endl;

}

vector<int>::reverse_iterator rpos(pos);

cout << "rpos=" << *rpos << endl;

vector<int>::iterator pos2 = find(ivec.begin(), ivec.end(), 2);

vector<int>::iterator pos7 = find(ivec.begin(),ivec.end(), 7);

copy(pos2,pos7, ostream_iterator<int>(cout));

cout << endl;

vector<int>::reverse_iterator rpos2(pos2);

vector<int>::reverse_iterator rpos7(pos7);

copy(rpos7, rpos2, ostream_iterator<int>(cout));

cout << endl;

vector<int>::iterator rrpos2 = rpos2.base();

cout << "rrpos2=" << *rrpos2 << endl;

getchar();

return 0;

}

输出：

pos=5

rpos=4

23456

65432

rrpos2=2

7.4.2 输入迭代器（Insert iterators）

输出迭代器主要用于算法，它使得算法可以将新值插入容器而不是覆盖，它将覆盖操作转换为插入操作。输入迭代器重载了解引用操作符（*）返回自身容器的一个引用，和赋值操作符（=），把它转化为容器的push_back，push_front或insert操作。

有三种输入迭代器：back_inserter，front_inserter和insertor，分别对应push_back，push_front和insert操作。

7.4.3 流迭代器（Stream Iterators）

流迭代器是一个迭代器适配器，它让你能用流作为算法的输入和输出源。

输出流迭代器（Ostream Iterators）

ostream_iterator<T>(ostream, delim=’’);

输入流迭代器（Istream Iterators）

istream_iterator<T>()，流输入迭代器的结束；

istream_iterator<T>(istream)，创建一个istream的迭代器。

7.5 迭代器特征（Iterator Traits）

每一个迭代器都有对应的Iterator tag，标准库的定义：

namespace std {

struct output_iterator_tag {

};

struct input_iterator_tag {

};

struct forward_iterator_tag

: public input_iterator_tag {

};

struct bidirectional_iterator_tag

: public forward_iterator_tag {

};

struct random_access_iterator_tag

: public bidirectional_iterator_tag {

};

}

Iterator Traits，它包含了迭代器相关的类型定义，使得你可以作为泛型编程的引用。

标准库的定义：

namespace std {

template <class T>

struct iterator_traits {

typedef typename T::value_type value_type;

typedef typename T::difference_type difference_type;

typedef typename T::iterator_category iterator_category;

typedef typename T::pointer pointer;

typedef typename T::reference reference;

};

}

namespace std {

template <class T>

struct iterator_traits<T*> {

typedef T value_type;

typedef ptrdiff_t difference_type;

typedef random_access_iterator_tag iterator_category;

typedef T* pointer;

typedef T& reference;

};

}