Lines Matching refs:__first
153 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
157 __glibcxx_requires_valid_range(__first, __last);
158 for ( ; __first != __last; ++__first)
159 __f(*__first);
170 __find(_InputIterator __first, _InputIterator __last,
173 while (__first != __last && !(*__first == __val))
174 ++__first;
175 return __first;
185 __find_if(_InputIterator __first, _InputIterator __last,
188 while (__first != __last && !__pred(*__first))
189 ++__first;
190 return __first;
200 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
204 __trip_count = (__last - __first) >> 2;
208 if (*__first == __val)
209 return __first;
210 ++__first;
212 if (*__first == __val)
213 return __first;
214 ++__first;
216 if (*__first == __val)
217 return __first;
218 ++__first;
220 if (*__first == __val)
221 return __first;
222 ++__first;
225 switch (__last - __first)
228 if (*__first == __val)
229 return __first;
230 ++__first;
232 if (*__first == __val)
233 return __first;
234 ++__first;
236 if (*__first == __val)
237 return __first;
238 ++__first;
252 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
256 __trip_count = (__last - __first) >> 2;
260 if (__pred(*__first))
261 return __first;
262 ++__first;
264 if (__pred(*__first))
265 return __first;
266 ++__first;
268 if (__pred(*__first))
269 return __first;
270 ++__first;
272 if (__pred(*__first))
273 return __first;
274 ++__first;
277 switch (__last - __first)
280 if (__pred(*__first))
281 return __first;
282 ++__first;
284 if (__pred(*__first))
285 return __first;
286 ++__first;
288 if (__pred(*__first))
289 return __first;
290 ++__first;
318 find(_InputIterator __first, _InputIterator __last,
325 __glibcxx_requires_valid_range(__first, __last);
326 return std::__find(__first, __last, __val,
327 std::__iterator_category(__first));
340 find_if(_InputIterator __first, _InputIterator __last,
347 __glibcxx_requires_valid_range(__first, __last);
348 return std::__find_if(__first, __last, __pred,
349 std::__iterator_category(__first));
362 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
368 __glibcxx_requires_valid_range(__first, __last);
369 if (__first == __last)
371 _ForwardIterator __next = __first;
374 if (*__first == *__next)
375 return __first;
376 __first = __next;
393 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
401 __glibcxx_requires_valid_range(__first, __last);
402 if (__first == __last)
404 _ForwardIterator __next = __first;
407 if (__binary_pred(*__first, *__next))
408 return __first;
409 __first = __next;
424 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
430 __glibcxx_requires_valid_range(__first, __last);
432 for ( ; __first != __last; ++__first)
433 if (*__first == __value)
448 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
454 __glibcxx_requires_valid_range(__first, __last);
456 for ( ; __first != __last; ++__first)
457 if (__pred(*__first))
630 __search_n(_ForwardIterator __first, _ForwardIterator __last,
634 __first = std::find(__first, __last, __val);
635 while (__first != __last)
639 _ForwardIterator __i = __first;
647 return __first;
650 __first = std::find(++__i, __last, __val);
664 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
672 _DistanceType __tailSize = __last - __first;
679 _RandomAccessIter __lookAhead = __first + __skipOffset;
722 search_n(_ForwardIterator __first, _ForwardIterator __last,
729 __glibcxx_requires_valid_range(__first, __last);
732 return __first;
734 return std::find(__first, __last, __val);
735 return std::__search_n(__first, __last, __count, __val,
736 std::__iterator_category(__first));
750 __search_n(_ForwardIterator __first, _ForwardIterator __last,
754 while (__first != __last && !__binary_pred(*__first, __val))
755 ++__first;
757 while (__first != __last)
761 _ForwardIterator __i = __first;
769 return __first;
772 __first = ++__i;
773 while (__first != __last && !__binary_pred(*__first, __val))
774 ++__first;
790 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
798 _DistanceType __tailSize = __last - __first;
805 _RandomAccessIter __lookAhead = __first + __skipOffset;
851 search_n(_ForwardIterator __first, _ForwardIterator __last,
859 __glibcxx_requires_valid_range(__first, __last);
862 return __first;
865 while (__first != __last && !__binary_pred(*__first, __val))
866 ++__first;
867 return __first;
869 return std::__search_n(__first, __last, __count, __val, __binary_pred,
870 std::__iterator_category(__first));
925 transform(_InputIterator __first, _InputIterator __last,
932 __typeof__(__unary_op(*__first))>)
933 __glibcxx_requires_valid_range(__first, __last);
935 for ( ; __first != __last; ++__first, ++__result)
936 *__result = __unary_op(*__first);
991 replace(_ForwardIterator __first, _ForwardIterator __last,
1001 __glibcxx_requires_valid_range(__first, __last);
1003 for ( ; __first != __last; ++__first)
1004 if (*__first == __old_value)
1005 *__first = __new_value;
1022 replace_if(_ForwardIterator __first, _ForwardIterator __last,
1032 __glibcxx_requires_valid_range(__first, __last);
1034 for ( ; __first != __last; ++__first)
1035 if (__pred(*__first))
1036 *__first = __new_value;
1055 replace_copy(_InputIterator __first, _InputIterator __last,
1065 __glibcxx_requires_valid_range(__first, __last);
1067 for ( ; __first != __last; ++__first, ++__result)
1068 if (*__first == __old_value)
1071 *__result = *__first;
1092 replace_copy_if(_InputIterator __first, _InputIterator __last,
1102 __glibcxx_requires_valid_range(__first, __last);
1104 for ( ; __first != __last; ++__first, ++__result)
1105 if (__pred(*__first))
1108 *__result = *__first;
1125 generate(_ForwardIterator __first, _ForwardIterator __last,
1132 __glibcxx_requires_valid_range(__first, __last);
1134 for ( ; __first != __last; ++__first)
1135 *__first = __gen();
1151 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
1158 for ( ; __n > 0; --__n, ++__first)
1159 *__first = __gen();
1160 return __first;
1178 remove_copy(_InputIterator __first, _InputIterator __last,
1187 __glibcxx_requires_valid_range(__first, __last);
1189 for ( ; __first != __last; ++__first)
1190 if (!(*__first == __value))
1192 *__result = *__first;
1215 remove_copy_if(_InputIterator __first, _InputIterator __last,
1224 __glibcxx_requires_valid_range(__first, __last);
1226 for ( ; __first != __last; ++__first)
1227 if (!__pred(*__first))
1229 *__result = *__first;
1253 remove(_ForwardIterator __first, _ForwardIterator __last,
1261 __glibcxx_requires_valid_range(__first, __last);
1263 __first = std::find(__first, __last, __value);
1264 _ForwardIterator __i = __first;
1265 return __first == __last ? __first
1267 __first, __value);
1288 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1296 __glibcxx_requires_valid_range(__first, __last);
1298 __first = std::find_if(__first, __last, __pred);
1299 _ForwardIterator __i = __first;
1300 return __first == __last ? __first
1302 __first, __pred);
1314 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1319 _ForwardIterator __next = __first;
1320 *__result = *__first;
1322 if (!(*__first == *__next))
1324 __first = __next;
1325 *++__result = *__first;
1339 __unique_copy(_InputIterator __first, _InputIterator __last,
1344 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1346 while (++__first != __last)
1347 if (!(__value == *__first))
1349 __value = *__first;
1364 __unique_copy(_InputIterator __first, _InputIterator __last,
1369 *__result = *__first;
1370 while (++__first != __last)
1371 if (!(*__result == *__first))
1372 *++__result = *__first;
1387 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1396 _ForwardIterator __next = __first;
1397 *__result = *__first;
1399 if (!__binary_pred(*__first, *__next))
1401 __first = __next;
1402 *++__result = *__first;
1418 __unique_copy(_InputIterator __first, _InputIterator __last,
1427 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1429 while (++__first != __last)
1430 if (!__binary_pred(__value, *__first))
1432 __value = *__first;
1449 __unique_copy(_InputIterator __first, _InputIterator __last,
1458 *__result = *__first;
1459 while (++__first != __last)
1460 if (!__binary_pred(*__result, *__first))
1461 *++__result = *__first;
1489 unique_copy(_InputIterator __first, _InputIterator __last,
1498 __glibcxx_requires_valid_range(__first, __last);
1500 if (__first == __last)
1502 return std::__unique_copy(__first, __last, __result,
1503 std::__iterator_category(__first),
1530 unique_copy(_InputIterator __first, _InputIterator __last,
1538 __glibcxx_requires_valid_range(__first, __last);
1540 if (__first == __last)
1542 return std::__unique_copy(__first, __last, __result, __binary_pred,
1543 std::__iterator_category(__first),
1562 unique(_ForwardIterator __first, _ForwardIterator __last)
1569 __glibcxx_requires_valid_range(__first, __last);
1572 __first = std::adjacent_find(__first, __last);
1573 if (__first == __last)
1577 _ForwardIterator __dest = __first;
1578 ++__first;
1579 while (++__first != __last)
1580 if (!(*__dest == *__first))
1581 *++__dest = *__first;
1601 unique(_ForwardIterator __first, _ForwardIterator __last,
1610 __glibcxx_requires_valid_range(__first, __last);
1613 __first = std::adjacent_find(__first, __last, __binary_pred);
1614 if (__first == __last)
1618 _ForwardIterator __dest = __first;
1619 ++__first;
1620 while (++__first != __last)
1621 if (!__binary_pred(*__dest, *__first))
1622 *++__dest = *__first;
1635 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1639 if (__first == __last || __first == --__last)
1643 std::iter_swap(__first, __last);
1644 ++__first;
1657 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1660 if (__first == __last)
1663 while (__first < __last)
1665 std::iter_swap(__first, __last);
1666 ++__first;
1684 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1689 __glibcxx_requires_valid_range(__first, __last);
1690 std::__reverse(__first, __last, std::__iterator_category(__first));
1710 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1718 __glibcxx_requires_valid_range(__first, __last);
1720 while (__first != __last)
1756 __rotate(_ForwardIterator __first,
1761 if (__first == __middle || __last == __middle)
1767 swap(*__first, *__first2);
1768 ++__first;
1770 if (__first == __middle)
1779 swap(*__first, *__first2);
1780 ++__first;
1782 if (__first == __middle)
1796 __rotate(_BidirectionalIterator __first,
1805 if (__first == __middle || __last == __middle)
1808 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1811 while (__first != __middle && __middle != __last)
1813 swap(*__first, *--__last);
1814 ++__first;
1817 if (__first == __middle)
1820 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1830 __rotate(_RandomAccessIterator __first,
1839 if (__first == __middle || __last == __middle)
1847 const _Distance __n = __last - __first;
1848 const _Distance __k = __middle - __first;
1853 std::swap_ranges(__first, __middle, __middle);
1861 _ValueType __tmp = *__first;
1862 _RandomAccessIterator __p = __first;
1868 if (__p > __first + __l)
1893 ++__first;
1917 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1923 __glibcxx_requires_valid_range(__first, __middle);
1928 std::__rotate(__first, __middle, __last, _IterType());
1950 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1957 __glibcxx_requires_valid_range(__first, __middle);
1960 return std::copy(__first, __middle,
1976 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
1981 __glibcxx_requires_valid_range(__first, __last);
1983 if (__first != __last)
1984 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1985 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
2003 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2009 __glibcxx_requires_valid_range(__first, __last);
2011 if (__first == __last)
2013 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2014 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
2025 __partition(_ForwardIterator __first, _ForwardIterator __last,
2029 if (__first == __last)
2030 return __first;
2032 while (__pred(*__first))
2033 if (++__first == __last)
2034 return __first;
2036 _ForwardIterator __next = __first;
2041 swap(*__first, *__next);
2042 ++__first;
2045 return __first;
2055 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
2062 if (__first == __last)
2063 return __first;
2064 else if (__pred(*__first))
2065 ++__first;
2070 if (__first == __last)
2071 return __first;
2076 std::iter_swap(__first, __last);
2077 ++__first;
2097 partition(_ForwardIterator __first, _ForwardIterator __last,
2105 __glibcxx_requires_valid_range(__first, __last);
2107 return std::__partition(__first, __last, __pred,
2108 std::__iterator_category(__first));
2119 __inplace_stable_partition(_ForwardIterator __first,
2124 return __pred(*__first) ? __last : __first;
2125 _ForwardIterator __middle = __first;
2127 _ForwardIterator __begin = std::__inplace_stable_partition(__first,
2148 __stable_partition_adaptive(_ForwardIterator __first,
2156 _ForwardIterator __result1 = __first;
2158 for ( ; __first != __last ; ++__first)
2159 if (__pred(*__first))
2161 *__result1 = *__first;
2166 *__result2 = *__first;
2174 _ForwardIterator __middle = __first;
2177 std::__stable_partition_adaptive(__first, __middle, __pred,
2208 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
2216 __glibcxx_requires_valid_range(__first, __last);
2218 if (__first == __last)
2219 return __first;
2227 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
2231 std::__stable_partition_adaptive(__first, __last, __pred,
2236 std::__inplace_stable_partition(__first, __last, __pred,
2248 __unguarded_partition(_RandomAccessIterator __first,
2253 while (*__first < __pivot)
2254 ++__first;
2258 if (!(__first < __last))
2259 return __first;
2260 std::iter_swap(__first, __last);
2261 ++__first;
2272 __unguarded_partition(_RandomAccessIterator __first,
2278 while (__comp(*__first, __pivot))
2279 ++__first;
2283 if (!(__first < __last))
2284 return __first;
2285 std::iter_swap(__first, __last);
2286 ++__first;
2346 __insertion_sort(_RandomAccessIterator __first,
2349 if (__first == __last)
2352 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2356 if (__val < *__first)
2358 std::copy_backward(__first, __i, __i + 1);
2359 *__first = __val;
2373 __insertion_sort(_RandomAccessIterator __first,
2376 if (__first == __last) return;
2378 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2382 if (__comp(__val, *__first))
2384 std::copy_backward(__first, __i, __i + 1);
2385 *__first = __val;
2399 __unguarded_insertion_sort(_RandomAccessIterator __first,
2405 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2416 __unguarded_insertion_sort(_RandomAccessIterator __first,
2422 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2433 __final_insertion_sort(_RandomAccessIterator __first,
2436 if (__last - __first > int(_S_threshold))
2438 std::__insertion_sort(__first, __first + int(_S_threshold));
2439 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2442 std::__insertion_sort(__first, __last);
2452 __final_insertion_sort(_RandomAccessIterator __first,
2455 if (__last - __first > int(_S_threshold))
2457 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2458 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2462 std::__insertion_sort(__first, __last, __comp);
2472 __heap_select(_RandomAccessIterator __first,
2479 std::make_heap(__first, __middle);
2481 if (*__i < *__first)
2482 std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
2492 __heap_select(_RandomAccessIterator __first,
2499 std::make_heap(__first, __middle, __comp);
2501 if (__comp(*__i, *__first))
2502 std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
2537 partial_sort(_RandomAccessIterator __first,
2548 __glibcxx_requires_valid_range(__first, __middle);
2551 std::__heap_select(__first, __middle, __last);
2552 std::sort_heap(__first, __middle);
2575 partial_sort(_RandomAccessIterator __first,
2588 __glibcxx_requires_valid_range(__first, __middle);
2591 std::__heap_select(__first, __middle, __last, __comp);
2592 std::sort_heap(__first, __middle, __comp);
2614 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2632 __glibcxx_requires_valid_range(__first, __last);
2638 while(__first != __last && __result_real_last != __result_last)
2640 *__result_real_last = *__first;
2642 ++__first;
2645 while (__first != __last)
2647 if (*__first < *__result_first)
2651 _InputValueType(*__first));
2652 ++__first;
2679 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2701 __glibcxx_requires_valid_range(__first, __last);
2707 while(__first != __last && __result_real_last != __result_last)
2709 *__result_real_last = *__first;
2711 ++__first;
2714 while (__first != __last)
2716 if (__comp(*__first, *__result_first))
2720 _InputValueType(*__first),
2722 ++__first;
2735 __introsort_loop(_RandomAccessIterator __first,
2742 while (__last - __first > int(_S_threshold))
2746 std::partial_sort(__first, __last, __last);
2751 std::__unguarded_partition(__first, __last,
2752 _ValueType(std::__median(*__first,
2753 *(__first
2755 - __first)
2771 __introsort_loop(_RandomAccessIterator __first,
2778 while (__last - __first > int(_S_threshold))
2782 std::partial_sort(__first, __last, __last, __comp);
2787 std::__unguarded_partition(__first, __last,
2788 _ValueType(std::__median(*__first,
2789 *(__first
2791 - __first)
2816 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
2825 __glibcxx_requires_valid_range(__first, __last);
2827 if (__first != __last)
2829 std::__introsort_loop(__first, __last,
2830 std::__lg(__last - __first) * 2);
2831 std::__final_insertion_sort(__first, __last);
2851 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2862 __glibcxx_requires_valid_range(__first, __last);
2864 if (__first != __last)
2866 std::__introsort_loop(__first, __last,
2867 std::__lg(__last - __first) * 2, __comp);
2868 std::__final_insertion_sort(__first, __last, __comp);
2884 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2895 __glibcxx_requires_partitioned(__first, __last, __val);
2897 _DistanceType __len = std::distance(__first, __last);
2904 __middle = __first;
2908 __first = __middle;
2909 ++__first;
2915 return __first;
2934 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2946 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
2948 _DistanceType __len = std::distance(__first, __last);
2955 __middle = __first;
2959 __first = __middle;
2960 ++__first;
2966 return __first;
2981 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2992 __glibcxx_requires_partitioned(__first, __last, __val);
2994 _DistanceType __len = std::distance(__first, __last);
3001 __middle = __first;
3007 __first = __middle;
3008 ++__first;
3012 return __first;
3031 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
3043 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
3045 _DistanceType __len = std::distance(__first, __last);
3052 __middle = __first;
3058 __first = __middle;
3059 ++__first;
3063 return __first;
3073 __merge_without_buffer(_BidirectionalIterator __first,
3082 if (*__middle < *__first)
3083 std::iter_swap(__first, __middle);
3086 _BidirectionalIterator __first_cut = __first;
3101 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3102 __len11 = std::distance(__first, __first_cut);
3107 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3121 __merge_without_buffer(_BidirectionalIterator __first,
3131 if (__comp(*__middle, *__first))
3132 std::iter_swap(__first, __middle);
3135 _BidirectionalIterator __first_cut = __first;
3151 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3153 __len11 = std::distance(__first, __first_cut);
3158 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3171 __inplace_stable_sort(_RandomAccessIterator __first,
3174 if (__last - __first < 15)
3176 std::__insertion_sort(__first, __last);
3179 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3180 std::__inplace_stable_sort(__first, __middle);
3182 std::__merge_without_buffer(__first, __middle, __last,
3183 __middle - __first,
3194 __inplace_stable_sort(_RandomAccessIterator __first,
3197 if (__last - __first < 15)
3199 std::__insertion_sort(__first, __last, __comp);
3202 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3203 std::__inplace_stable_sort(__first, __middle, __comp);
3205 std::__merge_without_buffer(__first, __middle, __last,
3206 __middle - __first,
3333 __merge_sort_loop(_RandomAccessIterator1 __first,
3340 while (__last - __first >= __two_step)
3342 __result = std::merge(__first, __first + __step_size,
3343 __first + __step_size, __first + __two_step,
3345 __first += __two_step;
3348 __step_size = std::min(_Distance(__last - __first), __step_size);
3349 std::merge(__first, __first + __step_size, __first + __step_size, __last,
3356 __merge_sort_loop(_RandomAccessIterator1 __first,
3363 while (__last - __first >= __two_step)
3365 __result = std::merge(__first, __first + __step_size,
3366 __first + __step_size, __first + __two_step,
3369 __first += __two_step;
3371 __step_size = std::min(_Distance(__last - __first), __step_size);
3373 std::merge(__first, __first + __step_size,
3374 __first + __step_size, __last,
3383 __chunk_insertion_sort(_RandomAccessIterator __first,
3387 while (__last - __first >= __chunk_size)
3389 std::__insertion_sort(__first, __first + __chunk_size);
3390 __first += __chunk_size;
3392 std::__insertion_sort(__first, __last);
3397 __chunk_insertion_sort(_RandomAccessIterator __first,
3401 while (__last - __first >= __chunk_size)
3403 std::__insertion_sort(__first, __first + __chunk_size, __comp);
3404 __first += __chunk_size;
3406 std::__insertion_sort(__first, __last, __comp);
3411 __merge_sort_with_buffer(_RandomAccessIterator __first,
3418 const _Distance __len = __last - __first;
3422 std::__chunk_insertion_sort(__first, __last, __step_size);
3426 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3428 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3435 __merge_sort_with_buffer(_RandomAccessIterator __first,
3442 const _Distance __len = __last - __first;
3446 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3450 std::__merge_sort_loop(__first, __last, __buffer,
3453 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3546 __rotate_adaptive(_BidirectionalIterator1 __first,
3557 std::copy_backward(__first, __middle, __last);
3558 return std::copy(__buffer, __buffer_end, __first);
3562 __buffer_end = std::copy(__first, __middle, __buffer);
3563 std::copy(__middle, __last, __first);
3568 std::rotate(__first, __middle, __last);
3569 std::advance(__first, std::distance(__middle, __last));
3570 return __first;
3582 __merge_adaptive(_BidirectionalIterator __first,
3590 _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
3591 std::merge(__buffer, __buffer_end, __middle, __last, __first);
3596 std::__merge_backward(__first, __middle, __buffer,
3601 _BidirectionalIterator __first_cut = __first;
3617 __first_cut = std::upper_bound(__first, __middle,
3619 __len11 = std::distance(__first, __first_cut);
3625 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3641 __merge_adaptive(_BidirectionalIterator __first,
3650 _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
3651 std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
3656 std::__merge_backward(__first, __middle, __buffer, __buffer_end,
3661 _BidirectionalIterator __first_cut = __first;
3677 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3679 __len11 = std::distance(__first, __first_cut);
3685 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3713 inplace_merge(_BidirectionalIterator __first,
3726 __glibcxx_requires_sorted(__first, __middle);
3729 if (__first == __middle || __middle == __last)
3732 _DistanceType __len1 = std::distance(__first, __middle);
3735 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3738 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3740 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3767 inplace_merge(_BidirectionalIterator __first,
3782 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3785 if (__first == __middle || __middle == __last)
3788 const _DistanceType __len1 = std::distance(__first, __middle);
3791 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3794 std::__merge_without_buffer(__first, __middle, __last, __len1,
3797 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3805 __stable_sort_adaptive(_RandomAccessIterator __first,
3809 const _Distance __len = (__last - __first + 1) / 2;
3810 const _RandomAccessIterator __middle = __first + __len;
3813 std::__stable_sort_adaptive(__first, __middle,
3820 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3823 std::__merge_adaptive(__first, __middle, __last,
3824 _Distance(__middle - __first),
3832 __stable_sort_adaptive(_RandomAccessIterator __first,
3837 const _Distance __len = (__last - __first + 1) / 2;
3838 const _RandomAccessIterator __middle = __first + __len;
3841 std::__stable_sort_adaptive(__first, __middle, __buffer,
3848 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3851 std::__merge_adaptive(__first, __middle, __last,
3852 _Distance(__middle - __first),
3876 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3887 __glibcxx_requires_valid_range(__first, __last);
3889 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
3892 std::__inplace_stable_sort(__first, __last);
3894 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
3917 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
3931 __glibcxx_requires_valid_range(__first, __last);
3933 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
3936 std::__inplace_stable_sort(__first, __last, __comp);
3938 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
3945 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
3951 while (__last - __first > 3)
3955 std::__heap_select(__first, __nth + 1, __last);
3957 std::iter_swap(__first, __nth);
3962 std::__unguarded_partition(__first, __last,
3963 _ValueType(std::__median(*__first,
3964 *(__first
3966 - __first)
3971 __first = __cut;
3975 std::__insertion_sort(__first, __last);
3980 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
3987 while (__last - __first > 3)
3991 std::__heap_select(__first, __nth + 1, __last, __comp);
3993 std::iter_swap(__first, __nth);
3998 std::__unguarded_partition(__first, __last,
3999 _ValueType(std::__median(*__first,
4000 *(__first
4002 - __first)
4008 __first = __cut;
4012 std::__insertion_sort(__first, __last, __comp);
4032 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4042 __glibcxx_requires_valid_range(__first, __nth);
4045 if (__first == __last || __nth == __last)
4048 std::__introselect(__first, __nth, __last,
4049 std::__lg(__last - __first) * 2);
4070 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4081 __glibcxx_requires_valid_range(__first, __nth);
4084 if (__first == __last || __nth == __last)
4087 std::__introselect(__first, __nth, __last,
4088 std::__lg(__last - __first) * 2, __comp);
4109 equal_range(_ForwardIterator __first, _ForwardIterator __last,
4121 __glibcxx_requires_partitioned(__first, __last, __val);
4123 _DistanceType __len = std::distance(__first, __last);
4130 __middle = __first;
4134 __first = __middle;
4135 ++__first;
4142 __left = std::lower_bound(__first, __middle, __val);
4143 std::advance(__first, __len);
4144 __right = std::upper_bound(++__middle, __first, __val);
4148 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4170 equal_range(_ForwardIterator __first, _ForwardIterator __last,
4185 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
4187 _DistanceType __len = std::distance(__first, __last);
4194 __middle = __first;
4198 __first = __middle;
4199 ++__first;
4206 __left = std::lower_bound(__first, __middle, __val, __comp);
4207 std::advance(__first, __len);
4208 __right = std::upper_bound(++__middle, __first, __val, __comp);
4212 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4228 binary_search(_ForwardIterator __first, _ForwardIterator __last,
4237 __glibcxx_requires_partitioned(__first, __last, __val);
4239 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
4260 binary_search(_ForwardIterator __first, _ForwardIterator __last,
4270 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
4272 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
4881 max_element(_ForwardIterator __first, _ForwardIterator __last)
4887 __glibcxx_requires_valid_range(__first, __last);
4889 if (__first == __last)
4890 return __first;
4891 _ForwardIterator __result = __first;
4892 while (++__first != __last)
4893 if (*__result < *__first)
4894 __result = __first;
4908 max_element(_ForwardIterator __first, _ForwardIterator __last,
4916 __glibcxx_requires_valid_range(__first, __last);
4918 if (__first == __last) return __first;
4919 _ForwardIterator __result = __first;
4920 while (++__first != __last)
4921 if (__comp(*__result, *__first)) __result = __first;
4933 min_element(_ForwardIterator __first, _ForwardIterator __last)
4939 __glibcxx_requires_valid_range(__first, __last);
4941 if (__first == __last)
4942 return __first;
4943 _ForwardIterator __result = __first;
4944 while (++__first != __last)
4945 if (*__first < *__result)
4946 __result = __first;
4960 min_element(_ForwardIterator __first, _ForwardIterator __last,
4968 __glibcxx_requires_valid_range(__first, __last);
4970 if (__first == __last)
4971 return __first;
4972 _ForwardIterator __result = __first;
4973 while (++__first != __last)
4974 if (__comp(*__first, *__result))
4975 __result = __first;
4995 next_permutation(_BidirectionalIterator __first,
5003 __glibcxx_requires_valid_range(__first, __last);
5005 if (__first == __last)
5007 _BidirectionalIterator __i = __first;
5027 if (__i == __first)
5029 std::reverse(__first, __last);
5051 next_permutation(_BidirectionalIterator __first,
5060 __glibcxx_requires_valid_range(__first, __last);
5062 if (__first == __last)
5064 _BidirectionalIterator __i = __first;
5084 if (__i == __first)
5086 std::reverse(__first, __last);
5106 prev_permutation(_BidirectionalIterator __first,
5114 __glibcxx_requires_valid_range(__first, __last);
5116 if (__first == __last)
5118 _BidirectionalIterator __i = __first;
5138 if (__i == __first)
5140 std::reverse(__first, __last);
5162 prev_permutation(_BidirectionalIterator __first,
5171 __glibcxx_requires_valid_range(__first, __last);
5173 if (__first == __last)
5175 _BidirectionalIterator __i = __first;
5195 if (__i == __first)
5197 std::reverse(__first, __last);