# 迭代器简介

# 迭代器是什么？

不搞抽象，直接举例。

对于一个 vector，我们可以用下标遍历：

	for (int i = 0; i < a.size(); i++)
	cout << a[i] << endl;

我们同时也可以用迭代器来遍历：

	for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
	cout << *it << endl;

a.begin() 是一个迭代器，指向的是第一个元素
a.end() 是一个迭代器，指向的是最后一个元素再后面一位
上述迭代器具有自增运算符，自增则迭代器向下一个元素移动
迭代器与指针相似，如果对它使用解引用运算符，即 *it ，就能取到对应值了

# 为何需要迭代器？

很多数据结构并不是线性的（例如红黑树），对于非线性数据结构，下标是无意义的。无法使用下标来遍历整个数据结构。

迭代器的作用就是定义某个数据结构的遍历方式，通过迭代器的增减，代表遍历到的位置，通过迭代器便能成功遍历非线性结构了。

例如，set 的实现是红黑树，我们是没法用下标来访问元素的。但是通过迭代器，我们就能遍历 set 中的元素了：

	for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
	cout << *it << endl;

# 迭代器用法

对于 vector 容器，它的迭代器功能比较完整，以它举例：

.begin() ：头迭代器
.end() ：尾迭代器
.rbegin() ：反向头迭代器
.rend() ：反向尾迭代器
迭代器 + 整型：将迭代器向后移动
迭代器 - 整型：将迭代器向前移动
迭代器 ++ ：将迭代器向后移动 1 位
迭代器 -- ：将迭代器向前移动 1 位
迭代器 - 迭代器：两个迭代器的距离
prev(it) ：返回 it 的前一个迭代器
next(it) ：返回 it 的后一个迭代器

对于其他容器，由于其结构特性，上面的功能不一定都有（例如 set 的迭代器是不能相减求距离的）

# 常见问题

.end() 和 .rend() 指向的位置是无意义的值

对于一个长度为 10 的数组： for (int i = 0; i < 10; i++) ，第 10 位是不可访问的

对于一个长度为 10 的容器： for (auto it = a.begin(); it != a.end(); ++it) ，.end 是不可访问的

不同容器的迭代器功能可能不一样

迭代器细化的话有正向、反向、双向，每个容器的迭代器支持的运算符也可能不同，因此不同容器的迭代器细节很有可能是不一样的。

删除操作时需要警惕

为什么 3 没删掉？

	vector<int> a{1, 2, 3, 4};
	for (auto it = a.begin(); it != a.end(); ++it)
	if (it == 2 \|\| it == 3)
	a.erase(it);
	// a = [1, 3, 4]

为啥 RE 了？

	vector<int> a{1, 2, 3, 4};
	for (auto it = a.begin(); it != a.end(); ++it)
	if (*it == 4)
	a.erase(it);

<center><b > 建议：如无必要，别用迭代器操作容器。（遍历与访问没关系）</b></center>

# 常用算法

# 内容总览

打勾的是本次将会详细讲解的，其他的是算法竞赛中建议学习的，不在下表列出的在比赛中基本用不到。

（很多函数的功能很简单，自己都能快速写出来，但是使用函数可以让代码可读性变得更高，这在比赛中是至关紧要的）

算法库 Algorithm
- count()
- find()
- fill()
- swap()
- reverse()
- shuffle() C++11
- unique()
- sort()
- lower_bound() / upper_bound()
- max() / min()
- max_element() / min_element()
- prev_permutation() / next_permutation()
数学函数 cmath
- abs()
- exp()
- log() / log10() / log2()
- pow()
- sqrt()
- sin() / cos() / tan()
- asin() / acos() / atan()
- sinh() / cosh() / tanh()
- asinh() / acosh() / atanh() C++11
- ceil() / floor()
- round() C++11
数值算法 numeric
- iota() C++11
- accumulate()
- gcd() C++17
- lcm() C++17
伪随机数生成 random
- mt19937
- random_device()

# `swap()`

交换两个变量的值

用法示例

	template< class T >
	void swap( T& a, T& b );

	int a = 0, b = 1;
	swap(a, b);
	// now a = 1, b = 0

	int arr[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	swap(arr[4], arr[6]);
	// now arr = {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}

注意事项

这个 swap 参数是引用的，不需要像 C 语言一样取地址。

# `sort()`

使用快速排序给一个可迭代对象排序

用法示例

	template< class RandomIt, class Compare >
	void sort( RandomIt first, RandomIt last, Compare comp );

默认排序从小到大

	vector<int> arr{1, 9, 1, 9, 8, 1, 0};
	sort(arr.begin(), arr.end());
	// arr = [0, 1, 1, 1, 8, 9, 9]

如果要从大到小，则需要传比较器进去。

	vector<int> arr{1, 9, 1, 9, 8, 1, 0};
	sort(arr.begin(), arr.end(), greater<int>());
	// arr = [9, 9, 8, 1, 1, 1, 0]

如果需要完成特殊比较，则需要手写比较器。

比较器函数返回值是 bool 类型，传参是需要比较的两个元素。记我们定义的该比较操作为 $\star$ ：

若 $a\star b$ ，则比较器函数应当返回 true
若 $a\not\star b$ ，则比较器函数应当返回 false

** 注意：** 如果 $a=b$ ，比较器函数必须返回 false

	bool cmp(pair<int, int> a, pair<int, int> b)
	{
	if (a.second != b.second)
	return a.second < b.second;
	return a.first > b.first;
	}

	int main()
	{
	vector<pair<int, int>> arr<!--swig0-->;
	sort(arr.begin(), arr.end(), cmp);
	// arr = [(0, 0), (8, 1), (2, 9), (1, 9)]
	}

# `lower_bound()` / `upper_bound()`

在已升序排序的元素中，应用二分查找检索指定元素，返回对应元素迭代器位置。找不到则返回尾迭代器。

lower_bound() : 寻找 $\geq x$ 的第一个元素的位置
upper_bound() : 寻找 $>x$ 的第一个元素的位置

怎么找 $\leq x$ / $< x$ 的第一个元素呢？

$>x$ 的第一个元素的前一个元素（如果有）便是 $\leq x$ 的第一个元素
$\geq x$ 的第一个元素的前一个元素（如果有）便是 $<x$ 的第一个元素

返回的是迭代器，如何转成下标索引呢？减去头迭代器即可。

用法示例

	template< class ForwardIt, class T >
	ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

	vector<int> arr{0, 1, 1, 1, 8, 9, 9};
	vector<int>::iterator it = lower_bound(arr.begin(), arr.end(), 7);
	int idx = it - arr.begin();
	// idx = 4

我们通常写成一行：

	vector<int> arr{0, 1, 1, 1, 8, 9, 9};
	idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
	idx = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4
	idx = upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
	idx = upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 5

# `reverse()`

反转一个可迭代对象的元素顺序

用法示例

	template< class BidirIt >
	void reverse( BidirIt first, BidirIt last );

	vector<int> arr(10);
	iota(arr.begin(), arr.end(), 1);
	// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
	reverse(arr.begin(), arr.end());
	// 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

# `max()` / `min()`

返回最大值 / 最小值的数值

用法示例

	int mx = max(1, 2); // 2
	int mn = min(1, 2); // 1

在 C++11 之后，可以使用列表构造语法传入一个列表，这样就能一次性给多个元素找最大值而不用套娃了：

	// Before C++11
	int mx = max(max(1, 2), max(3, 4)); // 4
	int mn = min(min(1, 2), min(3, 4)); // 1

	// After C++11
	int mx = max({1, 2, 3, 4}); // 4
	int mn = min({1, 2, 3, 4}); // 1

# `unique()`

消除数组的重复相邻元素，数组长度不变，但是有效数据缩短，返回的是有效数据位置的结尾迭代器。

例如： $[1,1,4,5,1,4]\to[1,4,5,1,4,\underline?]$ ，下划线位置为返回的迭代器指向。

	template< class ForwardIt >
	ForwardIt unique( ForwardIt first, ForwardIt last );

用法示例

单独使用 unique 并不能达成去重效果，因为它只消除相邻的重复元素。但是如果序列有序，那么它就能去重了。

但是它去重后，序列尾部会产生一些无效数据： $[1,1,2,4,4,4,5]\to[1,2,4,5,\underline?,?,?]$ ，为了删掉这些无效数据，我们需要结合 erase.

最终，给 vector 去重的写法便是：

	vector<int> arr{1, 2, 1, 4, 5, 4, 4};
	sort(arr.begin(), arr.end());
	arr.erase(unique(arr.begin(), arr.end()), arr.end());

# 数学函数

所有函数参数均支持 int / long long / float / double / long double

公式	示例
$f(x)=\lvert x\rvert$	`abs(-1.0)`
$f(x)=e^x$	`exp(2)`
$f(x)=\ln x$	`log(3)`
$f(x,y)=x^y$	`pow(2, 3)`
$f(x)=\sqrt x$	`sqrt(2)`
$f(x)=\lceil x\rceil$	`ceil(2.1)`
$f(x)=\lfloor x\rfloor$	`floor(2.1)`
$f(x)=\left<x\right>$	`rount(2.1)`

注意事项

由于浮点误差，有些的数学函数的行为可能与预期不符，导致 WA。如果你的操作数都是整型，那么用下面的写法会更稳妥。

原文地址：https://codeforces.com/blog/entry/107717

$\lfloor\frac{a}{b}\rfloor$ $⌊ \frac{a}{b} ⌋$
- 别用： floor(1.0 * a / b)
- 要用： a / b
$\lceil\frac{a}{b}\rceil$ $⌈ \frac{a}{b} ⌉$
- 别用： ceil(1.0 * a / b)
- 要用： (a + b - 1) / b （ $\lceil\frac{a}{b}\rceil=\lfloor\frac{a+b-1}{b}\rfloor$ ）
$\lfloor\sqrt a\rfloor$ $⌊ a ⌋$
- 别用： (int) sqrt(a)
- 要用：二分查找 https://io.zouht.com/7.html
$a^b$ $a^{b}$
- 别用： pow(a, b)
- 要用：快速幂 https://io.zouht.com/18.html
$\lfloor\log_2 a\rfloor$ $⌊ lo g_{2} a ⌋$
- 别用： log2(a)
- 要用： __lg （不规范，但是这是竞赛）/ bit_width （C++20 可用）

# `gcd()` / `lcm()`

（C++17）返回最大公因数 / 最小公倍数

	int x = gcd(8, 12); // 4
	int y = lcm(8, 12); // 24

如果不是 C17，但是是 GNU 编译器（g），那么可以用内置函数 __gcd() .

当然， gcd / lcm 函数也挺好写，直接写也行（欧几里得算法）：

	int gcd(int a, int b)
	{
	if (!b)
	return a;
	return gcd(b, a % b);
	}

	int lcm(int a, int b)
	{
	return a / gcd(a, b) * b;
	}

STL C++算法

# 迭代器简介

# 迭代器是什么？

# 为何需要迭代器？

# 迭代器用法

# 常见问题

# 常用算法

# 内容总览

# swap()

# sort()

# lower_bound() / upper_bound()

# reverse()

# max() / min()

# unique()

# 数学函数

# gcd() / lcm()

STL常用容器

java基础语法

# `swap()`

# `sort()`

# `lower_bound()` / `upper_bound()`

# `reverse()`

# `max()` / `min()`

# `unique()`

# `gcd()` / `lcm()`