STL Iterator

Iterator, STL

STL Iterator

每个容器定义自己的iterator类型，所以不用包含额外的头文件。
一些特殊类型的iterator和一些关于iterator的辅助操作需要头文件<iterator>。

Iterators are objects that can iterate over elements of a sequence via a common interface that is adapted from ordinary pointers.

Iterator Categories

Iterator Categories
Abilities of Iterator Categories

Output Iterators

Output iterators can only step forward with write access.

不能为同一个位置赋值两次。

Expression Effect
*iter = val Writes val to where the iterator refers
++iter Steps forward (returns new position)
iter++ Steps forward (returns old position)
TYPE(iter) Copies iterator (copy constructor) 
1
2
3
4
5
OutputIterator pos;
while (...) {
	*pos = ...;	// assign a value
	++pos;		// advance (prepare for the next assignment)
}

Input Iterators

Input iterators can only step forward element-by-element with read access.

不能读同一个位置两次。
==操作只能用于判断是否到末尾，指向不同位置的iterator也可能相等。

Expression Effect
*iter Provides read access to the actual element
iter->member Provides read access to a member of the actual element
++iter Steps forward (returns new position)
iter++ Steps forward
iter1 == iter2 Returns whether two iterators are equal
iter1 != iter2 Returns whether two iterators are not equal
TYPE(iter) Copies iterator (copy constructor) 
1
2
3
4
5
InputIterator pos, end;
while (pos != end) {
	...	// read-only access using *pos
	++pos;
}

Forward Iterators

Forward iterators are input iterators that provide additional guarantees while reading forward.

保证了两个指向同一个元素的iterator相等。

Expression Effect
*iter Provides access to the actual element
iter->member Provides access to a member of the actual element
++iter Steps forward (returns new position)
iter++ Steps forward (returns old position)
iter1 == iter2 Returns whether two iterators are equal
iter1 != iter2 Returns whether two iterators are not equal
TYPE() Creates iterator (default constructor)
TYPE(iter) Copies iterator (copy constructor)
iter1 = iter2 Assigns an iterator 
1
2
3
4
5
6
7
8
9
10
11
12
ForwardIterator pos1, pos2;
pos1 = pos2 = begin;	// both iterators refer to the same element
if (pos1 != end) {
	++pos1;	// pos1 is one element ahead
	while (pos1 != end) {
		if (*pos1 == *pos2) {
			...	// process adjacent duplicates
			++pos1;
			++pos2;
		}
	}
}

Bidirectional Iterators

Bidirectional iterators are forward iterators that provide the additional ability to iterate backward over the elements.

可以反向移动。

Expression Effect
*iter Provides access to the actual element
iter->member Provides access to a member of the actual element
++iter Steps forward (returns new position)
iter++ Steps forward (returns old position)
iter1 == iter2 Returns whether two iterators are equal
iter1 != iter2 Returns whether two iterators are not equal
TYPE() Creates iterator (default constructor)
TYPE(iter) Copies iterator (copy constructor)
iter1 = iter2 Assigns an iterator
–iter Steps backward (returns new position)
iter– Steps backward (returns old position)

Random-Access Iterators

Random-access iterators provide all the abilities of bidirectional iterators plus random access.

可以对iterator进行算数操作，增减位移，计算差值，比较iterator。

Expression Effect
*iter Provides access to the actual element
iter->member Provides access to a member of the actual element
++iter Steps forward (returns new position)
iter++ Steps forward (returns old position)
iter1 == iter2 Returns whether two iterators are equal
iter1 != iter2 Returns whether two iterators are not equal
TYPE() Creates iterator (default constructor)
TYPE(iter) Copies iterator (copy constructor)
iter1 = iter2 Assigns an iterator
–iter Steps backward (returns new position)
iter– Steps backward (returns old position)
iter[n] Provides access to the element that has index n
iter+=n Steps n elements forward (or backward, if n is negative)
iter-=n Steps n elements backward (or forward, if n is negative)
iter+n Returns the iterator of the nth next element
n+iter Returns the iterator of the nth next element
iter-n Returns the iterator of the nth previous element
iter1-iter2 Returns the distance between iter1 and iter2
iter1<iter2 Returns whether iter1 is before iter2
iter1>iter2 Returns whether iter1 is after iter2
iter1<=iter2 Returns whether iter1 is not after iter2
iter1>=iter2 Returns whether iter1 is not before iter2 
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 <vector>
#include <iostream>
using namespace std;
int main()
{
	vector<int> coll;
	// insert elements from -3 to 9
	for (int i = -3; i <= 9; ++i) {
		coll.push_back(i);
	}
	// print number of elements by processing the distance between beginning and end
	// NOTE: uses operator - for iterators
	cout << "number/distance: " << coll.end() - coll.begin() <<endl;
	// print all elements
	// NOTE: uses operator < instead of operator !=
	vector<int>::iterator pos;
	for (pos = coll.begin(); pos < coll.end(); ++pos) {
		cout << *pos << ' ';
	}
	cout << endl;
	// print every second element
	// NOTE: uses operator +=
	// ATTENTION: coll.end() - 1 may lead to undefined behavior if coll is empty.
	for (pos = coll.begin(); pos < coll.end() - 1; pos += 2) {
		cout << *pos << ' ';
	}
	cout << endl;
}

Auxiliary Iterator Functions

advance(); next(); prev(); distance(); iter_swap();
给其他一些类型的iterator一些random-access iterator才有的功能。

advance()

The function advance() increments the position of an iterator passed as the argument.

让iterator向前或向后移动几个元素。

1
2
#include <iterator>
void advance (InputIterator& pos, Dist n)
  • 让input iterator可以向前（或向后）移动n个元素。
  • 对于bidirectional和random-access的iterator，n可以是负值，从而向后移动。
  • Dist是一个模板类型。一般都是整型。
  • advance()不检查是否越过序列结尾。因为迭代器不知道容器里的情况。
  • 一般应该用advance()而不是+=，方便修改容器。不过要注意可能的效率降低，以及返回值的不同（advance没有返回值，+=返回新位置）。

next() and prev()

C++11后才有。

1
2
3
#include <iterator>
ForwardIterator next (ForwardIterator pos)
ForwardIterator next (ForwardIterator pos, Dist n)
  • Dist的类型是std::iterator_traits::difference_type。
  • 内部调用advance(pos, n)。
1
2
3
#include <iterator>
BidirectionIterator prev (BidirectionalIterator pos)
BidirectionIterator prev (BidirectionalIterator pos, Dist n)
  • Dist的类型是std::iterator_traits::difference_type。
  • 内部调用advance(pos, -n)。

distance()

The distance() function is provided to process the difference between two iterators.

1
2
#include <iterator>
Dist distance (InputIterator pos1, InputIterator pos2)
  • 两个迭代器需指向同一个容器。
  • 如果不是random-access迭代器，pos2必须等于或大于pos1，即从pos1可以到达pos2。
  • Dist的类型是iterator_traits::difference_type。

iter_swap()

The iter_swap() function is provided to swap the values to which two iterators refer.

1
2
#include <algorithm>
void iter_swap (ForwardIterator1 pos1, ForwardIterator2 pos2)
  • 交换pos1和pos2所指向的值。
  • 两个迭代器可以是不同类型，只要所指向的元素是可以修改的。

Iterator Adapters

Reverse Iterators

只有Forward List和Unordered Container不提供。

Position and Value of Reverse Iterators
rbegin() 返回反向的第一个元素的位置。
rend() 返回反向的最后一个元素之后的位置。

当普通iterator和reverse iterator相互转换时要注意，iterator需要是bidirectional iterator，并且他们的逻辑位置并不是对应的。
Conversion between Iterator pos and Reverse Iterator rpos
如{1,2,3,4,5,6,7}：
iter指向5，值也是5；riter指向5，值是4。物理位置相同，逻辑值不同。
如果iter1, iter2表示[2,5)的区间，即2,3,4。
如果riter1, riter2表示[4,1)的区间，即4,3,2。
区间还是相同的。
相互转化：

1
2
3
list<int>::iterator pos;
list<int>::reverse_iterator rpos(pos);		// iterator to reverse iterator
list<int>::iterator rrpos = rpos.base();	// reverse iterator to iterator

pos: 5; rpos: 4; rrpos: 5;

Insert Iterators

把对当前位置的赋值变成在当前位置插入。从而可以插入而不是覆盖。

三种类型。back inserter, front inserter, general inserter。
Kinds of Insert Iterators
容器必须提供called function，所以：

  • back inserter只能用于vector, deque, list, string。
  • front inserter只能用于deque, list。
  • general inserter除了array和forward list都可以用。因为需要insert()成员函数。
Back Inserters
1
2
3
4
5
6
vector<int> coll;
back_inserter(coll) = 1;	// 在尾部插入1
back_inserter(coll) = 2;	// 在尾部插入2，coll变成1,2
// 注意如果同数组copy的话要预先留好空间，因为插入操作可能会迭代器失效。
coll.reserve(2*coll.size());
copy(coll.begin(), coll.end(), back_inserter(coll));	// coll变成1,2,1,2
Front Inserters
1
2
3
4
5
list<int> coll;
front_inserter(coll) = 1;
front_inserter(coll) = 2;	// coll变成2,1
// List的插入操作不用担心迭代器失效。
copy(coll.begin(), coll.end(), front_inserter(coll));	// coll变成1,2,2,1

注意front inserter插入后顺序是反向的。

General Inserters

每次插入完成后，insert会自动++。

1
2
3
4
5
6
7
8
set<int> coll;
inserter(coll, coll.end()) = 1;	// 在coll.end()的位置插入1
inserter(coll, coll.end()) = 2;	// coll变成1,2
// 把coll的元素插入到一个list里。
list<int> coll2;
copy(coll.begin(), coll.end(), inserter(coll2, coll2.begin()));	// 在初始位置插入。插入的第一个元素说放哪儿就是哪儿。coll2变成1,2
// 把coll里的元素再次插入到list第二个元素的位置上。
copy(coll.begin(), coll.end(), inserter(coll2, ++coll2.begin()));	// coll2变成1,1,2,2。

Stream Iterators

A stream iterator is an iterator adapter that allows you to use a stream as a source of destination of algorithms.

Ostream Iterators

Ostream iterators write assigned values to an output stream.

1
2
3
string delim("|");
vector<int> coll = {1,2,3,4,5,6,7};
copy(coll.cbegin(), coll.cend(), ostream_iterator<int>(cout, delim.c_str()));

输出1|2|3|4|5|6|7|

Istream Iterators

Istream iterators reads elements from an input stream.

1
2
3
4
5
6
7
8
9
// create istream iterator that reads integers from cin
istream_iterator<int> intReader(cin);
// create end-of-stream iterator
istream_iterator<int> intReaderEOF;
// while able to read tokens with istream iterator write them
while (intReader != intReaderEOF)
{
	cout << "Element: " << *intReader << endl;
}
Example of Stream Iterators and advance()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iterator>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
	istream_iterator<string> cinPos(cin);
	ostream_iterator<string> coutPos(cout," ");
	// while input is not at the end ofthe file
	// - write every third string
	while (cinPos != istream_iterator<string>()) {
		// ignore the following two strings
		advance (cinPos, 2);
		// read and write the third string
		if (cinPos != istream_iterator<string>()) {
			*coutPos++ = *cinPos++;
		}
	}
	cout << endl;
}

如果输入：No one objects if you are doing a good programming job for someone whom you respect.
会输出：objects are good for you

[1] The C++ Standard Library 2nd Edition