自学C++ day16 stl 其他内容

// stl: 容器，适配器，算法，迭代器，仿函数以及空间适配器！

// 1.算法
//  （1） accumulate 
//  该算法作用是对区间中的元素进行累加，有以下两个版本！
#if 0
// 对区间[first,last)区间中的元素在init的基础上进行累加！
template <class InputIterator,class T>
T accumulate(InputIterator first, InputIterator last, T init);

// 对[first,last)区间中元素在init的基础上按照binary_op指定的操作进行累加。
template <class InputIterator,class T, class BinaryOperation>
T accumulate(InputIteartor first, InputIteartor last, T init, BinaryOpeartion binary_op);

// 注意使用时必须添加头文件
#include 

#endif 

#if 0

#include  
#include 
#include 
struct Mul2 {
	int operator()(int x, int y) {
		return x + 2 * y;
	}
};

int main() {
	// 对区间中的元素进行累加
	std::vector<int> v{ 10,20,30 };
	std::cout << accumulate(v.begin(), v.end(), 0) << std::endl;

	// 对区间中的每个元素乘2，让后累加
	std::cout << accumulate(v.begin(), v.end(), 0, Mul2());
	return 0;
}

#endif 



// （2） count 与 count_if 
//  该算法的作用是统计区间中某个元素的此数.
#if 0
// 统计value在区间[first,last) 中出现的此数！
template <class InputIterator,class T>
ptrdiff_t count(InputIterator first, InputIterator last, const T& value) {
	ptrdiff_t ret = 0;
	while (first != last) if (*first++ == value) ++ret;
	return ret;
}

// 统计满足 pred条件的元素在 [first,last) 中的个数
template <class InputIterator,class Predict>
ptrdiff_t count_if(InputIterator first, InputIterator last, Predicate pred) {
	ptrdiff_t ret = 0;
	while (first != last) {
		if (pred(*first++) == value) ret++;
	}
	return ret;
}
// 注意 使用时必须添加头文件
#include
#endif 

#if 0
#include 
#include
#include  

bool IsOdd(int i) {
	return (i % 2 == 1);
}

int main() {
	std::vector<int> v1{ 10,20,30,40,50,60,70,80,90 };
	std::cout << count(v1.begin(), v1.end(), 20) << std::endl;

	// 统计v2 中有多少个偶数！
	std::vector<int> v2{ 1,2,3,4,5,6,7,8,8,9,9,9,0,0,0 };
	std::cout << count_if(v2.begin(), v2.end(), IsOdd) << std::endl;
	return 0;
}

#endif 


// （3） find 与 find_if 
//	该算法是找元素在区间中第一次出现的位置
#if 0
	// 在[first,last) 中查找value第一次出现的位置，找到返回该元素的位置，否则返回last
	// 时间复杂度O(n)
	template <class InputItertor,class T>
	InputIterator find(InputIterator first, InputIterator last, const T& value) {
		for (; first != last; first++) {
			if (*first == value) break;
		}
		return first;
	}

	// 在[first,last)中查找满足pred条件的元素第一次出现的位置，找到返回该位置，否则返回last
	template <class InputItertor, class Predicate>
	InputIterator find_if(InputIterator first, InputIterator last, Predicate pred) {
		for (; first != last; first++) {
			if (pred(*first)) {
				break;
			}
		}
		return first;
	}
	// 注意使用时必须包含头文件 
#include 
#endif 


// （4） max 与 min
// max 返回两个元素中的较大值，min返回两个元素中较小值！
#if 0
	template <class T>
	const T& max(const T& a, const T& b) {
		return a < b ? b : a;
	}

	template <class T>
	const T& min(const T& a, const T& b) {
		return a < b ? a : b;
	}
	// 使用时必须包含头文件
#include  
#endif 


// （5）merge 
//		该算法的作用将两个有序序列合并成一个有序序列。

#if 0
template <class InputIterator1,class InputIterator2,class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2,
	OutputIterator result
) {
	while (true) {
		*result++ = (*first1 < *first2) ? *first1++ : *first2++;
		if (first1 == last1) return copy(first2, last2, result);
		if (firsr2 == last2) return copy(first1, last1, result);
	}
}
// 注意包含头文件
#include 
#endif 

#if 0
#include 
#include  
#include 
#include 

int main() {
	std::vector<int> v{ 2,3,4,5,6 };
	std::list<int> l{ 1,2,4,5,7 };

	sort(v.begin(), v.end());
	l.sort();

	std::vector<int> vRet(v.size() + l.size());
	merge(v.begin(), v.end(), l.begin(), l.end(), vRet.begin());
	for (auto e : vRet)
		std::cout << e << " ";
	std::cout << std::endl;
	return 0;
}

#endif


//  （6） partial_sort 
//  该算法的作用是: 找TOPK
#if 0
// 在[first,last) 中找前middle-first 个最小的元素,并存储在[first,middle) 中!	
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

// 在 [first,last) 中找前middle-first个最大或者最小的元素并存储在[first,middle) 中
template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare compare);
// 使用时必须包含头文件
#include 
#include 
#endif 

#if 0
#include 
#include 
#include 
#include  

int main() {
	std::vector<int> v1{ 4,1,2,8,0,8,3,5,6,7,10 };
	// 找到最小的4个!
	partial_sort(v1.begin(), v1.begin() + 4, v1.end());
	for (auto v : v1)
		std::cout << v << " ";
	std::cout << std::endl;

	// 找到最大的4 个!
	std::vector<int> v2{ 4,1,2,8,0,8,3,5,6,7,10 };
	partial_sort(v2.begin(), v2.begin() + 4, v2.end(), std::greater<int>());
	for (auto v : v2)
		std::cout << v << " ";
	std::cout << std::endl;
	return 0;
}

#endif 


// （7） partition 
//   该算法的作用是按照条件对区间中的元素进行划分.
#if 0
template <class BidirectionalIterator,class Predicate>
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred) {
	while (true) {
		while (first != last && pred(*first)) ++first;
		if (first == last--) break;
		while (first != last && pred(*last)) --last;
		if (first == last) break;
		swap(*first++, *last);
	}
	return first;
}
// 使用时一定要包含头文件
#include 
#endif 

#if 0
#include  
#include 
#include 

bool IsOdd(int i) {
	return (i % 2) == 1;
}

int main() {
	std::vector<int> v{ 0,1,2,3,4,5,6,7,8,9 };
	// 将区间中的元素分割成两个部分！
	auto div = partition(v.begin(), v.end(), IsOdd);

	for (auto it = v.begin(); it != div; it++)
		std::cout << *it << " ";
	std::cout << std::endl;

	for (auto it = div; it != v.end(); it++)
		std::cout << *it << " ";
	std::cout << std::endl;
	return 0;
}
#endif 

// （8） reverse
// 该算法的作用是对区间中的元素进行逆置，使用时必须包含头文件.algorithm
#if 0
template <class BidrectionalIterator>
void reverse(BidredictionalIterator first, BidredictionalIterator last) {
	while (first != last && first != --last) swap(*first++, *last);
}
#endif 


// （9） sort 
//  两个版本：
//   （1） sort(first,last) : 默认按照小于的方式排序，排序结果为升序，一般用于排序内置类型。
//   （2） sort(first,last,comp) : 可以通过comp更改元素比较方式，即可以指定排序结果，一般以仿函数和函数指针提供。
//    sort 并不是一种排序算法，而是将多个排序算法混合而成。
//    当元素个数少于 _stl_threshold 阈值 16 时，使用直接插入排序处理.
//    当元素个数超过_stl_threshold 时，考虑是否能用快排的方式排序，应为当元素数量达到一定程度，递归快排可能会导致栈溢出。
//    因此通过_lg 函数判断函数递归深度。
#if 0 
	template <calss Size>
	inline Size _lg(Size n) {
		Size k;
		for (k = 0; n > 1; n >>= 1)++;
		return k;
	}
#endif 
// 如果递归的深度没有超过2*log2N 时，则使用快排的方式排序。
// 如果递归的深度超过2*log2N 时，说明数据量打，递归层次抬升，可能导致栈溢出，此时使用堆排序.




// （10） unique 
// 该函数的作用是删除区间中相邻的重复元素，确保元素唯一性，注意在使用前要保证区间中的元素是有序的，才能达到真正的去重。

#if 0
	// 元素不想等时，用后一个将前一个元素覆盖掉
	template <class ForwardIteartor>
	ForwardIteartor unique(ForwardIteartor first, ForwardIteartor last);

	// 如果元素不满足pred条件时，后一个元素将前依噶元素覆盖掉.
	template <class ForwardIteartor,class BinaryPredicate>
	ForwardIteartor unique(ForwardIteartor first, ForwardIteartor last, BinaryPredicate pred);

	template <class ForwardIteartor>
	ForwardIteartor unique(ForwardIteartor first, ForwardIteartor last) {
		ForwardIteartor result = first;
		while (++first != last) {
			if (!(*result == *first)) {
				*(++result) = *first;
			}
		}
		return ++result;
	}
	// 注意这函数并不是将重复的元素删除掉，而是用后面不重复的元素将前面重复的元素覆盖掉了！
	// 返回值时一个迭代器，指向的是去重后容器中不重复最后一个元素的下一个位置。
	// 干函数需要配合erase 才能真正的将元素删除掉.
#endif 

#if 0
#include  
#include 
#include 
	using namespace std;
	int main() {
		vector<int> v{ 1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1 };
		auto it = unique(v.begin(), v.end());
		for (auto e : v) 
			cout << e << " ";
		cout << endl;


		v.erase(it, v.end());
		for (auto e : v)
			cout << e << " ";
		cout << endl;

		// 先对区间中的元素进行排序，另重复元素放在相邻位置
		sort(v.begin(), v.end());
		for (auto e : v)
			cout << e << " ";
		cout << endl;

		// 使用 unique 将重复元素覆盖掉！
		it = unique(v.begin(), v.end());

		v.erase(it, v.end());
		for (auto e : v)
			cout << e << " ";
		cout << endl;
		return 0;
	}
	
#endif 


// （11） next_permutation 和 pre_permutation 
//  next_permutation 是获取一个排序的下一个排列，可以遍历全排列，prev_permutation 刚好相反，获取排列的前一个排列！

#if 0
#include 
#include  
#include 
#include 
	using namespace std;
	int main() {
		// 因为next_permutation函数是按照大于字典序获取下一个排列组合的
		// 因此在排列时，必须保证序列是升序的
		vector<int> v = { 4,1,2,3 };
		sort(v.begin(), v.end());

		do {
			for (auto e : v)
				cout << e << " ";
			cout << endl;
		}while (next_permutation(v.begin(), v.end()));

		// 因为prev_permutation 函数是按照小于字典序获取下一个排列组合的,因此在排列时，必须保证序列是降序的
		sort(v.begin(), v.end(), greater<int>());
		do {
			for (auto e : v)
				cout << e << " ";
			cout << endl;
		} while (prev_permutation(v.begin(), v.end()));
		return 0;
	}
#endif 



//  2. 迭代器 Iterator 之前弄过现在就不弄了!


//  3. 适配器:又接着配接器,是一种设计模式,简单的说: 需要的东西就在眼前,但是由于接口不对而无法使用
//  需要对接口进行转化以方便使用.
//  即: 将一个类的接口转换成用户希望的另一个类的接口,是原本接口不兼容的类可以一起工作.

// 适配器总共三种:
//  (1) 容器适配器- stack & queue 
//  (2) 迭代器适配器,反向迭代器.
//  (3) 函数适配器.




// 4. 仿函数
// 一种具有函数特征的对象,调用者可以想函数一样使用该对象,为了能够欣慰类似函数,该对象所在类必须自定义函数调用运算符
// operator() ,重载该运算符后,就可以在仿函数对象的后面带商一堆小括号以此调用防函数!

#if 0
#include 
#include  
#include 
#include 
	using namespace std;
	class Mul2 {
	public:
		void operator()(int& data) {
			data <<= 1;
		}
	};

	class Mod3 {
	public:
		bool operator()(int data) {
			return 0 == data % 3;
		}
	};

	int main() {
		vector<int> v{ 1,2,3,4,5,6,7,8,9 };
		// 给所有元素*2;
		for_each(v.begin(), v.end(), Mul2());
		for (auto e : v)
			cout << e << " ";
		cout << endl;

		// 删除容器中3的倍数!
		auto pos = remove_if(v.begin(), v.end(), Mod3());
		v.erase(pos, v.end());

		for_each(v.begin(), v.end(), [](int data) {cout << data << " "; });
		cout << endl;

		return 0;
	}


#endif 
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451