-
Notifications
You must be signed in to change notification settings - Fork 1
/
stl_algo.h
executable file
·3356 lines (3095 loc) · 140 KB
/
stl_algo.h
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
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
/* NOTE: This is an internal header file, included by other STL headers.
* You should not attempt to use it directly.
*/
#ifndef __SGI_STL_INTERNAL_ALGO_H
#define __SGI_STL_INTERNAL_ALGO_H
#include <stl_heap.h> //包含了make_heap, push_heap, pop_heap和sort_heap等算法
// See concept_checks.h for the concept-checking macros
// __STL_REQUIRES, __STL_CONVERTIBLE, etc.
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1209
#endif
// __median (an extension, not present in the C++ standard).
// 三点中值决定函数
template <class _Tp>
inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
__STL_REQUIRES(_Tp, _LessThanComparable);
if (__a < __b)
if (__b < __c) //a < b < c
return __b;
else if (__a < __c) //a < b, b >= c, a < c
return __c;
else
return __a;
else if (__a < __c) //c > a >= b
return __a;
else if (__b < __c) //c > a >= b
return __c;
else //a >= b, a >= c, b < c
return __b;
}
template <class _Tp, class _Compare>
inline const _Tp&
__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
__STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
if (__comp(__a, __b))
if (__comp(__b, __c))
return __b;
else if (__comp(__a, __c))
return __c;
else
return __a;
else if (__comp(__a, __c))
return __a;
else if (__comp(__b, __c))
return __c;
else
return __b;
}
// for_each将仿函数f施行于[first, last)区间的每一个元素身上，f不可以改变元素内容，因为first和last都是输入迭代器InputIterators
// 不保证接受赋值行为(assignment), 如果想一一修改元素内容，应该使用算法transform(), f可返回一个值，但该值会被忽略
// for_each. Apply a function to every element of a range.
template <class _InputIter, class _Function>
_Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
__STL_REQUIRES(_InputIter, _InputIterator);
for ( ; __first != __last; ++__first)
__f(*__first); //调用仿函数f的function call操作符，返回值被忽略
return __f;
}
// find and find_if.
// 根据equality操作符，循序查找[first, last)内的所有元素，找出第一个匹配
// 等同条件者，如果找到就返回一个输入迭代器(Inputiterator)指向该元素，否则返回迭代器last
template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
const _Tp& __val,
input_iterator_tag)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}
// 根据指定的pred运算条件(以仿函数表示)，循序查找[first, last)内的所有元素，找出第一个令pred
// 运算结果为true者，如果找到就返回一个输入迭代器(Inputiterator)指向该元素，否则返回迭代器last
template <class _InputIter, class _Predicate>
inline _InputIter find_if(_InputIter __first, _InputIter __last,
_Predicate __pred,
input_iterator_tag)
{
while (__first != __last && !__pred(*__first))
++__first;
return __first;
}
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _RandomAccessIter, class _Tp>
_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
const _Tp& __val,
random_access_iterator_tag)
{
typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
= (__last - __first) >> 2;
for ( ; __trip_count > 0 ; --__trip_count) {
if (*__first == __val) return __first;
++__first;
if (*__first == __val) return __first;
++__first;
if (*__first == __val) return __first;
++__first;
if (*__first == __val) return __first;
++__first;
}
switch(__last - __first) {
case 3:
if (*__first == __val) return __first;
++__first;
case 2:
if (*__first == __val) return __first;
++__first;
case 1:
if (*__first == __val) return __first;
++__first;
case 0:
default:
return __last;
}
}
template <class _RandomAccessIter, class _Predicate>
_RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
_Predicate __pred,
random_access_iterator_tag)
{
typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
= (__last - __first) >> 2;
for ( ; __trip_count > 0 ; --__trip_count) {
if (__pred(*__first)) return __first;
++__first;
if (__pred(*__first)) return __first;
++__first;
if (__pred(*__first)) return __first;
++__first;
if (__pred(*__first)) return __first;
++__first;
}
switch(__last - __first) {
case 3:
if (__pred(*__first)) return __first;
++__first;
case 2:
if (__pred(*__first)) return __first;
++__first;
case 1:
if (__pred(*__first)) return __first;
++__first;
case 0:
default:
return __last;
}
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
const _Tp& __val)
{
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_InputIter>::value_type, _Tp);
return find(__first, __last, __val, __ITERATOR_CATEGORY(__first));
}
template <class _InputIter, class _Predicate>
inline _InputIter find_if(_InputIter __first, _InputIter __last,
_Predicate __pred) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
}
// adjacent_find. 找出第一组满足条件的相邻元素，默认条件是两元素相等，或用户指定二元运算
template <class _ForwardIter>
_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
if (__first == __last)
return __last;
_ForwardIter __next = __first;
while(++__next != __last) {
if (*__first == *__next) //找到相邻的元素值相同就结束
return __first;
__first = __next;
}
return __last;
}
template <class _ForwardIter, class _BinaryPredicate>
_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
_BinaryPredicate __binary_pred) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
typename iterator_traits<_ForwardIter>::value_type,
typename iterator_traits<_ForwardIter>::value_type);
if (__first == __last)
return __last;
_ForwardIter __next = __first;
while(++__next != __last) { //找到相邻的元素符合外界指定条件，就结束
if (__binary_pred(*__first, *__next)) //两个操作数分别是相邻的第一个元素和第二个元素
return __first;
__first = __next;
}
return __last;
}
// count and count_if. There are two version of each, one whose return type
// type is void and one (present only if we have partial specialization)
// whose return type is iterator_traits<_InputIter>::difference_type. The
// C++ standard only has the latter version, but the former, which was present
// in the HP STL, is retained for backward compatibility.
// 利用equality操作符，将[first, last)区间的每一个元素拿来和指定值value比较，并返回与value相等的元素个数
template <class _InputIter, class _Tp, class _Size>
void count(_InputIter __first, _InputIter __last, const _Tp& __value,
_Size& __n) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp, _EqualityComparable);
for ( ; __first != __last; ++__first) //整个区间走一遍
if (*__first == __value) //如果元素值和value相等
++__n; //计数器累加1
}
template <class _InputIter, class _Predicate, class _Size>
void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
_Size& __n) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
for ( ; __first != __last; ++__first) //整个区间走一遍
if (__pred(*__first)) //如果元素带入pred的运算结果为true
++__n; //计数器累加1
}
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _InputIter, class _Tp>
typename iterator_traits<_InputIter>::difference_type
count(_InputIter __first, _InputIter __last, const _Tp& __value) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp, _EqualityComparable); //以下声明一个计数器n
typename iterator_traits<_InputIter>::difference_type __n = 0;
for ( ; __first != __last; ++__first)
if (*__first == __value)
++__n;
return __n;
}
template <class _InputIter, class _Predicate>
typename iterator_traits<_InputIter>::difference_type
count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
typename iterator_traits<_InputIter>::difference_type __n = 0; //声明一个计数器n
for ( ; __first != __last; ++__first)
if (__pred(*__first))
++__n;
return __n;
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// search.在序列一[first1, last1)所蕴盖的区间中，查找序列二[first2, last2)的首次出现点
// 如果序列一内不存在与序列二完全匹配的子序列，返回迭代器last1
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2)
{
__STL_REQUIRES(_ForwardIter1, _ForwardIterator);
__STL_REQUIRES(_ForwardIter2, _ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_ForwardIter1>::value_type,
typename iterator_traits<_ForwardIter2>::value_type);
// Test for empty ranges
if (__first1 == __last1 || __first2 == __last2)
return __first1;
// Test for a pattern of length 1.
_ForwardIter2 __tmp(__first2);
++__tmp;
if (__tmp == __last2)
return find(__first1, __last1, *__first2);
// General case.
_ForwardIter2 __p1, __p;
__p1 = __first2; ++__p1;
_ForwardIter1 __current = __first1;
while (__first1 != __last1) { //遍历整个第一序列
__first1 = find(__first1, __last1, *__first2); //查找第二个元素的头是否在第一个序列中
if (__first1 == __last1)
return __last1; //不在则返回__last1
__p = __p1;
__current = __first1;
if (++__current == __last1)
return __last1;
while (*__current == *__p) {
if (++__p == __last2)
return __first1;
if (++__current == __last1)
return __last1;
}
++__first1;
}
return __first1;
}
template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
_BinaryPred __predicate)
{
__STL_REQUIRES(_ForwardIter1, _ForwardIterator);
__STL_REQUIRES(_ForwardIter2, _ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool,
typename iterator_traits<_ForwardIter1>::value_type,
typename iterator_traits<_ForwardIter2>::value_type);
// Test for empty ranges
if (__first1 == __last1 || __first2 == __last2)
return __first1;
// Test for a pattern of length 1.
_ForwardIter2 __tmp(__first2);
++__tmp;
if (__tmp == __last2) {
while (__first1 != __last1 && !__predicate(*__first1, *__first2))
++__first1;
return __first1;
}
// General case.
_ForwardIter2 __p1, __p;
__p1 = __first2; ++__p1;
_ForwardIter1 __current = __first1;
while (__first1 != __last1) {
while (__first1 != __last1) {
if (__predicate(*__first1, *__first2))
break;
++__first1;
}
while (__first1 != __last1 && !__predicate(*__first1, *__first2))
++__first1;
if (__first1 == __last1)
return __last1;
__p = __p1;
__current = __first1;
if (++__current == __last1) return __last1;
while (__predicate(*__current, *__p)) {
if (++__p == __last2)
return __first1;
if (++__current == __last1)
return __last1;
}
++__first1;
}
return __first1;
}
// search_n. Search for __count consecutive copies of __val.
// 在序列[first, last)所涵盖的区间中，查找连续count个符合条件的元素所形成的子序列
// 并返回一个迭代器指向该子序列起始处
template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp, _EqualityComparable);
// 查找元素value连续出现count次所形成的那个子序列，返回其发生的位置
if (__count <= 0)
return __first;
else {
__first = find(__first, __last, __val); //首先找出value第一次出现的位置
while (__first != __last) { //继续查找下一位置
_Integer __n = __count - 1; //value还应出现n次
_ForwardIter __i = __first; //从上次出现点接着查找
++__i;
while (__i != __last && __n != 0 && *__i == __val) { //下一个元素是value, good。
++__i;
--__n; //既然找到了，value应再出现次数应减1
} //回到内循环继续查找
if (__n == 0) //n==0表示确实找到了元素出现n次的子序列, 功德圆满
return __first; //返回起始位置
else //功德未圆满
__first = find(__i, __last, __val); //找value的下一个出现点，准备回到外循环
}
return __last; //没有找到则返回__last
}
}
template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val,
_BinaryPred __binary_pred) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool,
typename iterator_traits<_ForwardIter>::value_type, _Tp);
if (__count <= 0)
return __first;
else {
while (__first != __last) {
if (__binary_pred(*__first, __val)) //首先找出第一个符合条件的位置
break;
++__first; //找到就离开
}
while (__first != __last) { //继续查找
_Integer __n = __count - 1; //还有n个连续元素符合条件
_ForwardIter __i = __first; //从上次出现点接着往下查找
++__i; //以下循环确定接下来count-1个元素是否符合条件
while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
++__i;
--__n; //既然这个元素符合条件，符合条件的元素个数就减1
}
if (__n == 0) //功德圆满，__n == 0表示确实找到了count个符合条件的元素
return __first;
else { //功德未圆满
while (__i != __last) {
if (__binary_pred(*__i, __val)) //找value的下一个符合条件的元素
break;
++__i;
}
__first = __i; //准备回到外循环
}
}
return __last;
}
}
// swap_ranges 将[first1, last1)区间内的元素与从first2开始、个数相同的元素互相交换
// 返回一个迭代器，指向第二序列中最后一个被交换元素的下一位置 (将两端等长区间的元素互换)
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2) {
__STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator);
__STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator);
__STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type,
typename iterator_traits<_ForwardIter2>::value_type);
__STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type,
typename iterator_traits<_ForwardIter1>::value_type);
for ( ; __first1 != __last1; ++__first1, ++__first2)
iter_swap(__first1, __first2); //等长区间的元素互换
return __first2;
}
// transform()的第一版本以仿函数op作用于[first, last)中的每一个元素身上，并以其结果产生出一个新序列
// 第二个版本以仿函数binary_op作用域一双元素身上(一个来自[first1, last)，另一个来自first2开始的序列)，并以其结果产生出一个新序列
// 把结果放进result容器中; result可以指向源端容器; 返回值OutputIterator将指向结果序列的最后元素的下一位置
template <class _InputIter, class _OutputIter, class _UnaryOperation>
_OutputIter transform(_InputIter __first, _InputIter __last,
_OutputIter __result, _UnaryOperation __opr) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __first != __last; ++__first, ++__result)
*__result = __opr(*__first); //每个元素执行__opr()仿函数操作
return __result;
}
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _BinaryOperation>
_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _OutputIter __result,
_BinaryOperation __binary_op) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
*__result = __binary_op(*__first1, *__first2); //每个元素执行__binary_op()仿函数操作
return __result;
}
// replace, replace_if, replace_copy, replace_copy_if
// replace将[first, last)区间内的所有old_value都用new_value取代
template <class _ForwardIter, class _Tp>
void replace(_ForwardIter __first, _ForwardIter __last,
const _Tp& __old_value, const _Tp& __new_value) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_ForwardIter>::value_type, _Tp);
__STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
for ( ; __first != __last; ++__first)
if (*__first == __old_value) //将区间内所有__old_value用__new_value代替
*__first = __new_value;
}
// replace_if将[first, last)区间内所有被pred评估为true的元素，都以new_value取而代之
template <class _ForwardIter, class _Predicate, class _Tp>
void replace_if(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred, const _Tp& __new_value) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_ForwardIter>::value_type);
for ( ; __first != __last; ++__first)
if (__pred(*__first))
*__first = __new_value;
}
// 行为和replace类似，唯一不同的是新序列会被复制到result所指的容器中
// 返回值OutputIterator指向被复制的最后一个元素的下一位置(原序列没有任何改变)
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter replace_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
const _Tp& __old_value, const _Tp& __new_value) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_InputIter>::value_type, _Tp);
for ( ; __first != __last; ++__first, ++__result) //如果旧序列上的元素等于__old_value，就放__new_value到新序列中
*__result = *__first == __old_value ? __new_value : *__first; //否则将元素拷贝一份放进新序列中
return __result;
}
// replace_copy_if行为与replace_if()类似，但是新序列会被复制到result所指的区间内
// 返回值OutputIterator指向被复制的最后一个元素的下一位置，原序列无任何改变
template <class _InputIter, class _OutputIter, class _Predicate, class _Tp>
_OutputIter replace_copy_if(_InputIter __first, _InputIter __last,
_OutputIter __result,
_Predicate __pred, const _Tp& __new_value) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
for ( ; __first != __last; ++__first, ++__result) //如果旧序列上的元素被pred评估为true,就放new_value到新序列中
*__result = __pred(*__first) ? __new_value : *__first; //否则将元素拷贝一份放进新序列中
return __result;
}
// generate and generate_n
// 将仿函数gen的运算结果填写在[first, last)区间上的所有元素身上，
// 所谓填写使用迭代器的赋值操作符(assignment)
template <class _ForwardIter, class _Generator>
void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_GENERATOR_CHECK(_Generator,
typename iterator_traits<_ForwardIter>::value_type);
for ( ; __first != __last; ++__first) //遍历整个区间1
*__first = __gen();
}
// 将仿函数gen的运算结果填写在从first开始的n个元素上，
// 所谓填写使用迭代器的赋值操作符(assignment)
template <class _OutputIter, class _Size, class _Generator>
_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __n > 0; --__n, ++__first) //只限于n个元素
*__first = __gen();
return __first;
}
// remove, remove_if, remove_copy, remove_copy_if
// remove_copy原容器没有任何改变，而是将结果复制到一个以result标示起始位置的容器身上
// 新容器可以和原容器重合，但新容器大小，会出错; 返回值为OutputIterator指出被复制的最后元素的下一位置
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter remove_copy(_InputIter __first, _InputIter __last,
_OutputIter __result, const _Tp& __value) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_InputIter>::value_type, _Tp);
for ( ; __first != __last; ++__first)
if (!(*__first == __value)) { //如果不相等
*__result = *__first; //就赋值给新容器
++__result; //新容器前进一个位置
}
return __result;
}
// remove_copy_if移除[first, last)区间内所有被仿生函数pred评估为true的元素
// 返回值OutputIterator指出被复制的最后元素的下一位置
template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
_OutputIter __result, _Predicate __pred) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_InputIter>::value_type);
for ( ; __first != __last; ++__first)
if (!__pred(*__first)) { //如果pred核定为false
*__result = *__first; //就赋值给新容器(保留，不删除)
++__result; //新容器前进一个位置
}
return __result;
}
// 移除[first, last)中所有与value相等的元素; 这一算法并不真正从容器中删除那些元素
// 而是将每一个不与value相等的元素轮番赋值给first之后的空间，返回一个前向迭代器(Forwarditerator)
// 标示出重新整理后的最后元素的下一个位置
// 注意: array不适合使用remove()和remove_if()，因为array无法缩小尺寸，导致残留元素一直存在
// 对array而言，较受欢迎的算法是remove_copy()和remove_copy_if().
template <class _ForwardIter, class _Tp>
_ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
const _Tp& __value) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_ForwardIter>::value_type, _Tp);
__STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
__first = find(__first, __last, __value); //利用循环查找法找出第一个相等元素
_ForwardIter __i = __first; //以i标示出来
return __first == __last ? __first //利用remove_copy允许新旧容器重叠，进行移除操作
: remove_copy(++__i, __last, __first, __value); //将结果指定置于原容器中
}
// 从容器中真正删除那些元素，每一个不符合pred条件的元素都会被轮番赋值给first之后的空间
// 返回一个前向迭代器(ForwardIterator)标示出重新整理后的最后元素的下一位置
template <class _ForwardIter, class _Predicate>
_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
typename iterator_traits<_ForwardIter>::value_type);
__first = find_if(__first, __last, __pred); //利用循环查找法找出第一个相等元素
_ForwardIter __i = __first; //以i标示出来
return __first == __last ? __first //利用remove_copy_if允许新旧容器重叠，做删除操作
: remove_copy_if(++__i, __last, __first, __pred); //并将结果放到原容器中
}
// unique and unique_copy
// unique_copy()算法可从[first, last)中将元素复制到result开始的区间上
// 如果有相邻重复元素群，只复制其中第一个元素，返回的迭代器指向以result开头的区间尾端
// 原始指针版本
// output iterator为只写(write only), 无法像forward iterator版本那样可以读取
// 不能有类似__result != *__first这样的操作
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result, _Tp*) {
_Tp __value = *__first; //记录第一个元素
*__result = __value; //遍历整个区间
while (++__first != __last)
if (!(__value == *__first)) { //元素不同就记录，相同就跳过
__value = *__first;
*++__result = __value;
}
return ++__result;
}
// output_iterator_tag版本
template <class _InputIter, class _OutputIter>
inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
output_iterator_tag) { //output iterator有些功能限制，必须先知道其value tyoe
return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
}
// forward_iterator_tag版本
template <class _InputIter, class _ForwardIter>
_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result, forward_iterator_tag) {
*__result = *__first;
while (++__first != __last)
if (!(*__result == *__first))
*++__result = *__first;
return ++__result;
}
// 根据result迭代器版本做不同的处理
template <class _InputIter, class _OutputIter>
inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
_EqualityComparable);
if (__first == __last) return __result;
return __unique_copy(__first, __last, __result,
__ITERATOR_CATEGORY(__result));
}
template <class _InputIter, class _OutputIter, class _BinaryPredicate,
class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
_BinaryPredicate __binary_pred, _Tp*) {
__STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, _Tp, _Tp);
_Tp __value = *__first;
*__result = __value;
while (++__first != __last)
if (!__binary_pred(__value, *__first)) {
__value = *__first;
*++__result = __value;
}
return ++__result;
}
template <class _InputIter, class _OutputIter, class _BinaryPredicate>
inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
_BinaryPredicate __binary_pred,
output_iterator_tag) {
return __unique_copy(__first, __last, __result, __binary_pred,
__VALUE_TYPE(__first));
}
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result,
_BinaryPredicate __binary_pred,
forward_iterator_tag) {
__STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
typename iterator_traits<_ForwardIter>::value_type,
typename iterator_traits<_InputIter>::value_type);
*__result = *__first;
while (++__first != __last)
if (!__binary_pred(*__result, *__first)) *++__result = *__first;
return ++__result;
}
template <class _InputIter, class _OutputIter, class _BinaryPredicate>
inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
_BinaryPredicate __binary_pred) {
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
if (__first == __last) return __result;
return __unique_copy(__first, __last, __result, __binary_pred,
__ITERATOR_CATEGORY(__result));
}
// unique算法函数可以移除重复的元素，但只能移除相邻的重复元素，保留重复中最后一个元素
template <class _ForwardIter>
_ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
__first = adjacent_find(__first, __last); //首先找到相邻元素的起点
return unique_copy(__first, __last, __first); //利用unique完成
}
// 用户自己定义准则__binary_pred
template <class _ForwardIter, class _BinaryPredicate>
_ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
_BinaryPredicate __binary_pred) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
typename iterator_traits<_ForwardIter>::value_type,
typename iterator_traits<_ForwardIter>::value_type);
__first = adjacent_find(__first, __last, __binary_pred);
return unique_copy(__first, __last, __first, __binary_pred);
}
// reverse and reverse_copy, and their auxiliary functions
// reverse的双向迭代器版本(bidirectional iterator)
template <class _BidirectionalIter>
void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
bidirectional_iterator_tag) {
while (true)
if (__first == __last || __first == --__last)
return;
else
iter_swap(__first++, __last);
}
// reverse的随机迭代器版本(random access iterator)
template <class _RandomAccessIter>
void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
random_access_iterator_tag) {
while (__first < __last) //一下头尾两两互换，然后头部累金一个位置，尾部累退一个位置，两者交错式即停止
iter_swap(__first++, --__last); //注意: 只有random iterators才能做__first < __last的判断
}
// reverse将序列[first, last)内的元素在容器中颠倒重排
// 迭代器双向和随机定位能力，影响了这个算法的效率，所以设计采用双层架构
// 分派函数(dispatch function)
template <class _BidirectionalIter>
inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
__STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
__reverse(__first, __last, __ITERATOR_CATEGORY(__first));
}
//reverse_copy行为类似reverse(), 但产生出来的新序列会被置于以result指出的容器中
//返回值OutputIterator指向新产生的最后元素的下一位置，原序列没有任何改变
template <class _BidirectionalIter, class _OutputIter>
_OutputIter reverse_copy(_BidirectionalIter __first,
_BidirectionalIter __last,
_OutputIter __result) {
__STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
while (__first != __last) { //整个序列走一遍
--__last; //尾端前一个位置
*__result = *__last; //将尾端所指元素复制到result所指位置
++__result; //result前进一个位置
}
return __result;
}
// rotate and rotate_copy, and their auxiliary functions
// 求最大公因子的算法函数__gcd利用辗转相除法
// __gcd应用于__rotate()的Random Access Iterator版本
template <class _EuclideanRingElement>
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
_EuclideanRingElement __n)
{
while (__n != 0) { //一直迭代取余
_EuclideanRingElement __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
// 以下根据不同迭代器类型完成三个旋转操作
// 前向迭代器版本(forward iterator)
template <class _ForwardIter, class _Distance>
_ForwardIter __rotate(_ForwardIter __first,
_ForwardIter __middle,
_ForwardIter __last,
_Distance*,
forward_iterator_tag) {
if (__first == __middle) //如果要旋转的点在头
return __last; //直接返回尾
if (__last == __middle) //如果要旋转的点在尾
return __first; //直接返回头
_ForwardIter __first2 = __middle;
do {
swap(*__first++, *__first2++); //前段、后段的元素一一交换，并双双前进一
if (__first == __middle) //判断是前段[first, middle)先结束还是[middle, last)先结束
__middle = __first2; //前段先结束
} while (__first2 != __last);
_ForwardIter __new_middle = __first;
__first2 = __middle;
while (__first2 != __last) {
swap (*__first++, *__first2++);
if (__first == __middle)
__middle = __first2;
else if (__first2 == __last) //后段先结束
__first2 = __middle;
}
return __new_middle; //返回旋转点
}
// 双向迭代器版本(bidirectional iterator)
template <class _BidirectionalIter, class _Distance>
_BidirectionalIter __rotate(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last,
_Distance*,
bidirectional_iterator_tag) {
__STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
if (__first == __middle)
return __last;
if (__last == __middle)
return __first;
__reverse(__first, __middle, bidirectional_iterator_tag());
__reverse(__middle, __last, bidirectional_iterator_tag());
while (__first != __middle && __middle != __last)
swap (*__first++, *--__last);
if (__first == __middle) {
__reverse(__middle, __last, bidirectional_iterator_tag());
return __last;
}
else {
__reverse(__first, __middle, bidirectional_iterator_tag());
return __first;
}
}
// 随机访问迭代器版本(Random Access Iterator)
template <class _RandomAccessIter, class _Distance, class _Tp>
_RandomAccessIter __rotate(_RandomAccessIter __first,
_RandomAccessIter __middle,
_RandomAccessIter __last,
_Distance *, _Tp *) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
_Distance __n = __last - __first;
_Distance __k = __middle - __first;
_Distance __l = __n - __k;
_RandomAccessIter __result = __first + (__last - __middle);
if (__k == 0)
return __last;
else if (__k == __l) {
swap_ranges(__first, __middle, __middle);
return __result;
}
_Distance __d = __gcd(__n, __k); //取全长和前段长度的最大公因子
// 一下迭代器的相减操作，只适用于随机访问迭代器(random access iterators)
for (_Distance __i = 0; __i < __d; __i++) {
_Tp __tmp = *__first;
_RandomAccessIter __p = __first;
if (__k < __l) {
for (_Distance __j = 0; __j < __l/__d; __j++) {
if (__p > __first + __l) {
*__p = *(__p - __l);
__p -= __l;
}
*__p = *(__p + __k);
__p += __k;
}
}
else {
for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
if (__p < __last - __k) {
*__p = *(__p + __k);
__p += __k;
}
*__p = * (__p - __l);
__p -= __l;
}
}
*__p = __tmp;
++__first;
}
return __result;
}
// rotate算法将[first, middle)内的元素和[middle, last)内的元素互换; middle所指的元素会成为容器的第一个元素
// 看起来和swap_ranges()功能颇为相似，但swap_ranges()只能交换两个长度相同的区间，rotate()可以交换两个长度不同的区间
// 迭代器的移动功能，影响了这个算法的效率(所以设计为双层架构) 分派函数(dispatch function)
template <class _ForwardIter>
inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
_ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
return __rotate(__first, __middle, __last,
__DISTANCE_TYPE(__first),
__ITERATOR_CATEGORY(__first));
}
// 行为类似rotate()，但产生的结果置于result所指出的容器中,返回值OutputIterator所指向新产生的最后元素的下一位置
template <class _ForwardIter, class _OutputIter>
_OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
_ForwardIter __last, _OutputIter __result) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
return copy(__first, __middle, copy(__middle, __last, __result)); //旋转其实质是两端元素彼此交换(因为不需要在原容器中调整内容，直接可以调用copy)
}
// Return a random number in the range [0, __n). This function encapsulates
// whether we're using rand (part of the standard C library) or lrand48
// (not standard, but a much better choice whenever it's available).
template <class _Distance>
inline _Distance __random_number(_Distance __n) {
#ifdef __STL_NO_DRAND48
return rand() % __n;
#else
return lrand48() % __n;