c++ stl算法设计理念

c++ stl算法设计理念

• 函数对象
• 一元函数对象、一元谓词
• 二元函数对象、二元谓词
• 预定义函数对象
• 函数适配器
• 容器算法迭代器的设计理念
  • 要点：分清楚 stl算法返回的值是迭代器 还是 谓词（函数对象） 是stl算法入门的重点。

函数对象

重载函数调用操作符的类，其对象常称为函数对象，即他们是行为类似函数的对象。一个类对象，表现出一个函数的特征，就是通过 ”对象名+（参数列表）“ 的方式使用一个类对象，如果没有上下文，完全可以把他看做一个函数对待。

函数对象和普通函数的异同：

#include<iostream>
using namespace std;

//函数对象 类重载了()
template <typename T>
class ShowElemt {
public:
	void operator()(T& t) {
		cout << t << endl;
	}
};

//函数模板 
template <typename T>
void FuncShowElemt(T& t) {
	cout << t << endl;
}

//普通函数
void FuncShowElemt2(int& t) {
	cout << t << endl;
}

int main() {
	
	int a = 10;
	
	ShowElemt<int> s1;
	s1(a);

	FuncShowElemt<int>(a);
	FuncShowElemt2(a);


	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
29
30
31
32
33
34
35
36

函数对象是属于类对象的，能突破函数的概念，能保持调用状态信息。

for_each

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

//函数对象 类重载了()
template <typename T>
class ShowElemt {
public:
	ShowElemt() {
		n = 0;
	}
	void operator()(T& t) {
		n++;
		cout << t << endl;
	}
	int n;
}

//函数模板 
template <typename T>
void FuncShowElemt(T& t) {
	cout << t << endl;
}

//普通函数
void FuncShowElemt2(int& t) {
	cout << t << endl;
}

int main() {
	
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	ShowElemt<int> s1;
    
    for_each(v1.begin(), v1.end(), s1);//匿名函数对象 匿名仿函数
	cout << s1.n << endl;//0
    
	s1 = for_each(v1.begin(), v1.end(), s1);//匿名函数对象 匿名仿函数
	cout << s1.n << endl;//3

	for_each(v1.begin(), v1.end(), FuncShowElemt2);//通过回调函数 谁使用for_each 谁去填写回调函数的入口地址


	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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

//for_each 函数原型：
_EXPORT_STD template <class _InIt, class _Fn>
_CONSTEXPR20 _Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    for (; _UFirst != _ULast; ++_UFirst) {
        _Func(*_UFirst);
    }

    return _Func;
}
1
2
3
4
5
6
7
8
9
10
11
12

函数对象 对比 普通函数：函数对象可以保存调用的信息。
通过for_each函数原型可以看出，函数对象的传递并非引用，但是会返回函数对象。

谓词

一元函数对象：函数参数1个

二元函数对象：函数参数2个

一元谓词 函数参数1个，函数返回值是bool类型，可以作为一个判断式

​ 谓词可以是一个仿函数，也可以是一个回调函数。

find_if

一元谓词

例子：

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

template<typename T>
class IsDev {
public:
	IsDev(const T n) {
		this->n = n;
	}
	bool operator()(T &n) {
		if (n == this->n) return true;
		return false;
	}
	T n;
};

int main() {
	vector<int> v1;
	for (int i = 1; i <= 10; i++) {
		v1.push_back(i);
	}
	int a = 4;
	vector<int>::iterator it = find_if(v1.begin(), v1.end(), IsDev<int>(a));
	if (it != v1.end()) {
		cout << *it << endl;
	}
	else {
		cout << "false" << 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
29
30
31
32
33

transform

二元谓词

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

template<typename T>
class SumAdd {
public:
	T operator()(T &a,T &b) {
		return a + b;
	}
};
/* 两种方式 方式二
template<typename T>
T SumAdd(T a, T b) {
	return a + b;
}*/

//二元谓词
int main() {

	/*
	_EXPORT_STD template <class _InIt1, class _InIt2, class _OutIt, class _Fn>
	_CONSTEXPR20 _OutIt transform(
		const _InIt1 _First1, const _InIt1 _Last1, const _InIt2 _First2, _OutIt _Dest, _Fn _Func) {
		// transform [_First1, _Last1) and [_First2, ...) with _Func
		_Adl_verify_range(_First1, _Last1);
		auto _UFirst1      = _Get_unwrapped(_First1);
		const auto _ULast1 = _Get_unwrapped(_Last1);
		const auto _Count  = _Idl_distance<_InIt1>(_UFirst1, _ULast1);
		auto _UFirst2      = _Get_unwrapped_n(_First2, _Count);
		auto _UDest        = _Get_unwrapped_n(_Dest, _Count);
		for (; _UFirst1 != _ULast1; ++_UFirst1, (void) ++_UFirst2, ++_UDest) {
			*_UDest = _Func(*_UFirst1, *_UFirst2);
		}

		_Seek_wrapped(_Dest, _UDest);
		return _Dest;
	}
	*/
    
    // v1 + v2 ==> v3
	vector<int> v1, v2, v3;
	v1.push_back(1); v1.push_back(3); v1.push_back(5);
	v2.push_back(2); v2.push_back(4); v2.push_back(6);
	v3.resize(10);

	transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), SumAdd<int>());
    //transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), SumAdd<int>);//方式二
	for (vector<int>::iterator it = v3.begin(); it != v3.end();it++) {
		cout << *it << " ";
	}
	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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

sort

二元谓词

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

template<typename T>
void show(T &a) {
	cout << a << " ";
}
bool myCompare(int a, int b) {
	return a > b;
}

int main() {

	vector<int> v1(10);
	for (int i = 0; i < 10; i++) {
		int temp = rand() % 100;
		v1[i] = temp;
	}
	for_each(v1.begin(), v1.end(), show<int>);//遍历
	cout << endl;

	sort(v1.begin(), v1.end(), myCompare);//排序
	for_each(v1.begin(), v1.end(), show<int>);//遍历
	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
29

预定义函数对象

标准模版库 stl 提前定义了很多预定义的函数对象，#include<functional> 要包含（不包含也行。。）。

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

int main() {

	plus<int> intAdd;
	int s = intAdd(10, 20);
	cout << s << endl;//30

	plus<string> strAdd;
	string str = strAdd("a", "b");
	cout << str << endl;//ab

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

算术函数对象：

加法：plus<Types>

​ plus<string> stringAdd;

​ sres = stringAdd(sva1,sva2);

减法：minus<Types>

乘法：multiplies<Types>

除法divides<Tpye>

求余：modulus<Tpye>

取反：negate<Type>

​ negate<int> intNegate;

​ ires = intNegate(ires);

​ Ires= UnaryFunc(negate<int>(),Ival1);

关系函数对象

等于equal_to<Tpye>

​ equal_to<string> stringEqual;

​ sres = stringEqual(sval1,sval2);

不等于not_equal_to<Type>

大于 greater<Type>

大于等于greater_equal<Type>

小于 less<Type>

小于等于less_equal<Type>

逻辑函数对象

逻辑与 logical_and<Type>

​ logical_and<int> indAnd;

​ ires = intAnd(ival1,ival2);

​ dres=BinaryFunc( logical_and<double>(),dval1,dval2);

逻辑或logical_or<Type>

逻辑非logical_not<Type>

​ logical_not<int> IntNot;

​ Ires = IntNot(ival1);

​ Dres=UnaryFunc( logical_not<double>,dval1);

实例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
//#include<functional>

template<typename T>
void show(T &a) {
	cout << a << " ";
}

int main() {

	vector<string> v1;
	v1.push_back("bbb");
	v1.push_back("aaa");
	v1.push_back("ddd");
	v1.push_back("ccc");

	sort(v1.begin(), v1.end(), greater<string>());
	for_each(v1.begin(), v1.end(), show<string>);//遍历

	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

函数适配器

stl 中已经定义了大量的函数对象，但是有时候需要对函数返回值进行进一步的简单计算，或者填上多余的参数，不能直接带入算法。函数适配器实现了这一功能，将一种函数对象转化为另一种符合要求的函数对象。

函数适配器可以分为4大类：

1. 绑定适配器 (bind adaptor)
2. 组合适配器 (composite adaptor)
3. 指针函数适配器 (pointer function adaptor)
4. 成员函数适配器 (member function adaptor)

常用函数适配器：

1. 绑定器（binder）：binder通过把二元函数对象的一个实参绑定到一个特殊的值上，将其转换成一元函数对象。
   1. bind1st：把值绑定到二元函数对象的第一个实参上
   2. bind2nd：绑定在第二个实参上
2. 取反器（negator)：negator是一个将函数对象的值翻转的函数适配器。
   1. not1：翻转一元预定义函数对象的真值
   2. not2：翻转二元谓词函数的真值

bind1st(op, value)
bind2nd(op,value)
not1(op)
not2(op)
1
2
3
4

例子:

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

class IsGreat {
public:
	IsGreat(int i) {
		n = i;
	}
	bool operator()(int i) {
		return i > n;
	}
	int n;
};

int main() {

	vector<int> v1;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i + 1);
	}

	//通过 谓词 求大于2 的个数
	int num = count_if(v1.begin(), v1.end(), IsGreat(2));
	cout << num << endl;//8

	//通过 预定于的函数对象 求大于2 的个数
    //greater<int>()有两个参数 左参数来自容器的元素，右参数固定成2（通过bind2nd做的）
	int num2 = count_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 2));
	cout << num2 << endl;//8
    
    //求 奇数的个数
	int num3 = count_if(v1.begin(), v1.end(), bind2nd(modulus<int>(), 2));
	cout << num3 << endl;//5
	 
	//求 偶数的个数 (求奇数取反)
	int num4 = count_if(v1.begin(), v1.end(), not1(bind2nd(modulus<int>(), 2)));
	cout << num4 << endl;//5
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41

容器算法迭代器的设计理念

1. stl 的容器通过类模版技术，实现数据类型和容器模型的分离

2. stl 的迭代器技术 实现了 遍历容器 的统一方法；也为 stl 的算法提供了统一性奠定了基础

3. stl 的算法，通过函数对象 实现了 自定义数据类型 的算法运算；所以说：stl 的算法也提供了统一性

   核心思想：其实函数对象本质就是 回调函数，回调函数的思想：就是任务的编写者和任务的调用者有效解耦合。函数指针做函数参数。

4. 具体例子：transform 算法的输入，通过迭代器 first和last 指向的元素作为输入；通过result 作为输出；通过函数对象来做自定义数据类型的运算。

算法分类

操作对象：

• 直接改变容器的内容
• 将原容器的内容复制一份，修改其副本，然后传回该副本

功能：

• 非可变序列算法：指不直接修改其所操作的容器内容的算法
  • 计数算法：count、count_if
  • 搜索算法：search、find、find_if、find_first_of
  • 比较算法：equal、mismatch、lexicographical_compar
• 可变序列算法：指可以修改它们所操作的容器内容的算法
  • 删除算法：remove、remove_if、remove_copy
  • 修改算法：for_each、transform
  • 排序算法：sort、stable_sort、partial_sort
• 排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
• 数值算法：对容器内容进行数值计算

for_each和transform的区别

for_each() 速度快 不灵活

transform() 速度慢 非常灵活

for_each 所使用的函数对象，参数是引用，没有返回值

transform所使用的函数对象，参数一般不适用引用，而是还有返回值

例子：

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

template <typename T>
void printV(vector<T>& v) {
	for (auto it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

// for_each 遍历 与 transform 区别
template <typename T>
void showV(T &n) {
	cout << n << " ";
}
template <typename T>
T showV2(T& n) {
	cout << n << " ";
	return n;
}

template <typename T>
class showElemt {
public:
	void operator()(T &n){
		cout << n << " ";
	}
};


int increase(int i) {	

	return i+100;
}

int main() {

	vector<int> v1;
	v1.push_back(1);
	v1.push_back(3);
	v1.push_back(5); 
	printV<int>(v1);

	//for_each
	for_each(v1.begin(), v1.end(), showV<int>);
	cout << endl;
	for_each(v1.begin(), v1.end(), showElemt<int>());
	cout << endl;

	//transform 回调函数
	transform(v1.begin(), v1.end(), v1.begin(), increase);
	printV<int>(v1);
	//transform 预定义
	transform(v1.begin(), v1.end(), v1.begin(), negate<int>());
	printV<int>(v1);
	//transform 函数适配器
	transform(v1.begin(), v1.end(), v1.begin(), bind2nd(multiplies<int>(),10));
	printV<int>(v1);
	//transform 把运算结果直接输出到屏幕
	transform(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "), negate<int>());
	cout << endl;

	//transform 遍历 与 for_each 区别
	//transform(v1.begin(), v1.end(), v1.begin(), showV<int>);//error
	transform(v1.begin(), v1.end(), v1.begin(), showV2<int>);
	cout << endl;
	printV<int>(v1);
    
    
    //other..
    vector<string> v2;
	v2.push_back("aaa");
	v2.push_back("bbb");
	v2.push_back("ccc");
	printV<string>(v2);

	//for_each
	for_each(v2.begin(), v2.end(), showV<string>);
	cout << endl;
	for_each(v2.begin(), v2.end(), showElemt<string>());
	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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

transform 源码原型：

_EXPORT_STD template <class _InIt, class _OutIt, class _Fn>
_CONSTEXPR20 _OutIt transform(const _InIt _First, const _InIt _Last, _OutIt _Dest, _Fn _Func) {
    // transform [_First, _Last) with _Func
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    auto _UDest       = _Get_unwrapped_n(_Dest, _Idl_distance<_InIt>(_UFirst, _ULast));
    for (; _UFirst != _ULast; ++_UFirst, (void) ++_UDest) {
        *_UDest = _Func(*_UFirst);//关键所在：解释了为什么要有返回值。
    }

    _Seek_wrapped(_Dest, _UDest);
    return _Dest;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

常用的查找算法

• adjacent_find 查到第一个重复的元素
• binary_search 二分查找 速度快
• count 相等个数
• count_if 先定义比较函数
• find 查找第一个元素位置
• find_if 查找符合函数的第一个元素位置

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

//count_if 条件函数
bool GreaterThree(int num) {
	return num > 3;
}

//find_if
bool IsTwo(int num) {
	return num == 2;
}

int main() {
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(2);
	v1.push_back(3);
    
    // adjacent_find 查到第一个重复的元素
	vector<int>::iterator it = adjacent_find(v1.begin(), v1.end());
	if (it != v1.end()) {
		cout << *it << endl;//2
	}
	int index = distance(v1.begin(), it);
	cout << index << endl;//1

	//binary_search 二分查找 速度快
	bool b = binary_search(v1.begin(), v1.end(), 2);
	if (b) {
		cout << "has" << endl;//has
	}

	//count 相等个数
	int iCount = count(v1.begin(), v1.end(), 2);
	cout << iCount << endl;//2

	//count_if 先定义比较函数
	int iCount_if = count_if(v1.begin(), v1.end(), GreaterThree);
	cout << iCount_if << endl;//0

	//find 查找第一个元素位置
	vector<int>::iterator it1 = find(v1.begin(), v1.end(), 2);
	while (it1 != v1.end()) {
		cout << *it1 << " ";//2 2 3
		it1++;
	}
	cout << endl;

	//find_if 查找符合函数的第一个元素位置
	vector<int>::iterator it2 = find_if(v1.begin(), v1.end(), IsTwo);
	while (it2 != v1.end()) {
		cout << *it2 << " ";//2 2 3
		it2++;
	}
	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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

常用的排序算法

• sort 排序（默认升序）
• merge 将两个有序容器合一 无序会error(还要升序,用之前先sort()一下)
• random_shuffle 随机排序
• reverse 倒序

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

void printV(vector<int> v) {
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {
	vector<int> v1;
	v1.push_back(5);
	v1.push_back(3);
	v1.push_back(1);
	vector<int> v2;
	v2.push_back(6);
	v2.push_back(4);
	v2.push_back(2);
	vector<int> v3;
	v3.resize(v1.size() + v2.size());

	//sort 排序（默认升序）
	sort(v1.begin(), v1.end());
	printV(v1);
	sort(v2.begin(), v2.end());
	printV(v2);

	//merge 将两个有序容器合一 无序会error(还要升序,用之前先sort()一下) 
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	printV(v3);

	//random_shuffle 随机排序
	srand(time(0));//设置随机种子（没：每次结果都一样）
	random_shuffle(v3.begin(), v3.end());
	printV(v3);
	string str("hello world!");
	random_shuffle(str.begin(), str.end());
	cout << str << endl;

	sort(v3.begin(), v3.end());//重新排序
	//reverse 倒序
	reverse(v3.begin(), v3.end());
	printV(v3);	

	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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

常见的拷贝替换算法

• copy 拷贝
• replace 替换
• replace 根据条件替换
• swap 交换

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

void printV(vector<int> v) {
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

bool GreaterFive(int num) {
	return num > 5;
}
int main() {
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(3);
	v1.push_back(3);
	v1.push_back(5);
	v1.push_back(7);

	vector<int> v2;
	v2.resize(v1.size());

	//copy 拷贝
	copy(v1.begin(), v1.end(), v2.begin());
	printV(v2);

	//replace 替换
	replace(v1.begin(), v1.end(), 3, 8);
	printV(v1);

	//replace 根据条件替换
	replace_if(v1.begin(), v1.end(), GreaterFive, 3);
	printV(v1);

	//swap 交换
	vector<int> v3;
	v3.push_back(2);
	v3.push_back(4);
	v3.push_back(6);
	swap(v1, v3);
	printV(v1);//2 4 6

	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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

常见的算术和生成算法

• accumulate 容器值先相加，再加上10
• fill 将容器中所以值改成 10

#include<iostream>
using namespace std;
#include<vector>
#include<numeric>

void printV(vector<int> v) {
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	vector<int> v1;
	v1.push_back(1);
	v1.push_back(3);
	v1.push_back(5);
	v1.push_back(7);

	//accumulate 容器值先相加，再加上10
	int iSum = accumulate(v1.begin(), v1.end(), 10);
	cout << iSum << endl;//26

	//fill 将容器中所以值改成 10
	fill(v1.begin(), v1.end(), 10);
	printV(v1);
    
	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
29
30

常用的集合算法

• set_union 两个有序序列的并集
• set_intersection 两个有序序列的交集
• set_difference 第一个序列存在，而第二个序列没有的

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

void printV(vector<int> v) {
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

int main() {

	vector<int> v1;
	v1.push_back(1);
	v1.push_back(3);
	v1.push_back(5);
	vector<int> v2;
	v2.push_back(1);
	v2.push_back(3);
	v2.push_back(6);
	vector<int> v3;
	v3.resize(v1.size() + v2.size());

	//set_union 两个有序序列的并集
	set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	printV(v3);//1 3 5 6 

	fill(v3.begin(), v3.end(), 0);//置0
	//set_intersection 两个有序序列的交集
	set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	printV(v3);//1 3

	fill(v3.begin(), v3.end(), 0);//置0
	//set_difference 第一个序列存在，而第二个序列没有的
	set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	printV(v3);//5


	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
29
30
31
32
33
34
35
36
37
38
39
40
41
42