C++标准模板库STL：算法

1. 了解了解

1.1 算法分类

1. 不变序列算法
2. 变值算法
3. 删除算法
4. 变序算法
5. 排序算法
6. 有序区间算法
7. 数值算法

1.2 版本

大多重载的算法都是有两个版本的：
- 用 " == " 判断元素是否相等， 或用 " < " 来比较大小
- 多出一个类型参数 " Pred " 和函数形参 “Pred op”: 通过表达式 “op(x, y)” 的返回值: true / false → 来判断 x 是否"等于" y， 或者 x 是否 “小于” y

• 实例1. min_element:

iterator min_element(iterator first, iterator last);
iterator min_element(iterator first, iterator last, Pred op);

2. 不变序列算法

2.1 了解了解

1. 不会修改算法所作用的容器或对象
2. 适用于顺序容器和关联容器
3. 时间复杂度都是O(n)

2.2 常见算法

算法名称	功能
min	求两个对象中较小的（可自定义比较器）
max	求两个对象中较大的（可自定义比较器）
min_element	求区间中的最小值（可自定义比较器）
max_element	求区间中的最大值（可自定义比较器）
for_each	对区间中的每个元素都做某种操作
count	计算区间中等于某值的元素个数
count_if	计算区间中符合某种条件的元素个数
★find	在区间中查找等于某值的元素
find_if	在区间中查找符合某种条件的元素
find_end	在区间中查找另一个区间最后一次出现的位置（可自定义比较器）
find_first_of	在区间中查找第一个出现在另一个区间中的元素（可自定义比较器）
adjacent_find	在区间中寻找第一次出现连续两个相等元素的位置（可自定义比较器）
search	在区间中查找另外一个区间第一次出现的位置（可自定义比较器）
search_n	在区间中查找第一次出现等于某值的连续n个元素（可自定义比较器）
equal	判断两区间是否相等（可自定义比较器）
mismatch	逐个比较两个区间的元素，返回第一次发生不相等的两个元素的位置（可自定义比较器）
lexicographical_compare	按字典序比较两个区间的大小（可自定义比较器）

1. find:

template<class Init, class T>
Init find(Init first, Init last, const T& val);

• 返回区间[first, last)中的迭代器i，使得 *i = val

2. find_if:

template<class Init, class Pred>
Init find_if(Init first, Init last, Pred pr);

• 返回区间[first, last)中的迭代器i，使得pr(*i) == true

3. for_each:

template<class Init, class Fun>
Fun for_each(Init first, Init last, Fun f);

• 对[first, last)中的每一个元素e，执行f(e)，要求f(e)不能改变e

4. count:

template<class Init, class T>
size_t count(Init first, Init last, const T& val);

• 计算[first, last)中等于val的元素的个数（x == y为true 算等于）

5. count_if:

template<class Init, class Pred>
size_t count_if(Init first, Init last, Pred pr);

• 计算[first, last)中符合 pr(e) == true 的元素e的个数

6. min_element:

template<class Fwdlt>
Fwdlt min_element(Fwdlt first, Fwdlt last);

• 返回[first, last)中最小的元素的迭代器，以 “<” 做比较器

• 最小值没有元素比它小，而不是它比别的不同的元素都小 见 实例2

• 因为即便 a != b，a < b和a > b有可能都不成立（取决于<和>被定义的规则）

• 实例2：

#include <iostream>
#include <algorithm>
using namespace std;

class A{
	public:
		int n;
	A(int i):n(i){}
};
bool operator < (const A& a1, const A& a2){
//rule:只有3<7为true，其他都false 
	cout << "< called" <<endl;
	if(a1.n == 3 && a2.n == 7)
		return true;
	return false;
} 

int main(){
	A aa[] = {3, 5, 7, 2, 1};
	cout << min_element(aa, aa + 5) -> n <<endl;	//输出 3 
	cout << max_element(aa, aa + 5) -> n <<endl;	//输出 7  
	A bb[] = {3, 5, 8, 2, 1};
	cout << max_element(bb, bb + 5) -> n <<endl;	//输出 3 
	return 0;	
} 

7. max_element:

template<class Fwdlt>
Fwdlt max_element(Fwdlt first, Fwdlt last);

• 返回[first, last)中最大的元素的迭代器，以 “<” 做比较器

3. 变值算法

3.1 了解了解

1. 此类算法会修改原区间或目标区间元素的值
2. 值被修改的那个区间，不可以是属于关联容器的（有序性被破坏）

3.2 常见算法

算法名称	功能
for_each	对区间中的每个元素都做某种操作
★copy	复制一个区间到别处 特殊用法见实例中：①
copy_backward	复制一个区间到别处，但目标区间是从后往前被修改的（Q1）
transform	将一个区间的元素变形后拷贝到另一个区间
swap_ranges	交换两个区间内容
fill	用某个值填充区间
fill_n	用某个值替换区间中的n个元素
generate	用某个操作的结果填充区间
generate_n	用某个操作的结果替换区间中的n个元素
replace	将区间中的某个值替换为另一个值
replace_if	将区间中符合某种条件的值替换成另一个值
replace_copy	将一个区间拷贝到另一个区间，拷贝时某个值要换成新值拷过去
replace_copy_if	将一个区间拷贝到另一个区间，拷贝时符合某条件的值要更换成新值拷过去

• Q1:为什么从后往前？
  A: 考虑两个区间有重叠的情况，若从前往后，可能还没拷贝到重叠部分，重叠部分就被覆盖掉了，找不到了

1. transform:

template<class Init, class OutIt, class Unop>
OutIt transform(Init first, Init last, OutIt x, Unop uop);

• 对[first, last)中的每个迭代器I:
  - 执行uop(*I);并将结果一次放入从x 开始的地方
  - 要求uop(*I);不得改变*I的值
• 本模板返回值是个迭代器，即x + (last - first)
  - x可以和first相等

2. copy算法

template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);

• 对每个在区间[0, last - first)中的N执行一次 *(x + N) = *(first + N),并返回 x + N

Copy源码：

template<class _II, class _OI>
inline_OI copy(_II_F, _II_L, _OI_X){
	for(; _F != _L; ++_X, ++_F)
		*_X = *_F;
	return (_X);
}

• 实例：

#include <vector>
#include <iostream>
#include <numeric>
#include <list>
#include <algorithm>
#include <iterator>
using namespace std;

class CLessThen9{
	public:
		bool operator () (int n){return n < 9;}
}; 
void outputSquare(int value){cout << value * value << " ";}
int calculateCube(int value){return value * value * value;}

int main(){
	const int SIZE = 10;
	int a1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int a2[] = {100, 2, 8, 1, 50, 3, 8, 9, 10, 2};
	vector<int> v(a1, a1 + SIZE);
	ostream_iterator<int> output(cout, " ");
	//以后把什么交给output ，都等价于交给cout（以整数+空格形式）输出到屏幕上 
	random_shuffle(v.begin(), v.end());
	//变序算法， 随机打乱v中值, 伪随机 
	cout << endl << "1) ";
	//输出： 1) 9 2 10 3 1 6 8 4 5 7 
	copy(v.begin(), v.end(), output);
	//特殊① 用output作参数，使用copy，来输出 
	copy(a2, a2 + SIZE, v.begin());
	//copy要求用足够的空间，否则会越界 
	cout << endl << "2) ";
	cout << count(v.begin(), v.end(), 8); 
	cout << endl << "3) ";
	cout << count_if(v.begin(), v.end(), CLessThen9());
	//CLessThen9()是一个函数对象:count_if按CLessThen9()的规则来跑 
	cout << endl << "4) ";
	cout << *(min_element(v.begin(), v.end()));
	cout << endl << "5) ";
	cout << *(max_element(v.begin(), v.end()));
	cout << endl << "6) ";
	cout << accumulate(v.begin(), v.end(), 0);	//求和区间[f,l)的元素，累加到初始值0上 
	cout << endl << "7) ";
	for_each(v.begin(), v.end(), outputSquare);
	vector<int> cubes(SIZE);
	transform(a1, a1 + SIZE, cubes.begin(), calculateCube);
	cout << endl << "8) ";
	copy(cubes.begin(), cubes.end(), output);
	return 0;
}

• 上实例中出现的copy特殊使用：

1.
ostream_iterator<int> output(cout, " ");
//定义一个ostream_iterator<int>对象，可以通过cout输出以" "（空格）分隔的整数
2.
copy(v.begin(), v.end(), output);
//导致v的内容在cout上输出

对于copy(v.begin(), v.end(), output);first和last的类型是vector<int>::const_iterator, output的类型是ostream_iterator<int>

4. 删除算法

4.1 了解了解

1. 删除一个容器里的某些元素
2. 删除不会使容器里的元素减少：
   - 将所有应该被删除的元素看做空位置
   - 用留下的元素从后往前移，依次去填空位置
   - 元素往前移后，它原来的位置也就算是空位置
   - 也应由后面留下的元素来填上
   - 最后，没有被填上的空位置，维持其原来的值不变（用后面补前面，最后将unique后的部分放到最前面，后面的不管了，只取最前面那部分），见：4.2 实例1.①
3. 删除算法不应作用于关联容器

4.2 常见算法

算法名称	功能
★remove	删除区间中等于某个值的元素
remove_if	删除区间中满足某种条件的元素
remove_copy	拷贝区间到另一个区间，等于某个值的元素不拷贝
remove_copy_if	拷贝区间到另一个区间，符合某种条件的元素不拷贝
★unique	删除区间中连续相等的元素，只留下一个（可自定义比较器）
unique_copy	拷贝区间到另一个区间，连续相等的元素，只拷贝第一个到目标区间（可自定义比较器）

TIPS:算法复杂度都是O(n)

1. unique:

• version1：

template<class FwdIT>
FwdIt unique(FwidIt first, FwdIt last);

• 用 == 比较是否相等

• version2:

template<class FwdIt, class Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);

• 用pr(x, y)为true 判断是否相等
• 对[first, last)这个序列中连续相等的元素，只留下第一个
• 返回值是迭代器，指向元素删除后的区间的最后一个元素的后面（可以通过- begin()得到unique后的区间长度）

TIPS：用sort+unique去重

• 实例1：

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

int main(){
	int a[5] = {1, 2, 3, 4, 5};
	int b[6] = {1, 2, 3, 2, 5, 6};
	ostream_iterator<int> oit(cout, ",");
	int *p = remove(a, a + 5, 2);
	cout << "1) ";	copy(a, a + 5, oit);	cout <<endl;
	//输出:	1) 1,3,4,5,5,
	cout << "2) " << p - a <<endl;
	//输出：2) 4
	vector<int> v(b, b + 6);
	remove(v.begin(), v.end(), 2);
	cout << "3) ";	copy(v.begin(), v.end(), oit);	cout <<endl;
	//输出：3) 1,3,5,6,5,6,
	cout << "4) "; 	cout << v.size() <<endl;
	//①：v中的元素没有减少
	//输出：4) 6
	return 0; 
}

5. 变序算法

5.1 了解了解

1. 变序算法改变容器中元素的顺序，但不改变元素的值
2. 变序算法不适用于关联容器
3. 算法复杂度都是O(n)

5.2 常见算法

算法名称	功能
★reverse	颠倒区间的前后次序
reverse_copy	把一个区间颠倒后的结果拷贝到另一个区间，源区间不变
rotate	将区间进行循环左移
rotate_copy	将区间以首尾相接的形式进行旋转后的结果，拷贝到另一个区间，源区间不变
★next_permutation	将区间改为下一个排序（可自定义比较器）
★prev_permutation	将区间改为上一个排序（可自定义比较器）
★random_shuffle	随机打乱区间内元素的顺序
partition	将区间内满足某个条件的元素移到前面，不满足该条件的移到后面

1. stable_patition:

• 把区间内满足某个条件的元素移到前面
• 把不满足该条件的移到后面
• 而对这两部分元素，分别保持它们原来的先后次序不变

2. random_shuffle:

template<class RanIt>
void random_shuffle(RanIt first, RanIt last);

• 随机打乱[first, last)中的元素，适用于能随机访问的容器

3. reverse：

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

• 颠倒区间[first, last)顺序

4. next_permutation:

template<class InIt>
bool next_permutation(InIt first, InIt last);

• 求下一个排列

• 实例1：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(){
	string str = "231";
	char szStr[] = "324";
	while(next_permutation(str.begin(), str.end())){
		cout << str <<endl;
	}
	//输出:	312 321 
	//next_permutation每次都改变str中的内容
	//类似桶子法，各位逐一排序 
	cout << "****" <<endl;
	while(next_permutation(szStr, szStr + 3)){
		cout << szStr <<endl;
	}
	//输出:	342	423	432
	sort(str.begin(), str.end());
	cout << "****" <<endl;
	while(next_permutation(str.begin(), str.end())){
		cout << str <<endl;
	}
	//输出:	132 213 231 312 321 
	return 0;
}

• 实例2：

#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <iterator>
using namespace std;

int main(){
	int a[] = {8, 7, 10};
	list<int> Is(a, a+3);
	while(next_permutation(Is.begin(), Is.end())){
		list<int>::iterator i;
		for(i = Is.begin(); i != Is.end(); ++i)
			cout << *i << " ";
		cout <<endl;
	}
} 

• 实例2 输出结果：

8 10 7
10 7 8
10 8 7

6. 排序算法

6.1 了解了解

1. 比前面的变序算法复杂度更高，一般是O(nlog(n))
2. 排序算法需要随机访问迭代器的支持
3. 不适用于关联容器和list

6.2 常见算法

算法名称	功能
★sort	将区间从小到大排序（可自定义比较器）
stable_sort	将区间从小到大排序，并保持相等元素间的相对次序(可自定义比较器)
partial_sort	对区间部分排序，直到最小的n个元素就位（可自定义比较器）
partial_sort_copy	将区间前n个元素排序结果拷贝到别处，源区间不变（可自定义比较器）
nth_element	对区间部分排序，使得第n小的元素（n从0开始算）就位，而且比它小的都在它前面，比它大的都在它后面（可自定义比较器）
make_heap	使区间成为一个"堆"（可以自定义比较器）
push_heap	将元素加入一个"堆"区间（可以自定义比较器）
pop_heap	从"堆"区间删除堆顶元素（可以自定义比较器）
sort_heap	将一个""堆区间进行排序，排序结束后，该区间就是普通的有序区间，不再是"堆"了（可以自定义比较器）

1. sort（快排）

• version1:

template<class RanIt>
void sort(RanIt first, RanIt last);

• 按升序排序

• 判断x是否应比y靠前，就看 x < y 是否为true

• version2:

template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);

• 按升序排序
• 判断x是否应比y靠前，就看 pr(x, y) 是否为true

TIPS:

1. sort实际上是快排，时间复杂度O(nlog(n))
   - 平均性能最优
   - 但最坏情况，性能很差
2. 如果要保证在"最坏情况下"的性能，那么可以使用：
   - stable_sort:实际上是归并排序
   - 在有足够空间的情况下，复杂度O(nlog(n)),否则复杂度O(nlog(n)log(n))
   - stable_sort用法与sort相同
3. 排序算法要求随机存取迭代的支持，所以list不能使用排序算法，要使用list::sort

• 实例：

#include <iostream>
#include <algorithm>
using namespace std;

class MyLess{
//按个位数大小，从小到大排序 
	public:
		bool operator () (int n1, int n2){
			return (n1 % 10) < (n2 % 10);
		}
};

int main(){
	int a[] = {14, 2, 9, 111, 78};
	sort(a, a + 5, MyLess());
	int i;
	for(i=0; i<5; i++)
		cout << a[i] << " ";
	cout <<endl;
	sort(a, a+5, greater<int>());
	//greater<int>用>比大小，谁大在前，降序 
	for(i=0; i<5; i++)
		cout << a[i] << " "; 
}

7. 有序区间算法

6.1 了解了解

1. 要求所操作的区间是已经从小到大排好序的
2. 需要随机访问迭代器的支持
3. 有序区间算法不能用于关联容器和list

6.2 常见算法

算法名称	功能
★binary_search	（折半查找）判断区间中是否包含某个元素（“相等”）
includes	判断是否一个区间中的每个元素，都在另一个区间中（子集）
★lower_bound	查找最后一个不小于某值的元素的位置
★upper_bound	查找第一个大于某值的元素的位置
★equal_range	同时获取lower_bound和upper_bound
merge	合并两个有序区间到第三个区间
set_union	将两个有序区间的"并"拷贝到第三个区间
set_intersection	将两个有序区间的"交"拷贝到第三个区间
set_difference	将两个有序区间的"差"拷贝到第三个区间
set_symmetric_difference	将两个有序区间的"对称差"拷贝到第三个区间
inplace_merge	将两个连续的有序区间原地合并为一个有序区间

1. binary_search:

• version1:

template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last, const T& val);

• 通过 < 比较大小
• version2:

template<class FwdIt， class T, class Pred>
bool binary_search(FwdIt first, FwdIt last, const T& val, Pred pr);

• 通过pr(x, y)返回值比较大小（true 等价于 x<y）

TIPS:折半查找要求容器已经有序且支持随机访问迭代器，返回是否找到

• 实例：

#include <vector>
#include <bitset>
#include <iostream>
#include <numeric>
#include <list>
#include <algorithm>
#include <iterator>
using namespace std;

bool Greater10(int n){
	return n > 10;
} 

int main(){
	const int SIZE = 10;
	int a1[] = {2, 8, 1, 50, 3, 100, 8, 9, 10, 2};
	vector<int> v(a1, a1+SIZE);
	ostream_iterator<int> output(cout, " ");
	vector<int>::iterator location;
	location = find(v.begin(), v.end(), 10);
	if(location != v.end()){
	//找不到10，location就 == v.end() 
		cout << endl << "1) " << location - v.begin();
		//输出： 1）8  
		//10的下标 
	}
	location = find_if(v.begin(), v.end(), Greater10);
	if(location != v.end())
		cout << endl << "2) " << location - v.begin();
		sort(v.begin(), v.end());
		if(binary_search(v.begin(), v.end(), 9)){
			cout << endl << "3) " << "9 found";
		}
}

2. lower_bound:

template<class FwdIt, class T>
FwdIt lower_bound(FwdIt first, FwdIt last, const T& val);

• 要求[first, last)是有序的
• 查找[first, last)中的，最大位置FwdIt,使得[first, Fwdit)中所有的元素都比val小

3. upper_bound：

template<class FwdIt, class T>
FwdIt upper_bound(FwdIt first, FwdIt last, const T& val);

• 要求[first, last)是有序的
• 查找[first, last)中的，最小位置FwdIt,使得[first, Fwdit)中所有的元素都比val大

4. equal_bound：

template<class FwdIt, class T>
pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last, const T& val);

• 要求[first, last)是有序的
• 返回值是一个pair,假设为p，则：
  - [first, last)中的元素都比val小
  - [p.second, last)中的所有元素都比val大
  - p.first 就是lower_bound的结果
  - p.last 就是upper_bound的结果

5. merge: 把[first, last1), [first2, last2)两个升序序列合并，形成第3个升序序列，第3个升序序列以地址x开头

• version1:

template<class InIt1, class InIt2, class OutIt>
OutIt merge(InIt first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);

• 用 < 作比较器

• version2:

template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt merge(InIt first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);

• 用pr作比较器

6. includes: 判断[first2, last2)中的每个元素，是否都在[first1, last1)中

• version1:

template<class InIt1, class InIt2>
bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);

• 用 < 作比较器
• version2:

template<class InIt1, class InIt2, class Pred>
bool include(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, Pred pr);

• 用pr作比较器，pr(x, y) == true 等价于 x == y

8. bitset(标志位)

8.1 了解了解

template<size_t N>
class bitset{
	...
};

• 实际使用的时候，N是个整型常数
• 如：bitset<40> bst; bst是一个由40位组成的对象
• 用bitset的函数可以方便的访问任何一位

TIPS:bitset为了实现标志位

8.2 常见算法

算法名称	功能
bitset<N>& operator &= (cosnt bitset<N>& rhs);	按位与
bitset<N>&operator |= (cosnt bitset<N>& rhs);	按位或
bitset<N>&operator ^= (cosnt bitset<N>& rhs);	按位异或
bitset<N>&operator <<= (size_t num);	左移
bitset<N>&operator >>= (size_t num);	右移
bitset<N>& set();	全部置1
bitset<N>& set(size_t pos, bool val = true);	设置某位（val决定设0/1）
bitset<N>& reset();	全部置0
bitset<N>& reset(size_t pos);	某位设为0
bitset<N>& flip();	全部翻转
bitset<N>& flip(size_t pos);	翻转某位
reference operator [] (size_t pos);	返回对某位的引用
bool operator [] (size_t pos) const;	判断某位是否为1
reference at(size_t pos);	取某一位，对下标是否越界判断
bool at(size_t pos) cosnt;	对某一位判断
unsigned long to_ulong() const;	转换成整数
string to_string() const;	转换成字符串
size_t count() const;	计算1的个数
size_t size() const;	求bitset的大小
bool operator == (const bitset<N>& rhs) const;
bool operator != (const bitset<N>& rhs) const;
bool test(size_t pos) const;	测试某位是否为1
bool any() const;	是否有某位为1
bool none() const;	是否全部为0
bitset<N> operator << (size_t pos) const;
bitset<N> operator >> (size_t pos) const;
bitset<N> operator~();	取反
static const size_t bitset_size = N;

TIPS:第0位在最右边