1 : // algorithm standard header
2 : #pragma once
3 : #ifndef _ALGORITHM_
4 : #define _ALGORITHM_
5 : #ifndef RC_INVOKED
6 : #include <memory>
7 :
8 : #ifdef _MSC_VER
9 : #pragma pack(push,_CRT_PACKING)
10 : #pragma warning(push,3)
11 : #pragma warning(disable: 4244)
12 : #endif /* _MSC_VER */
13 :
14 : _STD_BEGIN
15 :
16 : // COMMON SORT PARAMETERS
17 : const int _ISORT_MAX = 32; // maximum size for insertion sort
18 :
19 : // TEMPLATE FUNCTION for_each
20 : template<class _InIt,
21 : class _Fn1> inline
22 : _Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
23 45 : { // perform function for each element
24 45 : _DEBUG_RANGE(_First, _Last);
25 45 : _DEBUG_POINTER(_Func);
26 45 : _CHECKED_BASE_TYPE(_InIt) _ChkFirst(_CHECKED_BASE(_First));
27 45 : _CHECKED_BASE_TYPE(_InIt) _ChkLast(_CHECKED_BASE(_Last));
28 45 : for (; _ChkFirst != _ChkLast; ++_ChkFirst)
29 27 : _Func(*_ChkFirst);
30 45 : return (_Func);
31 45 : }
32 :
33 : // TEMPLATE FUNCTION find
34 : template<class _InIt, class _Ty>
35 : inline
36 : _InIt _Find(_InIt _First, _InIt _Last, const _Ty& _Val)
37 : { // find first matching _Val
38 : _DEBUG_RANGE(_First, _Last);
39 : for (; _First != _Last; ++_First)
40 : if (*_First == _Val)
41 : break;
42 : return (_First);
43 : }
44 :
45 : inline const char *_Find(const char *_First, const char *_Last, int _Val)
46 : { // find first char that matches _Val
47 : _DEBUG_RANGE(_First, _Last);
48 : _First = (const char *)::memchr(_First, _Val, _Last - _First);
49 : return (_First == 0 ? _Last : _First);
50 : }
51 :
52 : inline const signed char *_Find(const signed char *_First,
53 : const signed char *_Last, int _Val)
54 : { // find first signed char that matches _Val
55 : _DEBUG_RANGE(_First, _Last);
56 : _First = (const signed char *)::memchr(_First, _Val,
57 : _Last - _First);
58 : return (_First == 0 ? _Last : _First);
59 : }
60 :
61 : inline const unsigned char *_Find(const unsigned char *_First,
62 : const unsigned char *_Last, int _Val)
63 : { // find first unsigned char that matches _Val
64 : _DEBUG_RANGE(_First, _Last);
65 : _First = (const unsigned char *)::memchr(_First, _Val,
66 : _Last - _First);
67 : return (_First == 0 ? _Last : _First);
68 : }
69 :
70 : template<class _InIt, class _Ty>
71 : inline
72 : _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
73 : { // find first matching _Val
74 : _ASSIGN_FROM_BASE(_First,
75 : _Find(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val));
76 : return (_First);
77 : }
78 :
79 : // TEMPLATE FUNCTION find_if
80 : template<class _InIt,
81 : class _Pr> inline
82 : _InIt _Find_if(_InIt _First, _InIt _Last, _Pr _Pred)
83 9 : { // find first satisfying _Pred
84 9 : _DEBUG_RANGE(_First, _Last);
85 9 : _DEBUG_POINTER(_Pred);
86 9 : for (; _First != _Last; ++_First)
87 9 : if (_Pred(*_First))
88 9 : break;
89 9 : return (_First);
90 9 : }
91 :
92 : template<class _InIt,
93 : class _Pr> inline
94 : _InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
95 9 : { // find first satisfying _Pred
96 9 : _ASSIGN_FROM_BASE(_First,
97 : _Find_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
98 9 : return (_First);
99 9 : }
100 :
101 : // TEMPLATE FUNCTION adjacent_find
102 : template<class _FwdIt> inline
103 : _FwdIt _Adjacent_find(_FwdIt _First, _FwdIt _Last)
104 : { // find first matching successor
105 : _DEBUG_RANGE(_First, _Last);
106 : for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
107 : if (*_Firstb == *_First)
108 : return (_Firstb);
109 : return (_Last);
110 : }
111 :
112 : template<class _FwdIt> inline
113 : _FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)
114 : { // find first matching successor
115 : _ASSIGN_FROM_BASE(_First,
116 : _Adjacent_find(_CHECKED_BASE(_First), _CHECKED_BASE(_Last)));
117 : return (_First);
118 : }
119 :
120 : // TEMPLATE FUNCTION adjacent_find WITH PRED
121 : template<class _FwdIt,
122 : class _Pr> inline
123 : _FwdIt _Adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
124 : { // find first satisfying _Pred with successor
125 : _DEBUG_RANGE(_First, _Last);
126 : _DEBUG_POINTER(_Pred);
127 : for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
128 : if (_Pred(*_Firstb, *_First))
129 : return (_Firstb);
130 : return (_Last);
131 : }
132 :
133 : template<class _FwdIt,
134 : class _Pr> inline
135 : _FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
136 : { // find first satisfying _Pred with successor
137 : _ASSIGN_FROM_BASE(_First,
138 : _Adjacent_find(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
139 : return (_First);
140 : }
141 :
142 : // TEMPLATE FUNCTION count
143 : template<class _InIt,
144 : class _Ty> inline
145 : typename iterator_traits<_InIt>::difference_type
146 : _Count(_InIt _First, _InIt _Last, const _Ty& _Val)
147 : { // count elements that match _Val
148 : _DEBUG_RANGE(_First, _Last);
149 : typename iterator_traits<_InIt>::difference_type _Cnt = 0;
150 :
151 : for (; _First != _Last; ++_First)
152 : if (*_First == _Val)
153 : ++_Cnt;
154 : return (_Cnt);
155 : }
156 :
157 : template<class _InIt,
158 : class _Ty> inline
159 : typename iterator_traits<_InIt>::difference_type
160 : count(_InIt _First, _InIt _Last, const _Ty& _Val)
161 : { // count elements that match _Val
162 : return _Count(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val);
163 : }
164 :
165 : // TEMPLATE FUNCTION count_if
166 : template<class _InIt,
167 : class _Pr> inline
168 : typename iterator_traits<_InIt>::difference_type
169 : _Count_if(_InIt _First, _InIt _Last, _Pr _Pred)
170 : { // count elements satisfying _Pred
171 : _DEBUG_RANGE(_First, _Last);
172 : _DEBUG_POINTER(_Pred);
173 : typename iterator_traits<_InIt>::difference_type _Count = 0;
174 :
175 : for (; _First != _Last; ++_First)
176 : if (_Pred(*_First))
177 : ++_Count;
178 : return (_Count);
179 : }
180 :
181 : template<class _InIt,
182 : class _Pr> inline
183 : typename iterator_traits<_InIt>::difference_type
184 : count_if(_InIt _First, _InIt _Last, _Pr _Pred)
185 : { // count elements satisfying _Pred
186 : return _Count_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred);
187 : }
188 :
189 : // TEMPLATE FUNCTION search
190 : template<class _FwdIt1,
191 : class _FwdIt2,
192 : class _Diff1,
193 : class _Diff2> inline
194 : _FwdIt1 _Search(_FwdIt1 _First1, _FwdIt1 _Last1,
195 : _FwdIt2 _First2, _FwdIt2 _Last2, _Diff1 *, _Diff2 *)
196 : { // find first [_First2, _Last2) match
197 : _DEBUG_RANGE(_First1, _Last1);
198 : _DEBUG_RANGE(_First2, _Last2);
199 : _Diff1 _Count1 = 0;
200 : _Distance(_First1, _Last1, _Count1);
201 : _Diff2 _Count2 = 0;
202 : _Distance(_First2, _Last2, _Count2);
203 :
204 : for (; _Count2 <= _Count1; ++_First1, --_Count1)
205 : { // room for match, try it
206 : _FwdIt1 _Mid1 = _First1;
207 : for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_Mid2)
208 : if (_Mid2 == _Last2)
209 : return (_First1);
210 : else if (!(*_Mid1 == *_Mid2))
211 : break;
212 : }
213 : return (_Last1);
214 : }
215 :
216 : template<class _FwdIt1,
217 : class _FwdIt2> inline
218 : _FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
219 : _FwdIt2 _First2, _FwdIt2 _Last2)
220 : { // find first [_First2, _Last2) match
221 : _ASSIGN_FROM_BASE(_First1,
222 : _Search(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
223 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
224 : _Dist_type(_First1), _Dist_type(_First2)));
225 : return _First1;
226 : }
227 :
228 : // TEMPLATE FUNCTION search WITH PRED
229 : template<class _FwdIt1,
230 : class _FwdIt2,
231 : class _Diff1,
232 : class _Diff2,
233 : class _Pr> inline
234 : _FwdIt1 _Search(_FwdIt1 _First1, _FwdIt1 _Last1,
235 : _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
236 : { // find first [_First2, _Last2) satisfying _Pred
237 : _DEBUG_RANGE(_First1, _Last1);
238 : _DEBUG_RANGE(_First2, _Last2);
239 : _DEBUG_POINTER(_Pred);
240 : _Diff1 _Count1 = 0;
241 : _Distance(_First1, _Last1, _Count1);
242 : _Diff2 _Count2 = 0;
243 : _Distance(_First2, _Last2, _Count2);
244 :
245 : for (; _Count2 <= _Count1; ++_First1, --_Count1)
246 : { // room for match, try it
247 : _FwdIt1 _Mid1 = _First1;
248 : for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_Mid2)
249 : if (_Mid2 == _Last2)
250 : return (_First1);
251 : else if (!_Pred(*_Mid1, *_Mid2))
252 : break;
253 : }
254 : return (_Last1);
255 : }
256 :
257 : template<class _FwdIt1,
258 : class _FwdIt2,
259 : class _Pr> inline
260 : _FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
261 : _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
262 : { // find first [_First2, _Last2) satisfying _Pred
263 : _ASSIGN_FROM_BASE(_First1,
264 : _Search(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
265 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred,
266 : _Dist_type(_First1), _Dist_type(_First2)));
267 : return _First1;
268 : }
269 :
270 : // TEMPLATE FUNCTION search_n
271 : template<class _FwdIt1,
272 : class _Diff2,
273 : class _Ty> inline
274 : _FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
275 : _Diff2 _Count, const _Ty& _Val, forward_iterator_tag)
276 : { // find first _Count * _Val match, forward iterators
277 : _DEBUG_RANGE(_First1, _Last1);
278 :
279 : if (_Count <= 0)
280 : return (_First1);
281 :
282 : for (; _First1 != _Last1; ++_First1)
283 : if (*_First1 == _Val)
284 : { // found start of possible match, check it out
285 : _FwdIt1 _Mid1 = _First1;
286 :
287 : for (_Diff2 _Count1 = _Count; ; )
288 : if (--_Count1 == 0)
289 : return (_First1); // found rest of match, report it
290 : else if (++_Mid1 == _Last1)
291 : return (_Last1); // short match at end
292 : else if (!(*_Mid1 == _Val))
293 : break; // short match not at end
294 :
295 : _First1 = _Mid1; // pick up just beyond failed match
296 : }
297 : return (_Last1);
298 : }
299 :
300 : template<class _FwdIt1,
301 : class _Diff2,
302 : class _Ty> inline
303 : _FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
304 : _Diff2 _Count, const _Ty& _Val, random_access_iterator_tag)
305 : { // find first _Count * _Val match, random-access iterators
306 : _DEBUG_RANGE(_First1, _Last1);
307 :
308 : if (_Count <= 0)
309 : return (_First1);
310 :
311 : _FwdIt1 _Oldfirst1 = _First1;
312 : for (_Diff2 _Inc = 0; _Count <= _Last1 - _Oldfirst1; )
313 : { // enough room, look for a match
314 : _First1 = _Oldfirst1 + _Inc;
315 : if (*_First1 == _Val)
316 : { // found part of possible match, check it out
317 : _Diff2 _Count1 = _Count;
318 : _FwdIt1 _Mid1 = _First1;
319 :
320 : for (; _Oldfirst1 != _First1 && _First1[-1] == _Val; --_First1)
321 : --_Count1; // back up over any skipped prefix
322 :
323 : if (_Count1 <= _Last1 - _Mid1)
324 : for (; ; ) // enough left, test suffix
325 : if (--_Count1 == 0)
326 : return (_First1); // found rest of match, report it
327 : else if (!(*++_Mid1 == _Val))
328 : break; // short match not at end
329 :
330 : _Oldfirst1 = ++_Mid1; // failed match, take small jump
331 : _Inc = 0;
332 : }
333 : else
334 : { // no match, take big jump and back up as needed
335 : _Oldfirst1 = _First1 + 1;
336 : _Inc = _Count - 1;
337 : }
338 : }
339 : return (_Last1);
340 : }
341 :
342 : template<class _FwdIt1,
343 : class _Diff2,
344 : class _Ty> inline
345 : _FwdIt1 search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
346 : _Diff2 _Count, const _Ty& _Val)
347 : { // find first _Count * _Val match
348 : _ASSIGN_FROM_BASE(_First1,
349 : _Search_n(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _Count, _Val,
350 : _Iter_cat(_First1)));
351 : return _First1;
352 : }
353 :
354 : // TEMPLATE FUNCTION search_n WITH PRED
355 : template<class _FwdIt1,
356 : class _Diff2,
357 : class _Ty,
358 : class _Pr> inline
359 : _FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
360 : _Diff2 _Count, const _Ty& _Val, _Pr _Pred, forward_iterator_tag)
361 : { // find first _Count * _Val satisfying _Pred, forward iterators
362 : _DEBUG_RANGE(_First1, _Last1);
363 : _DEBUG_POINTER(_Pred);
364 :
365 : if (_Count <= 0)
366 : return (_First1);
367 :
368 : for (; _First1 != _Last1; ++_First1)
369 : if (_Pred(*_First1, _Val))
370 : { // found start of possible match, check it out
371 : _FwdIt1 _Mid1 = _First1;
372 :
373 : for (_Diff2 _Count1 = _Count; ; )
374 : if (--_Count1 == 0)
375 : return (_First1); // found rest of match, report it
376 : else if (++_Mid1 == _Last1)
377 : return (_Last1); // short match at end
378 : else if (!_Pred(*_Mid1, _Val))
379 : break; // short match not at end
380 :
381 : _First1 = _Mid1; // pick up just beyond failed match
382 : }
383 : return (_Last1);
384 : }
385 :
386 : template<class _FwdIt1,
387 : class _Diff2,
388 : class _Ty,
389 : class _Pr> inline
390 : _FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
391 : _Diff2 _Count, const _Ty& _Val, _Pr _Pred, random_access_iterator_tag)
392 : { // find first _Count * _Val satisfying _Pred, random-access iterators
393 : _DEBUG_RANGE(_First1, _Last1);
394 : _DEBUG_POINTER(_Pred);
395 :
396 : if (_Count <= 0)
397 : return (_First1);
398 :
399 : _FwdIt1 _Oldfirst1 = _First1;
400 : for (; _Count <= _Last1 - _Oldfirst1; )
401 : { // enough room, look for a match
402 : if (_Pred(*_First1, _Val))
403 : { // found part of possible match, check it out
404 : _Diff2 _Count1 = _Count;
405 : _FwdIt1 _Mid1 = _First1;
406 :
407 : for (; _Oldfirst1 != _First1 && _Pred(_First1[-1], _Val);
408 : --_First1)
409 : --_Count1; // back up over any skipped prefix
410 :
411 : if (_Count1 <= _Last1 - _Mid1)
412 : for (; ; ) // enough left, test suffix
413 : if (--_Count1 == 0)
414 : return (_First1); // found rest of match, report it
415 : else if (!_Pred(*++_Mid1, _Val))
416 : break; // short match not at end
417 :
418 : _Oldfirst1 = ++_Mid1; // failed match, take small jump
419 : _First1 = _Oldfirst1;
420 : }
421 : else
422 : { // no match, take big jump and back up as needed
423 : _Oldfirst1 = _First1 + 1;
424 : _First1 += _Count;
425 : }
426 : }
427 : return (_Last1);
428 : }
429 :
430 : template<class _FwdIt1,
431 : class _Diff2,
432 : class _Ty,
433 : class _Pr> inline
434 : _FwdIt1 search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
435 : _Diff2 _Count, const _Ty& _Val, _Pr _Pred)
436 : { // find first _Count * _Val satisfying _Pred
437 : _ASSIGN_FROM_BASE(_First1,
438 : _Search_n(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _Count, _Val, _Pred,
439 : _Iter_cat(_First1)));
440 : return _First1;
441 : }
442 :
443 : // TEMPLATE FUNCTION find_end
444 : template<class _FwdIt1,
445 : class _FwdIt2,
446 : class _Diff1,
447 : class _Diff2> inline
448 : _FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
449 : _FwdIt2 _First2, _FwdIt2 _Last2, _Diff1 *, _Diff2 *)
450 : { // find last [_First2, _Last2) match
451 : _DEBUG_RANGE(_First1, _Last1);
452 : _DEBUG_RANGE(_First2, _Last2);
453 : _Diff1 _Count1 = 0;
454 : _Distance(_First1, _Last1, _Count1);
455 : _Diff2 _Count2 = 0;
456 : _Distance(_First2, _Last2, _Count2);
457 : _FwdIt1 _Ans = _Last1;
458 :
459 : if (0 < _Count2)
460 : for (; _Count2 <= _Count1; ++_First1, --_Count1)
461 : { // room for match, try it
462 : _FwdIt1 _Mid1 = _First1;
463 : for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1)
464 : if (!(*_Mid1 == *_Mid2))
465 : break;
466 : else if (++_Mid2 == _Last2)
467 : { // potential answer, save it
468 : _Ans = _First1;
469 : break;
470 : }
471 : }
472 : return (_Ans);
473 : }
474 :
475 : template<class _FwdIt1,
476 : class _FwdIt2> inline
477 : _FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
478 : _FwdIt2 _First2, _FwdIt2 _Last2)
479 : { // find last [_First2, _Last2) match
480 : _ASSIGN_FROM_BASE(_First1,
481 : _Find_end(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
482 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
483 : _Dist_type(_First1), _Dist_type(_First2)));
484 : return _First1;
485 : }
486 :
487 : // TEMPLATE FUNCTION find_end WITH PRED
488 : template<class _FwdIt1,
489 : class _FwdIt2,
490 : class _Diff1,
491 : class _Diff2,
492 : class _Pr> inline
493 : _FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
494 : _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
495 : { // find last [_First2, _Last2) satisfying _Pred
496 : _DEBUG_RANGE(_First1, _Last1);
497 : _DEBUG_RANGE(_First2, _Last2);
498 : _DEBUG_POINTER(_Pred);
499 : _Diff1 _Count1 = 0;
500 : _Distance(_First1, _Last1, _Count1);
501 : _Diff2 _Count2 = 0;
502 : _Distance(_First2, _Last2, _Count2);
503 : _FwdIt1 _Ans = _Last1;
504 :
505 : if (0 < _Count2)
506 : for (; _Count2 <= _Count1; ++_First1, --_Count1)
507 : { // room for match, try it
508 : _FwdIt1 _Mid1 = _First1;
509 : for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1)
510 : if (!_Pred(*_Mid1, *_Mid2))
511 : break;
512 : else if (++_Mid2 == _Last2)
513 : { // potential answer, save it
514 : _Ans = _First1;
515 : break;
516 : }
517 : }
518 : return (_Ans);
519 : }
520 :
521 : template<class _FwdIt1,
522 : class _FwdIt2,
523 : class _Pr> inline
524 : _FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
525 : _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
526 : { // find last [_First2, _Last2) satisfying _Pred
527 : _ASSIGN_FROM_BASE(_First1,
528 : _Find_end(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
529 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred,
530 : _Dist_type(_First1), _Dist_type(_First2)));
531 : return _First1;
532 : }
533 :
534 : // TEMPLATE FUNCTION find_first_of
535 : template<class _FwdIt1,
536 : class _FwdIt2> inline
537 : _FwdIt1 _Find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
538 : _FwdIt2 _First2, _FwdIt2 _Last2)
539 : { // look for one of [_First2, _Last2) that matches element
540 : _DEBUG_RANGE(_First1, _Last1);
541 : _DEBUG_RANGE(_First2, _Last2);
542 : for (; _First1 != _Last1; ++_First1)
543 : for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
544 : if (*_First1 == *_Mid2)
545 : return (_First1);
546 : return (_First1);
547 : }
548 :
549 : template<class _FwdIt1,
550 : class _FwdIt2> inline
551 : _FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
552 : _FwdIt2 _First2, _FwdIt2 _Last2)
553 : { // look for one of [_First2, _Last2) that matches element
554 : _DEBUG_RANGE(_First1, _Last1);
555 : _DEBUG_RANGE(_First2, _Last2);
556 : _ASSIGN_FROM_BASE(_First1,
557 : _Find_first_of(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
558 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2)));
559 : return _First1;
560 : }
561 :
562 : // TEMPLATE FUNCTION find_first_of WITH PRED
563 : template<class _FwdIt1,
564 : class _FwdIt2,
565 : class _Pr> inline
566 : _FwdIt1 _Find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
567 : _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
568 : { // look for one of [_First2, _Last2) satisfying _Pred with element
569 : _DEBUG_POINTER(_Pred);
570 : for (; _First1 != _Last1; ++_First1)
571 : for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
572 : if (_Pred(*_First1, *_Mid2))
573 : return (_First1);
574 : return (_First1);
575 : }
576 :
577 : template<class _FwdIt1,
578 : class _FwdIt2,
579 : class _Pr> inline
580 : _FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
581 : _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
582 : { // look for one of [_First2, _Last2) satisfying _Pred with element
583 : _ASSIGN_FROM_BASE(_First1,
584 : _Find_first_of(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
585 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred));
586 : return (_First1);
587 : }
588 :
589 : // TEMPLATE FUNCTION iter_swap
590 : template<class _FwdIt1,
591 : class _FwdIt2> inline
592 : void iter_swap(_FwdIt1 _Left, _FwdIt2 _Right)
593 : { // swap *_Left and *_Right
594 : swap(*_Left, *_Right);
595 : }
596 :
597 : // TEMPLATE FUNCTION swap_ranges
598 : template<class _FwdIt1, class _FwdIt2, class _FwdItCats>
599 : inline
600 : _FwdIt2 _Swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2,
601 : _FwdItCats, _Range_checked_iterator_tag)
602 : { // swap [_First1, _Last1) with [_First2, ...)
603 : _DEBUG_RANGE(_First1, _Last1);
604 : for (; _First1 != _Last1; ++_First1, ++_First2)
605 : std::iter_swap(_First1, _First2);
606 : return (_First2);
607 : }
608 :
609 : #if _SECURE_SCL
610 : template<class _FwdIt1, class _FwdIt2>
611 : inline
612 : _FwdIt2 _Swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2,
613 : random_access_iterator_tag, _Range_checked_iterator_tag)
614 : { // swap [_First1, _Last1) with [_First2, ...)
615 : // if _FwdIt2 is range checked, this will make sure there is enough space
616 : _FwdIt2 _Result = _First2 + (_Last1 - _First1);
617 : _Swap_ranges(_First1, _Last1, _CHECKED_BASE(_First2),
618 : forward_iterator_tag(), _Range_checked_iterator_tag());
619 : return (_Result);
620 : }
621 : #endif
622 :
623 : #if _SECURE_SCL
624 :
625 : template<class _FwdIt1, class _FwdIt2>
626 : inline
627 : _IF_CHK(_FwdIt2) swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
628 : {
629 : return _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
630 : _Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
631 : }
632 :
633 : template<class _FwdIt1, class _FwdElem2, size_t _Size>
634 : inline
635 : _FwdElem2* swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdElem2 (&_First2)[_Size])
636 : {
637 : return (swap_ranges(_First1, _Last1, _STDEXT make_checked_array_iterator(_First2, _Size)).base());
638 : }
639 :
640 : template<class _FwdIt1, class _FwdIt2>
641 : inline
642 : _SCL_INSECURE_DEPRECATE
643 : _IF_NOT_CHK(_FwdIt2) swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
644 : {
645 : return _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
646 : _Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
647 : }
648 :
649 : #else
650 :
651 : template<class _FwdIt1, class _FwdIt2>
652 : inline
653 : _FwdIt2 swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
654 : {
655 : return _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
656 : _Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
657 : }
658 :
659 : #endif
660 :
661 : // TEMPLATE FUNCTION transform WITH UNARY OP
662 : template<class _InIt, class _OutIt, class _Fn1, class _InOutItCat>
663 : inline
664 : _OutIt _Transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func,
665 : _InOutItCat, _Range_checked_iterator_tag)
666 : { // transform [_First, _Last) with _Func
667 : _DEBUG_RANGE(_First, _Last);
668 : _DEBUG_POINTER(_Dest);
669 : _DEBUG_POINTER(_Func);
670 : for (; _First != _Last; ++_First, ++_Dest)
671 : *_Dest = _Func(*_First);
672 : return (_Dest);
673 : }
674 :
675 : #if _SECURE_SCL
676 : template<class _InIt, class _OutIt, class _Fn1>
677 : inline
678 : _OutIt _Transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func,
679 : random_access_iterator_tag, _Range_checked_iterator_tag)
680 : { // transform [_First, _Last) with _Func
681 : // for range checked iterators, this will make sure there is enough space
682 : _OutIt _Result = _Dest + (_Last - _First);
683 : _Transform(_First, _Last, _CHECKED_BASE(_Dest), _Func,
684 : forward_iterator_tag(), _Range_checked_iterator_tag());
685 : return (_Result);
686 : }
687 : #endif
688 :
689 : #if _SECURE_SCL
690 :
691 : template<class _InIt, class _OutIt, class _Fn1>
692 : inline
693 : _IF_CHK(_OutIt) transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
694 : {
695 : return _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
696 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
697 : }
698 :
699 : template<class _InIt, class _OutElem, class _Fn1, size_t _Size>
700 : inline
701 : _OutElem* transform(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Fn1 _Func)
702 : {
703 : return (transform(_First, _Last,
704 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Func).base());
705 : }
706 :
707 : template<class _InIt, class _OutIt, class _Fn1>
708 : inline
709 : _SCL_INSECURE_DEPRECATE
710 : _IF_NOT_CHK(_OutIt) transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
711 : {
712 : return _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
713 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
714 : }
715 :
716 : #else
717 :
718 : template<class _InIt, class _OutIt, class _Fn1>
719 : inline
720 : _OutIt transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
721 : {
722 : return _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
723 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
724 : }
725 :
726 : #endif
727 :
728 : // TEMPLATE FUNCTION transform WITH BINARY OP
729 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2, class _InItCats, class _InOutItCat>
730 : inline
731 : _OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
732 : _OutIt _Dest, _Fn2 _Func,
733 : _InItCats, _InOutItCat,
734 : _Range_checked_iterator_tag, _Range_checked_iterator_tag)
735 : { // transform [_First1, _Last1) and [_First2, _Last2) with _Func
736 : _DEBUG_RANGE(_First1, _Last1);
737 : _DEBUG_POINTER(_Dest);
738 : _DEBUG_POINTER(_Func);
739 : for (; _First1 != _Last1; ++_First1, ++_First2, ++_Dest)
740 : *_Dest = _Func(*_First1, *_First2);
741 : return (_Dest);
742 : }
743 :
744 : #if _SECURE_SCL
745 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
746 : inline
747 : _OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
748 : _OutIt _Dest, _Fn2 _Func,
749 : random_access_iterator_tag, random_access_iterator_tag,
750 : _Range_checked_iterator_tag, _Range_checked_iterator_tag)
751 : { // transform [_First1, _Last1) and [_First2, _Last2) with _Func
752 : // for range checked iterators, this will make sure there is enough space
753 : _InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
754 : _OutIt _Result = _Dest + (_Last1 - _First1);
755 : _Transform(_First1, _Last1, _CHECKED_BASE(_First2),
756 : _CHECKED_BASE(_Dest), _Func,
757 : forward_iterator_tag(), forward_iterator_tag(),
758 : _Range_checked_iterator_tag(), _Range_checked_iterator_tag());
759 : return _Result;
760 : }
761 :
762 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2, class _InOutItCat>
763 : inline
764 : _OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
765 : _OutIt _Dest, _Fn2 _Func,
766 : random_access_iterator_tag, _InOutItCat,
767 : _Range_checked_iterator_tag, _Range_checked_iterator_tag)
768 : { // transform [_First1, _Last1) and [_First2, _Last2) with _Func
769 : // for range checked iterators, this will make sure there is enough space
770 : _InIt2 _Last2 = _First2 + (_Last1 - _First1); (_Last2);
771 : return _Transform(_First1, _Last1, _CHECKED_BASE(_First2),
772 : _Dest, _Func,
773 : forward_iterator_tag(), forward_iterator_tag(),
774 : _Range_checked_iterator_tag(), _Range_checked_iterator_tag());
775 : }
776 :
777 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2, class _InItCats>
778 : inline
779 : _OutIt _Transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
780 : _OutIt _Dest, _Fn2 _Func,
781 : _InItCats, random_access_iterator_tag,
782 : _Range_checked_iterator_tag, _Range_checked_iterator_tag)
783 : { // transform [_First1, _Last1) and [_First2, _Last2) with _Func
784 : // for range checked iterators, this will make sure there is enough space
785 : _OutIt _Result = _Dest + (_Last1 - _First1);
786 : _Transform(_First1, _Last1, _First2,
787 : _CHECKED_BASE(_Dest), _Func,
788 : forward_iterator_tag(), forward_iterator_tag(),
789 : _Range_checked_iterator_tag(), _Range_checked_iterator_tag());
790 : return _Result;
791 : }
792 : #endif
793 :
794 : #if _SECURE_SCL
795 :
796 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
797 : inline
798 : _IF_CHK2_(_InIt2, _OutIt, _OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
799 : _OutIt _Dest, _Fn2 _Func)
800 : {
801 : return _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
802 : _Iter_random(_First1, _First2), _Iter_random(_First1, _Dest),
803 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
804 : }
805 :
806 : template<class _InIt1, class _InElem2, class _OutElem, class _Fn2, size_t _SizeFirst2, size_t _SizeDest>
807 : inline
808 : _OutElem* transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
809 : _OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
810 : {
811 : return (transform(_First1, _Last1,
812 : _STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
813 : _STDEXT make_checked_array_iterator(_Dest, _SizeDest),
814 : _Func).base());
815 : }
816 :
817 : template<class _InIt1, class _InIt2, class _OutElem, class _Fn2, size_t _SizeDest>
818 : inline
819 : _IF_CHK_(_InIt2, _OutElem*) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
820 : _OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
821 : {
822 : return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
823 : _STDEXT make_checked_array_iterator(_Dest, _SizeDest), _Func,
824 : _Iter_random(_First1, _First2), _Iter_cat(_First1),
825 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()).base());
826 : }
827 :
828 : template<class _InIt1, class _InIt2, class _OutElem, class _Fn2, size_t _SizeDest>
829 : inline
830 : _SCL_INSECURE_DEPRECATE
831 : _IF_NOT_CHK_(_InIt2, _OutElem*) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
832 : _OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
833 : {
834 : return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
835 : _STDEXT make_checked_array_iterator(_Dest, _SizeDest), _Func,
836 : _Iter_random(_First1, _First2), _Iter_cat(_First1),
837 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()).base());
838 : }
839 :
840 : template<class _InIt1, class _InElem2, class _OutIt, class _Fn2, size_t _SizeFirst2>
841 : inline
842 : _IF_CHK(_OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
843 : _OutIt _Dest, _Fn2 _Func)
844 : {
845 : return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
846 : _STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
847 : _Dest, _Func,
848 : _Iter_cat(_First1), _Iter_random(_First1, _Dest),
849 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()));
850 : }
851 :
852 : template<class _InIt1, class _InElem2, class _OutIt, class _Fn2, size_t _SizeFirst2>
853 : inline
854 : _SCL_INSECURE_DEPRECATE
855 : _IF_NOT_CHK(_OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
856 : _OutIt _Dest, _Fn2 _Func)
857 : {
858 : return (_Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
859 : _STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
860 : _Dest, _Func,
861 : _Iter_cat(_First1), _Iter_random(_First1, _Dest),
862 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()));
863 : }
864 :
865 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
866 : inline
867 : _SCL_INSECURE_DEPRECATE
868 : _IF_NOT_CHK2_(_InIt2, _OutIt, _OutIt) transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
869 : _OutIt _Dest, _Fn2 _Func)
870 : {
871 : return _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
872 : _Iter_random(_First1, _First2), _Iter_random(_First1, _Dest),
873 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
874 : }
875 :
876 : #else
877 :
878 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
879 : inline
880 : _OutIt transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
881 : _OutIt _Dest, _Fn2 _Func)
882 : {
883 : return _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
884 : _Iter_random(_First1, _First2), _Iter_random(_First1, _Dest),
885 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
886 : }
887 :
888 : #endif
889 :
890 : // TEMPLATE FUNCTION replace
891 : template<class _FwdIt,
892 : class _Ty> inline
893 : void _Replace(_FwdIt _First, _FwdIt _Last,
894 : const _Ty& _Oldval, const _Ty& _Newval)
895 : { // replace each matching _Oldval with _Newval
896 : _DEBUG_RANGE(_First, _Last);
897 : for (; _First != _Last; ++_First)
898 : if (*_First == _Oldval)
899 : *_First = _Newval;
900 : }
901 :
902 : template<class _FwdIt,
903 : class _Ty> inline
904 : void replace(_FwdIt _First, _FwdIt _Last,
905 : const _Ty& _Oldval, const _Ty& _Newval)
906 : { // replace each matching _Oldval with _Newval
907 : _Replace(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Oldval, _Newval);
908 : }
909 :
910 : // TEMPLATE FUNCTION replace_if
911 : template<class _FwdIt,
912 : class _Pr,
913 : class _Ty> inline
914 : void _Replace_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred, const _Ty& _Val)
915 : { // replace each satisfying _Pred with _Val
916 : _DEBUG_RANGE(_First, _Last);
917 : _DEBUG_POINTER(_Pred);
918 : for (; _First != _Last; ++_First)
919 : if (_Pred(*_First))
920 : *_First = _Val;
921 : }
922 :
923 : template<class _FwdIt,
924 : class _Pr,
925 : class _Ty> inline
926 : void replace_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred, const _Ty& _Val)
927 : { // replace each satisfying _Pred with _Val
928 : _Replace_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred, _Val);
929 : }
930 :
931 : // TEMPLATE FUNCTION replace_copy
932 : template<class _InIt, class _OutIt, class _Ty, class _InOutItCat>
933 : inline
934 : _OutIt _Replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
935 : const _Ty& _Oldval, const _Ty& _Newval,
936 : _InOutItCat, _Range_checked_iterator_tag)
937 : { // copy replacing each matching _Oldval with _Newval
938 : _DEBUG_RANGE(_First, _Last);
939 : _DEBUG_POINTER(_Dest);
940 : for (; _First != _Last; ++_First, ++_Dest)
941 : *_Dest = *_First == _Oldval ? _Newval : *_First;
942 : return (_Dest);
943 : }
944 :
945 : #if _SECURE_SCL
946 : template<class _InIt, class _OutIt, class _Ty>
947 : inline
948 : _OutIt _Replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
949 : const _Ty& _Oldval, const _Ty& _Newval,
950 : random_access_iterator_tag, _Range_checked_iterator_tag)
951 : { // copy replacing each matching _Oldval with _Newval
952 : // for range checked iterators, this will make sure there is enough space
953 : _OutIt _Result = _Dest + (_Last - _First);
954 : _Replace_copy(_First, _Last, _CHECKED_BASE(_Dest),
955 : _Oldval, _Newval,
956 : forward_iterator_tag(), _Range_checked_iterator_tag());
957 : return (_Result);
958 : }
959 : #endif
960 :
961 : #if _SECURE_SCL
962 :
963 : template<class _InIt,
964 : class _OutIt,
965 : class _Ty> inline
966 : _IF_CHK(_OutIt) replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
967 : const _Ty& _Oldval, const _Ty& _Newval)
968 : { // copy replacing each matching _Oldval with _Newval
969 : return _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
970 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
971 : }
972 :
973 : template<class _InIt, class _OutElem, class _Ty, size_t _Size>
974 : inline
975 : _OutElem* replace_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size],
976 : const _Ty& _Oldval, const _Ty& _Newval)
977 : { // copy replacing each matching _Oldval with _Newval
978 : return (replace_copy(_First, _Last,
979 : _STDEXT make_checked_array_iterator(_Dest, _Size),
980 : _Oldval, _Newval).base());
981 : }
982 :
983 : template<class _InIt,
984 : class _OutIt,
985 : class _Ty> inline
986 : _SCL_INSECURE_DEPRECATE
987 : _IF_NOT_CHK(_OutIt) replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
988 : const _Ty& _Oldval, const _Ty& _Newval)
989 : { // copy replacing each matching _Oldval with _Newval
990 : return _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
991 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
992 : }
993 :
994 : #else
995 :
996 : template<class _InIt,
997 : class _OutIt,
998 : class _Ty> inline
999 : _OutIt replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
1000 : const _Ty& _Oldval, const _Ty& _Newval)
1001 : { // copy replacing each matching _Oldval with _Newval
1002 : return _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
1003 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1004 : }
1005 :
1006 : #endif
1007 :
1008 : // TEMPLATE FUNCTION replace_copy_if
1009 : template<class _InIt, class _OutIt, class _Pr, class _Ty, class _InOutItCat>
1010 : inline
1011 : _OutIt _Replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1012 : _Pr _Pred, const _Ty& _Val, _InOutItCat, _Range_checked_iterator_tag)
1013 : { // copy replacing each satisfying _Pred with _Val
1014 : _DEBUG_RANGE(_First, _Last);
1015 : _DEBUG_POINTER(_Dest);
1016 : _DEBUG_POINTER(_Pred);
1017 : for (; _First != _Last; ++_First, ++_Dest)
1018 : *_Dest = _Pred(*_First) ? _Val : *_First;
1019 : return (_Dest);
1020 : }
1021 :
1022 : #if _SECURE_SCL
1023 : template<class _InIt, class _OutIt, class _Pr, class _Ty>
1024 : inline
1025 : _OutIt _Replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1026 : _Pr _Pred, const _Ty& _Val,
1027 : random_access_iterator_tag, _Range_checked_iterator_tag)
1028 : { // copy replacing each satisfying _Pred with _Val
1029 : // for range checked iterators, this will make sure there is enough space
1030 : _OutIt _Result = _Dest + (_Last - _First);
1031 : _Replace_copy_if(_First, _Last, _CHECKED_BASE(_Dest),
1032 : _Pred, _Val,
1033 : forward_iterator_tag(), _Range_checked_iterator_tag());
1034 : return (_Result);
1035 : }
1036 : #endif
1037 :
1038 : #if _SECURE_SCL
1039 :
1040 : template<class _InIt,
1041 : class _OutIt,
1042 : class _Pr,
1043 : class _Ty> inline
1044 : _IF_CHK(_OutIt) replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1045 : _Pr _Pred, const _Ty& _Val)
1046 : { // copy replacing each satisfying _Pred with _Val
1047 : return _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
1048 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1049 : }
1050 :
1051 : template<class _InIt, class _OutElem, class _Pr, class _Ty, size_t _Size>
1052 : inline
1053 : _OutElem* replace_copy_if(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size],
1054 : _Pr _Pred, const _Ty& _Val)
1055 : { // copy replacing each satisfying _Pred with _Val
1056 : return (replace_copy_if(_First, _Last,
1057 : _STDEXT make_checked_array_iterator(_Dest, _Size),
1058 : _Pred, _Val).base());
1059 : }
1060 :
1061 : template<class _InIt,
1062 : class _OutIt,
1063 : class _Pr,
1064 : class _Ty> inline
1065 : _SCL_INSECURE_DEPRECATE
1066 : _IF_NOT_CHK(_OutIt) replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1067 : _Pr _Pred, const _Ty& _Val)
1068 : { // copy replacing each satisfying _Pred with _Val
1069 : return _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
1070 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1071 : }
1072 :
1073 : #else
1074 :
1075 : template<class _InIt,
1076 : class _OutIt,
1077 : class _Pr,
1078 : class _Ty> inline
1079 : _OutIt replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
1080 : _Pr _Pred, const _Ty& _Val)
1081 : { // copy replacing each satisfying _Pred with _Val
1082 : return _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
1083 : _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1084 : }
1085 :
1086 : #endif
1087 :
1088 : // TEMPLATE FUNCTION generate
1089 : template<class _FwdIt,
1090 : class _Fn0> inline
1091 : void _Generate(_FwdIt _First, _FwdIt _Last, _Fn0 _Func)
1092 : { // replace [_First, _Last) with _Func()
1093 : _DEBUG_RANGE(_First, _Last);
1094 : _DEBUG_POINTER(_Func);
1095 : for (; _First != _Last; ++_First)
1096 : *_First = _Func();
1097 : }
1098 :
1099 : template<class _FwdIt,
1100 : class _Fn0> inline
1101 : void generate(_FwdIt _First, _FwdIt _Last, _Fn0 _Func)
1102 : { // replace [_First, _Last) with _Func()
1103 : _Generate(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Func);
1104 : }
1105 :
1106 : // TEMPLATE FUNCTION generate_n
1107 : template<class _OutIt, class _Diff, class _Fn0, class _OutItCat>
1108 : inline
1109 : void _Generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func,
1110 : _OutItCat, _Range_checked_iterator_tag)
1111 : { // replace [_Dest, _Dest + _Count) with _Func()
1112 : _DEBUG_POINTER(_Dest);
1113 : _DEBUG_POINTER(_Func);
1114 : for (; 0 < _Count; --_Count, ++_Dest)
1115 : *_Dest = _Func();
1116 : }
1117 :
1118 : #if _SECURE_SCL
1119 : template<class _OutIt, class _Diff, class _Fn0>
1120 : inline
1121 : void _Generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func,
1122 : random_access_iterator_tag, _Range_checked_iterator_tag)
1123 : { // replace [_Dest, _Dest + _Count) with _Func()
1124 : // for range checked iterators, this will make sure there is enough space
1125 : _OutIt _Result = _Dest + _Count;
1126 : _Generate_n(_CHECKED_BASE(_Dest), _Count, _Func,
1127 : forward_iterator_tag(), _Range_checked_iterator_tag());
1128 : }
1129 : #endif
1130 :
1131 : #if _SECURE_SCL
1132 :
1133 : template<class _OutIt,
1134 : class _Diff,
1135 : class _Fn0> inline
1136 : _IF_CHK_(_OutIt, void) generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
1137 : { // replace [_Dest, _Dest + _Count) with _Func()
1138 : _Generate_n(_Dest, _Count, _Func,
1139 : _Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
1140 : }
1141 :
1142 : template<class _OutElem, class _Diff, class _Fn0, size_t _Size>
1143 : inline
1144 : void generate_n(_OutElem (&_Dest)[_Size], _Diff _Count, _Fn0 _Func)
1145 : { // replace [_Dest, _Dest + _Count) with _Func()
1146 : generate_n(_STDEXT make_checked_array_iterator(_Dest, _Size), _Count, _Func);
1147 : }
1148 :
1149 : template<class _OutIt,
1150 : class _Diff,
1151 : class _Fn0> inline
1152 : _SCL_INSECURE_DEPRECATE
1153 : _IF_NOT_CHK_(_OutIt, void) generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
1154 : { // replace [_Dest, _Dest + _Count) with _Func()
1155 : _Generate_n(_Dest, _Count, _Func,
1156 : _Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
1157 : }
1158 :
1159 : #else
1160 :
1161 : template<class _OutIt,
1162 : class _Diff,
1163 : class _Fn0> inline
1164 : void generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
1165 : { // replace [_Dest, _Dest + _Count) with _Func()
1166 : _Generate_n(_Dest, _Count, _Func,
1167 : _Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
1168 : }
1169 :
1170 : #endif
1171 :
1172 : // TEMPLATE FUNCTION remove_copy
1173 : template<class _InIt,
1174 : class _OutIt,
1175 : class _Ty> inline
1176 : _OutIt _Remove_copy(_InIt _First, _InIt _Last,
1177 : _OutIt _Dest, const _Ty& _Val, _Range_checked_iterator_tag)
1178 : { // copy omitting each matching _Val
1179 : _DEBUG_RANGE(_First, _Last);
1180 : _DEBUG_POINTER(_Dest);
1181 : for (; _First != _Last; ++_First)
1182 : if (!(*_First == _Val))
1183 : *_Dest++ = *_First;
1184 : return (_Dest);
1185 : }
1186 :
1187 : #if _SECURE_SCL
1188 :
1189 : template<class _InIt,
1190 : class _OutIt,
1191 : class _Ty> inline
1192 : _IF_CHK(_OutIt) remove_copy(_InIt _First, _InIt _Last,
1193 : _OutIt _Dest, const _Ty& _Val)
1194 : { // copy omitting each matching _Val
1195 : return _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
1196 : }
1197 :
1198 : template<class _InIt, class _OutElem, class _Ty, size_t _Size>
1199 : inline
1200 : _OutElem* remove_copy(_InIt _First, _InIt _Last,
1201 : _OutElem (&_Dest)[_Size], const _Ty& _Val)
1202 : { // copy omitting each matching _Val
1203 : return (remove_copy(_First, _Last,
1204 : _STDEXT make_checked_array_iterator(_Dest, _Size),
1205 : _Val).base());
1206 : }
1207 :
1208 : template<class _InIt,
1209 : class _OutIt,
1210 : class _Ty> inline
1211 : _SCL_INSECURE_DEPRECATE
1212 : _IF_NOT_CHK(_OutIt) remove_copy(_InIt _First, _InIt _Last,
1213 : _OutIt _Dest, const _Ty& _Val)
1214 : { // copy omitting each matching _Val
1215 : return _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
1216 : }
1217 :
1218 : #else
1219 :
1220 : template<class _InIt,
1221 : class _OutIt,
1222 : class _Ty> inline
1223 : _OutIt remove_copy(_InIt _First, _InIt _Last,
1224 : _OutIt _Dest, const _Ty& _Val)
1225 : { // copy omitting each matching _Val
1226 : return _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
1227 : }
1228 :
1229 : #endif
1230 :
1231 : // TEMPLATE FUNCTION remove_copy_if
1232 : template<class _InIt,
1233 : class _OutIt,
1234 : class _Pr> inline
1235 : _OutIt _Remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
1236 : { // copy omitting each element satisfying _Pred
1237 : _DEBUG_RANGE(_First, _Last);
1238 : _DEBUG_POINTER(_Dest);
1239 : _DEBUG_POINTER(_Pred);
1240 : for (; _First != _Last; ++_First)
1241 : if (!_Pred(*_First))
1242 : *_Dest++ = *_First;
1243 : return (_Dest);
1244 : }
1245 :
1246 : #if _SECURE_SCL
1247 :
1248 : template<class _InIt,
1249 : class _OutIt,
1250 : class _Pr> inline
1251 : _IF_CHK(_OutIt) remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1252 : { // copy omitting each element satisfying _Pred
1253 : return _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
1254 : }
1255 :
1256 : template<class _InIt, class _OutElem, class _Pr, size_t _Size>
1257 : inline
1258 : _OutElem* remove_copy_if(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Pr _Pred)
1259 : { // copy omitting each element satisfying _Pred
1260 : return (remove_copy_if(_First, _Last,
1261 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
1262 : }
1263 :
1264 : template<class _InIt,
1265 : class _OutIt,
1266 : class _Pr> inline
1267 : _SCL_CHECKED_ALGORITHM_WARN
1268 : _IF_NOT_CHK(_OutIt) remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1269 : { // copy omitting each element satisfying _Pred
1270 : return _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
1271 : }
1272 :
1273 : #else
1274 :
1275 : template<class _InIt,
1276 : class _OutIt,
1277 : class _Pr> inline
1278 : _OutIt remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1279 : { // copy omitting each element satisfying _Pred
1280 : return _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
1281 : }
1282 :
1283 : #endif
1284 :
1285 : // TEMPLATE FUNCTION remove
1286 : template<class _FwdIt,
1287 : class _Ty> inline
1288 : _FwdIt remove(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
1289 : { // remove each matching _Val
1290 : _First = find(_First, _Last, _Val);
1291 : if (_First == _Last)
1292 : return (_First); // empty sequence, all done
1293 : else
1294 : { // nonempty sequence, worth doing
1295 : _FwdIt _First1 = _First;
1296 : return (_STDEXT unchecked_remove_copy(++_First1, _Last, _First, _Val));
1297 : }
1298 : }
1299 :
1300 : // TEMPLATE FUNCTION remove_if
1301 : template<class _FwdIt,
1302 : class _Pr> inline
1303 : _FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
1304 : { // remove each satisfying _Pred
1305 : _First = std::find_if(_First, _Last, _Pred);
1306 : if (_First == _Last)
1307 : return (_First); // empty sequence, all done
1308 : else
1309 : { // nonempty sequence, worth doing
1310 : _FwdIt _First1 = _First;
1311 : return (_STDEXT unchecked_remove_copy_if(++_First1, _Last, _First, _Pred));
1312 : }
1313 : }
1314 :
1315 : // TEMPLATE FUNCTION unique
1316 : template<class _FwdIt> inline
1317 : _FwdIt _Unique(_FwdIt _First, _FwdIt _Last)
1318 : { // remove each matching previous
1319 : _DEBUG_RANGE(_First, _Last);
1320 : for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
1321 : if (*_Firstb == *_First)
1322 : { // copy down
1323 : for (; ++_First != _Last; )
1324 : if (!(*_Firstb == *_First))
1325 : *++_Firstb = *_First;
1326 : return (++_Firstb);
1327 : }
1328 : return (_Last);
1329 : }
1330 :
1331 : template<class _FwdIt> inline
1332 : _FwdIt unique(_FwdIt _First, _FwdIt _Last)
1333 : { // remove each matching previous
1334 : _ASSIGN_FROM_BASE(_Last,
1335 : _Unique(_CHECKED_BASE(_First), _CHECKED_BASE(_Last)));
1336 : return (_Last);
1337 : }
1338 :
1339 : // TEMPLATE FUNCTION unique WITH PRED
1340 : template<class _FwdIt,
1341 : class _Pr> inline
1342 : _FwdIt _Unique(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
1343 : { // remove each satisfying _Pred with previous
1344 : _DEBUG_RANGE(_First, _Last);
1345 : _DEBUG_POINTER(_Pred);
1346 : for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
1347 : if (_Pred(*_Firstb, *_First))
1348 : { // copy down
1349 : for (; ++_First != _Last; )
1350 : if (!_Pred(*_Firstb, *_First))
1351 : *++_Firstb = *_First;
1352 : return (++_Firstb);
1353 : }
1354 : return (_Last);
1355 : }
1356 :
1357 : template<class _FwdIt,
1358 : class _Pr> inline
1359 : _FwdIt unique(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
1360 : { // remove each satisfying _Pred with previous
1361 : _ASSIGN_FROM_BASE(_Last,
1362 : _Unique(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
1363 : return (_Last);
1364 : }
1365 :
1366 : // TEMPLATE FUNCTION unique_copy
1367 : template<class _InIt,
1368 : class _OutIt,
1369 : class _Ty> inline
1370 : _OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Ty *, _Range_checked_iterator_tag)
1371 : { // copy compressing pairs that match, input iterators
1372 : _DEBUG_POINTER(_Dest);
1373 : _Ty _Val = *_First;
1374 :
1375 : for (*_Dest++ = _Val; ++_First != _Last; )
1376 : if (!(_Val == *_First))
1377 : _Val = *_First, *_Dest++ = _Val;
1378 : return (_Dest);
1379 : }
1380 :
1381 : template<class _InIt,
1382 : class _OutIt> inline
1383 : _OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
1384 : input_iterator_tag, _Range_checked_iterator_tag)
1385 : { // copy compressing pairs that match, input iterators
1386 : return (_Unique_copy(_First, _Last, _Dest, _Val_type(_First), _Range_checked_iterator_tag()));
1387 : }
1388 :
1389 : template<class _FwdIt,
1390 : class _OutIt> inline
1391 : _OutIt _Unique_copy(_FwdIt _First, _FwdIt _Last, _OutIt _Dest,
1392 : forward_iterator_tag, _Range_checked_iterator_tag)
1393 : { // copy compressing pairs that match, forward iterators
1394 : _DEBUG_RANGE(_First, _Last);
1395 : _DEBUG_POINTER(_Dest);
1396 : _FwdIt _Firstb = _First;
1397 : for (*_Dest++ = *_Firstb; ++_First != _Last; )
1398 : if (!(*_Firstb == *_First))
1399 : _Firstb = _First, *_Dest++ = *_Firstb;
1400 : return (_Dest);
1401 : }
1402 :
1403 : template<class _BidIt,
1404 : class _OutIt> inline
1405 : _OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
1406 : bidirectional_iterator_tag, _Range_checked_iterator_tag)
1407 : { // copy compressing pairs that match, bidirectional iterators
1408 : return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag(), _Range_checked_iterator_tag()));
1409 : }
1410 :
1411 : template<class _RanIt,
1412 : class _OutIt> inline
1413 : _OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest,
1414 : random_access_iterator_tag, _Range_checked_iterator_tag)
1415 : { // copy compressing pairs that match, random-access iterators
1416 : return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag(), _Range_checked_iterator_tag()));
1417 : }
1418 :
1419 : #if _SECURE_SCL
1420 :
1421 : template<class _InIt,
1422 : class _OutIt> inline
1423 : _IF_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
1424 : { // copy compressing pairs that match
1425 : return (_First == _Last ? _Dest :
1426 : _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1427 : }
1428 :
1429 : template<class _InIt, class _OutElem, size_t _Size>
1430 : inline
1431 : _OutElem* unique_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size])
1432 : { // copy compressing pairs that match
1433 : return (_First == _Last ? _Dest :
1434 : (unique_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base()));
1435 : }
1436 :
1437 : template<class _InIt,
1438 : class _OutIt> inline
1439 : _SCL_INSECURE_DEPRECATE
1440 : _IF_NOT_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
1441 : { // copy compressing pairs that match
1442 : return (_First == _Last ? _Dest :
1443 : _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1444 : }
1445 :
1446 : #else
1447 :
1448 : template<class _InIt,
1449 : class _OutIt> inline
1450 : _OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
1451 : { // copy compressing pairs that match
1452 : return (_First == _Last ? _Dest :
1453 : _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1454 : }
1455 :
1456 : #endif
1457 :
1458 : // TEMPLATE FUNCTION unique_copy WITH PRED
1459 : template<class _InIt,
1460 : class _OutIt,
1461 : class _Ty,
1462 : class _Pr> inline
1463 : _OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred,
1464 : _Ty *, _Range_checked_iterator_tag)
1465 : { // copy compressing pairs satisfying _Pred, input iterators
1466 : _DEBUG_POINTER(_Dest);
1467 : _DEBUG_POINTER(_Pred);
1468 : _Ty _Val = *_First;
1469 :
1470 : for (*_Dest++ = _Val; ++_First != _Last; )
1471 : if (!_Pred(_Val, *_First))
1472 : _Val = *_First, *_Dest++ = _Val;
1473 : return (_Dest);
1474 : }
1475 :
1476 : template<class _InIt,
1477 : class _OutIt,
1478 : class _Pr> inline
1479 : _OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred,
1480 : input_iterator_tag, _Range_checked_iterator_tag)
1481 : { // copy compressing pairs satisfying _Pred, input iterators
1482 : return (_Unique_copy(_First, _Last, _Dest, _Pred, _Val_type(_First), _Range_checked_iterator_tag()));
1483 : }
1484 :
1485 : template<class _FwdIt,
1486 : class _OutIt,
1487 : class _Pr> inline
1488 : _OutIt _Unique_copy(_FwdIt _First, _FwdIt _Last, _OutIt _Dest, _Pr _Pred,
1489 : forward_iterator_tag, _Range_checked_iterator_tag)
1490 : { // copy compressing pairs satisfying _Pred, forward iterators
1491 : _DEBUG_RANGE(_First, _Last);
1492 : _DEBUG_POINTER(_Dest);
1493 : _DEBUG_POINTER(_Pred);
1494 : _FwdIt _Firstb = _First;
1495 :
1496 : for (*_Dest++ = *_Firstb; ++_First != _Last; )
1497 : if (!_Pred(*_Firstb, *_First))
1498 : _Firstb = _First, *_Dest++ = *_Firstb;
1499 : return (_Dest);
1500 : }
1501 :
1502 : template<class _BidIt,
1503 : class _OutIt,
1504 : class _Pr> inline
1505 : _OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest, _Pr _Pred,
1506 : bidirectional_iterator_tag, _Range_checked_iterator_tag)
1507 : { // copy compressing pairs satisfying _Pred, bidirectional iterators
1508 : return (_Unique_copy(_First, _Last, _Dest, _Pred,
1509 : forward_iterator_tag(), _Range_checked_iterator_tag()));
1510 : }
1511 :
1512 : template<class _RanIt,
1513 : class _OutIt,
1514 : class _Pr> inline
1515 : _OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest, _Pr _Pred,
1516 : random_access_iterator_tag, _Range_checked_iterator_tag)
1517 : { // copy compressing pairs satisfying _Pred, random-access iterators
1518 : return (_Unique_copy(_First, _Last, _Dest, _Pred,
1519 : forward_iterator_tag(), _Range_checked_iterator_tag()));
1520 : }
1521 :
1522 : #if _SECURE_SCL
1523 :
1524 : template<class _InIt,
1525 : class _OutIt,
1526 : class _Pr> inline
1527 : _IF_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1528 : { // copy compressing pairs satisfying _Pred
1529 : return (_First == _Last ? _Dest
1530 : : _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1531 : }
1532 :
1533 : template<class _InIt, class _OutElem, class _Pr, size_t _Size>
1534 : inline
1535 : _OutElem* unique_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Pr _Pred)
1536 : { // copy compressing pairs satisfying _Pred
1537 : return (_First == _Last ? _Dest
1538 : : (unique_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base()));
1539 : }
1540 :
1541 : template<class _InIt,
1542 : class _OutIt,
1543 : class _Pr> inline
1544 : _SCL_INSECURE_DEPRECATE
1545 : _IF_NOT_CHK(_OutIt) unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1546 : { // copy compressing pairs satisfying _Pred
1547 : return (_First == _Last ? _Dest
1548 : : _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1549 : }
1550 :
1551 : #else
1552 :
1553 : template<class _InIt,
1554 : class _OutIt,
1555 : class _Pr> inline
1556 : _OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
1557 : { // copy compressing pairs satisfying _Pred
1558 : return (_First == _Last ? _Dest
1559 : : _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
1560 : }
1561 :
1562 : #endif
1563 :
1564 : // TEMPLATE FUNCTION reverse
1565 : template<class _BidIt> inline
1566 : void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
1567 : { // reverse elements in [_First, _Last), bidirectional iterators
1568 : for (; _First != _Last && _First != --_Last; ++_First)
1569 : std::iter_swap(_First, _Last);
1570 : }
1571 :
1572 : template<class _RanIt> inline
1573 : void _Reverse(_RanIt _First, _RanIt _Last, random_access_iterator_tag)
1574 : { // reverse elements in [_First, _Last), random-access iterators
1575 : _DEBUG_RANGE(_First, _Last);
1576 : for (; _First < _Last; ++_First)
1577 : std::iter_swap(_First, --_Last);
1578 : }
1579 :
1580 : template<class _BidIt> inline
1581 : void reverse(_BidIt _First, _BidIt _Last)
1582 : { // reverse elements in [_First, _Last)
1583 : _Reverse(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Iter_cat(_First));
1584 : }
1585 :
1586 : // TEMPLATE FUNCTION reverse_copy
1587 : template<class _BidIt, class _OutIt, class _InOutItCat>
1588 : inline
1589 : _OutIt _Reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
1590 : _InOutItCat, _Range_checked_iterator_tag)
1591 : { // copy reversing elements in [_First, _Last)
1592 : _DEBUG_RANGE(_First, _Last);
1593 : _DEBUG_POINTER(_Dest);
1594 : for (; _First != _Last; ++_Dest)
1595 : *_Dest = *--_Last;
1596 : return (_Dest);
1597 : }
1598 :
1599 : #if _SECURE_SCL
1600 : template<class _BidIt, class _OutIt>
1601 : inline
1602 : _OutIt _Reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
1603 : random_access_iterator_tag, _Range_checked_iterator_tag)
1604 : { // copy reversing elements in [_First, _Last)
1605 : // for range checked iterators, this will make sure there is enough space
1606 : _OutIt _Result = _Dest + (_Last - _First);
1607 : _Reverse_copy(_First, _Last, _CHECKED_BASE(_Dest),
1608 : forward_iterator_tag(), _Range_checked_iterator_tag());
1609 : return (_Result);
1610 : }
1611 : #endif
1612 :
1613 : #if _SECURE_SCL
1614 :
1615 : template<class _BidIt,
1616 : class _OutIt> inline
1617 : _IF_CHK(_OutIt) reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
1618 : { // copy reversing elements in [_First, _Last)
1619 : return _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1620 : }
1621 :
1622 : template<class _BidIt, class _OutElem, size_t _Size>
1623 : inline
1624 : _OutElem* reverse_copy(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size])
1625 : { // copy reversing elements in [_First, _Last)
1626 : return (reverse_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
1627 : }
1628 :
1629 : template<class _BidIt,
1630 : class _OutIt> inline
1631 : _SCL_INSECURE_DEPRECATE
1632 : _IF_NOT_CHK(_OutIt) reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
1633 : { // copy reversing elements in [_First, _Last)
1634 : return _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1635 : }
1636 :
1637 : #else
1638 :
1639 : template<class _BidIt,
1640 : class _OutIt> inline
1641 : _OutIt reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
1642 : { // copy reversing elements in [_First, _Last)
1643 : return _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
1644 : }
1645 :
1646 : #endif
1647 :
1648 : // TEMPLATE FUNCTION rotate
1649 : template<class _FwdIt> inline
1650 : void _Rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
1651 : forward_iterator_tag)
1652 : { // rotate [_First, _Last), forward iterators
1653 : for (_FwdIt _Next = _Mid; ; )
1654 : { // swap [_First, ...) into place
1655 : std::iter_swap(_First, _Next);
1656 : if (++_First == _Mid)
1657 : if (++_Next == _Last)
1658 : break; // done, quit
1659 : else
1660 : _Mid = _Next; // mark end of next interval
1661 : else if (++_Next == _Last)
1662 : _Next = _Mid; // wrap to last end
1663 : }
1664 : }
1665 :
1666 : template<class _BidIt> inline
1667 : void _Rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
1668 : bidirectional_iterator_tag)
1669 : { // rotate [_First, _Last), bidirectional iterators
1670 : std::reverse(_First, _Mid);
1671 : std::reverse(_Mid, _Last);
1672 : std::reverse(_First, _Last);
1673 : }
1674 :
1675 : template<class _RanIt,
1676 : class _Diff,
1677 : class _Ty> inline
1678 : void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Diff *, _Ty *)
1679 : { // rotate [_First, _Last), random-access iterators
1680 : _DEBUG_RANGE(_First, _Mid);
1681 : _DEBUG_RANGE(_Mid, _Last);
1682 : _Diff _Shift = _Mid - _First;
1683 : _Diff _Count = _Last - _First;
1684 :
1685 : for (_Diff _Factor = _Shift; _Factor != 0; )
1686 : { // find subcycle count as GCD of shift count and length
1687 : _Diff _Tmp = _Count % _Factor;
1688 : _Count = _Factor, _Factor = _Tmp;
1689 : }
1690 :
1691 : if (_Count < _Last - _First)
1692 : for (; 0 < _Count; --_Count)
1693 : { // rotate each subcycle
1694 : _RanIt _Hole = _First + _Count;
1695 : _RanIt _Next = _Hole;
1696 : _Ty _Holeval = *_Hole;
1697 : _RanIt _Next1 = _Next + _Shift == _Last ? _First : _Next + _Shift;
1698 : while (_Next1 != _Hole)
1699 : { // percolate elements back around subcycle
1700 : *_Next = *_Next1;
1701 : _Next = _Next1;
1702 : _Next1 = _Shift < _Last - _Next1 ? _Next1 + _Shift
1703 : : _First + (_Shift - (_Last - _Next1));
1704 : }
1705 : *_Next = _Holeval;
1706 : }
1707 : }
1708 :
1709 : template<class _RanIt> inline
1710 : void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
1711 : random_access_iterator_tag)
1712 : { // rotate [_First, _Last), random-access iterators
1713 : _Rotate(_First, _Mid, _Last, _Dist_type(_First), _Val_type(_First));
1714 : }
1715 :
1716 : template<class _FwdIt> inline
1717 : void rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last)
1718 : { // rotate [_First, _Last)
1719 : if (_First != _Mid && _Mid != _Last)
1720 : _Rotate(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last), _Iter_cat(_First));
1721 : }
1722 :
1723 : // TEMPLATE FUNCTION rotate_copy
1724 : template<class _FwdIt,
1725 : class _OutIt> inline
1726 : _OutIt _Rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest, _Range_checked_iterator_tag)
1727 : { // copy rotating [_First, _Last)
1728 : _Dest = _STDEXT unchecked_copy(_Mid, _Last, _Dest);
1729 : return (_STDEXT unchecked_copy(_First, _Mid, _Dest));
1730 : }
1731 :
1732 : #if _SECURE_SCL
1733 :
1734 : template<class _FwdIt, class _OutIt>
1735 : inline
1736 : _IF_CHK(_OutIt) rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
1737 : {
1738 : return _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
1739 : }
1740 :
1741 : template<class _FwdIt, class _OutElem, size_t _Size>
1742 : inline
1743 : _OutElem* rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutElem (&_Dest)[_Size])
1744 : {
1745 : return (rotate_copy(_First, _Mid, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
1746 : }
1747 :
1748 : template<class _FwdIt, class _OutIt>
1749 : inline
1750 : _SCL_INSECURE_DEPRECATE
1751 : _IF_NOT_CHK(_OutIt) rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
1752 : {
1753 : return _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
1754 : }
1755 :
1756 : #else
1757 :
1758 : template<class _FwdIt, class _OutIt>
1759 : inline
1760 : _OutIt rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
1761 : {
1762 : return _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
1763 : }
1764 :
1765 : #endif
1766 :
1767 : // TEMPLATE FUNCTION random_shuffle
1768 : template<class _RanIt,
1769 : class _Diff> inline
1770 : void _Random_shuffle(_RanIt _First, _RanIt _Last, _Diff *)
1771 : { // shuffle [_First, _Last)
1772 : _DEBUG_RANGE(_First, _Last);
1773 : const int _RANDOM_BITS = 15; // minimum random bits from rand()
1774 : const int _RANDOM_MAX = (1U << _RANDOM_BITS) - 1;
1775 :
1776 : _RanIt _Next = _First;
1777 : for (unsigned long _Index = 2; ++_Next != _Last; ++_Index)
1778 : { // assume unsigned long big enough for _Diff count
1779 : unsigned long _Rm = _RANDOM_MAX;
1780 : unsigned long _Rn = ::rand() & _RANDOM_MAX;
1781 : for (; _Rm < _Index && _Rm != ~0UL;
1782 : _Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX)
1783 : _Rn = _Rn << _RANDOM_BITS
1784 : | (::rand() & _RANDOM_MAX); // build random value
1785 :
1786 : std::iter_swap(_Next, _First + _Diff(_Rn % _Index)); // swap a pair
1787 : }
1788 : }
1789 :
1790 : template<class _RanIt> inline
1791 : void random_shuffle(_RanIt _First, _RanIt _Last)
1792 : { // shuffle [_First, _Last)
1793 : if (_First != _Last)
1794 : _Random_shuffle(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dist_type(_First));
1795 : }
1796 :
1797 : // TEMPLATE FUNCTION random_shuffle WITH RANDOM FN
1798 : template<class _RanIt,
1799 : class _Fn1,
1800 : class _Diff> inline
1801 : void _Random_shuffle(_RanIt _First, _RanIt _Last, _Fn1& _Func, _Diff *)
1802 : { // shuffle nonempty [_First, _Last) using random function _Func
1803 : _DEBUG_RANGE(_First, _Last);
1804 : _DEBUG_POINTER(_Func);
1805 : _RanIt _Next = _First;
1806 :
1807 : for (_Diff _Index = 2; ++_Next != _Last; ++_Index)
1808 : std::iter_swap(_Next, _First + _Diff(_Func(_Index) % _Index));
1809 : }
1810 :
1811 : template<class _RanIt,
1812 : class _Fn1> inline
1813 : void random_shuffle(_RanIt _First, _RanIt _Last, _Fn1& _Func)
1814 : { // shuffle [_First, _Last) using random function _Func
1815 : if (_First != _Last)
1816 : _Random_shuffle(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Func, _Dist_type(_First));
1817 : }
1818 :
1819 : // TEMPLATE FUNCTION partition
1820 : template<class _BidIt,
1821 : class _Pr> inline
1822 : _BidIt _Partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
1823 : { // move elements satisfying _Pred to beginning of sequence
1824 : _DEBUG_RANGE(_First, _Last);
1825 : _DEBUG_POINTER(_Pred);
1826 : for (; ; ++_First)
1827 : { // find any out-of-order pair
1828 : for (; _First != _Last && _Pred(*_First); ++_First)
1829 : ; // skip in-place elements at beginning
1830 : if (_First == _Last)
1831 : break; // done
1832 :
1833 : for (; _First != --_Last && !_Pred(*_Last); )
1834 : ; // skip in-place elements at end
1835 : if (_First == _Last)
1836 : break; // done
1837 :
1838 : std::iter_swap(_First, _Last); // swap out-of-place pair and loop
1839 : }
1840 : return (_First);
1841 : }
1842 :
1843 : template<class _BidIt,
1844 : class _Pr> inline
1845 : _BidIt partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
1846 : { // move elements satisfying _Pred to beginning of sequence
1847 : _ASSIGN_FROM_BASE(_First,
1848 : _Partition(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
1849 : return (_First);
1850 : }
1851 :
1852 : // TEMPLATE FUNCTION stable_partition
1853 : template<class _BidIt,
1854 : class _Pr,
1855 : class _Diff,
1856 : class _Ty> inline
1857 : _BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
1858 : _Diff _Count, _Temp_iterator<_Ty>& _Tempbuf)
1859 : { // partition preserving order of equivalents, using _Pred
1860 : if (_Count == 0)
1861 : return (_First);
1862 : else if (_Count == 1)
1863 : return (_Pred(*_First) ? _Last : _First);
1864 : else if (_Count <= _Tempbuf._Maxlen())
1865 : { // temp buffer big enough, copy right partition out and back
1866 : _BidIt _Next = _First;
1867 : for (_Tempbuf._Init(); _First != _Last; ++_First)
1868 : if (_Pred(*_First))
1869 : *_Next++ = *_First;
1870 : else
1871 : *_Tempbuf++ = *_First;
1872 :
1873 : _STDEXT unchecked_copy(_Tempbuf._First(), _Tempbuf._Last(), _Next); // copy back
1874 : return (_Next);
1875 : }
1876 : else
1877 : { // temp buffer not big enough, divide and conquer
1878 : _BidIt _Mid = _First;
1879 : std::advance(_Mid, _Count / 2);
1880 :
1881 : _BidIt _Left = _Stable_partition(_First, _Mid, _Pred,
1882 : _Count / 2, _Tempbuf); // form L1R1 in left half
1883 : _BidIt _Right = _Stable_partition(_Mid, _Last, _Pred,
1884 : _Count - _Count / 2, _Tempbuf); // form L2R2 in right half
1885 :
1886 : _Diff _Count1 = 0;
1887 : _Distance(_Left, _Mid, _Count1);
1888 : _Diff _Count2 = 0;
1889 : _Distance(_Mid, _Right, _Count2);
1890 :
1891 : return (_Buffered_rotate(_Left, _Mid, _Right,
1892 : _Count1, _Count2, _Tempbuf)); // rotate L1R1L2R2 to L1L2R1R2
1893 : }
1894 : }
1895 :
1896 : template<class _BidIt,
1897 : class _Pr,
1898 : class _Diff,
1899 : class _Ty> inline
1900 : _BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
1901 : _Diff *, _Ty *)
1902 : { // partition preserving order of equivalents, using _Pred
1903 : _Diff _Count = 0;
1904 : _Distance(_First, _Last, _Count);
1905 : _Temp_iterator<_Ty> _Tempbuf(_Count);
1906 : return (_Stable_partition(_First, _Last, _Pred, _Count, _Tempbuf));
1907 : }
1908 :
1909 : template<class _BidIt,
1910 : class _Pr> inline
1911 : _BidIt stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
1912 : { // partition preserving order of equivalents, using _Pred
1913 : if (_First != _Last)
1914 : {
1915 : _ASSIGN_FROM_BASE(_First,
1916 : _Stable_partition(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred,
1917 : _Dist_type(_First), _Val_type(_First)));
1918 : }
1919 : return _First;
1920 : }
1921 :
1922 : #ifndef _DEBUG_HEAP_IMPL
1923 : #define _DEBUG_HEAP_IMPL _Debug_heap
1924 : #endif
1925 :
1926 : #if _HAS_ITERATOR_DEBUGGING
1927 : // TEMPLATE FUNCTION _Debug_heap
1928 : template<class _RanIt> inline
1929 : void _Debug_heap(_RanIt _First, _RanIt _Last)
1930 : { // test if range is a heap ordered by operator<
1931 : if (_First != _Last)
1932 : for (_RanIt _Root = _First; ++_First != _Last; ++_Root)
1933 : if (_DEBUG_LT(*_Root, *_First))
1934 : _DEBUG_ERROR("invalid heap");
1935 : else if (++_First == _Last)
1936 : break;
1937 : else if (_DEBUG_LT(*_Root, *_First))
1938 : _DEBUG_ERROR("invalid heap");
1939 : }
1940 :
1941 : // TEMPLATE FUNCTION _Debug_heap WITH PRED
1942 : template<class _RanIt,
1943 : class _Pr> inline
1944 : void _Debug_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
1945 : { // test if range is a heap ordered by _Pred
1946 : if (_First != _Last)
1947 : for (_RanIt _Root = _First; ++_First != _Last; ++_Root)
1948 : if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
1949 : _DEBUG_ERROR("invalid heap");
1950 : else if (++_First == _Last)
1951 : break;
1952 : else if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
1953 : _DEBUG_ERROR("invalid heap");
1954 : }
1955 :
1956 : #define _DEBUG_HEAP(first, last) \
1957 : _DEBUG_HEAP_IMPL(first, last)
1958 : #define _DEBUG_HEAP_PRED(first, last, pred) \
1959 : _DEBUG_HEAP_IMPL(first, last, pred)
1960 :
1961 : #else /* _HAS_ITERATOR_DEBUGGING */
1962 : #define _DEBUG_HEAP(first, last)
1963 : #define _DEBUG_HEAP_PRED(first, last, pred)
1964 : #endif /* _HAS_ITERATOR_DEBUGGING */
1965 :
1966 : // TEMPLATE FUNCTION push_heap
1967 : template<class _RanIt,
1968 : class _Diff,
1969 : class _Ty> inline
1970 : void _Push_heap(_RanIt _First, _Diff _Hole,
1971 : _Diff _Top, _Ty _Val)
1972 : { // percolate _Hole to _Top or where _Val belongs, using operator<
1973 : for (_Diff _Idx = (_Hole - 1) / 2;
1974 : _Top < _Hole && _DEBUG_LT(*(_First + _Idx), _Val);
1975 : _Idx = (_Hole - 1) / 2)
1976 : { // move _Hole up to parent
1977 : *(_First + _Hole) = *(_First + _Idx);
1978 : _Hole = _Idx;
1979 : }
1980 :
1981 : *(_First + _Hole) = _Val; // drop _Val into final hole
1982 : }
1983 :
1984 : template<class _RanIt,
1985 : class _Diff,
1986 : class _Ty> inline
1987 : void _Push_heap_0(_RanIt _First, _RanIt _Last, _Diff *, _Ty *)
1988 : { // push *_Last onto heap at [_First, _Last), using operator<
1989 : _Diff _Count = _Last - _First;
1990 : if (0 < _Count)
1991 : std::_Push_heap(_First, _Count, _Diff(0), _Ty(*_Last));
1992 : }
1993 :
1994 : template<class _RanIt> inline
1995 : void push_heap(_RanIt _First, _RanIt _Last)
1996 : { // push *(_Last - 1) onto heap at [_First, _Last - 1), using operator<
1997 : _DEBUG_RANGE(_First, _Last);
1998 : if (_First != _Last)
1999 : { // check and push to nontrivial heap
2000 : _DEBUG_HEAP(_First, _Last - 1);
2001 : std::_Push_heap_0(_CHECKED_BASE(_First), _CHECKED_BASE(--_Last),
2002 : _Dist_type(_First), _Val_type(_First));
2003 : }
2004 : }
2005 :
2006 : // TEMPLATE FUNCTION push_heap WITH PRED
2007 : template<class _RanIt,
2008 : class _Diff,
2009 : class _Ty,
2010 : class _Pr> inline
2011 : void _Push_heap(_RanIt _First, _Diff _Hole,
2012 : _Diff _Top, _Ty _Val, _Pr _Pred)
2013 : { // percolate _Hole to _Top or where _Val belongs, using operator<
2014 : for (_Diff _Idx = (_Hole - 1) / 2;
2015 : _Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val);
2016 : _Idx = (_Hole - 1) / 2)
2017 : { // move _Hole up to parent
2018 : *(_First + _Hole) = *(_First + _Idx);
2019 : _Hole = _Idx;
2020 : }
2021 :
2022 : *(_First + _Hole) = _Val; // drop _Val into final hole
2023 : }
2024 :
2025 : template<class _RanIt,
2026 : class _Diff,
2027 : class _Ty,
2028 : class _Pr> inline
2029 : void _Push_heap_0(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
2030 : { // push *_Last onto heap at [_First, _Last), using _Pred
2031 : _Diff _Count = _Last - _First;
2032 : if (0 < _Count)
2033 : std::_Push_heap(_First, _Count, _Diff(0), _Ty(*_Last), _Pred);
2034 : }
2035 :
2036 : template<class _RanIt,
2037 : class _Pr> inline
2038 : void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
2039 : { // push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
2040 : _DEBUG_RANGE(_First, _Last);
2041 : _DEBUG_POINTER(_Pred);
2042 : if (_First != _Last)
2043 : { // check and push to nontrivial heap
2044 : _DEBUG_HEAP_PRED(_First, _Last - 1, _Pred);
2045 : std::_Push_heap_0(_CHECKED_BASE(_First), _CHECKED_BASE(--_Last), _Pred,
2046 : _Dist_type(_First), _Val_type(_First));
2047 : }
2048 : }
2049 :
2050 : // TEMPLATE FUNCTION pop_heap
2051 : template<class _RanIt,
2052 : class _Diff,
2053 : class _Ty> inline
2054 : void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom, _Ty _Val)
2055 : { // percolate _Hole to _Bottom, then push _Val, using operator<
2056 : _Diff _Top = _Hole;
2057 : _Diff _Idx = 2 * _Hole + 2;
2058 :
2059 : for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
2060 : { // move _Hole down to larger child
2061 : if (_DEBUG_LT(*(_First + _Idx), *(_First + (_Idx - 1))))
2062 : --_Idx;
2063 : *(_First + _Hole) = *(_First + _Idx), _Hole = _Idx;
2064 : }
2065 :
2066 : if (_Idx == _Bottom)
2067 : { // only child at bottom, move _Hole down to it
2068 : *(_First + _Hole) = *(_First + (_Bottom - 1));
2069 : _Hole = _Bottom - 1;
2070 : }
2071 : std::_Push_heap(_First, _Hole, _Top, _Val);
2072 : }
2073 :
2074 : template<class _RanIt,
2075 : class _Diff,
2076 : class _Ty> inline
2077 : void _Pop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
2078 : _Ty _Val, _Diff *)
2079 : { // pop *_First to *_Dest and reheap, using operator<
2080 : *_Dest = *_First;
2081 : std::_Adjust_heap(_First, _Diff(0), _Diff(_Last - _First), _Val);
2082 : }
2083 :
2084 : template<class _RanIt,
2085 : class _Ty> inline
2086 : void _Pop_heap_0(_RanIt _First, _RanIt _Last, _Ty *)
2087 : { // pop *_First to *(_Last - 1) and reheap, using operator<
2088 : _Pop_heap(_First, _Last - 1, _Last - 1,
2089 : _Ty(*(_Last - 1)), _Dist_type(_First));
2090 : }
2091 :
2092 : template<class _RanIt> inline
2093 : void pop_heap(_RanIt _First, _RanIt _Last)
2094 : { // pop *_First to *(_Last - 1) and reheap, using operator<
2095 : _DEBUG_RANGE(_First, _Last);
2096 : _DEBUG_HEAP(_First, _Last);
2097 : if (1 < _Last - _First)
2098 : _Pop_heap_0(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val_type(_First));
2099 : }
2100 :
2101 : // TEMPLATE FUNCTION pop_heap WITH PRED
2102 : template<class _RanIt,
2103 : class _Diff,
2104 : class _Ty,
2105 : class _Pr> inline
2106 : void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom,
2107 : _Ty _Val, _Pr _Pred)
2108 : { // percolate _Hole to _Bottom, then push _Val, using _Pred
2109 : _Diff _Top = _Hole;
2110 : _Diff _Idx = 2 * _Hole + 2;
2111 :
2112 : for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
2113 : { // move _Hole down to larger child
2114 : if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1))))
2115 : --_Idx;
2116 : *(_First + _Hole) = *(_First + _Idx), _Hole = _Idx;
2117 : }
2118 :
2119 : if (_Idx == _Bottom)
2120 : { // only child at bottom, move _Hole down to it
2121 : *(_First + _Hole) = *(_First + (_Bottom - 1));
2122 : _Hole = _Bottom - 1;
2123 : }
2124 : std::_Push_heap(_First, _Hole, _Top, _Val, _Pred);
2125 : }
2126 :
2127 : template<class _RanIt,
2128 : class _Diff,
2129 : class _Ty,
2130 : class _Pr> inline
2131 : void _Pop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
2132 : _Ty _Val, _Pr _Pred, _Diff *)
2133 : { // pop *_First to *_Dest and reheap, using _Pred
2134 : *_Dest = *_First;
2135 : std::_Adjust_heap(_First, _Diff(0), _Diff(_Last - _First),
2136 : _Val, _Pred);
2137 : }
2138 :
2139 : template<class _RanIt,
2140 : class _Ty,
2141 : class _Pr> inline
2142 : void _Pop_heap_0(_RanIt _First, _RanIt _Last, _Pr _Pred, _Ty *)
2143 : { // pop *_First to *(_Last - 1) and reheap, using _Pred
2144 : _Pop_heap(_First, _Last - 1, _Last - 1,
2145 : _Ty(*(_Last - 1)), _Pred, _Dist_type(_First));
2146 : }
2147 :
2148 : template<class _RanIt,
2149 : class _Pr> inline
2150 : void pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
2151 : { // pop *_First to *(_Last - 1) and reheap, using _Pred
2152 : _DEBUG_RANGE(_First, _Last);
2153 : _DEBUG_POINTER(_Pred);
2154 : _DEBUG_HEAP_PRED(_First, _Last, _Pred);
2155 : if (1 < _Last - _First)
2156 : _Pop_heap_0(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred, _Val_type(_First));
2157 : }
2158 :
2159 : // TEMPLATE FUNCTION make_heap
2160 : template<class _RanIt,
2161 : class _Diff,
2162 : class _Ty> inline
2163 : void _Make_heap(_RanIt _First, _RanIt _Last, _Diff *, _Ty *)
2164 : { // make nontrivial [_First, _Last) into a heap, using operator<
2165 : _Diff _Bottom = _Last - _First;
2166 :
2167 : for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
2168 : { // reheap top half, bottom to top
2169 : --_Hole;
2170 : std::_Adjust_heap(_First, _Hole, _Bottom,
2171 : _Ty(*(_First + _Hole)));
2172 : }
2173 : }
2174 :
2175 : template<class _RanIt> inline
2176 : void make_heap(_RanIt _First, _RanIt _Last)
2177 : { // make [_First, _Last) into a heap, using operator<
2178 : _DEBUG_RANGE(_First, _Last);
2179 : if (1 < _Last - _First)
2180 : _Make_heap(_CHECKED_BASE(_First), _CHECKED_BASE(_Last),
2181 : _Dist_type(_First), _Val_type(_First));
2182 : }
2183 :
2184 : // TEMPLATE FUNCTION make_heap WITH PRED
2185 : template<class _RanIt,
2186 : class _Diff,
2187 : class _Ty,
2188 : class _Pr> inline
2189 : void _Make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
2190 : { // make nontrivial [_First, _Last) into a heap, using _Pred
2191 : _Diff _Bottom = _Last - _First;
2192 : for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
2193 : { // reheap top half, bottom to top
2194 : --_Hole;
2195 : std::_Adjust_heap(_First, _Hole, _Bottom,
2196 : _Ty(*(_First + _Hole)), _Pred);
2197 : }
2198 : }
2199 :
2200 : template<class _RanIt,
2201 : class _Pr> inline
2202 : void make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
2203 : { // make [_First, _Last) into a heap, using _Pred
2204 : _DEBUG_RANGE(_First, _Last);
2205 : _DEBUG_POINTER(_Pred);
2206 : if (1 < _Last - _First)
2207 : _Make_heap(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred,
2208 : _Dist_type(_First), _Val_type(_First));
2209 : }
2210 :
2211 : // TEMPLATE FUNCTION sort_heap
2212 : template<class _RanIt> inline
2213 : void _Sort_heap(_RanIt _First, _RanIt _Last)
2214 : { // order heap by repeatedly popping, using operator<
2215 : _DEBUG_RANGE(_First, _Last);
2216 : _DEBUG_HEAP(_First, _Last);
2217 : for (; 1 < _Last - _First; --_Last)
2218 : std::pop_heap(_First, _Last);
2219 : }
2220 :
2221 : template<class _RanIt> inline
2222 : void sort_heap(_RanIt _First, _RanIt _Last)
2223 : { // order heap by repeatedly popping, using operator<
2224 : _DEBUG_HEAP(_First, _Last);
2225 : _Sort_heap(_CHECKED_BASE(_First), _CHECKED_BASE(_Last));
2226 : }
2227 :
2228 : // TEMPLATE FUNCTION sort_heap WITH PRED
2229 : template<class _RanIt,
2230 : class _Pr> inline
2231 : void _Sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
2232 : { // order heap by repeatedly popping, using _Pred
2233 : for (; 1 < _Last - _First; --_Last)
2234 : std::pop_heap(_First, _Last, _Pred);
2235 : }
2236 :
2237 : template<class _RanIt,
2238 : class _Pr> inline
2239 : void sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
2240 : { // order heap by repeatedly popping, using _Pred
2241 : _DEBUG_RANGE(_First, _Last);
2242 : _DEBUG_POINTER(_Pred);
2243 : _DEBUG_HEAP_PRED(_First, _Last, _Pred);
2244 : _Sort_heap(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred);
2245 : }
2246 :
2247 : // TEMPLATE FUNCTION lower_bound
2248 : template<class _FwdIt,
2249 : class _Ty,
2250 : class _Diff> inline
2251 : _FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
2252 : { // find first element not before _Val, using operator<
2253 : _DEBUG_ORDER_SINGLE(_First, _Last, true);
2254 : _Diff _Count = 0;
2255 : _Distance(_First, _Last, _Count);
2256 :
2257 : for (; 0 < _Count; )
2258 : { // divide and conquer, find half that contains answer
2259 : _Diff _Count2 = _Count / 2;
2260 : _FwdIt _Mid = _First;
2261 : std::advance(_Mid, _Count2);
2262 : _DEBUG_ORDER_SINGLE(_Mid, _Last, false);
2263 :
2264 : if (_DEBUG_LT(*_Mid, _Val))
2265 : _First = ++_Mid, _Count -= _Count2 + 1;
2266 : else
2267 : _Count = _Count2;
2268 : }
2269 : return (_First);
2270 : }
2271 :
2272 : template<class _FwdIt,
2273 : class _Ty> inline
2274 : _FwdIt lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
2275 : { // find first element not before _Val, using operator<
2276 : _ASSIGN_FROM_BASE(_First,
2277 : _Lower_bound(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val, _Dist_type(_First)));
2278 : return _First;
2279 : }
2280 :
2281 : // TEMPLATE FUNCTION lower_bound WITH PRED
2282 : template<class _FwdIt,
2283 : class _Ty,
2284 : class _Diff,
2285 : class _Pr> inline
2286 : _FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last,
2287 : const _Ty& _Val, _Pr _Pred, _Diff *)
2288 : { // find first element not before _Val, using _Pred
2289 : _DEBUG_POINTER(_Pred);
2290 : _DEBUG_ORDER_SINGLE_PRED(_First, _Last, _Pred, true);
2291 : _Diff _Count = 0;
2292 : _Distance(_First, _Last, _Count);
2293 : for (; 0 < _Count; )
2294 : { // divide and conquer, find half that contains answer
2295 : _Diff _Count2 = _Count / 2;
2296 : _FwdIt _Mid = _First;
2297 : std::advance(_Mid, _Count2);
2298 : _DEBUG_ORDER_SINGLE_PRED(_Mid, _Last, _Pred, false);
2299 :
2300 : if (_DEBUG_LT_PRED(_Pred, *_Mid, _Val))
2301 : _First = ++_Mid, _Count -= _Count2 + 1;
2302 : else
2303 : _Count = _Count2;
2304 : }
2305 : return (_First);
2306 : }
2307 :
2308 : template<class _FwdIt,
2309 : class _Ty,
2310 : class _Pr> inline
2311 : _FwdIt lower_bound(_FwdIt _First, _FwdIt _Last,
2312 : const _Ty& _Val, _Pr _Pred)
2313 : { // find first element not before _Val, using _Pred
2314 : _ASSIGN_FROM_BASE(_First,
2315 : _Lower_bound(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val, _Pred, _Dist_type(_First)));
2316 : return _First;
2317 : }
2318 :
2319 : // TEMPLATE FUNCTION upper_bound
2320 : template<class _FwdIt,
2321 : class _Ty,
2322 : class _Diff> inline
2323 : _FwdIt _Upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
2324 : { // find first element that _Val is before, using operator<
2325 : _DEBUG_ORDER_SINGLE(_First, _Last, true);
2326 : _Diff _Count = 0;
2327 : _Distance(_First, _Last, _Count);
2328 : for (; 0 < _Count; )
2329 : { // divide and conquer, find half that contains answer
2330 : _Diff _Count2 = _Count / 2;
2331 : _FwdIt _Mid = _First;
2332 : std::advance(_Mid, _Count2);
2333 : _DEBUG_ORDER_SINGLE(_Mid, _Last, false);
2334 :
2335 : if (!_DEBUG_LT(_Val, *_Mid))
2336 : _First = ++_Mid, _Count -= _Count2 + 1;
2337 : else
2338 : _Count = _Count2;
2339 : }
2340 : return (_First);
2341 : }
2342 :
2343 : template<class _FwdIt,
2344 : class _Ty> inline
2345 : _FwdIt upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
2346 : { // find first element that _Val is before, using operator<
2347 : _ASSIGN_FROM_BASE(_First,
2348 : _Upper_bound(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val, _Dist_type(_First)));
2349 : return _First;
2350 : }
2351 :
2352 : // TEMPLATE FUNCTION upper_bound WITH PRED
2353 : template<class _FwdIt,
2354 : class _Ty,
2355 : class _Diff,
2356 : class _Pr> inline
2357 : _FwdIt _Upper_bound(_FwdIt _First, _FwdIt _Last,
2358 : const _Ty& _Val, _Pr _Pred, _Diff *)
2359 : { // find first element that _Val is before, using _Pred
2360 : _DEBUG_POINTER(_Pred);
2361 : _DEBUG_ORDER_SINGLE_PRED(_First, _Last, _Pred, true);
2362 : _Diff _Count = 0;
2363 : _Distance(_First, _Last, _Count);
2364 : for (; 0 < _Count; )
2365 : { // divide and conquer, find half that contains answer
2366 : _Diff _Count2 = _Count / 2;
2367 : _FwdIt _Mid = _First;
2368 : std::advance(_Mid, _Count2);
2369 : _DEBUG_ORDER_SINGLE_PRED(_Mid, _Last, _Pred, false);
2370 :
2371 : if (!_DEBUG_LT_PRED(_Pred, _Val, *_Mid))
2372 : _First = ++_Mid, _Count -= _Count2 + 1;
2373 : else
2374 : _Count = _Count2;
2375 : }
2376 : return (_First);
2377 : }
2378 :
2379 : template<class _FwdIt,
2380 : class _Ty,
2381 : class _Pr> inline
2382 : _FwdIt upper_bound(_FwdIt _First, _FwdIt _Last,
2383 : const _Ty& _Val, _Pr _Pred)
2384 : { // find first element that _Val is before, using _Pred
2385 : _ASSIGN_FROM_BASE(_First,
2386 : _Upper_bound(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val, _Pred, _Dist_type(_First)));
2387 : return _First;
2388 : }
2389 :
2390 : // TEMPLATE FUNCTION equal_range
2391 : template<class _FwdIt,
2392 : class _Ty,
2393 : class _Diff> inline
2394 : pair<_FwdIt, _FwdIt> _Equal_range(_FwdIt _First, _FwdIt _Last,
2395 : const _Ty& _Val, _Diff *)
2396 : { // find range equivalent to _Val, using operator<
2397 : _DEBUG_ORDER_SINGLE(_First, _Last, true);
2398 : _Diff _Count = 0;
2399 : _Distance(_First, _Last, _Count);
2400 :
2401 : for (; 0 < _Count; )
2402 : { // divide and conquer, check midpoint
2403 : _Diff _Count2 = _Count / 2;
2404 : _FwdIt _Mid = _First;
2405 : std::advance(_Mid, _Count2);
2406 : _DEBUG_ORDER_SINGLE(_Mid, _Last, false);
2407 :
2408 : if (_DEBUG_LT(*_Mid, _Val))
2409 : { // range begins above _Mid, loop
2410 : _First = ++_Mid;
2411 : _Count -= _Count2 + 1;
2412 : }
2413 : else if (_Val < *_Mid)
2414 : _Count = _Count2; // range in first half, loop
2415 : else
2416 : { // range straddles mid, find each end and return
2417 : _FwdIt _First2 = lower_bound(_First, _Mid, _Val);
2418 : std::advance(_First, _Count);
2419 : _FwdIt _Last2 = upper_bound(++_Mid, _First, _Val);
2420 : return (pair<_FwdIt, _FwdIt>(_First2, _Last2));
2421 : }
2422 : }
2423 :
2424 : return (pair<_FwdIt, _FwdIt>(_First, _First)); // empty range
2425 : }
2426 :
2427 : template<class _FwdIt,
2428 : class _Ty> inline
2429 : pair<_FwdIt, _FwdIt> equal_range(_FwdIt _First, _FwdIt _Last,
2430 : const _Ty& _Val)
2431 : { // find range equivalent to _Val, using operator<
2432 : return (_Equal_range(_First, _Last, _Val, _Dist_type(_First)));
2433 : }
2434 :
2435 : // TEMPLATE FUNCTION equal_range WITH PRED
2436 : template<class _FwdIt,
2437 : class _Ty,
2438 : class _Diff,
2439 : class _Pr> inline
2440 : pair<_FwdIt, _FwdIt> _Equal_range(_FwdIt _First, _FwdIt _Last,
2441 : const _Ty& _Val, _Pr _Pred, _Diff *)
2442 : { // find range equivalent to _Val, using _Pred
2443 : _DEBUG_POINTER(_Pred);
2444 : _DEBUG_ORDER_SINGLE_PRED(_First, _Last, _Pred, true);
2445 : _Diff _Count = 0;
2446 : _Distance(_First, _Last, _Count);
2447 :
2448 : for (; 0 < _Count; )
2449 : { // divide and conquer, check midpoint
2450 : _Diff _Count2 = _Count / 2;
2451 : _FwdIt _Mid = _First;
2452 : std::advance(_Mid, _Count2);
2453 : _DEBUG_ORDER_SINGLE_PRED(_Mid, _Last, _Pred, false);
2454 :
2455 : if (_DEBUG_LT_PRED(_Pred, *_Mid, _Val))
2456 : { // range begins above _Mid, loop
2457 : _First = ++_Mid;
2458 : _Count -= _Count2 + 1;
2459 : }
2460 : else if (_Pred(_Val, *_Mid))
2461 : _Count = _Count2; // range in first half, loop
2462 : else
2463 : { // range straddles _Mid, find each end and return
2464 : _FwdIt _First2 = lower_bound(_First, _Mid, _Val, _Pred);
2465 : std::advance(_First, _Count);
2466 : _FwdIt _Last2 = upper_bound(++_Mid, _First, _Val, _Pred);
2467 : return (pair<_FwdIt, _FwdIt>(_First2, _Last2));
2468 : }
2469 : }
2470 :
2471 : return (pair<_FwdIt, _FwdIt>(_First, _First)); // empty range
2472 : }
2473 :
2474 : template<class _FwdIt,
2475 : class _Ty,
2476 : class _Pr> inline
2477 : pair<_FwdIt, _FwdIt> equal_range(_FwdIt _First, _FwdIt _Last,
2478 : const _Ty& _Val, _Pr _Pred)
2479 : { // find range equivalent to _Val, using _Pred
2480 : return (_Equal_range(_First, _Last, _Val, _Pred, _Dist_type(_First)));
2481 : }
2482 :
2483 : // TEMPLATE FUNCTION binary_search
2484 : template<class _FwdIt,
2485 : class _Ty> inline
2486 : bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
2487 : { // test if _Val equivalent to some element, using operator<
2488 : _First = std::lower_bound(_First, _Last, _Val);
2489 : return (_First != _Last && !(_Val < *_First));
2490 : }
2491 :
2492 : // TEMPLATE FUNCTION binary_search WITH PRED
2493 : template<class _FwdIt,
2494 : class _Ty,
2495 : class _Pr> inline
2496 : bool binary_search(_FwdIt _First, _FwdIt _Last,
2497 : const _Ty& _Val, _Pr _Pred)
2498 : { // test if _Val equivalent to some element, using _Pred
2499 : _First = std::lower_bound(_First, _Last, _Val, _Pred);
2500 : return (_First != _Last && !_Pred(_Val, *_First));
2501 : }
2502 :
2503 : // TEMPLATE FUNCTION merge
2504 : template<class _InIt1, class _InIt2, class _OutIt, class _InOutItCat>
2505 : inline
2506 : _OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2507 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest,
2508 : _InOutItCat, _Range_checked_iterator_tag)
2509 : { // copy merging ranges, both using operator<
2510 : _DEBUG_ORDER(_First1, _Last1);
2511 : _DEBUG_ORDER(_First2, _Last2);
2512 : _DEBUG_POINTER(_Dest);
2513 : for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
2514 : if (_DEBUG_LT(*_First2, *_First1))
2515 : *_Dest = *_First2, ++_First2;
2516 : else
2517 : *_Dest = *_First1, ++_First1;
2518 :
2519 : _Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest); // copy any tail
2520 : return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
2521 : }
2522 :
2523 : #if _SECURE_SCL
2524 : template<class _InIt1, class _InIt2, class _OutIt>
2525 : inline
2526 : _OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2527 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest,
2528 : random_access_iterator_tag, _Range_checked_iterator_tag)
2529 : { // copy merging ranges, both using operator<
2530 : // for range checked iterators, this will make sure there is enough space
2531 : _OutIt _Result = _Dest + (_Last1 - _First1) + (_Last2 - _First2);
2532 : _Merge(_First1, _Last1, _First2, _Last2, _CHECKED_BASE(_Dest),
2533 : forward_iterator_tag(), _Range_checked_iterator_tag());
2534 : return _Result;
2535 : }
2536 : #endif
2537 :
2538 : #if _SECURE_SCL
2539 :
2540 : template<class _InIt1,
2541 : class _InIt2,
2542 : class _OutIt> inline
2543 : _IF_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2544 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
2545 : { // copy merging ranges, both using operator<
2546 : return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2547 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
2548 : _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2549 : }
2550 :
2551 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
2552 : inline
2553 : _OutElem* merge(_InIt1 _First1, _InIt1 _Last1,
2554 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
2555 : { // copy merging ranges, both using operator<
2556 : return (merge(_First1, _Last1, _First2, _Last2,
2557 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
2558 : }
2559 :
2560 : template<class _InIt1,
2561 : class _InIt2,
2562 : class _OutIt> inline
2563 : _SCL_INSECURE_DEPRECATE
2564 : _IF_NOT_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2565 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
2566 : { // copy merging ranges, both using operator<
2567 : return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2568 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
2569 : _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2570 : }
2571 :
2572 : #else
2573 :
2574 : template<class _InIt1,
2575 : class _InIt2,
2576 : class _OutIt> inline
2577 : _OutIt merge(_InIt1 _First1, _InIt1 _Last1,
2578 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
2579 : { // copy merging ranges, both using operator<
2580 : return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2581 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
2582 : _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2583 : }
2584 :
2585 : #endif
2586 :
2587 : // TEMPLATE FUNCTION merge WITH PRED
2588 : template<class _InIt1, class _InIt2, class _OutIt, class _Pr, class _InOutItCat>
2589 : inline
2590 : _OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2591 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred,
2592 : _InOutItCat, _Range_checked_iterator_tag)
2593 : { // copy merging ranges, both using _Pred
2594 : _DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
2595 : _DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
2596 : _DEBUG_POINTER(_Dest);
2597 : for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
2598 : if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
2599 : *_Dest = *_First2, ++_First2;
2600 : else
2601 : *_Dest = *_First1, ++_First1;
2602 :
2603 : _Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest); // copy any tail
2604 : return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
2605 : }
2606 :
2607 : #if _SECURE_SCL
2608 : template<class _InIt1, class _InIt2, class _OutIt, class _Pr>
2609 : inline
2610 : _OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
2611 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred,
2612 : random_access_iterator_tag, _Range_checked_iterator_tag)
2613 : { // copy merging ranges, both using _Pred
2614 : // for range checked iterators, this will make sure there is enough space
2615 : _OutIt _Result = _Dest + (_Last1 - _First1) + (_Last2 - _First2);
2616 : _Merge(_First1, _Last1, _First2, _Last2, _CHECKED_BASE(_Dest), _Pred,
2617 : forward_iterator_tag(), _Range_checked_iterator_tag());
2618 : return _Result;
2619 : }
2620 : #endif
2621 :
2622 : #if _SECURE_SCL
2623 :
2624 : template<class _InIt1,
2625 : class _InIt2,
2626 : class _OutIt,
2627 : class _Pr> inline
2628 : _IF_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2629 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
2630 : { // copy merging ranges, both using _Pred
2631 : return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2632 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
2633 : _Dest, _Pred,
2634 : _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2635 : }
2636 :
2637 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
2638 : inline
2639 : _OutElem* merge(_InIt1 _First1, _InIt1 _Last1,
2640 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
2641 : { // copy merging ranges, both using _Pred
2642 : return (merge(_First1, _Last1, _First2, _Last2,
2643 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
2644 : }
2645 :
2646 : template<class _InIt1,
2647 : class _InIt2,
2648 : class _OutIt,
2649 : class _Pr> inline
2650 : _SCL_INSECURE_DEPRECATE
2651 : _IF_NOT_CHK(_OutIt) merge(_InIt1 _First1, _InIt1 _Last1,
2652 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
2653 : { // copy merging ranges, both using _Pred
2654 : return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2655 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
2656 : _Dest, _Pred,
2657 : _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2658 : }
2659 :
2660 : #else
2661 :
2662 : template<class _InIt1,
2663 : class _InIt2,
2664 : class _OutIt,
2665 : class _Pr> inline
2666 : _OutIt merge(_InIt1 _First1, _InIt1 _Last1,
2667 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
2668 : { // copy merging ranges, both using _Pred
2669 : return _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
2670 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
2671 : _Dest, _Pred,
2672 : _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
2673 : }
2674 :
2675 : #endif
2676 :
2677 : // TEMPLATE FUNCTION inplace_merge
2678 : template<class _BidIt,
2679 : class _Diff,
2680 : class _Ty> inline
2681 : _BidIt _Buffered_rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2682 : _Diff _Count1, _Diff _Count2, _Temp_iterator<_Ty>& _Tempbuf)
2683 : { // rotate [_First, _Last) using temp buffer
2684 : if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2685 : { // buffer left partition, then copy parts
2686 : _STDEXT unchecked_copy(_First, _Mid, _Tempbuf._Init());
2687 : _STDEXT unchecked_copy(_Mid, _Last, _First);
2688 : return (_STDEXT unchecked_copy_backward(_Tempbuf._First(), _Tempbuf._Last(),
2689 : _Last));
2690 : }
2691 : else if (_Count2 <= _Tempbuf._Maxlen())
2692 : { // buffer right partition, then copy parts
2693 : _STDEXT unchecked_copy(_Mid, _Last, _Tempbuf._Init());
2694 : _STDEXT unchecked_copy_backward(_First, _Mid, _Last);
2695 : return (_STDEXT unchecked_copy(_Tempbuf._First(), _Tempbuf._Last(), _First));
2696 : }
2697 : else
2698 : { // buffer too small, rotate in place
2699 : std::rotate(_First, _Mid, _Last);
2700 : std::advance(_First, _Count2);
2701 : return (_First);
2702 : }
2703 : }
2704 :
2705 : template<class _BidIt1,
2706 : class _BidIt2,
2707 : class _BidIt3> inline
2708 : _BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2709 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Range_checked_iterator_tag)
2710 : { // merge backwards to _Dest, using operator<
2711 : for (; ; )
2712 : if (_First1 == _Last1)
2713 : return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
2714 : else if (_First2 == _Last2)
2715 : return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
2716 : else if (_DEBUG_LT(*--_Last2, *--_Last1))
2717 : *--_Dest = *_Last1, ++_Last2;
2718 : else
2719 : *--_Dest = *_Last2, ++_Last1;
2720 : }
2721 :
2722 : #if _SECURE_SCL
2723 :
2724 : template<class _BidIt1, class _BidIt2, class _BidIt3>
2725 : inline
2726 : _IF_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2727 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
2728 : {
2729 : return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
2730 : }
2731 :
2732 : template<class _BidIt1, class _BidIt2, class _BidIt3>
2733 : inline
2734 : _SCL_INSECURE_DEPRECATE
2735 : _IF_NOT_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2736 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
2737 : {
2738 : return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
2739 : }
2740 :
2741 : #else
2742 :
2743 : template<class _BidIt1, class _BidIt2, class _BidIt3>
2744 : inline
2745 : _BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2746 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
2747 : {
2748 : return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
2749 : }
2750 :
2751 : #endif
2752 :
2753 : template<class _BidIt,
2754 : class _Diff,
2755 : class _Ty> inline
2756 : void _Buffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2757 : _Diff _Count1, _Diff _Count2,
2758 : _Temp_iterator<_Ty>& _Tempbuf)
2759 : { // merge [_First, _Mid) with [_Mid, _Last), using operator<
2760 : if (_Count1 + _Count2 == 2)
2761 : { // order two one-element partitions
2762 : if (_DEBUG_LT(*_Mid, *_First))
2763 : std::iter_swap(_First, _Mid);
2764 : }
2765 : else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2766 : { // buffer left partition, then merge
2767 : _STDEXT unchecked_copy(_First, _Mid, _Tempbuf._Init());
2768 : _STDEXT unchecked_merge(_Tempbuf._First(), _Tempbuf._Last(), _Mid, _Last, _First);
2769 : }
2770 : else if (_Count2 <= _Tempbuf._Maxlen())
2771 : { // buffer right partition, then merge
2772 : _STDEXT unchecked_copy(_Mid, _Last, _Tempbuf._Init());
2773 : _STDEXT _Unchecked_merge_backward(_First, _Mid,
2774 : _Tempbuf._First(), _Tempbuf._Last(), _Last);
2775 : }
2776 : else
2777 : { // buffer too small, divide and conquer
2778 : _BidIt _Firstn, _Lastn;
2779 : _Diff _Count1n, _Count2n;
2780 :
2781 : if (_Count2 < _Count1)
2782 : { // left larger, cut it in half and partition right to match
2783 : _Count1n = _Count1 / 2, _Count2n = 0;
2784 : _Firstn = _First;
2785 : std::advance(_Firstn, _Count1n);
2786 : _Lastn = std::lower_bound(_Mid, _Last, *_Firstn);
2787 : _Distance(_Mid, _Lastn, _Count2n);
2788 : }
2789 : else
2790 : { // right larger, cut it in half and partition left to match
2791 : _Count1n = 0, _Count2n = _Count2 / 2;
2792 : _Lastn = _Mid;
2793 : std::advance(_Lastn, _Count2n);
2794 : _Firstn = std::upper_bound(_First, _Mid, *_Lastn);
2795 : _Distance(_First, _Firstn, _Count1n);
2796 : }
2797 :
2798 : _BidIt _Midn = _Buffered_rotate(_Firstn, _Mid, _Lastn,
2799 : _Count1 - _Count1n, _Count2n, _Tempbuf); // rearrange middle
2800 : _Buffered_merge(_First, _Firstn, _Midn,
2801 : _Count1n, _Count2n, _Tempbuf); // merge each new part
2802 : _Buffered_merge(_Midn, _Lastn, _Last,
2803 : _Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf);
2804 : }
2805 : }
2806 :
2807 : template<class _BidIt,
2808 : class _Diff,
2809 : class _Ty> inline
2810 : void _Inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2811 : _Diff *, _Ty *)
2812 : { // merge [_First, _Mid) with [_Mid, _Last), using operator<
2813 : _DEBUG_ORDER(_First, _Mid);
2814 : _DEBUG_ORDER(_Mid, _Last);
2815 : _Diff _Count1 = 0;
2816 : _Distance(_First, _Mid, _Count1);
2817 : _Diff _Count2 = 0;
2818 : _Distance(_Mid, _Last, _Count2);
2819 : _Temp_iterator<_Ty> _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
2820 : _Buffered_merge(_First, _Mid, _Last,
2821 : _Count1, _Count2, _Tempbuf);
2822 : }
2823 :
2824 : template<class _BidIt> inline
2825 : void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last)
2826 : { // merge [_First, _Mid) with [_Mid, _Last), using operator<
2827 : if (_First != _Mid && _Mid != _Last)
2828 : _Inplace_merge(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last),
2829 : _Dist_type(_First), _Val_type(_First));
2830 : }
2831 :
2832 : // TEMPLATE FUNCTION inplace_merge WITH PRED
2833 : template<class _BidIt1,
2834 : class _BidIt2,
2835 : class _BidIt3,
2836 : class _Pr> inline
2837 : _BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2838 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred, _Range_checked_iterator_tag)
2839 : { // merge backwards to _Dest, using _Pred
2840 : for (; ; )
2841 : if (_First1 == _Last1)
2842 : return (_STDEXT unchecked_copy_backward(_First2, _Last2, _Dest));
2843 : else if (_First2 == _Last2)
2844 : return (_STDEXT unchecked_copy_backward(_First1, _Last1, _Dest));
2845 : else if (_DEBUG_LT_PRED(_Pred, *--_Last2, *--_Last1))
2846 : *--_Dest = *_Last1, ++_Last2;
2847 : else
2848 : *--_Dest = *_Last2, ++_Last1;
2849 : }
2850 :
2851 : #if _SECURE_SCL
2852 :
2853 : template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
2854 : inline
2855 : _IF_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2856 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
2857 : {
2858 : return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
2859 : }
2860 :
2861 : template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
2862 : inline
2863 : _SCL_INSECURE_DEPRECATE
2864 : _IF_NOT_CHK(_BidIt3) _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2865 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
2866 : {
2867 : return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
2868 : }
2869 :
2870 : #else
2871 :
2872 : template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
2873 : inline
2874 : _BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2875 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
2876 : {
2877 : return _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
2878 : }
2879 :
2880 : #endif
2881 :
2882 : template<class _BidIt,
2883 : class _Diff,
2884 : class _Ty,
2885 : class _Pr> inline
2886 : void _Buffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2887 : _Diff _Count1, _Diff _Count2,
2888 : _Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
2889 : { // merge [_First, _Mid) with [_Mid, _Last), using _Pred
2890 : if (_Count1 + _Count2 == 2)
2891 : { // order two one-element partitions
2892 : if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
2893 : std::iter_swap(_First, _Mid);
2894 : }
2895 : else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2896 : { // buffer left partition, then merge
2897 : _STDEXT unchecked_copy(_First, _Mid, _Tempbuf._Init());
2898 : _STDEXT unchecked_merge(_Tempbuf._First(), _Tempbuf._Last(),
2899 : _Mid, _Last, _First, _Pred);
2900 : }
2901 : else if (_Count2 <= _Tempbuf._Maxlen())
2902 : { // buffer right partition, then merge
2903 : _STDEXT unchecked_copy(_Mid, _Last, _Tempbuf._Init());
2904 : _STDEXT _Unchecked_merge_backward(_First, _Mid, _Tempbuf._First(), _Tempbuf._Last(),
2905 : _Last, _Pred);
2906 : }
2907 : else
2908 : { // buffer too small, divide and conquer
2909 : _BidIt _Firstn, _Lastn;
2910 : _Diff _Count1n, _Count2n;
2911 : if (_Count2 < _Count1)
2912 : { // left larger, cut it in half and partition right to match
2913 : _Count1n = _Count1 / 2, _Count2n = 0;
2914 : _Firstn = _First;
2915 : std::advance(_Firstn, _Count1n);
2916 : _Lastn = lower_bound(_Mid, _Last, *_Firstn, _Pred);
2917 : _Distance(_Mid, _Lastn, _Count2n);
2918 : }
2919 : else
2920 : { // right larger, cut it in half and partition left to match
2921 : _Count1n = 0, _Count2n = _Count2 / 2;
2922 : _Lastn = _Mid;
2923 : std::advance(_Lastn, _Count2n);
2924 : _Firstn = upper_bound(_First, _Mid, *_Lastn, _Pred);
2925 : _Distance(_First, _Firstn, _Count1n);
2926 : }
2927 : _BidIt _Midn = _Buffered_rotate(_Firstn, _Mid, _Lastn,
2928 : _Count1 - _Count1n, _Count2n, _Tempbuf); // rearrange middle
2929 : _Buffered_merge(_First, _Firstn, _Midn,
2930 : _Count1n, _Count2n, _Tempbuf, _Pred); // merge each new part
2931 : _Buffered_merge(_Midn, _Lastn, _Last,
2932 : _Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf, _Pred);
2933 : }
2934 : }
2935 :
2936 : template<class _BidIt,
2937 : class _Diff,
2938 : class _Ty,
2939 : class _Pr> inline
2940 : void _Inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred,
2941 : _Diff *, _Ty *)
2942 : { // merge [_First, _Mid) with [_Mid, _Last), using _Pred
2943 : _DEBUG_ORDER_PRED(_First, _Mid, _Pred);
2944 : _DEBUG_ORDER_PRED(_Mid, _Last, _Pred);
2945 : _Diff _Count1 = 0;
2946 : _Distance(_First, _Mid, _Count1);
2947 : _Diff _Count2 = 0;
2948 : _Distance(_Mid, _Last, _Count2);
2949 : _Temp_iterator<_Ty> _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
2950 : _Buffered_merge(_First, _Mid, _Last,
2951 : _Count1, _Count2, _Tempbuf, _Pred);
2952 : }
2953 :
2954 : template<class _BidIt,
2955 : class _Pr> inline
2956 : void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred)
2957 : { // merge [_First, _Mid) with [_Mid, _Last), using _Pred
2958 : if (_First != _Mid && _Mid != _Last)
2959 : _Inplace_merge(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last), _Pred,
2960 : _Dist_type(_First), _Val_type(_First));
2961 : }
2962 :
2963 : // TEMPLATE FUNCTION sort
2964 : template<class _BidIt,
2965 : class _Ty> inline
2966 : void _Insertion_sort1(_BidIt _First, _BidIt _Last, _Ty *)
2967 : { // insertion sort [_First, _Last), using operator<
2968 : if (_First != _Last)
2969 : for (_BidIt _Next = _First; ++_Next != _Last; )
2970 : { // order next element
2971 : _BidIt _Next1 = _Next;
2972 : _Ty _Val = *_Next;
2973 :
2974 : if (_DEBUG_LT(_Val, *_First))
2975 : { // found new earliest element, move to front
2976 : _STDEXT unchecked_copy_backward(_First, _Next, ++_Next1);
2977 : *_First = _Val;
2978 : }
2979 : else
2980 : { // look for insertion point after first
2981 : for (_BidIt _First1 = _Next1;
2982 : _DEBUG_LT(_Val, *--_First1);
2983 : _Next1 = _First1)
2984 : *_Next1 = *_First1; // move hole down
2985 : *_Next1 = _Val; // insert element in hole
2986 : }
2987 : }
2988 : }
2989 :
2990 : template<class _BidIt> inline
2991 : void _Insertion_sort(_BidIt _First, _BidIt _Last)
2992 : { // insertion sort [_First, _Last), using operator<
2993 : std::_Insertion_sort1(_First, _Last, _Val_type(_First));
2994 : }
2995 :
2996 : template<class _RanIt> inline
2997 : void _Med3(_RanIt _First, _RanIt _Mid, _RanIt _Last)
2998 : { // sort median of three elements to middle
2999 : if (_DEBUG_LT(*_Mid, *_First))
3000 : std::iter_swap(_Mid, _First);
3001 : if (_DEBUG_LT(*_Last, *_Mid))
3002 : std::iter_swap(_Last, _Mid);
3003 : if (_DEBUG_LT(*_Mid, *_First))
3004 : std::iter_swap(_Mid, _First);
3005 : }
3006 :
3007 : template<class _RanIt> inline
3008 : void _Median(_RanIt _First, _RanIt _Mid, _RanIt _Last)
3009 : { // sort median element to middle
3010 : if (40 < _Last - _First)
3011 : { // median of nine
3012 : size_t _Step = (_Last - _First + 1) / 8;
3013 : std::_Med3(_First, _First + _Step, _First + 2 * _Step);
3014 : std::_Med3(_Mid - _Step, _Mid, _Mid + _Step);
3015 : std::_Med3(_Last - 2 * _Step, _Last - _Step, _Last);
3016 : std::_Med3(_First + _Step, _Mid, _Last - _Step);
3017 : }
3018 : else
3019 : std::_Med3(_First, _Mid, _Last);
3020 : }
3021 :
3022 : template<class _RanIt> inline
3023 : pair<_RanIt, _RanIt> _Unguarded_partition(_RanIt _First, _RanIt _Last)
3024 : { // partition [_First, _Last), using operator<
3025 : _RanIt _Mid = _First + (_Last - _First) / 2; // sort median to _Mid
3026 : std::_Median(_First, _Mid, _Last - 1);
3027 : _RanIt _Pfirst = _Mid;
3028 : _RanIt _Plast = _Pfirst + 1;
3029 :
3030 : while (_First < _Pfirst
3031 : && !_DEBUG_LT(*(_Pfirst - 1), *_Pfirst)
3032 : && !(*_Pfirst < *(_Pfirst - 1)))
3033 : --_Pfirst;
3034 : while (_Plast < _Last
3035 : && !_DEBUG_LT(*_Plast, *_Pfirst)
3036 : && !(*_Pfirst < *_Plast))
3037 : ++_Plast;
3038 :
3039 : _RanIt _Gfirst = _Plast;
3040 : _RanIt _Glast = _Pfirst;
3041 :
3042 : for (; ; )
3043 : { // partition
3044 : for (; _Gfirst < _Last; ++_Gfirst)
3045 : if (_DEBUG_LT(*_Pfirst, *_Gfirst))
3046 : ;
3047 : else if (*_Gfirst < *_Pfirst)
3048 : break;
3049 : else
3050 : std::iter_swap(_Plast++, _Gfirst);
3051 : for (; _First < _Glast; --_Glast)
3052 : if (_DEBUG_LT(*(_Glast - 1), *_Pfirst))
3053 : ;
3054 : else if (*_Pfirst < *(_Glast - 1))
3055 : break;
3056 : else
3057 : std::iter_swap(--_Pfirst, _Glast - 1);
3058 : if (_Glast == _First && _Gfirst == _Last)
3059 : return (pair<_RanIt, _RanIt>(_Pfirst, _Plast));
3060 :
3061 : if (_Glast == _First)
3062 : { // no room at bottom, rotate pivot upward
3063 : if (_Plast != _Gfirst)
3064 : std::iter_swap(_Pfirst, _Plast);
3065 : ++_Plast;
3066 : std::iter_swap(_Pfirst++, _Gfirst++);
3067 : }
3068 : else if (_Gfirst == _Last)
3069 : { // no room at top, rotate pivot downward
3070 : if (--_Glast != --_Pfirst)
3071 : std::iter_swap(_Glast, _Pfirst);
3072 : std::iter_swap(_Pfirst, --_Plast);
3073 : }
3074 : else
3075 : std::iter_swap(_Gfirst++, --_Glast);
3076 : }
3077 : }
3078 :
3079 : template<class _RanIt,
3080 : class _Diff> inline
3081 : void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
3082 : { // order [_First, _Last), using operator<
3083 : _Diff _Count;
3084 : for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
3085 : { // divide and conquer by quicksort
3086 : pair<_RanIt, _RanIt> _Mid =
3087 : std::_Unguarded_partition(_First, _Last);
3088 : _Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
3089 :
3090 : if (_Mid.first - _First < _Last - _Mid.second)
3091 : { // loop on second half
3092 : std::_Sort(_First, _Mid.first, _Ideal);
3093 : _First = _Mid.second;
3094 : }
3095 : else
3096 : { // loop on first half
3097 : std::_Sort(_Mid.second, _Last, _Ideal);
3098 : _Last = _Mid.first;
3099 : }
3100 : }
3101 :
3102 : if (_ISORT_MAX < _Count)
3103 : { // heap sort if too many divisions
3104 : std::make_heap(_First, _Last);
3105 : std::sort_heap(_First, _Last);
3106 : }
3107 : else if (1 < _Count)
3108 : std::_Insertion_sort(_First, _Last); // small
3109 : }
3110 :
3111 : template<class _RanIt> inline
3112 : void sort(_RanIt _First, _RanIt _Last)
3113 : { // order [_First, _Last), using operator<
3114 : _DEBUG_RANGE(_First, _Last);
3115 : std::_Sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Last - _First);
3116 : }
3117 :
3118 : // TEMPLATE FUNCTION sort WITH PRED
3119 : template<class _BidIt,
3120 : class _Pr,
3121 : class _Ty> inline
3122 : void _Insertion_sort1(_BidIt _First, _BidIt _Last, _Pr _Pred, _Ty *)
3123 : { // insertion sort [_First, _Last), using _Pred
3124 : if (_First != _Last)
3125 : for (_BidIt _Next = _First; ++_Next != _Last; )
3126 : { // order next element
3127 : _BidIt _Next1 = _Next;
3128 : _Ty _Val = *_Next;
3129 :
3130 : if (_DEBUG_LT_PRED(_Pred, _Val, *_First))
3131 : { // found new earliest element, move to front
3132 : _STDEXT unchecked_copy_backward(_First, _Next, ++_Next1);
3133 : *_First = _Val;
3134 : }
3135 : else
3136 : { // look for insertion point after first
3137 : for (_BidIt _First1 = _Next1;
3138 : _DEBUG_LT_PRED(_Pred, _Val, *--_First1);
3139 : _Next1 = _First1)
3140 : *_Next1 = *_First1; // move hole down
3141 : *_Next1 = _Val; // insert element in hole
3142 : }
3143 : }
3144 : }
3145 :
3146 : template<class _BidIt,
3147 : class _Pr> inline
3148 : void _Insertion_sort(_BidIt _First, _BidIt _Last, _Pr _Pred)
3149 : { // insertion sort [_First, _Last), using _Pred
3150 : std::_Insertion_sort1(_First, _Last, _Pred, _Val_type(_First));
3151 : }
3152 :
3153 : template<class _RanIt,
3154 : class _Pr> inline
3155 : void _Med3(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
3156 : { // sort median of three elements to middle
3157 : if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
3158 : std::iter_swap(_Mid, _First);
3159 : if (_DEBUG_LT_PRED(_Pred, *_Last, *_Mid))
3160 : std::iter_swap(_Last, _Mid);
3161 : if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
3162 : std::iter_swap(_Mid, _First);
3163 : }
3164 :
3165 : template<class _RanIt,
3166 : class _Pr> inline
3167 : void _Median(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
3168 : { // sort median element to middle
3169 : if (40 < _Last - _First)
3170 : { // median of nine
3171 : size_t _Step = (_Last - _First + 1) / 8;
3172 : std::_Med3(_First, _First + _Step, _First + 2 * _Step, _Pred);
3173 : std::_Med3(_Mid - _Step, _Mid, _Mid + _Step, _Pred);
3174 : std::_Med3(_Last - 2 * _Step, _Last - _Step, _Last, _Pred);
3175 : std::_Med3(_First + _Step, _Mid, _Last - _Step, _Pred);
3176 : }
3177 : else
3178 : std::_Med3(_First, _Mid, _Last, _Pred);
3179 : }
3180 :
3181 : template<class _RanIt,
3182 : class _Pr> inline
3183 : pair<_RanIt, _RanIt> _Unguarded_partition(_RanIt _First, _RanIt _Last,
3184 : _Pr _Pred)
3185 : { // partition [_First, _Last), using _Pred
3186 : _RanIt _Mid = _First + (_Last - _First) / 2;
3187 : std::_Median(_First, _Mid, _Last - 1, _Pred);
3188 : _RanIt _Pfirst = _Mid;
3189 : _RanIt _Plast = _Pfirst + 1;
3190 :
3191 : while (_First < _Pfirst
3192 : && !_DEBUG_LT_PRED(_Pred, *(_Pfirst - 1), *_Pfirst)
3193 : && !_Pred(*_Pfirst, *(_Pfirst - 1)))
3194 : --_Pfirst;
3195 : while (_Plast < _Last
3196 : && !_DEBUG_LT_PRED(_Pred, *_Plast, *_Pfirst)
3197 : && !_Pred(*_Pfirst, *_Plast))
3198 : ++_Plast;
3199 :
3200 : _RanIt _Gfirst = _Plast;
3201 : _RanIt _Glast = _Pfirst;
3202 :
3203 : for (; ; )
3204 : { // partition
3205 : for (; _Gfirst < _Last; ++_Gfirst)
3206 : if (_DEBUG_LT_PRED(_Pred, *_Pfirst, *_Gfirst))
3207 : ;
3208 : else if (_Pred(*_Gfirst, *_Pfirst))
3209 : break;
3210 : else
3211 : std::iter_swap(_Plast++, _Gfirst);
3212 : for (; _First < _Glast; --_Glast)
3213 : if (_DEBUG_LT_PRED(_Pred, *(_Glast - 1), *_Pfirst))
3214 : ;
3215 : else if (_Pred(*_Pfirst, *(_Glast - 1)))
3216 : break;
3217 : else
3218 : std::iter_swap(--_Pfirst, _Glast - 1);
3219 : if (_Glast == _First && _Gfirst == _Last)
3220 : return (pair<_RanIt, _RanIt>(_Pfirst, _Plast));
3221 :
3222 : if (_Glast == _First)
3223 : { // no room at bottom, rotate pivot upward
3224 : if (_Plast != _Gfirst)
3225 : std::iter_swap(_Pfirst, _Plast);
3226 : ++_Plast;
3227 : std::iter_swap(_Pfirst++, _Gfirst++);
3228 : }
3229 : else if (_Gfirst == _Last)
3230 : { // no room at top, rotate pivot downward
3231 : if (--_Glast != --_Pfirst)
3232 : std::iter_swap(_Glast, _Pfirst);
3233 : std::iter_swap(_Pfirst, --_Plast);
3234 : }
3235 : else
3236 : std::iter_swap(_Gfirst++, --_Glast);
3237 : }
3238 : }
3239 :
3240 : template<class _RanIt,
3241 : class _Diff,
3242 : class _Pr> inline
3243 : void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
3244 : { // order [_First, _Last), using _Pred
3245 : _Diff _Count;
3246 : for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
3247 : { // divide and conquer by quicksort
3248 : pair<_RanIt, _RanIt> _Mid =
3249 : std::_Unguarded_partition(_First, _Last, _Pred);
3250 : _Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
3251 :
3252 : if (_Mid.first - _First < _Last - _Mid.second)
3253 : { // loop on second half
3254 : std::_Sort(_First, _Mid.first, _Ideal, _Pred);
3255 : _First = _Mid.second;
3256 : }
3257 : else
3258 : { // loop on first half
3259 : std::_Sort(_Mid.second, _Last, _Ideal, _Pred);
3260 : _Last = _Mid.first;
3261 : }
3262 : }
3263 :
3264 : if (_ISORT_MAX < _Count)
3265 : { // heap sort if too many divisions
3266 : std::make_heap(_First, _Last, _Pred);
3267 : std::sort_heap(_First, _Last, _Pred);
3268 : }
3269 : else if (1 < _Count)
3270 : std::_Insertion_sort(_First, _Last, _Pred); // small
3271 : }
3272 :
3273 : template<class _RanIt,
3274 : class _Pr> inline
3275 : void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
3276 : { // order [_First, _Last), using _Pred
3277 : _DEBUG_RANGE(_First, _Last);
3278 : _DEBUG_POINTER(_Pred);
3279 : std::_Sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Last - _First, _Pred);
3280 : }
3281 :
3282 : // TEMPLATE FUNCTION stable_sort
3283 : template<class _BidIt,
3284 : class _OutIt,
3285 : class _Diff> inline
3286 : void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3287 : _Diff _Chunk, _Diff _Count, _Range_checked_iterator_tag)
3288 : { // copy merging chunks, using operator<
3289 : for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
3290 : { // copy merging pairs of adjacent chunks
3291 : _BidIt _Mid1 = _First;
3292 : std::advance(_Mid1, _Chunk);
3293 : _BidIt _Mid2 = _Mid1;
3294 : std::advance(_Mid2, _Chunk);
3295 :
3296 : _Dest = _STDEXT unchecked_merge(_First, _Mid1, _Mid1, _Mid2, _Dest);
3297 : _First = _Mid2;
3298 : }
3299 :
3300 : if (_Count <= _Chunk)
3301 : _STDEXT unchecked_copy(_First, _Last, _Dest); // copy partial last chunk
3302 : else
3303 : { // copy merging whole and partial last chunk
3304 : _BidIt _Mid = _First;
3305 : std::advance(_Mid, _Chunk);
3306 :
3307 : _STDEXT unchecked_merge(_First, _Mid, _Mid, _Last, _Dest);
3308 : }
3309 : }
3310 :
3311 : #if _SECURE_SCL
3312 :
3313 : template<class _BidIt, class _OutIt, class _Diff>
3314 : inline
3315 : _IF_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3316 : _Diff _Chunk, _Diff _Count)
3317 : {
3318 : _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
3319 : }
3320 :
3321 : template<class _BidIt, class _OutElem, class _Diff, size_t _Size>
3322 : inline
3323 : void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size],
3324 : _Diff _Chunk, _Diff _Count)
3325 : {
3326 : _Chunked_merge(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Chunk, _Count, _STD _Range_checked_iterator_tag());
3327 : }
3328 :
3329 : template<class _BidIt, class _OutIt, class _Diff>
3330 : inline
3331 : _SCL_INSECURE_DEPRECATE
3332 : _IF_NOT_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3333 : _Diff _Chunk, _Diff _Count)
3334 : {
3335 : _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
3336 : }
3337 :
3338 : #else
3339 :
3340 : template<class _BidIt, class _OutIt, class _Diff>
3341 : inline
3342 : void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3343 : _Diff _Chunk, _Diff _Count)
3344 : {
3345 : _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
3346 : }
3347 :
3348 : #endif
3349 :
3350 : template<class _BidIt,
3351 : class _Diff,
3352 : class _Ty> inline
3353 : void _Buffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3354 : _Temp_iterator<_Ty>& _Tempbuf)
3355 : { // sort using temp buffer for merges, using operator<
3356 : _BidIt _Mid = _First;
3357 : for (_Diff _Nleft = _Count; _ISORT_MAX <= _Nleft; _Nleft -= _ISORT_MAX)
3358 : { // sort chunks
3359 : _BidIt _Midend = _Mid;
3360 : std::advance(_Midend, (int)_ISORT_MAX);
3361 :
3362 : std::_Insertion_sort(_Mid, _Midend);
3363 : _Mid = _Midend;
3364 : }
3365 : std::_Insertion_sort(_Mid, _Last); // sort partial last chunk
3366 :
3367 : for (_Diff _Chunk = _ISORT_MAX; _Chunk < _Count; _Chunk *= 2)
3368 : { // merge adjacent pairs of chunks to and from temp buffer
3369 : _STDEXT _Unchecked_chunked_merge(_First, _Last, _Tempbuf._Init(),
3370 : _Chunk, _Count);
3371 : _STDEXT _Unchecked_chunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
3372 : _Chunk *= 2, _Count);
3373 : }
3374 : }
3375 :
3376 : template<class _BidIt,
3377 : class _Diff,
3378 : class _Ty> inline
3379 : void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3380 : _Temp_iterator<_Ty>& _Tempbuf)
3381 : { // sort preserving order of equivalents, using operator<
3382 : if (_Count <= _ISORT_MAX)
3383 : std::_Insertion_sort(_First, _Last); // small
3384 : else
3385 : { // sort halves and merge
3386 : _Diff _Count2 = (_Count + 1) / 2;
3387 : _BidIt _Mid = _First;
3388 : std::advance(_Mid, _Count2);
3389 :
3390 : if (_Count2 <= _Tempbuf._Maxlen())
3391 : { // temp buffer big enough, sort each half using buffer
3392 : _Buffered_merge_sort(_First, _Mid, _Count2, _Tempbuf);
3393 : _Buffered_merge_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
3394 : }
3395 : else
3396 : { // temp buffer not big enough, divide and conquer
3397 : _Stable_sort(_First, _Mid, _Count2, _Tempbuf);
3398 : _Stable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
3399 : }
3400 :
3401 : _Buffered_merge(_First, _Mid, _Last,
3402 : _Count2, _Count - _Count2, _Tempbuf); // merge sorted halves
3403 : }
3404 : }
3405 :
3406 : template<class _BidIt,
3407 : class _Diff,
3408 : class _Ty> inline
3409 : void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff *, _Ty *)
3410 : { // sort preserving order of equivalents, using operator<
3411 : _Diff _Count = 0;
3412 : _Distance(_First, _Last, _Count);
3413 : _Temp_iterator<_Ty> _Tempbuf((_Count + 1) / 2);
3414 : _Stable_sort(_First, _Last, _Count, _Tempbuf);
3415 : }
3416 :
3417 : template<class _BidIt> inline
3418 : void stable_sort(_BidIt _First, _BidIt _Last)
3419 : { // sort preserving order of equivalents, using operator<
3420 : _DEBUG_RANGE(_First, _Last);
3421 : if (_First != _Last)
3422 : {
3423 : _Stable_sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dist_type(_First), _Val_type(_First));
3424 : }
3425 : }
3426 :
3427 : // TEMPLATE FUNCTION stable_sort WITH PRED
3428 : template<class _BidIt,
3429 : class _OutIt,
3430 : class _Diff,
3431 : class _Pr> inline
3432 : void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3433 : _Diff _Chunk, _Diff _Count, _Pr _Pred, _Range_checked_iterator_tag)
3434 : { // copy merging chunks, using _Pred
3435 : for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
3436 : { // copy merging pairs of adjacent chunks
3437 : _BidIt _Mid1 = _First;
3438 : std::advance(_Mid1, _Chunk);
3439 : _BidIt _Mid2 = _Mid1;
3440 : std::advance(_Mid2, _Chunk);
3441 :
3442 : _Dest = _STDEXT unchecked_merge(_First, _Mid1, _Mid1, _Mid2, _Dest, _Pred);
3443 : _First = _Mid2;
3444 : }
3445 :
3446 : if (_Count <= _Chunk)
3447 : _STDEXT unchecked_copy(_First, _Last, _Dest); // copy partial last chunk
3448 : else
3449 : { // copy merging whole and partial last chunk
3450 : _BidIt _Mid1 = _First;
3451 : std::advance(_Mid1, _Chunk);
3452 :
3453 : _STDEXT unchecked_merge(_First, _Mid1, _Mid1, _Last, _Dest, _Pred);
3454 : }
3455 : }
3456 :
3457 : #if _SECURE_SCL
3458 :
3459 : template<class _BidIt, class _OutIt, class _Diff, class _Pr>
3460 : inline
3461 : _IF_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3462 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
3463 : {
3464 : _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3465 : }
3466 :
3467 : template<class _BidIt, class _OutElem, class _Diff, class _Pr, size_t _Size>
3468 : inline
3469 : void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size],
3470 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
3471 : {
3472 : _Chunked_merge(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3473 : }
3474 :
3475 : template<class _BidIt, class _OutIt, class _Diff, class _Pr>
3476 : inline
3477 : _SCL_INSECURE_DEPRECATE
3478 : _IF_NOT_CHK_(_OutIt, void) _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3479 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
3480 : {
3481 : _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3482 : }
3483 :
3484 : #else
3485 :
3486 : template<class _BidIt, class _OutIt, class _Diff, class _Pr>
3487 : inline
3488 : void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3489 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
3490 : {
3491 : _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
3492 : }
3493 :
3494 : #endif
3495 :
3496 : template<class _BidIt,
3497 : class _Diff,
3498 : class _Ty,
3499 : class _Pr> inline
3500 : void _Buffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3501 : _Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
3502 : { // sort using temp buffer for merges, using _Pred
3503 : _BidIt _Mid = _First;
3504 : for (_Diff _Nleft = _Count; _ISORT_MAX <= _Nleft; _Nleft -= _ISORT_MAX)
3505 : { // sort chunks
3506 : _BidIt _Midn = _Mid;
3507 : std::advance(_Midn, (int)_ISORT_MAX);
3508 :
3509 : std::_Insertion_sort(_Mid, _Midn, _Pred);
3510 : _Mid = _Midn;
3511 : }
3512 : std::_Insertion_sort(_Mid, _Last, _Pred); // sort partial last chunk
3513 :
3514 : for (_Diff _Chunk = _ISORT_MAX; _Chunk < _Count; _Chunk *= 2)
3515 : { // merge adjacent pairs of chunks to and from temp buffer
3516 : _STDEXT _Unchecked_chunked_merge(_First, _Last, _Tempbuf._Init(),
3517 : _Chunk, _Count, _Pred);
3518 : _STDEXT _Unchecked_chunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
3519 : _Chunk *= 2, _Count, _Pred);
3520 : }
3521 : }
3522 :
3523 : template<class _BidIt,
3524 : class _Diff,
3525 : class _Ty,
3526 : class _Pr> inline
3527 : void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3528 : _Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
3529 : { // sort preserving order of equivalents, using _Pred
3530 : if (_Count <= _ISORT_MAX)
3531 : std::_Insertion_sort(_First, _Last, _Pred); // small
3532 : else
3533 : { // sort halves and merge
3534 : _Diff _Count2 = (_Count + 1) / 2;
3535 : _BidIt _Mid = _First;
3536 : std::advance(_Mid, _Count2);
3537 :
3538 : if (_Count2 <= _Tempbuf._Maxlen())
3539 : { // temp buffer big enough, sort each half using buffer
3540 : _Buffered_merge_sort(_First, _Mid, _Count2, _Tempbuf, _Pred);
3541 : _Buffered_merge_sort(_Mid, _Last, _Count - _Count2,
3542 : _Tempbuf, _Pred);
3543 : }
3544 : else
3545 : { // temp buffer not big enough, divide and conquer
3546 : _Stable_sort(_First, _Mid, _Count2, _Tempbuf, _Pred);
3547 : _Stable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf, _Pred);
3548 : }
3549 :
3550 : _Buffered_merge(_First, _Mid, _Last,
3551 : _Count2, _Count - _Count2, _Tempbuf, _Pred); // merge halves
3552 : }
3553 : }
3554 :
3555 : template<class _BidIt,
3556 : class _Diff,
3557 : class _Ty,
3558 : class _Pr> inline
3559 : void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff *, _Ty *, _Pr _Pred)
3560 : { // sort preserving order of equivalents, using _Pred
3561 : _Diff _Count = 0;
3562 : _Distance(_First, _Last, _Count);
3563 : _Temp_iterator<_Ty> _Tempbuf((_Count + 1) / 2);
3564 : _Stable_sort(_First, _Last, _Count, _Tempbuf, _Pred);
3565 : }
3566 :
3567 : template<class _BidIt,
3568 : class _Pr> inline
3569 : void stable_sort(_BidIt _First, _BidIt _Last, _Pr _Pred)
3570 : { // sort preserving order of equivalents, using _Pred
3571 : _DEBUG_RANGE(_First, _Last);
3572 : _DEBUG_POINTER(_Pred);
3573 : if (_First != _Last)
3574 : {
3575 : _Stable_sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Last),
3576 : _Dist_type(_First), _Val_type(_First), _Pred);
3577 : }
3578 : }
3579 :
3580 : // TEMPLATE FUNCTION partial_sort
3581 : template<class _RanIt,
3582 : class _Ty> inline
3583 : void _Partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Ty *)
3584 : { // order [First, _Last) up to _Mid, using operator<
3585 : _DEBUG_RANGE(_First, _Mid);
3586 : _DEBUG_RANGE(_Mid, _Last);
3587 : std::make_heap(_First, _Mid);
3588 :
3589 : for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
3590 : if (_DEBUG_LT(*_Next, *_First))
3591 : _Pop_heap(_First, _Mid, _Next, _Ty(*_Next),
3592 : _Dist_type(_First)); // replace top with new largest
3593 : std::sort_heap(_First, _Mid);
3594 : }
3595 :
3596 : template<class _RanIt> inline
3597 : void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last)
3598 : { // order [First, _Last) up to _Mid, using operator<
3599 : _Partial_sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last), _Val_type(_First));
3600 : }
3601 :
3602 : // TEMPLATE FUNCTION partial_sort WITH PRED
3603 : template<class _RanIt,
3604 : class _Ty,
3605 : class _Pr> inline
3606 : void _Partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last,
3607 : _Pr _Pred, _Ty *)
3608 : { // order [First, _Last) up to _Mid, using _Pred
3609 : _DEBUG_RANGE(_First, _Mid);
3610 : _DEBUG_RANGE(_Mid, _Last);
3611 : _DEBUG_POINTER(_Pred);
3612 : std::make_heap(_First, _Mid, _Pred);
3613 :
3614 : for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
3615 : if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
3616 : _Pop_heap(_First, _Mid, _Next, _Ty(*_Next), _Pred,
3617 : _Dist_type(_First)); // replace top with new largest
3618 : std::sort_heap(_First, _Mid, _Pred);
3619 : }
3620 :
3621 : template<class _RanIt,
3622 : class _Pr> inline
3623 : void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
3624 : { // order [First, _Last) up to _Mid, using _Pred
3625 : _Partial_sort(_CHECKED_BASE(_First), _CHECKED_BASE(_Mid), _CHECKED_BASE(_Last), _Pred, _Val_type(_First));
3626 : }
3627 :
3628 : // TEMPLATE FUNCTION partial_sort_copy
3629 : template<class _InIt,
3630 : class _RanIt,
3631 : class _Diff,
3632 : class _Ty> inline
3633 : _RanIt _Partial_sort_copy(_InIt _First1, _InIt _Last1,
3634 : _RanIt _First2, _RanIt _Last2, _Diff *, _Ty *)
3635 : { // copy [First1, _Last1) into [_First2, _Last2), using operator<
3636 : _DEBUG_RANGE(_First1, _Last1);
3637 : _DEBUG_RANGE(_First2, _Last2);
3638 : _RanIt _Mid2 = _First2;
3639 : for (; _First1 != _Last1 && _Mid2 != _Last2; ++_First1, ++_Mid2)
3640 : *_Mid2 = *_First1; // copy min(_Last1 - _First1, _Last2 - _First2)
3641 : std::make_heap(_First2, _Mid2);
3642 :
3643 : for (; _First1 != _Last1; ++_First1)
3644 : if (_DEBUG_LT(*_First1, *_First2))
3645 : std::_Adjust_heap(_First2, _Diff(0), _Diff(_Mid2 - _First2),
3646 : _Ty(*_First1)); // replace top with new largest
3647 :
3648 : std::sort_heap(_First2, _Mid2);
3649 : return (_Mid2);
3650 : }
3651 :
3652 : template<class _InIt,
3653 : class _RanIt> inline
3654 : _RanIt partial_sort_copy(_InIt _First1, _InIt _Last1,
3655 : _RanIt _First2, _RanIt _Last2)
3656 : { // copy [First1, _Last1) into [_First2, _Last2), using operator<
3657 : if (_First1 != _Last1 && _First2 != _Last2)
3658 : _ASSIGN_FROM_BASE(_First2, _Partial_sort_copy(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3659 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3660 : _Dist_type(_First2), _Val_type(_First1)));
3661 : return (_First2);
3662 : }
3663 :
3664 : // TEMPLATE FUNCTION partial_sort_copy WITH PRED
3665 : template<class _InIt,
3666 : class _RanIt,
3667 : class _Diff,
3668 : class _Ty,
3669 : class _Pr> inline
3670 : _RanIt _Partial_sort_copy(_InIt _First1, _InIt _Last1,
3671 : _RanIt _First2, _RanIt _Last2, _Pr _Pred, _Diff *, _Ty *)
3672 : { // copy [First1, _Last1) into [_First2, _Last2) using _Pred
3673 : _DEBUG_RANGE(_First1, _Last1);
3674 : _DEBUG_RANGE(_First2, _Last2);
3675 : _DEBUG_POINTER(_Pred);
3676 : _RanIt _Mid2 = _First2;
3677 : for (; _First1 != _Last1 && _Mid2 != _Last2; ++_First1, ++_Mid2)
3678 : *_Mid2 = *_First1; // copy min(_Last1 - _First1, _Last2 - _First2)
3679 : std::make_heap(_First2, _Mid2, _Pred);
3680 :
3681 : for (; _First1 != _Last1; ++_First1)
3682 : if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
3683 : std::_Adjust_heap(_First2, _Diff(0), _Diff(_Mid2 - _First2),
3684 : _Ty(*_First1), _Pred); // replace top with new largest
3685 :
3686 : std::sort_heap(_First2, _Mid2, _Pred);
3687 : return (_Mid2);
3688 : }
3689 :
3690 : template<class _InIt,
3691 : class _RanIt,
3692 : class _Pr> inline
3693 : _RanIt partial_sort_copy(_InIt _First1, _InIt _Last1,
3694 : _RanIt _First2, _RanIt _Last2, _Pr _Pred)
3695 : { // copy [First1, _Last1) into [_First2, _Last2) using _Pred
3696 : if (_First1 != _Last1 && _First2 != _Last2)
3697 : _ASSIGN_FROM_BASE (_First2, _Partial_sort_copy(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3698 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred,
3699 : _Dist_type(_First2), _Val_type(_First1)));
3700 : return (_First2);
3701 : }
3702 :
3703 : // TEMPLATE FUNCTION nth_element
3704 : template<class _RanIt> inline
3705 : void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last)
3706 : { // order Nth element, using operator<
3707 : _DEBUG_RANGE(_First, _Last);
3708 : for (; _ISORT_MAX < _Last - _First; )
3709 : { // divide and conquer, ordering partition containing Nth
3710 : pair<_RanIt, _RanIt> _Mid =
3711 : std::_Unguarded_partition(_First, _Last);
3712 :
3713 : if (_Mid.second <= _Nth)
3714 : _First = _Mid.second;
3715 : else if (_Mid.first <= _Nth)
3716 : return; // Nth inside fat pivot, done
3717 : else
3718 : _Last = _Mid.first;
3719 : }
3720 :
3721 : std::_Insertion_sort(_First, _Last); // sort any remainder
3722 : }
3723 :
3724 : template<class _RanIt> inline
3725 : void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last)
3726 : { // order Nth element, using operator<
3727 : _Nth_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Nth), _CHECKED_BASE(_Last));
3728 : }
3729 :
3730 : // TEMPLATE FUNCTION nth_element WITH PRED
3731 : template<class _RanIt,
3732 : class _Pr> inline
3733 : void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
3734 : { // order Nth element, using _Pred
3735 : _DEBUG_RANGE(_First, _Last);
3736 : _DEBUG_POINTER(_Pred);
3737 : for (; _ISORT_MAX < _Last - _First; )
3738 : { // divide and conquer, ordering partition containing Nth
3739 : pair<_RanIt, _RanIt> _Mid =
3740 : std::_Unguarded_partition(_First, _Last, _Pred);
3741 :
3742 : if (_Mid.second <= _Nth)
3743 : _First = _Mid.second;
3744 : else if (_Mid.first <= _Nth)
3745 : return; // Nth inside fat pivot, done
3746 : else
3747 : _Last = _Mid.first;
3748 : }
3749 :
3750 : std::_Insertion_sort(_First, _Last, _Pred); // sort any remainder
3751 : }
3752 :
3753 : template<class _RanIt,
3754 : class _Pr> inline
3755 : void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
3756 : { // order Nth element, using _Pred
3757 : _Nth_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Nth), _CHECKED_BASE(_Last), _Pred);
3758 : }
3759 :
3760 : // TEMPLATE FUNCTION includes
3761 : template<class _InIt1,
3762 : class _InIt2> inline
3763 : bool _Includes(_InIt1 _First1, _InIt1 _Last1,
3764 : _InIt2 _First2, _InIt2 _Last2)
3765 : { // test if all [_First1, _Last1) in [_First2, _Last2), using operator<
3766 : _DEBUG_ORDER(_First1, _Last1);
3767 : _DEBUG_ORDER(_First2, _Last2);
3768 : for (; _First1 != _Last1 && _First2 != _Last2; )
3769 : if (_DEBUG_LT(*_First2, *_First1))
3770 : return (false);
3771 : else if (*_First1 < *_First2)
3772 : ++_First1;
3773 : else
3774 : ++_First1, ++_First2;
3775 : return (_First2 == _Last2);
3776 : }
3777 :
3778 : template<class _InIt1,
3779 : class _InIt2> inline
3780 : bool includes(_InIt1 _First1, _InIt1 _Last1,
3781 : _InIt2 _First2, _InIt2 _Last2)
3782 : { // test if all [_First1, _Last1) in [_First2, _Last2), using operator<
3783 : return _Includes(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3784 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2));
3785 : }
3786 :
3787 : // TEMPLATE FUNCTION includes WITH PRED
3788 : template<class _InIt1,
3789 : class _InIt2,
3790 : class _Pr> inline
3791 : bool _Includes(_InIt1 _First1, _InIt1 _Last1,
3792 : _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
3793 : { // test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
3794 : _DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
3795 : _DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
3796 : for (; _First1 != _Last1 && _First2 != _Last2; )
3797 : if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
3798 : return (false);
3799 : else if (_Pred(*_First1, *_First2))
3800 : ++_First1;
3801 : else
3802 : ++_First1, ++_First2;
3803 : return (_First2 == _Last2);
3804 : }
3805 :
3806 : template<class _InIt1,
3807 : class _InIt2,
3808 : class _Pr> inline
3809 : bool includes(_InIt1 _First1, _InIt1 _Last1,
3810 : _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
3811 : { // test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
3812 : return _Includes(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3813 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred);
3814 : }
3815 :
3816 : // TEMPLATE FUNCTION set_union
3817 : template<class _InIt1,
3818 : class _InIt2,
3819 : class _OutIt> inline
3820 : _OutIt _Set_union(_InIt1 _First1, _InIt1 _Last1,
3821 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
3822 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3823 : _DEBUG_ORDER(_First1, _Last1);
3824 : _DEBUG_ORDER(_First2, _Last2);
3825 : _DEBUG_POINTER(_Dest);
3826 : for (; _First1 != _Last1 && _First2 != _Last2; )
3827 : if (_DEBUG_LT(*_First1, *_First2))
3828 : *_Dest++ = *_First1, ++_First1;
3829 : else if (*_First2 < *_First1)
3830 : *_Dest++ = *_First2, ++_First2;
3831 : else
3832 : *_Dest++ = *_First1, ++_First1, ++_First2;
3833 : _Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
3834 : return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
3835 : }
3836 :
3837 : #if _SECURE_SCL
3838 :
3839 : template<class _InIt1,
3840 : class _InIt2,
3841 : class _OutIt> inline
3842 : _IF_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3843 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3844 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3845 : return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3846 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3847 : _Dest, _STD _Range_checked_iterator_tag());
3848 : }
3849 :
3850 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
3851 : inline
3852 : _OutElem* set_union(_InIt1 _First1, _InIt1 _Last1,
3853 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
3854 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3855 : return (set_union(_First1, _Last1, _First2, _Last2,
3856 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
3857 : }
3858 :
3859 : template<class _InIt1,
3860 : class _InIt2,
3861 : class _OutIt> inline
3862 : _SCL_INSECURE_DEPRECATE
3863 : _IF_NOT_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3864 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3865 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3866 : return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3867 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3868 : _Dest, _STD _Range_checked_iterator_tag());
3869 : }
3870 :
3871 : #else
3872 :
3873 : template<class _InIt1,
3874 : class _InIt2,
3875 : class _OutIt> inline
3876 : _OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
3877 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3878 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
3879 : return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3880 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3881 : _Dest, _STD _Range_checked_iterator_tag());
3882 : }
3883 :
3884 : #endif
3885 :
3886 : // TEMPLATE FUNCTION set_union WITH PRED
3887 : template<class _InIt1,
3888 : class _InIt2,
3889 : class _OutIt,
3890 : class _Pr> inline
3891 : _OutIt _Set_union(_InIt1 _First1, _InIt1 _Last1,
3892 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
3893 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3894 : _DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
3895 : _DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
3896 : _DEBUG_POINTER(_Dest);
3897 : for (; _First1 != _Last1 && _First2 != _Last2; )
3898 : if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
3899 : *_Dest++ = *_First1, ++_First1;
3900 : else if (_Pred(*_First2, *_First1))
3901 : *_Dest++ = *_First2, ++_First2;
3902 : else
3903 : *_Dest++ = *_First1, ++_First1, ++_First2;
3904 : _Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
3905 : return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
3906 : }
3907 :
3908 : #if _SECURE_SCL
3909 :
3910 : template<class _InIt1,
3911 : class _InIt2,
3912 : class _OutIt,
3913 : class _Pr> inline
3914 : _IF_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3915 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
3916 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3917 : return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3918 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3919 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
3920 : }
3921 :
3922 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
3923 : inline
3924 : _OutElem* set_union(_InIt1 _First1, _InIt1 _Last1,
3925 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
3926 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3927 : return (set_union(_First1, _Last1, _First2, _Last2,
3928 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
3929 : }
3930 :
3931 : template<class _InIt1,
3932 : class _InIt2,
3933 : class _OutIt,
3934 : class _Pr> inline
3935 : _SCL_INSECURE_DEPRECATE
3936 : _IF_NOT_CHK(_OutIt) set_union(_InIt1 _First1, _InIt1 _Last1,
3937 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
3938 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3939 : return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3940 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3941 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
3942 : }
3943 :
3944 : #else
3945 :
3946 : template<class _InIt1,
3947 : class _InIt2,
3948 : class _OutIt,
3949 : class _Pr> inline
3950 : _OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
3951 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
3952 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
3953 : return _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3954 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3955 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
3956 : }
3957 :
3958 : #endif
3959 :
3960 : // TEMPLATE FUNCTION set_intersection
3961 : template<class _InIt1,
3962 : class _InIt2,
3963 : class _OutIt> inline
3964 : _OutIt _Set_intersection(_InIt1 _First1, _InIt1 _Last1,
3965 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
3966 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
3967 : _DEBUG_ORDER(_First1, _Last1);
3968 : _DEBUG_ORDER(_First2, _Last2);
3969 : _DEBUG_POINTER(_Dest);
3970 : for (; _First1 != _Last1 && _First2 != _Last2; )
3971 : if (_DEBUG_LT(*_First1, *_First2))
3972 : ++_First1;
3973 : else if (*_First2 < *_First1)
3974 : ++_First2;
3975 : else
3976 : *_Dest++ = *_First1++, ++_First2;
3977 : return (_Dest);
3978 : }
3979 :
3980 : #if _SECURE_SCL
3981 :
3982 : template<class _InIt1,
3983 : class _InIt2,
3984 : class _OutIt> inline
3985 : _IF_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
3986 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
3987 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
3988 : return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
3989 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
3990 : _Dest, _STD _Range_checked_iterator_tag());
3991 : }
3992 :
3993 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
3994 : inline
3995 : _OutElem* set_intersection(_InIt1 _First1, _InIt1 _Last1,
3996 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
3997 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
3998 : return (set_intersection(_First1, _Last1, _First2, _Last2,
3999 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
4000 : }
4001 :
4002 : template<class _InIt1,
4003 : class _InIt2,
4004 : class _OutIt> inline
4005 : _SCL_INSECURE_DEPRECATE
4006 : _IF_NOT_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
4007 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4008 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
4009 : return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4010 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4011 : _Dest, _STD _Range_checked_iterator_tag());
4012 : }
4013 :
4014 : #else
4015 :
4016 : template<class _InIt1,
4017 : class _InIt2,
4018 : class _OutIt> inline
4019 : _OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
4020 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4021 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
4022 : return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4023 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4024 : _Dest, _STD _Range_checked_iterator_tag());
4025 : }
4026 :
4027 : #endif
4028 :
4029 : // TEMPLATE FUNCTION set_intersection WITH PRED
4030 : template<class _InIt1,
4031 : class _InIt2,
4032 : class _OutIt,
4033 : class _Pr> inline
4034 : _OutIt _Set_intersection(_InIt1 _First1, _InIt1 _Last1,
4035 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
4036 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4037 : _DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
4038 : _DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
4039 : _DEBUG_POINTER(_Dest);
4040 : for (; _First1 != _Last1 && _First2 != _Last2; )
4041 : if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
4042 : ++_First1;
4043 : else if (_Pred(*_First2, *_First1))
4044 : ++_First2;
4045 : else
4046 : *_Dest++ = *_First1++, ++_First2;
4047 : return (_Dest);
4048 : }
4049 :
4050 : #if _SECURE_SCL
4051 :
4052 : template<class _InIt1,
4053 : class _InIt2,
4054 : class _OutIt,
4055 : class _Pr> inline
4056 : _IF_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
4057 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4058 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4059 : return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4060 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4061 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4062 : }
4063 :
4064 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
4065 : inline
4066 : _OutElem* set_intersection(_InIt1 _First1, _InIt1 _Last1,
4067 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
4068 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4069 : return (set_intersection(_First1, _Last1, _First2, _Last2,
4070 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
4071 : }
4072 :
4073 : template<class _InIt1,
4074 : class _InIt2,
4075 : class _OutIt,
4076 : class _Pr> inline
4077 : _SCL_INSECURE_DEPRECATE
4078 : _IF_NOT_CHK(_OutIt) set_intersection(_InIt1 _First1, _InIt1 _Last1,
4079 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4080 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4081 : return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4082 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4083 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4084 : }
4085 :
4086 : #else
4087 :
4088 : template<class _InIt1,
4089 : class _InIt2,
4090 : class _OutIt,
4091 : class _Pr> inline
4092 : _OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
4093 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4094 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4095 : return _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4096 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4097 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4098 : }
4099 :
4100 : #endif
4101 :
4102 : // TEMPLATE FUNCTION set_difference
4103 : template<class _InIt1,
4104 : class _InIt2,
4105 : class _OutIt> inline
4106 : _OutIt _Set_difference(_InIt1 _First1, _InIt1 _Last1,
4107 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
4108 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4109 : _DEBUG_ORDER(_First1, _Last1);
4110 : _DEBUG_ORDER(_First2, _Last2);
4111 : _DEBUG_POINTER(_Dest);
4112 : for (; _First1 != _Last1 && _First2 != _Last2; )
4113 : if (_DEBUG_LT(*_First1, *_First2))
4114 : *_Dest++ = *_First1, ++_First1;
4115 : else if (*_First2 < *_First1)
4116 : ++_First2;
4117 : else
4118 : ++_First1, ++_First2;
4119 : return (_STDEXT unchecked_copy(_First1, _Last1, _Dest));
4120 : }
4121 :
4122 : #if _SECURE_SCL
4123 :
4124 : template<class _InIt1,
4125 : class _InIt2,
4126 : class _OutIt> inline
4127 : _IF_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4128 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4129 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4130 : return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4131 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4132 : _Dest, _STD _Range_checked_iterator_tag());
4133 : }
4134 :
4135 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
4136 : inline
4137 : _OutElem* set_difference(_InIt1 _First1, _InIt1 _Last1,
4138 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
4139 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4140 : return (set_difference(_First1, _Last1, _First2, _Last2,
4141 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
4142 : }
4143 :
4144 : template<class _InIt1,
4145 : class _InIt2,
4146 : class _OutIt> inline
4147 : _SCL_INSECURE_DEPRECATE
4148 : _IF_NOT_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4149 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4150 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4151 : return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4152 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4153 : _Dest, _STD _Range_checked_iterator_tag());
4154 : }
4155 :
4156 : #else
4157 :
4158 : template<class _InIt1,
4159 : class _InIt2,
4160 : class _OutIt> inline
4161 : _OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
4162 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4163 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
4164 : return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4165 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4166 : _Dest, _STD _Range_checked_iterator_tag());
4167 : }
4168 :
4169 : #endif
4170 :
4171 : // TEMPLATE FUNCTION set_difference WITH PRED
4172 : template<class _InIt1,
4173 : class _InIt2,
4174 : class _OutIt,
4175 : class _Pr> inline
4176 : _OutIt _Set_difference(_InIt1 _First1, _InIt1 _Last1,
4177 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
4178 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4179 : _DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
4180 : _DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
4181 : _DEBUG_POINTER(_Dest);
4182 : for (; _First1 != _Last1 && _First2 != _Last2; )
4183 : if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
4184 : *_Dest++ = *_First1, ++_First1;
4185 : else if (_Pred(*_First2, *_First1))
4186 : ++_First2;
4187 : else
4188 : ++_First1, ++_First2;
4189 : return (_STDEXT unchecked_copy(_First1, _Last1, _Dest));
4190 : }
4191 :
4192 : #if _SECURE_SCL
4193 :
4194 : template<class _InIt1,
4195 : class _InIt2,
4196 : class _OutIt,
4197 : class _Pr> inline
4198 : _IF_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4199 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4200 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4201 : return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4202 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4203 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4204 : }
4205 :
4206 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
4207 : inline
4208 : _OutElem* set_difference(_InIt1 _First1, _InIt1 _Last1,
4209 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
4210 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4211 : return (set_difference(_First1, _Last1, _First2, _Last2,
4212 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
4213 : }
4214 :
4215 : template<class _InIt1,
4216 : class _InIt2,
4217 : class _OutIt,
4218 : class _Pr> inline
4219 : _SCL_INSECURE_DEPRECATE
4220 : _IF_NOT_CHK(_OutIt) set_difference(_InIt1 _First1, _InIt1 _Last1,
4221 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4222 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4223 : return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4224 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4225 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4226 : }
4227 :
4228 : #else
4229 :
4230 : template<class _InIt1,
4231 : class _InIt2,
4232 : class _OutIt,
4233 : class _Pr> inline
4234 : _OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
4235 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4236 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
4237 : return _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4238 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4239 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4240 : }
4241 :
4242 : #endif
4243 :
4244 : // TEMPLATE FUNCTION set_symmetric_difference
4245 : template<class _InIt1,
4246 : class _InIt2,
4247 : class _OutIt> inline
4248 : _OutIt _Set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4249 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
4250 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4251 : _DEBUG_ORDER(_First1, _Last1);
4252 : _DEBUG_ORDER(_First2, _Last2);
4253 : _DEBUG_POINTER(_Dest);
4254 : for (; _First1 != _Last1 && _First2 != _Last2; )
4255 : if (_DEBUG_LT(*_First1, *_First2))
4256 : *_Dest++ = *_First1, ++_First1;
4257 : else if (*_First2 < *_First1)
4258 : *_Dest++ = *_First2, ++_First2;
4259 : else
4260 : ++_First1, ++_First2;
4261 : _Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
4262 : return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
4263 : }
4264 :
4265 : #if _SECURE_SCL
4266 :
4267 : template<class _InIt1,
4268 : class _InIt2,
4269 : class _OutIt> inline
4270 : _IF_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4271 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4272 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4273 : return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4274 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4275 : _Dest, _STD _Range_checked_iterator_tag());
4276 : }
4277 :
4278 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
4279 : inline
4280 : _OutElem* set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4281 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
4282 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4283 : return (set_symmetric_difference(_First1, _Last1, _First2, _Last2,
4284 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
4285 : }
4286 :
4287 : template<class _InIt1,
4288 : class _InIt2,
4289 : class _OutIt> inline
4290 : _SCL_INSECURE_DEPRECATE
4291 : _IF_NOT_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4292 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4293 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4294 : return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4295 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4296 : _Dest, _STD _Range_checked_iterator_tag());
4297 : }
4298 :
4299 : #else
4300 :
4301 : template<class _InIt1,
4302 : class _InIt2,
4303 : class _OutIt> inline
4304 : _OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4305 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
4306 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
4307 : return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4308 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4309 : _Dest, _STD _Range_checked_iterator_tag());
4310 : }
4311 :
4312 : #endif
4313 :
4314 : // TEMPLATE FUNCTION set_symmetric_difference WITH PRED
4315 : template<class _InIt1,
4316 : class _InIt2,
4317 : class _OutIt,
4318 : class _Pr> inline
4319 : _OutIt _Set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4320 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred, _Range_checked_iterator_tag)
4321 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4322 : _DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
4323 : _DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
4324 : _DEBUG_POINTER(_Dest);
4325 : for (; _First1 != _Last1 && _First2 != _Last2; )
4326 : if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
4327 : *_Dest++ = *_First1, ++_First1;
4328 : else if (_Pred(*_First2, *_First1))
4329 : *_Dest++ = *_First2, ++_First2;
4330 : else
4331 : ++_First1, ++_First2;
4332 : _Dest = _STDEXT unchecked_copy(_First1, _Last1, _Dest);
4333 : return (_STDEXT unchecked_copy(_First2, _Last2, _Dest));
4334 : }
4335 :
4336 : #if _SECURE_SCL
4337 :
4338 : template<class _InIt1,
4339 : class _InIt2,
4340 : class _OutIt,
4341 : class _Pr> inline
4342 : _IF_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4343 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4344 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4345 : return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4346 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4347 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4348 : }
4349 :
4350 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
4351 : inline
4352 : _OutElem* set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4353 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
4354 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4355 : return (set_symmetric_difference(_First1, _Last1, _First2, _Last2,
4356 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
4357 : }
4358 :
4359 : template<class _InIt1,
4360 : class _InIt2,
4361 : class _OutIt,
4362 : class _Pr> inline
4363 : _SCL_INSECURE_DEPRECATE
4364 : _IF_NOT_CHK(_OutIt) set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4365 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4366 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4367 : return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4368 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4369 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4370 : }
4371 :
4372 : #else
4373 :
4374 : template<class _InIt1,
4375 : class _InIt2,
4376 : class _OutIt,
4377 : class _Pr> inline
4378 : _OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
4379 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
4380 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
4381 : return _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4382 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
4383 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
4384 : }
4385 :
4386 : #endif
4387 :
4388 : // TEMPLATE FUNCTION max_element
4389 : template<class _FwdIt> inline
4390 : _FwdIt _Max_element(_FwdIt _First, _FwdIt _Last)
4391 : { // find largest element, using operator<
4392 : _DEBUG_RANGE(_First, _Last);
4393 : _FwdIt _Found = _First;
4394 : if (_First != _Last)
4395 : for (; ++_First != _Last; )
4396 : if (_DEBUG_LT(*_Found, *_First))
4397 : _Found = _First;
4398 : return (_Found);
4399 : }
4400 :
4401 : template<class _FwdIt> inline
4402 : _FwdIt max_element(_FwdIt _First, _FwdIt _Last)
4403 : { // find largest element, using operator<
4404 : _ASSIGN_FROM_BASE(_First,
4405 : _Max_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Last)));
4406 : return (_First);
4407 : }
4408 :
4409 : // TEMPLATE FUNCTION max_element WITH PRED
4410 : template<class _FwdIt,
4411 : class _Pr> inline
4412 : _FwdIt _Max_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
4413 : { // find largest element, using _Pred
4414 : _DEBUG_RANGE(_First, _Last);
4415 : _DEBUG_POINTER(_Pred);
4416 : _FwdIt _Found = _First;
4417 : if (_First != _Last)
4418 : for (; ++_First != _Last; )
4419 : if (_DEBUG_LT_PRED(_Pred, *_Found, *_First))
4420 : _Found = _First;
4421 : return (_Found);
4422 : }
4423 :
4424 : template<class _FwdIt,
4425 : class _Pr> inline
4426 : _FwdIt max_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
4427 : { // find largest element, using _Pred
4428 : _ASSIGN_FROM_BASE(_First,
4429 : _Max_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
4430 : return (_First);
4431 : }
4432 :
4433 : // TEMPLATE FUNCTION min_element
4434 : template<class _FwdIt> inline
4435 : _FwdIt _Min_element(_FwdIt _First, _FwdIt _Last)
4436 : { // find smallest element, using operator<
4437 : _DEBUG_RANGE(_First, _Last);
4438 : _FwdIt _Found = _First;
4439 : if (_First != _Last)
4440 : for (; ++_First != _Last; )
4441 : if (_DEBUG_LT(*_First, *_Found))
4442 : _Found = _First;
4443 : return (_Found);
4444 : }
4445 :
4446 : template<class _FwdIt> inline
4447 : _FwdIt min_element(_FwdIt _First, _FwdIt _Last)
4448 : { // find smallest element, using operator<
4449 : _ASSIGN_FROM_BASE(_First,
4450 : _Min_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Last)));
4451 : return (_First);
4452 : }
4453 :
4454 : // TEMPLATE FUNCTION min_element WITH PRED
4455 : template<class _FwdIt,
4456 : class _Pr> inline
4457 : _FwdIt _Min_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
4458 : { // find smallest element, using _Pred
4459 : _DEBUG_RANGE(_First, _Last);
4460 : _DEBUG_POINTER(_Pred);
4461 : _FwdIt _Found = _First;
4462 : if (_First != _Last)
4463 : for (; ++_First != _Last; )
4464 : if (_DEBUG_LT_PRED(_Pred, *_First, *_Found))
4465 : _Found = _First;
4466 : return (_Found);
4467 : }
4468 :
4469 : template<class _FwdIt,
4470 : class _Pr> inline
4471 : _FwdIt min_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
4472 : { // find smallest element, using _Pred
4473 : _ASSIGN_FROM_BASE(_First,
4474 : _Min_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
4475 : return (_First);
4476 : }
4477 :
4478 : // TEMPLATE FUNCTION next_permutation
4479 : template<class _BidIt> inline
4480 : bool _Next_permutation(_BidIt _First, _BidIt _Last)
4481 : { // permute and test for pure ascending, using operator<
4482 : _DEBUG_RANGE(_First, _Last);
4483 : _BidIt _Next = _Last;
4484 : if (_First == _Last || _First == --_Next)
4485 : return (false);
4486 :
4487 : for (; ; )
4488 : { // find rightmost element smaller than successor
4489 : _BidIt _Next1 = _Next;
4490 : if (_DEBUG_LT(*--_Next, *_Next1))
4491 : { // swap with rightmost element that's smaller, flip suffix
4492 : _BidIt _Mid = _Last;
4493 : for (; !_DEBUG_LT(*_Next, *--_Mid); )
4494 : ;
4495 : std::iter_swap(_Next, _Mid);
4496 : std::reverse(_Next1, _Last);
4497 : return (true);
4498 : }
4499 :
4500 : if (_Next == _First)
4501 : { // pure descending, flip all
4502 : std::reverse(_First, _Last);
4503 : return (false);
4504 : }
4505 : }
4506 : }
4507 :
4508 : template<class _BidIt> inline
4509 : bool next_permutation(_BidIt _First, _BidIt _Last)
4510 : { // permute and test for pure ascending, using operator<
4511 : return _Next_permutation(_CHECKED_BASE(_First), _CHECKED_BASE(_Last));
4512 : }
4513 :
4514 : // TEMPLATE FUNCTION next_permutation WITH PRED
4515 : template<class _BidIt,
4516 : class _Pr> inline
4517 : bool _Next_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
4518 : { // permute and test for pure ascending, using _Pred
4519 : _DEBUG_RANGE(_First, _Last);
4520 : _DEBUG_POINTER(_Pred);
4521 : _BidIt _Next = _Last;
4522 : if (_First == _Last || _First == --_Next)
4523 : return (false);
4524 :
4525 : for (; ; )
4526 : { // find rightmost element smaller than successor
4527 : _BidIt _Next1 = _Next;
4528 : if (_DEBUG_LT_PRED(_Pred, *--_Next, *_Next1))
4529 : { // swap with rightmost element that's smaller, flip suffix
4530 : _BidIt _Mid = _Last;
4531 : for (; !_DEBUG_LT_PRED(_Pred, *_Next, *--_Mid); )
4532 : ;
4533 : std::iter_swap(_Next, _Mid);
4534 : std::reverse(_Next1, _Last);
4535 : return (true);
4536 : }
4537 :
4538 : if (_Next == _First)
4539 : { // pure descending, flip all
4540 : std::reverse(_First, _Last);
4541 : return (false);
4542 : }
4543 : }
4544 : }
4545 :
4546 : template<class _BidIt,
4547 : class _Pr> inline
4548 : bool next_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
4549 : { // permute and test for pure ascending, using _Pred
4550 : return _Next_permutation(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred);
4551 : }
4552 :
4553 : // TEMPLATE FUNCTION prev_permutation
4554 : template<class _BidIt> inline
4555 : bool _Prev_permutation(_BidIt _First, _BidIt _Last)
4556 : { // reverse permute and test for pure descending, using operator<
4557 : _DEBUG_RANGE(_First, _Last);
4558 : _BidIt _Next = _Last;
4559 : if (_First == _Last || _First == --_Next)
4560 : return (false);
4561 : for (; ; )
4562 : { // find rightmost element not smaller than successor
4563 : _BidIt _Next1 = _Next;
4564 : if (_DEBUG_LT(*_Next1, *--_Next))
4565 : { // swap with rightmost element that's not smaller, flip suffix
4566 : _BidIt _Mid = _Last;
4567 : for (; !_DEBUG_LT(*--_Mid, *_Next); )
4568 : ;
4569 : std::iter_swap(_Next, _Mid);
4570 : std::reverse(_Next1, _Last);
4571 : return (true);
4572 : }
4573 :
4574 : if (_Next == _First)
4575 : { // pure ascending, flip all
4576 : std::reverse(_First, _Last);
4577 : return (false);
4578 : }
4579 : }
4580 : }
4581 :
4582 : template<class _BidIt> inline
4583 : bool prev_permutation(_BidIt _First, _BidIt _Last)
4584 : { // reverse permute and test for pure descending, using operator<
4585 : return _Prev_permutation(_CHECKED_BASE(_First), _CHECKED_BASE(_Last));
4586 : }
4587 :
4588 : // TEMPLATE FUNCTION prev_permutation WITH PRED
4589 : template<class _BidIt,
4590 : class _Pr> inline
4591 : bool _Prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
4592 : { // reverse permute and test for pure descending, using _Pred
4593 : _DEBUG_RANGE(_First, _Last);
4594 : _DEBUG_POINTER(_Pred);
4595 : _BidIt _Next = _Last;
4596 : if (_First == _Last || _First == --_Next)
4597 : return (false);
4598 :
4599 : for (; ; )
4600 : { // find rightmost element not smaller than successor
4601 : _BidIt _Next1 = _Next;
4602 : if (_DEBUG_LT_PRED(_Pred, *_Next1, *--_Next))
4603 : { // swap with rightmost element that's not smaller, flip suffix
4604 : _BidIt _Mid = _Last;
4605 : for (; !_DEBUG_LT_PRED(_Pred, *--_Mid, *_Next); )
4606 : ;
4607 : std::iter_swap(_Next, _Mid);
4608 : std::reverse(_Next1, _Last);
4609 : return (true);
4610 : }
4611 :
4612 : if (_Next == _First)
4613 : { // pure ascending, flip all
4614 : std::reverse(_First, _Last);
4615 : return (false);
4616 : }
4617 : }
4618 : }
4619 :
4620 : template<class _BidIt,
4621 : class _Pr> inline
4622 : bool prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
4623 : { // reverse permute and test for pure descending, using _Pred
4624 : return _Prev_permutation(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred);
4625 : }
4626 :
4627 : _STD_END
4628 :
4629 : _STDEXT_BEGIN
4630 :
4631 : template<class _InIt, class _OutIt, class _Fn1>
4632 : inline
4633 : _OutIt unchecked_transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
4634 : {
4635 : return _STD _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
4636 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4637 : }
4638 :
4639 : template<class _InIt, class _OutIt, class _Fn1>
4640 : inline
4641 : _IF_CHK(_OutIt) checked_transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
4642 : {
4643 : return _STD _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
4644 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4645 : }
4646 :
4647 : template<class _InIt, class _OutElem, class _Fn1, size_t _Size>
4648 : inline
4649 : _OutElem* checked_transform(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Fn1 _Func)
4650 : {
4651 : return (checked_transform(_First, _Last,
4652 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Func).base());
4653 : }
4654 :
4655 : template<class _InIt, class _OutIt, class _Fn1>
4656 : inline
4657 : _SCL_CHECKED_ALGORITHM_WARN
4658 : _IF_NOT_CHK(_OutIt) checked_transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
4659 : {
4660 : return _STD _Transform(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Func,
4661 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4662 : }
4663 :
4664 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
4665 : inline
4666 : _OutIt unchecked_transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
4667 : _OutIt _Dest, _Fn2 _Func)
4668 : {
4669 : return _STD _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
4670 : _STD _Iter_random(_First1, _First2), _STD _Iter_random(_First1, _Dest),
4671 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
4672 : }
4673 :
4674 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
4675 : inline
4676 : _IF_CHK2_(_InIt2, _OutIt, _OutIt) checked_transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
4677 : _OutIt _Dest, _Fn2 _Func)
4678 : {
4679 : return _STD _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
4680 : _STD _Iter_random(_First1, _First2), _STD _Iter_random(_First1, _Dest),
4681 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
4682 : }
4683 :
4684 : template<class _InIt1, class _InElem2, class _OutElem, class _Fn2, size_t _SizeFirst2, size_t _SizeDest>
4685 : inline
4686 : _OutElem* checked_transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
4687 : _OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
4688 : {
4689 : return (checked_transform(_First1, _Last1,
4690 : _STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
4691 : _STDEXT make_checked_array_iterator(_Dest, _SizeDest),
4692 : _Func).base());
4693 : }
4694 :
4695 : template<class _InIt1, class _InIt2, class _OutElem, class _Fn2, size_t _SizeDest>
4696 : inline
4697 : _IF_CHK_(_InIt2, _OutElem*) checked_transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
4698 : _OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
4699 : {
4700 : return (_STD _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
4701 : _STDEXT make_checked_array_iterator(_Dest, _SizeDest), _Func,
4702 : _STD _Iter_random(_First1, _First2), _STD _Iter_cat(_First1),
4703 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()).base());
4704 : }
4705 :
4706 : template<class _InIt1, class _InIt2, class _OutElem, class _Fn2, size_t _SizeDest>
4707 : inline
4708 : _SCL_CHECKED_ALGORITHM_WARN
4709 : _IF_NOT_CHK_(_InIt2, _OutElem*) checked_transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
4710 : _OutElem (&_Dest)[_SizeDest], _Fn2 _Func)
4711 : {
4712 : return (_STD _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
4713 : _STDEXT make_checked_array_iterator(_Dest, _SizeDest), _Func,
4714 : _STD _Iter_random(_First1, _First2), _STD _Iter_cat(_First1),
4715 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()).base());
4716 : }
4717 :
4718 : template<class _InIt1, class _InElem2, class _OutIt, class _Fn2, size_t _SizeFirst2>
4719 : inline
4720 : _IF_CHK(_OutIt) checked_transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
4721 : _OutIt _Dest, _Fn2 _Func)
4722 : {
4723 : return (_STD _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4724 : _STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
4725 : _Dest, _Func,
4726 : _STD _Iter_cat(_First1), _STD _Iter_random(_First1, _Dest),
4727 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()));
4728 : }
4729 :
4730 : template<class _InIt1, class _InElem2, class _OutIt, class _Fn2, size_t _SizeFirst2>
4731 : inline
4732 : _SCL_CHECKED_ALGORITHM_WARN
4733 : _IF_NOT_CHK(_OutIt) checked_transform(_InIt1 _First1, _InIt1 _Last1, _InElem2 (&_First2)[_SizeFirst2],
4734 : _OutIt _Dest, _Fn2 _Func)
4735 : {
4736 : return (_STD _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
4737 : _STDEXT make_checked_array_iterator(_First2, _SizeFirst2),
4738 : _Dest, _Func,
4739 : _STD _Iter_cat(_First1), _STD _Iter_random(_First1, _Dest),
4740 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag()));
4741 : }
4742 :
4743 : template<class _InIt1, class _InIt2, class _OutIt, class _Fn2>
4744 : inline
4745 : _SCL_CHECKED_ALGORITHM_WARN
4746 : _IF_NOT_CHK2_(_InIt2, _OutIt, _OutIt) checked_transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
4747 : _OutIt _Dest, _Fn2 _Func)
4748 : {
4749 : return _STD _Transform(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2, _Dest, _Func,
4750 : _STD _Iter_random(_First1, _First2), _STD _Iter_random(_First1, _Dest),
4751 : _STD _Range_checked_iterator_tag(), _STD _Range_checked_iterator_tag());
4752 : }
4753 :
4754 : template<class _FwdIt1, class _FwdIt2>
4755 : inline
4756 : _FwdIt2 unchecked_swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
4757 : {
4758 : return _STD _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
4759 : _STD _Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
4760 : }
4761 :
4762 : template<class _FwdIt1, class _FwdIt2>
4763 : inline
4764 : _IF_CHK(_FwdIt2) checked_swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
4765 : {
4766 : return _STD _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
4767 : _STD _Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
4768 : }
4769 :
4770 : template<class _FwdIt1, class _FwdElem2, size_t _Size>
4771 : inline
4772 : _FwdElem2* checked_swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdElem2 (&_First2)[_Size])
4773 : {
4774 : return (checked_swap_ranges(_First1, _Last1, _STDEXT make_checked_array_iterator(_First2, _Size)).base());
4775 : }
4776 :
4777 : template<class _FwdIt1, class _FwdIt2>
4778 : inline
4779 : _SCL_CHECKED_ALGORITHM_WARN
4780 : _IF_NOT_CHK(_FwdIt2) checked_swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
4781 : {
4782 : return _STD _Swap_ranges(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _First2,
4783 : _STD _Iter_random(_First1, _First2), _STD _Range_checked_iterator_tag());
4784 : }
4785 :
4786 : template<class _InIt,
4787 : class _OutIt,
4788 : class _Ty> inline
4789 : _OutIt unchecked_replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
4790 : const _Ty& _Oldval, const _Ty& _Newval)
4791 : { // copy replacing each matching _Oldval with _Newval
4792 : return _STD _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
4793 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4794 : }
4795 :
4796 : template<class _InIt,
4797 : class _OutIt,
4798 : class _Ty> inline
4799 : _IF_CHK(_OutIt) checked_replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
4800 : const _Ty& _Oldval, const _Ty& _Newval)
4801 : { // copy replacing each matching _Oldval with _Newval
4802 : return _STD _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
4803 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4804 : }
4805 :
4806 : template<class _InIt, class _OutElem, class _Ty, size_t _Size>
4807 : inline
4808 : _OutElem* checked_replace_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size],
4809 : const _Ty& _Oldval, const _Ty& _Newval)
4810 : { // copy replacing each matching _Oldval with _Newval
4811 : return (checked_replace_copy(_First, _Last,
4812 : _STDEXT make_checked_array_iterator(_Dest, _Size),
4813 : _Oldval, _Newval).base());
4814 : }
4815 :
4816 : template<class _InIt,
4817 : class _OutIt,
4818 : class _Ty> inline
4819 : _SCL_CHECKED_ALGORITHM_WARN
4820 : _IF_NOT_CHK(_OutIt) checked_replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
4821 : const _Ty& _Oldval, const _Ty& _Newval)
4822 : { // copy replacing each matching _Oldval with _Newval
4823 : return _STD _Replace_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Oldval, _Newval,
4824 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4825 : }
4826 :
4827 : template<class _InIt,
4828 : class _OutIt,
4829 : class _Pr,
4830 : class _Ty> inline
4831 : _OutIt unchecked_replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
4832 : _Pr _Pred, const _Ty& _Val)
4833 : { // copy replacing each satisfying _Pred with _Val
4834 : return _STD _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
4835 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4836 : }
4837 :
4838 : template<class _InIt,
4839 : class _OutIt,
4840 : class _Pr,
4841 : class _Ty> inline
4842 : _IF_CHK(_OutIt) checked_replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
4843 : _Pr _Pred, const _Ty& _Val)
4844 : { // copy replacing each satisfying _Pred with _Val
4845 : return _STD _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
4846 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4847 : }
4848 :
4849 : template<class _InIt, class _OutElem, class _Pr, class _Ty, size_t _Size>
4850 : inline
4851 : _OutElem* checked_replace_copy_if(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size],
4852 : _Pr _Pred, const _Ty& _Val)
4853 : { // copy replacing each satisfying _Pred with _Val
4854 : return (checked_replace_copy_if(_First, _Last,
4855 : _STDEXT make_checked_array_iterator(_Dest, _Size),
4856 : _Pred, _Val).base());
4857 : }
4858 :
4859 : template<class _InIt,
4860 : class _OutIt,
4861 : class _Pr,
4862 : class _Ty> inline
4863 : _SCL_CHECKED_ALGORITHM_WARN
4864 : _IF_NOT_CHK(_OutIt) checked_replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
4865 : _Pr _Pred, const _Ty& _Val)
4866 : { // copy replacing each satisfying _Pred with _Val
4867 : return _STD _Replace_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _Val,
4868 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
4869 : }
4870 :
4871 : template<class _OutIt,
4872 : class _Diff,
4873 : class _Fn0> inline
4874 : void unchecked_generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
4875 : { // replace [_Dest, _Dest + _Count) with _Func()
4876 : _STD _Generate_n(_Dest, _Count, _Func,
4877 : _STD _Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
4878 : }
4879 :
4880 : template<class _OutIt,
4881 : class _Diff,
4882 : class _Fn0> inline
4883 : void checked_generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func, _IF_CHK_(_OutIt, _Diff) = 0)
4884 : { // replace [_Dest, _Dest + _Count) with _Func()
4885 : _STD _Generate_n(_Dest, _Count, _Func,
4886 : _STD _Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
4887 : }
4888 :
4889 : template<class _OutElem, class _Diff, class _Fn0, size_t _Size>
4890 : inline
4891 : void checked_generate_n(_OutElem (&_Dest)[_Size], _Diff _Count, _Fn0 _Func)
4892 : { // replace [_Dest, _Dest + _Count) with _Func()
4893 : checked_generate_n(_STDEXT make_checked_array_iterator(_Dest, _Size), _Count, _Func);
4894 : }
4895 :
4896 : template<class _OutIt,
4897 : class _Diff,
4898 : class _Fn0> inline
4899 : _SCL_CHECKED_ALGORITHM_WARN
4900 : void checked_generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func, _IF_NOT_CHK_(_OutIt, _Diff) = 0)
4901 : { // replace [_Dest, _Dest + _Count) with _Func()
4902 : _STD _Generate_n(_Dest, _Count, _Func,
4903 : _STD _Iter_cat(_Dest), _STD _Range_checked_iterator_tag());
4904 : }
4905 :
4906 : template<class _InIt,
4907 : class _OutIt,
4908 : class _Ty> inline
4909 : _OutIt unchecked_remove_copy(_InIt _First, _InIt _Last,
4910 : _OutIt _Dest, const _Ty& _Val)
4911 : { // copy omitting each matching _Val
4912 : return _STD _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val,
4913 : _STD _Range_checked_iterator_tag());
4914 : }
4915 :
4916 : template<class _InIt,
4917 : class _OutIt,
4918 : class _Ty> inline
4919 : _IF_CHK(_OutIt) checked_remove_copy(_InIt _First, _InIt _Last,
4920 : _OutIt _Dest, const _Ty& _Val)
4921 : { // copy omitting each matching _Val
4922 : return _STD _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
4923 : }
4924 :
4925 : template<class _InIt, class _OutElem, class _Ty, size_t _Size>
4926 : inline
4927 : _OutElem* checked_remove_copy(_InIt _First, _InIt _Last,
4928 : _OutElem (&_Dest)[_Size], const _Ty& _Val)
4929 : { // copy omitting each matching _Val
4930 : return (checked_remove_copy(_First, _Last,
4931 : _STDEXT make_checked_array_iterator(_Dest, _Size),
4932 : _Val).base());
4933 : }
4934 :
4935 : template<class _InIt,
4936 : class _OutIt,
4937 : class _Ty> inline
4938 : _SCL_CHECKED_ALGORITHM_WARN
4939 : _IF_NOT_CHK(_OutIt) checked_remove_copy(_InIt _First, _InIt _Last,
4940 : _OutIt _Dest, const _Ty& _Val)
4941 : { // copy omitting each matching _Val
4942 : return _STD _Remove_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Val, _STD _Range_checked_iterator_tag());
4943 : }
4944 :
4945 : template<class _InIt,
4946 : class _OutIt,
4947 : class _Pr> inline
4948 : _OutIt unchecked_remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
4949 : { // copy omitting each element satisfying _Pred
4950 : return _STD _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred,
4951 : _STD _Range_checked_iterator_tag());
4952 : }
4953 :
4954 : template<class _InIt,
4955 : class _OutIt,
4956 : class _Pr> inline
4957 : _IF_CHK(_OutIt) checked_remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
4958 : { // copy omitting each element satisfying _Pred
4959 : return _STD _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
4960 : }
4961 :
4962 : template<class _InIt, class _OutElem, class _Pr, size_t _Size>
4963 : inline
4964 : _OutElem* checked_remove_copy_if(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Pr _Pred)
4965 : { // copy omitting each element satisfying _Pred
4966 : return (checked_remove_copy_if(_First, _Last,
4967 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
4968 : }
4969 :
4970 : template<class _InIt,
4971 : class _OutIt,
4972 : class _Pr> inline
4973 : _SCL_CHECKED_ALGORITHM_WARN
4974 : _IF_NOT_CHK(_OutIt) checked_remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
4975 : { // copy omitting each element satisfying _Pred
4976 : return _STD _Remove_copy_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Range_checked_iterator_tag());
4977 : }
4978 :
4979 : template<class _InIt,
4980 : class _OutIt> inline
4981 : _OutIt unchecked_unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
4982 : { // copy compressing pairs that match
4983 : return (_First == _Last ? _Dest :
4984 : _STD _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
4985 : _STD _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
4986 : }
4987 :
4988 : template<class _InIt,
4989 : class _OutIt> inline
4990 : _IF_CHK(_OutIt) checked_unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
4991 : { // copy compressing pairs that match
4992 : return (_First == _Last ? _Dest :
4993 : _STD _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _STD _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
4994 : }
4995 :
4996 : template<class _InIt, class _OutElem, size_t _Size>
4997 : inline
4998 : _OutElem* checked_unique_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size])
4999 : { // copy compressing pairs that match
5000 : return (_First == _Last ? _Dest :
5001 : (checked_unique_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base()));
5002 : }
5003 :
5004 : template<class _InIt,
5005 : class _OutIt> inline
5006 : _SCL_CHECKED_ALGORITHM_WARN
5007 : _IF_NOT_CHK(_OutIt) checked_unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
5008 : { // copy compressing pairs that match
5009 : return (_First == _Last ? _Dest :
5010 : _STD _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _STD _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
5011 : }
5012 :
5013 : template<class _InIt,
5014 : class _OutIt,
5015 : class _Pr> inline
5016 : _OutIt unchecked_unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
5017 : { // copy compressing pairs satisfying _Pred
5018 : return (_First == _Last ? _Dest
5019 : : _STD _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred,
5020 : _STD _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
5021 : }
5022 :
5023 : template<class _InIt,
5024 : class _OutIt,
5025 : class _Pr> inline
5026 : _IF_CHK(_OutIt) checked_unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
5027 : { // copy compressing pairs satisfying _Pred
5028 : return (_First == _Last ? _Dest
5029 : : _STD _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
5030 : }
5031 :
5032 : template<class _InIt, class _OutElem, class _Pr, size_t _Size>
5033 : inline
5034 : _OutElem* checked_unique_copy(_InIt _First, _InIt _Last, _OutElem (&_Dest)[_Size], _Pr _Pred)
5035 : { // copy compressing pairs satisfying _Pred
5036 : return (_First == _Last ? _Dest
5037 : : (checked_unique_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base()));
5038 : }
5039 :
5040 : template<class _InIt,
5041 : class _OutIt,
5042 : class _Pr> inline
5043 : _SCL_CHECKED_ALGORITHM_WARN
5044 : _IF_NOT_CHK(_OutIt) checked_unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
5045 : { // copy compressing pairs satisfying _Pred
5046 : return (_First == _Last ? _Dest
5047 : : _STD _Unique_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _Pred, _STD _Iter_cat(_First), _STD _Range_checked_iterator_tag()));
5048 : }
5049 :
5050 : template<class _BidIt,
5051 : class _OutIt> inline
5052 : _OutIt unchecked_reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
5053 : { // copy reversing elements in [_First, _Last)
5054 : return _STD _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest,
5055 : _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
5056 : }
5057 :
5058 : template<class _BidIt,
5059 : class _OutIt> inline
5060 : _IF_CHK(_OutIt) checked_reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
5061 : { // copy reversing elements in [_First, _Last)
5062 : return _STD _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
5063 : }
5064 :
5065 : template<class _BidIt, class _OutElem, size_t _Size>
5066 : inline
5067 : _OutElem* checked_reverse_copy(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size])
5068 : { // copy reversing elements in [_First, _Last)
5069 : return (checked_reverse_copy(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
5070 : }
5071 :
5072 : template<class _BidIt,
5073 : class _OutIt> inline
5074 : _SCL_CHECKED_ALGORITHM_WARN
5075 : _IF_NOT_CHK(_OutIt) checked_reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
5076 : { // copy reversing elements in [_First, _Last)
5077 : return _STD _Reverse_copy(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Dest, _STD _Iter_random(_First, _Dest), _STD _Range_checked_iterator_tag());
5078 : }
5079 :
5080 : template<class _FwdIt,
5081 : class _OutIt> inline
5082 : _OutIt unchecked_rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
5083 : { // copy rotating [_First, _Last)
5084 : return _STD _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
5085 : }
5086 :
5087 : template<class _FwdIt, class _OutIt>
5088 : inline
5089 : _IF_CHK(_OutIt) checked_rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
5090 : {
5091 : return _STD _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
5092 : }
5093 :
5094 : template<class _FwdIt, class _OutElem, size_t _Size>
5095 : inline
5096 : _OutElem* checked_rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutElem (&_Dest)[_Size])
5097 : {
5098 : return (checked_rotate_copy(_First, _Mid, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
5099 : }
5100 :
5101 : template<class _FwdIt, class _OutIt>
5102 : inline
5103 : _SCL_CHECKED_ALGORITHM_WARN
5104 : _IF_NOT_CHK(_OutIt) checked_rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
5105 : {
5106 : return _STD _Rotate_copy(_First, _Mid, _Last, _Dest, _STD _Range_checked_iterator_tag());
5107 : }
5108 :
5109 : template<class _InIt1,
5110 : class _InIt2,
5111 : class _OutIt> inline
5112 : _OutIt unchecked_merge(_InIt1 _First1, _InIt1 _Last1,
5113 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5114 : { // copy merging ranges, both using operator<
5115 : return _STD _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
5116 : _STD _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
5117 : }
5118 :
5119 : template<class _InIt1,
5120 : class _InIt2,
5121 : class _OutIt> inline
5122 : _IF_CHK(_OutIt) checked_merge(_InIt1 _First1, _InIt1 _Last1,
5123 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5124 : { // copy merging ranges, both using operator<
5125 : return _STD _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5126 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
5127 : _STD _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
5128 : }
5129 :
5130 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
5131 : inline
5132 : _OutElem* checked_merge(_InIt1 _First1, _InIt1 _Last1,
5133 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
5134 : { // copy merging ranges, both using operator<
5135 : return (checked_merge(_First1, _Last1, _First2, _Last2,
5136 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
5137 : }
5138 :
5139 : template<class _InIt1,
5140 : class _InIt2,
5141 : class _OutIt> inline
5142 : _SCL_CHECKED_ALGORITHM_WARN
5143 : _IF_NOT_CHK(_OutIt) checked_merge(_InIt1 _First1, _InIt1 _Last1,
5144 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5145 : { // copy merging ranges, both using operator<
5146 : return _STD _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5147 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
5148 : _STD _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
5149 : }
5150 :
5151 : template<class _InIt1,
5152 : class _InIt2,
5153 : class _OutIt,
5154 : class _Pr> inline
5155 : _OutIt unchecked_merge(_InIt1 _First1, _InIt1 _Last1,
5156 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5157 : { // copy merging ranges, both using _Pred
5158 : return _STD _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest, _Pred,
5159 : _STD _Iter_random(_First1, _First2,_Dest), _STD _Range_checked_iterator_tag());
5160 : }
5161 :
5162 : template<class _InIt1,
5163 : class _InIt2,
5164 : class _OutIt,
5165 : class _Pr> inline
5166 : _IF_CHK(_OutIt) checked_merge(_InIt1 _First1, _InIt1 _Last1,
5167 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5168 : { // copy merging ranges, both using _Pred
5169 : return _STD _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5170 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5171 : _Dest, _Pred,
5172 : _STD _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
5173 : }
5174 :
5175 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
5176 : inline
5177 : _OutElem* checked_merge(_InIt1 _First1, _InIt1 _Last1,
5178 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
5179 : { // copy merging ranges, both using _Pred
5180 : return (checked_merge(_First1, _Last1, _First2, _Last2,
5181 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
5182 : }
5183 :
5184 : template<class _InIt1,
5185 : class _InIt2,
5186 : class _OutIt,
5187 : class _Pr> inline
5188 : _SCL_CHECKED_ALGORITHM_WARN
5189 : _IF_NOT_CHK(_OutIt) checked_merge(_InIt1 _First1, _InIt1 _Last1,
5190 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5191 : { // copy merging ranges, both using _Pred
5192 : return _STD _Merge(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5193 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5194 : _Dest, _Pred,
5195 : _STD _Iter_random(_First1, _First2, _Dest), _STD _Range_checked_iterator_tag());
5196 : }
5197 :
5198 : template<class _BidIt1, class _BidIt2, class _BidIt3>
5199 : inline
5200 : _BidIt3 _Unchecked_merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
5201 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
5202 : {
5203 : return _STD _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
5204 : }
5205 :
5206 : template<class _BidIt1, class _BidIt2, class _BidIt3>
5207 : inline
5208 : _IF_CHK(_BidIt3) _Checked_merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
5209 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
5210 : {
5211 : return _STD _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
5212 : }
5213 :
5214 : template<class _BidIt1, class _BidIt2, class _BidIt3>
5215 : inline
5216 : _SCL_CHECKED_ALGORITHM_WARN
5217 : _IF_NOT_CHK(_BidIt3) _Checked_merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
5218 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
5219 : {
5220 : return _STD _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _STD _Range_checked_iterator_tag());
5221 : }
5222 :
5223 : template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
5224 : inline
5225 : _BidIt3 _Unchecked_merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
5226 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
5227 : {
5228 : return _STD _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
5229 : }
5230 :
5231 : template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
5232 : inline
5233 : _IF_CHK(_BidIt3) _Checked_merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
5234 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
5235 : {
5236 : return _STD _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
5237 : }
5238 :
5239 : template<class _BidIt1, class _BidIt2, class _BidIt3, class _Pr>
5240 : inline
5241 : _SCL_CHECKED_ALGORITHM_WARN
5242 : _IF_NOT_CHK(_BidIt3) _Checked_merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
5243 : _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
5244 : {
5245 : return _STD _Merge_backward(_First1, _Last1, _First2, _Last2, _Dest, _Pred, _STD _Range_checked_iterator_tag());
5246 : }
5247 :
5248 : template<class _BidIt, class _OutIt, class _Diff>
5249 : inline
5250 : void _Unchecked_chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
5251 : _Diff _Chunk, _Diff _Count)
5252 : {
5253 : _STD _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
5254 : }
5255 :
5256 : template<class _BidIt, class _OutIt, class _Diff>
5257 : inline
5258 : _IF_CHK_(_OutIt, void) _Checked_chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
5259 : _Diff _Chunk, _Diff _Count)
5260 : {
5261 : _STD _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
5262 : }
5263 :
5264 : template<class _BidIt, class _OutElem, class _Diff, size_t _Size>
5265 : inline
5266 : void _Checked_chunked_merge(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size],
5267 : _Diff _Chunk, _Diff _Count)
5268 : {
5269 : _STD _Chunked_merge(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Chunk, _Count, _STD _Range_checked_iterator_tag());
5270 : }
5271 :
5272 : template<class _BidIt, class _OutIt, class _Diff>
5273 : inline
5274 : _SCL_CHECKED_ALGORITHM_WARN
5275 : _IF_NOT_CHK_(_OutIt, void) _Checked_chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
5276 : _Diff _Chunk, _Diff _Count)
5277 : {
5278 : _STD _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _STD _Range_checked_iterator_tag());
5279 : }
5280 :
5281 : template<class _BidIt, class _OutIt, class _Diff, class _Pr>
5282 : inline
5283 : void _Unchecked_chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
5284 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
5285 : {
5286 : _STD _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
5287 : }
5288 :
5289 : template<class _BidIt, class _OutIt, class _Diff, class _Pr>
5290 : inline
5291 : _IF_CHK_(_OutIt, void) _Checked_chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
5292 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
5293 : {
5294 : _STD _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
5295 : }
5296 :
5297 : template<class _BidIt, class _OutElem, class _Diff, class _Pr, size_t _Size>
5298 : inline
5299 : void _Checked_chunked_merge(_BidIt _First, _BidIt _Last, _OutElem (&_Dest)[_Size],
5300 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
5301 : {
5302 : _STD _Chunked_merge(_First, _Last, _STDEXT make_checked_array_iterator(_Dest, _Size), _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
5303 : }
5304 :
5305 : template<class _BidIt, class _OutIt, class _Diff, class _Pr>
5306 : inline
5307 : _SCL_CHECKED_ALGORITHM_WARN
5308 : _IF_NOT_CHK_(_OutIt, void) _Checked_chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
5309 : _Diff _Chunk, _Diff _Count, _Pr _Pred)
5310 : {
5311 : _STD _Chunked_merge(_First, _Last, _Dest, _Chunk, _Count, _Pred, _STD _Range_checked_iterator_tag());
5312 : }
5313 :
5314 : template<class _InIt1,
5315 : class _InIt2,
5316 : class _OutIt> inline
5317 : _OutIt unchecked_set_union(_InIt1 _First1, _InIt1 _Last1,
5318 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5319 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5320 : return _STD _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
5321 : _STD _Range_checked_iterator_tag());
5322 : }
5323 :
5324 : template<class _InIt1,
5325 : class _InIt2,
5326 : class _OutIt> inline
5327 : _IF_CHK(_OutIt) checked_set_union(_InIt1 _First1, _InIt1 _Last1,
5328 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5329 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5330 : return _STD _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5331 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5332 : _Dest, _STD _Range_checked_iterator_tag());
5333 : }
5334 :
5335 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
5336 : inline
5337 : _OutElem* checked_set_union(_InIt1 _First1, _InIt1 _Last1,
5338 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
5339 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5340 : return (checked_set_union(_First1, _Last1, _First2, _Last2,
5341 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
5342 : }
5343 :
5344 : template<class _InIt1,
5345 : class _InIt2,
5346 : class _OutIt> inline
5347 : _SCL_CHECKED_ALGORITHM_WARN
5348 : _IF_NOT_CHK(_OutIt) checked_set_union(_InIt1 _First1, _InIt1 _Last1,
5349 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5350 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5351 : return _STD _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5352 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5353 : _Dest, _STD _Range_checked_iterator_tag());
5354 : }
5355 :
5356 : template<class _InIt1,
5357 : class _InIt2,
5358 : class _OutIt,
5359 : class _Pr> inline
5360 : _OutIt unchecked_set_union(_InIt1 _First1, _InIt1 _Last1,
5361 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5362 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5363 : return _STD _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest, _Pred,
5364 : _STD _Range_checked_iterator_tag());
5365 : }
5366 :
5367 : template<class _InIt1,
5368 : class _InIt2,
5369 : class _OutIt,
5370 : class _Pr> inline
5371 : _IF_CHK(_OutIt) checked_set_union(_InIt1 _First1, _InIt1 _Last1,
5372 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5373 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5374 : return _STD _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5375 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5376 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5377 : }
5378 :
5379 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
5380 : inline
5381 : _OutElem* checked_set_union(_InIt1 _First1, _InIt1 _Last1,
5382 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
5383 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5384 : return (checked_set_union(_First1, _Last1, _First2, _Last2,
5385 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
5386 : }
5387 :
5388 : template<class _InIt1,
5389 : class _InIt2,
5390 : class _OutIt,
5391 : class _Pr> inline
5392 : _SCL_CHECKED_ALGORITHM_WARN
5393 : _IF_NOT_CHK(_OutIt) checked_set_union(_InIt1 _First1, _InIt1 _Last1,
5394 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5395 : { // OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5396 : return _STD _Set_union(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5397 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5398 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5399 : }
5400 :
5401 : template<class _InIt1,
5402 : class _InIt2,
5403 : class _OutIt> inline
5404 : _OutIt unchecked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5405 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5406 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
5407 : return _STD _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
5408 : _STD _Range_checked_iterator_tag());
5409 : }
5410 :
5411 : template<class _InIt1,
5412 : class _InIt2,
5413 : class _OutIt> inline
5414 : _IF_CHK(_OutIt) checked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5415 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5416 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
5417 : return _STD _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5418 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5419 : _Dest, _STD _Range_checked_iterator_tag());
5420 : }
5421 :
5422 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
5423 : inline
5424 : _OutElem* checked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5425 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
5426 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
5427 : return (checked_set_intersection(_First1, _Last1, _First2, _Last2,
5428 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
5429 : }
5430 :
5431 : template<class _InIt1,
5432 : class _InIt2,
5433 : class _OutIt> inline
5434 : _SCL_CHECKED_ALGORITHM_WARN
5435 : _IF_NOT_CHK(_OutIt) checked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5436 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5437 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
5438 : return _STD _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5439 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5440 : _Dest, _STD _Range_checked_iterator_tag());
5441 : }
5442 :
5443 : template<class _InIt1,
5444 : class _InIt2,
5445 : class _OutIt,
5446 : class _Pr> inline
5447 : _OutIt unchecked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5448 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5449 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5450 : return _STD _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest, _Pred,
5451 : _STD _Range_checked_iterator_tag());
5452 : }
5453 :
5454 : template<class _InIt1,
5455 : class _InIt2,
5456 : class _OutIt,
5457 : class _Pr> inline
5458 : _IF_CHK(_OutIt) checked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5459 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5460 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5461 : return _STD _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5462 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5463 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5464 : }
5465 :
5466 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
5467 : inline
5468 : _OutElem* checked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5469 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
5470 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5471 : return (checked_set_intersection(_First1, _Last1, _First2, _Last2,
5472 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
5473 : }
5474 :
5475 : template<class _InIt1,
5476 : class _InIt2,
5477 : class _OutIt,
5478 : class _Pr> inline
5479 : _SCL_CHECKED_ALGORITHM_WARN
5480 : _IF_NOT_CHK(_OutIt) checked_set_intersection(_InIt1 _First1, _InIt1 _Last1,
5481 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5482 : { // AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5483 : return _STD _Set_intersection(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5484 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5485 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5486 : }
5487 :
5488 : template<class _InIt1,
5489 : class _InIt2,
5490 : class _OutIt> inline
5491 : _OutIt unchecked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5492 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5493 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
5494 : return _STD _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
5495 : _STD _Range_checked_iterator_tag());
5496 : }
5497 :
5498 : template<class _InIt1,
5499 : class _InIt2,
5500 : class _OutIt> inline
5501 : _IF_CHK(_OutIt) checked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5502 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5503 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
5504 : return _STD _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5505 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5506 : _Dest, _STD _Range_checked_iterator_tag());
5507 : }
5508 :
5509 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
5510 : inline
5511 : _OutElem* checked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5512 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
5513 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
5514 : return (checked_set_difference(_First1, _Last1, _First2, _Last2,
5515 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
5516 : }
5517 :
5518 : template<class _InIt1,
5519 : class _InIt2,
5520 : class _OutIt> inline
5521 : _SCL_CHECKED_ALGORITHM_WARN
5522 : _IF_NOT_CHK(_OutIt) checked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5523 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5524 : { // take set [_First2, _Last2) from [_First1, _Last1), using operator<
5525 : return _STD _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5526 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5527 : _Dest, _STD _Range_checked_iterator_tag());
5528 : }
5529 :
5530 : template<class _InIt1,
5531 : class _InIt2,
5532 : class _OutIt,
5533 : class _Pr> inline
5534 : _OutIt unchecked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5535 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5536 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
5537 : return _STD _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest, _Pred,
5538 : _STD _Range_checked_iterator_tag());
5539 : }
5540 :
5541 : template<class _InIt1,
5542 : class _InIt2,
5543 : class _OutIt,
5544 : class _Pr> inline
5545 : _IF_CHK(_OutIt) checked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5546 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5547 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
5548 : return _STD _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5549 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5550 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5551 : }
5552 :
5553 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
5554 : inline
5555 : _OutElem* checked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5556 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
5557 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
5558 : return (checked_set_difference(_First1, _Last1, _First2, _Last2,
5559 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
5560 : }
5561 :
5562 : template<class _InIt1,
5563 : class _InIt2,
5564 : class _OutIt,
5565 : class _Pr> inline
5566 : _SCL_CHECKED_ALGORITHM_WARN
5567 : _IF_NOT_CHK(_OutIt) checked_set_difference(_InIt1 _First1, _InIt1 _Last1,
5568 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5569 : { // take set [_First2, _Last2) from [_First1, _Last1), using _Pred
5570 : return _STD _Set_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5571 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5572 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5573 : }
5574 :
5575 : template<class _InIt1,
5576 : class _InIt2,
5577 : class _OutIt> inline
5578 : _OutIt unchecked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5579 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5580 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5581 : return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest,
5582 : _STD _Range_checked_iterator_tag());
5583 : }
5584 :
5585 : template<class _InIt1,
5586 : class _InIt2,
5587 : class _OutIt> inline
5588 : _IF_CHK(_OutIt) checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5589 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5590 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5591 : return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5592 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5593 : _Dest, _STD _Range_checked_iterator_tag());
5594 : }
5595 :
5596 : template<class _InIt1, class _InIt2, class _OutElem, size_t _Size>
5597 : inline
5598 : _OutElem* checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5599 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size])
5600 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5601 : return (checked_set_symmetric_difference(_First1, _Last1, _First2, _Last2,
5602 : _STDEXT make_checked_array_iterator(_Dest, _Size)).base());
5603 : }
5604 :
5605 : template<class _InIt1,
5606 : class _InIt2,
5607 : class _OutIt> inline
5608 : _SCL_CHECKED_ALGORITHM_WARN
5609 : _IF_NOT_CHK(_OutIt) checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5610 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
5611 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
5612 : return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5613 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5614 : _Dest, _STD _Range_checked_iterator_tag());
5615 : }
5616 :
5617 : template<class _InIt1,
5618 : class _InIt2,
5619 : class _OutIt,
5620 : class _Pr> inline
5621 : _OutIt unchecked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5622 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5623 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5624 : return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1), _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Dest, _Pred,
5625 : _STD _Range_checked_iterator_tag());
5626 : }
5627 :
5628 : template<class _InIt1,
5629 : class _InIt2,
5630 : class _OutIt,
5631 : class _Pr> inline
5632 : _IF_CHK(_OutIt) checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5633 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5634 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5635 : return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5636 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5637 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5638 : }
5639 :
5640 : template<class _InIt1, class _InIt2, class _OutElem, class _Pr, size_t _Size>
5641 : inline
5642 : _OutElem* checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5643 : _InIt2 _First2, _InIt2 _Last2, _OutElem (&_Dest)[_Size], _Pr _Pred)
5644 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5645 : return (checked_set_symmetric_difference(_First1, _Last1, _First2, _Last2,
5646 : _STDEXT make_checked_array_iterator(_Dest, _Size), _Pred).base());
5647 : }
5648 :
5649 : template<class _InIt1,
5650 : class _InIt2,
5651 : class _OutIt,
5652 : class _Pr> inline
5653 : _SCL_CHECKED_ALGORITHM_WARN
5654 : _IF_NOT_CHK(_OutIt) checked_set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
5655 : _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
5656 : { // XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
5657 : return _STD _Set_symmetric_difference(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
5658 : _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
5659 : _Dest, _Pred, _STD _Range_checked_iterator_tag());
5660 : }
5661 :
5662 : #if _HAS_TRADITIONAL_STL
5663 : // TEMPLATE FUNCTION count
5664 : template<class _InIt,
5665 : class _Ty,
5666 : class _Diff> inline
5667 : void count(_InIt _First, _InIt _Last, const _Ty& _Val, _Diff &_Ans)
5668 : { // count elements that match _Val
5669 : _DEBUG_RANGE(_First, _Last);
5670 : _Diff _Count = 0;
5671 :
5672 : for (; _First != _Last; ++_First)
5673 : if (*_First == _Val)
5674 : ++_Count;
5675 : _Ans = _Count;
5676 : }
5677 :
5678 : // TEMPLATE FUNCTION count_if
5679 : template<class _InIt,
5680 : class _Pr,
5681 : class _Diff> inline
5682 : void count_if(_InIt _First, _InIt _Last, _Pr _Pred, _Diff &_Ans)
5683 : { // count elements satisfying _Pred
5684 : _DEBUG_RANGE(_First, _Last);
5685 : _DEBUG_POINTER(_Pred);
5686 : _Diff _Count = 0;
5687 :
5688 : for (; _First != _Last; ++_First)
5689 : if (_Pred(*_First))
5690 : ++_Count;
5691 : _Ans = _Count;
5692 : }
5693 :
5694 : // TEMPLATE FUNCTION is_heap
5695 : template<class _RanIt,
5696 : class _Diff> inline
5697 : bool _Is_heap(_RanIt _First, _RanIt _Last, _Diff *)
5698 : { // test if range is a heap ordered by operator<
5699 : _DEBUG_RANGE(_First, _Last);
5700 : _Diff _Size = _Last - _First;
5701 :
5702 : if (2 <= _Size)
5703 : for (_Diff _Off = 0; ++_Off < _Size; )
5704 : if (_DEBUG_LT(*(_First + (_Off - 1) / 2), *(_First + _Off)))
5705 : return (false);
5706 : return (true);
5707 : }
5708 :
5709 : template<class _RanIt>
5710 : bool is_heap(_RanIt _First, _RanIt _Last)
5711 : { // test if range is a heap ordered by operator<
5712 : return (_Is_heap(_First, _Last, _Dist_type(_First)));
5713 : }
5714 :
5715 : // TEMPLATE FUNCTION is_heap WITH PRED
5716 : template<class _RanIt,
5717 : class _Diff,
5718 : class _Pr> inline
5719 : bool _Is_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *)
5720 : { // test if range is a heap ordered by _Pred
5721 : _DEBUG_RANGE(_First, _Last);
5722 : _DEBUG_POINTER(_Pred);
5723 : _Diff _Size = _Last - _First;
5724 :
5725 : if (2 <= _Size)
5726 : for (_Diff _Off = 0; ++_Off < _Size; )
5727 : if (_DEBUG_LT_PRED(_Pred, *(_First + (_Off - 1) / 2),
5728 : *(_First + _Off)))
5729 : return (false);
5730 : return (true);
5731 : }
5732 :
5733 : template<class _RanIt,
5734 : class _Pr>
5735 : bool is_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
5736 : { // test if range is a heap ordered by _Pred
5737 : return (_Is_heap(_First, _Last, _Pred, _Dist_type(_First)));
5738 : }
5739 :
5740 : // TEMPLATE FUNCTION is_sorted
5741 : template<class _FwdIt> inline
5742 : bool is_sorted(_FwdIt _First, _FwdIt _Last)
5743 : { // test is range is ordered by operator<
5744 : _DEBUG_RANGE(_First, _Last);
5745 : for (_FwdIt _Next = _First; _First != _Last && ++_Next != _Last; ++_First)
5746 : if (_DEBUG_LT(*_Next, *_First))
5747 : return (false);
5748 : return (true);
5749 : }
5750 :
5751 : // TEMPLATE FUNCTION is_sorted WITH PRED
5752 : template<class _FwdIt,
5753 : class _Pr> inline
5754 : bool is_sorted(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
5755 : { // test if range is ordered by predicate, forward iterators
5756 : _DEBUG_RANGE(_First, _Last);
5757 : _DEBUG_POINTER(_Pred);
5758 : for (_FwdIt _Next = _First; _First != _Last && ++_Next != _Last; ++_First)
5759 : if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
5760 : return (false);
5761 : return (true);
5762 : }
5763 : #endif /* _HAS_TRADITIONAL_STL */
5764 :
5765 : _STDEXT_END
5766 :
5767 : #pragma warning(default: 4244)
5768 :
5769 : #ifdef _MSC_VER
5770 : #pragma warning(pop)
5771 : #pragma pack(pop)
5772 : #endif /* _MSC_VER */
5773 :
5774 : #endif /* RC_INVOKED */
5775 : #endif /* _ALGORITHM_ */
5776 :
5777 : /*
5778 : * This file is derived from software bearing the following
5779 : * restrictions:
5780 : *
5781 : * Copyright (c) 1994
5782 : * Hewlett-Packard Company
5783 : *
5784 : * Permission to use, copy, modify, distribute and sell this
5785 : * software and its documentation for any purpose is hereby
5786 : * granted without fee, provided that the above copyright notice
5787 : * appear in all copies and that both that copyright notice and
5788 : * this permission notice appear in supporting documentation.
5789 : * Hewlett-Packard Company makes no representations about the
5790 : * suitability of this software for any purpose. It is provided
5791 : * "as is" without express or implied warranty.
5792 : */
5793 :
5794 : /*
5795 : * Copyright (c) 1992-2008 by P.J. Plauger. ALL RIGHTS RESERVED.
5796 : * Consult your license regarding permissions and restrictions.
5797 : V5.05:0009 */
5798 :
5799 :
|
