Lines Matching refs:__first
128 __find(_InputIterator __first, _InputIterator __last,
131 while (__first != __last && !(*__first == __val))
132 ++__first;
133 return __first;
139 __find_if(_InputIterator __first, _InputIterator __last,
142 while (__first != __last && !bool(__pred(*__first)))
143 ++__first;
144 return __first;
150 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
154 __trip_count = (__last - __first) >> 2;
158 if (*__first == __val)
159 return __first;
160 ++__first;
162 if (*__first == __val)
163 return __first;
164 ++__first;
166 if (*__first == __val)
167 return __first;
168 ++__first;
170 if (*__first == __val)
171 return __first;
172 ++__first;
175 switch (__last - __first)
178 if (*__first == __val)
179 return __first;
180 ++__first;
182 if (*__first == __val)
183 return __first;
184 ++__first;
186 if (*__first == __val)
187 return __first;
188 ++__first;
198 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
202 __trip_count = (__last - __first) >> 2;
206 if (__pred(*__first))
207 return __first;
208 ++__first;
210 if (__pred(*__first))
211 return __first;
212 ++__first;
214 if (__pred(*__first))
215 return __first;
216 ++__first;
218 if (__pred(*__first))
219 return __first;
220 ++__first;
223 switch (__last - __first)
226 if (__pred(*__first))
227 return __first;
228 ++__first;
230 if (__pred(*__first))
231 return __first;
232 ++__first;
234 if (__pred(*__first))
235 return __first;
236 ++__first;
247 __find_if_not(_InputIterator __first, _InputIterator __last,
250 while (__first != __last && bool(__pred(*__first)))
251 ++__first;
252 return __first;
258 __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
262 __trip_count = (__last - __first) >> 2;
266 if (!bool(__pred(*__first)))
267 return __first;
268 ++__first;
270 if (!bool(__pred(*__first)))
271 return __first;
272 ++__first;
274 if (!bool(__pred(*__first)))
275 return __first;
276 ++__first;
278 if (!bool(__pred(*__first)))
279 return __first;
280 ++__first;
283 switch (__last - __first)
286 if (!bool(__pred(*__first)))
287 return __first;
288 ++__first;
290 if (!bool(__pred(*__first)))
291 return __first;
292 ++__first;
294 if (!bool(__pred(*__first)))
295 return __first;
296 ++__first;
324 __search_n(_ForwardIterator __first, _ForwardIterator __last,
328 __first = _GLIBCXX_STD_P::find(__first, __last, __val);
329 while (__first != __last)
333 _ForwardIterator __i = __first;
341 return __first;
344 __first = _GLIBCXX_STD_P::find(++__i, __last, __val);
356 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
364 _DistanceType __tailSize = __last - __first;
371 _RandomAccessIter __lookAhead = __first + __skipOffset;
410 __search_n(_ForwardIterator __first, _ForwardIterator __last,
414 while (__first != __last && !bool(__binary_pred(*__first, __val)))
415 ++__first;
417 while (__first != __last)
421 _ForwardIterator __i = __first;
429 return __first;
432 __first = ++__i;
433 while (__first != __last
434 && !bool(__binary_pred(*__first, __val)))
435 ++__first;
449 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
457 _DistanceType __tailSize = __last - __first;
464 _RandomAccessIter __lookAhead = __first + __skipOffset;
728 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
729 { return __last == std::find_if_not(__first, __last, __pred); }
745 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
746 { return __last == _GLIBCXX_STD_P::find_if(__first, __last, __pred); }
762 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
763 { return !std::none_of(__first, __last, __pred); }
777 find_if_not(_InputIterator __first, _InputIterator __last,
784 __glibcxx_requires_valid_range(__first, __last);
785 return std::__find_if_not(__first, __last, __pred,
786 std::__iterator_category(__first));
801 is_partitioned(_InputIterator __first, _InputIterator __last,
804 __first = std::find_if_not(__first, __last, __pred);
805 return std::none_of(__first, __last, __pred);
819 partition_point(_ForwardIterator __first, _ForwardIterator __last,
828 __glibcxx_requires_valid_range(__first, __last);
833 _DistanceType __len = std::distance(__first, __last);
840 __middle = __first;
844 __first = __middle;
845 ++__first;
851 return __first;
872 remove_copy(_InputIterator __first, _InputIterator __last,
881 __glibcxx_requires_valid_range(__first, __last);
883 for (; __first != __last; ++__first)
884 if (!(*__first == __value))
886 *__result = *__first;
910 remove_copy_if(_InputIterator __first, _InputIterator __last,
919 __glibcxx_requires_valid_range(__first, __last);
921 for (; __first != __last; ++__first)
922 if (!bool(__pred(*__first)))
924 *__result = *__first;
949 copy_if(_InputIterator __first, _InputIterator __last,
958 __glibcxx_requires_valid_range(__first, __last);
960 for (; __first != __last; ++__first)
961 if (__pred(*__first))
963 *__result = *__first;
972 __copy_n(_InputIterator __first, _Size __n,
977 *__result = *__first;
978 ++__first;
987 __copy_n(_RandomAccessIterator __first, _Size __n,
989 { return std::copy(__first, __first + __n, __result); }
1006 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1013 return std::__copy_n(__first, __n, __result,
1014 std::__iterator_category(__first));
1035 partition_copy(_InputIterator __first, _InputIterator __last,
1047 __glibcxx_requires_valid_range(__first, __last);
1049 for (; __first != __last; ++__first)
1050 if (__pred(*__first))
1052 *__out_true = *__first;
1057 *__out_false = *__first;
1084 remove(_ForwardIterator __first, _ForwardIterator __last,
1092 __glibcxx_requires_valid_range(__first, __last);
1094 __first = _GLIBCXX_STD_P::find(__first, __last, __value);
1095 if(__first == __last)
1096 return __first;
1097 _ForwardIterator __result = __first;
1098 ++__first;
1099 for(; __first != __last; ++__first)
1100 if(!(*__first == __value))
1102 *__result = _GLIBCXX_MOVE(*__first);
1127 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1135 __glibcxx_requires_valid_range(__first, __last);
1137 __first = _GLIBCXX_STD_P::find_if(__first, __last, __pred);
1138 if(__first == __last)
1139 return __first;
1140 _ForwardIterator __result = __first;
1141 ++__first;
1142 for(; __first != __last; ++__first)
1143 if(!bool(__pred(*__first)))
1145 *__result = _GLIBCXX_MOVE(*__first);
1167 unique(_ForwardIterator __first, _ForwardIterator __last)
1174 __glibcxx_requires_valid_range(__first, __last);
1177 __first = _GLIBCXX_STD_P::adjacent_find(__first, __last);
1178 if (__first == __last)
1182 _ForwardIterator __dest = __first;
1183 ++__first;
1184 while (++__first != __last)
1185 if (!(*__dest == *__first))
1186 *++__dest = _GLIBCXX_MOVE(*__first);
1207 unique(_ForwardIterator __first, _ForwardIterator __last,
1216 __glibcxx_requires_valid_range(__first, __last);
1219 __first = _GLIBCXX_STD_P::adjacent_find(__first, __last, __binary_pred);
1220 if (__first == __last)
1224 _ForwardIterator __dest = __first;
1225 ++__first;
1226 while (++__first != __last)
1227 if (!bool(__binary_pred(*__dest, *__first)))
1228 *++__dest = _GLIBCXX_MOVE(*__first);
1239 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1244 _ForwardIterator __next = __first;
1245 *__result = *__first;
1247 if (!(*__first == *__next))
1249 __first = __next;
1250 *++__result = *__first;
1262 __unique_copy(_InputIterator __first, _InputIterator __last,
1267 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1269 while (++__first != __last)
1270 if (!(__value == *__first))
1272 __value = *__first;
1285 __unique_copy(_InputIterator __first, _InputIterator __last,
1290 *__result = *__first;
1291 while (++__first != __last)
1292 if (!(*__result == *__first))
1293 *++__result = *__first;
1306 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1315 _ForwardIterator __next = __first;
1316 *__result = *__first;
1318 if (!bool(__binary_pred(*__first, *__next)))
1320 __first = __next;
1321 *++__result = *__first;
1335 __unique_copy(_InputIterator __first, _InputIterator __last,
1344 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1346 while (++__first != __last)
1347 if (!bool(__binary_pred(__value, *__first)))
1349 __value = *__first;
1364 __unique_copy(_InputIterator __first, _InputIterator __last,
1373 *__result = *__first;
1374 while (++__first != __last)
1375 if (!bool(__binary_pred(*__result, *__first)))
1376 *++__result = *__first;
1387 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1391 if (__first == __last || __first == --__last)
1395 std::iter_swap(__first, __last);
1396 ++__first;
1407 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1410 if (__first == __last)
1413 while (__first < __last)
1415 std::iter_swap(__first, __last);
1416 ++__first;
1435 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1440 __glibcxx_requires_valid_range(__first, __last);
1441 std::__reverse(__first, __last, std::__iterator_category(__first));
1462 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1470 __glibcxx_requires_valid_range(__first, __last);
1472 while (__first != __last)
1501 __rotate(_ForwardIterator __first,
1506 if (__first == __middle || __last == __middle)
1512 std::iter_swap(__first, __first2);
1513 ++__first;
1515 if (__first == __middle)
1524 std::iter_swap(__first, __first2);
1525 ++__first;
1527 if (__first == __middle)
1537 __rotate(_BidirectionalIterator __first,
1546 if (__first == __middle || __last == __middle)
1549 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1552 while (__first != __middle && __middle != __last)
1554 std::iter_swap(__first, --__last);
1555 ++__first;
1558 if (__first == __middle)
1561 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1567 __rotate(_RandomAccessIterator __first,
1576 if (__first == __middle || __last == __middle)
1584 _Distance __n = __last - __first;
1585 _Distance __k = __middle - __first;
1589 std::swap_ranges(__first, __middle, __middle);
1593 _RandomAccessIterator __p = __first;
1666 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1672 __glibcxx_requires_valid_range(__first, __middle);
1677 std::__rotate(__first, __middle, __last, _IterType());
1700 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1707 __glibcxx_requires_valid_range(__first, __middle);
1710 return std::copy(__first, __middle,
1717 __partition(_ForwardIterator __first, _ForwardIterator __last,
1720 if (__first == __last)
1721 return __first;
1723 while (__pred(*__first))
1724 if (++__first == __last)
1725 return __first;
1727 _ForwardIterator __next = __first;
1732 std::iter_swap(__first, __next);
1733 ++__first;
1736 return __first;
1742 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1748 if (__first == __last)
1749 return __first;
1750 else if (__pred(*__first))
1751 ++__first;
1756 if (__first == __last)
1757 return __first;
1762 std::iter_swap(__first, __last);
1763 ++__first;
1772 __inplace_stable_partition(_ForwardIterator __first,
1777 return __pred(*__first) ? __last : __first;
1778 _ForwardIterator __middle = __first;
1780 _ForwardIterator __begin = std::__inplace_stable_partition(__first,
1797 __stable_partition_adaptive(_ForwardIterator __first,
1805 _ForwardIterator __result1 = __first;
1807 for (; __first != __last; ++__first)
1808 if (__pred(*__first))
1810 *__result1 = _GLIBCXX_MOVE(*__first);
1815 *__result2 = _GLIBCXX_MOVE(*__first);
1823 _ForwardIterator __middle = __first;
1826 std::__stable_partition_adaptive(__first, __middle, __pred,
1858 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1866 __glibcxx_requires_valid_range(__first, __last);
1868 if (__first == __last)
1869 return __first;
1877 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1881 std::__stable_partition_adaptive(__first, __last, __pred,
1887 std::__inplace_stable_partition(__first, __last, __pred,
1895 __heap_select(_RandomAccessIterator __first,
1899 std::make_heap(__first, __middle);
1901 if (*__i < *__first)
1902 std::__pop_heap(__first, __middle, __i);
1908 __heap_select(_RandomAccessIterator __first,
1912 std::make_heap(__first, __middle, __comp);
1914 if (__comp(*__i, *__first))
1915 std::__pop_heap(__first, __middle, __i, __comp);
1940 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1958 __glibcxx_requires_valid_range(__first, __last);
1964 while(__first != __last && __result_real_last != __result_last)
1966 *__result_real_last = *__first;
1968 ++__first;
1971 while (__first != __last)
1973 if (*__first < *__result_first)
1977 _InputValueType(*__first));
1978 ++__first;
2006 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2028 __glibcxx_requires_valid_range(__first, __last);
2034 while(__first != __last && __result_real_last != __result_last)
2036 *__result_real_last = *__first;
2038 ++__first;
2041 while (__first != __last)
2043 if (__comp(*__first, *__result_first))
2047 _InputValueType(*__first),
2049 ++__first;
2095 __insertion_sort(_RandomAccessIterator __first,
2098 if (__first == __last)
2101 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2103 if (*__i < *__first)
2107 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2108 *__first = _GLIBCXX_MOVE(__val);
2118 __insertion_sort(_RandomAccessIterator __first,
2121 if (__first == __last) return;
2123 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2125 if (__comp(*__i, *__first))
2129 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2130 *__first = _GLIBCXX_MOVE(__val);
2140 __unguarded_insertion_sort(_RandomAccessIterator __first,
2146 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2153 __unguarded_insertion_sort(_RandomAccessIterator __first,
2159 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2172 __final_insertion_sort(_RandomAccessIterator __first,
2175 if (__last - __first > int(_S_threshold))
2177 std::__insertion_sort(__first, __first + int(_S_threshold));
2178 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2181 std::__insertion_sort(__first, __last);
2187 __final_insertion_sort(_RandomAccessIterator __first,
2190 if (__last - __first > int(_S_threshold))
2192 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2193 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2197 std::__insertion_sort(__first, __last, __comp);
2203 __unguarded_partition(_RandomAccessIterator __first,
2208 while (*__first < __pivot)
2209 ++__first;
2213 if (!(__first < __last))
2214 return __first;
2215 std::iter_swap(__first, __last);
2216 ++__first;
2223 __unguarded_partition(_RandomAccessIterator __first,
2229 while (__comp(*__first, __pivot))
2230 ++__first;
2234 if (!(__first < __last))
2235 return __first;
2236 std::iter_swap(__first, __last);
2237 ++__first;
2244 __unguarded_partition_pivot(_RandomAccessIterator __first,
2247 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2248 std::__move_median_first(__first, __mid, (__last - 1));
2249 return std::__unguarded_partition(__first + 1, __last, *__first);
2256 __unguarded_partition_pivot(_RandomAccessIterator __first,
2259 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2260 std::__move_median_first(__first, __mid, (__last - 1), __comp);
2261 return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2267 __introsort_loop(_RandomAccessIterator __first,
2271 while (__last - __first > int(_S_threshold))
2275 _GLIBCXX_STD_P::partial_sort(__first, __last, __last);
2280 std::__unguarded_partition_pivot(__first, __last);
2289 __introsort_loop(_RandomAccessIterator __first,
2293 while (__last - __first > int(_S_threshold))
2297 _GLIBCXX_STD_P::partial_sort(__first, __last, __last, __comp);
2302 std::__unguarded_partition_pivot(__first, __last, __comp);
2312 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2318 while (__last - __first > 3)
2322 std::__heap_select(__first, __nth + 1, __last);
2325 std::iter_swap(__first, __nth);
2330 std::__unguarded_partition_pivot(__first, __last);
2332 __first = __cut;
2336 std::__insertion_sort(__first, __last);
2341 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2348 while (__last - __first > 3)
2352 std::__heap_select(__first, __nth + 1, __last, __comp);
2354 std::iter_swap(__first, __nth);
2359 std::__unguarded_partition_pivot(__first, __last, __comp);
2361 __first = __cut;
2365 std::__insertion_sort(__first, __last, __comp);
2390 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2402 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2405 _DistanceType __len = std::distance(__first, __last);
2412 __middle = __first;
2416 __first = __middle;
2417 ++__first;
2423 return __first;
2439 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2450 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2452 _DistanceType __len = std::distance(__first, __last);
2459 __middle = __first;
2465 __first = __middle;
2466 ++__first;
2470 return __first;
2490 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2502 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2505 _DistanceType __len = std::distance(__first, __last);
2512 __middle = __first;
2518 __first = __middle;
2519 ++__first;
2523 return __first;
2545 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2557 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2558 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2560 _DistanceType __len = std::distance(__first, __last);
2567 __middle = __first;
2571 __first = __middle;
2572 ++__first;
2579 __left = std::lower_bound(__first, __middle, __val);
2580 std::advance(__first, __len);
2581 __right = std::upper_bound(++__middle, __first, __val);
2585 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2607 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2622 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2624 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2627 _DistanceType __len = std::distance(__first, __last);
2634 __middle = __first;
2638 __first = __middle;
2639 ++__first;
2646 __left = std::lower_bound(__first, __middle, __val, __comp);
2647 std::advance(__first, __len);
2648 __right = std::upper_bound(++__middle, __first, __val, __comp);
2652 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2668 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2677 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2678 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2680 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2701 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2711 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2713 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2716 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2797 __rotate_adaptive(_BidirectionalIterator1 __first,
2808 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2809 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2813 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2814 _GLIBCXX_MOVE3(__middle, __last, __first);
2819 std::rotate(__first, __middle, __last);
2820 std::advance(__first, std::distance(__middle, __last));
2821 return __first;
2829 __merge_adaptive(_BidirectionalIterator __first,
2837 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2842 __first);
2847 std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
2855 _BidirectionalIterator __first_cut = __first;
2871 __first_cut = std::upper_bound(__first, __middle,
2873 __len11 = std::distance(__first, __first_cut);
2879 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2891 __merge_adaptive(_BidirectionalIterator __first,
2900 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2905 __first, __comp);
2910 std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
2918 _BidirectionalIterator __first_cut = __first;
2934 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
2936 __len11 = std::distance(__first, __first_cut);
2942 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2954 __merge_without_buffer(_BidirectionalIterator __first,
2963 if (*__middle < *__first)
2964 std::iter_swap(__first, __middle);
2967 _BidirectionalIterator __first_cut = __first;
2982 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
2983 __len11 = std::distance(__first, __first_cut);
2988 std::__merge_without_buffer(__first, __first_cut, __new_middle,
2998 __merge_without_buffer(_BidirectionalIterator __first,
3008 if (__comp(*__middle, *__first))
3009 std::iter_swap(__first, __middle);
3012 _BidirectionalIterator __first_cut = __first;
3028 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3030 __len11 = std::distance(__first, __first_cut);
3035 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3061 inplace_merge(_BidirectionalIterator __first,
3074 __glibcxx_requires_sorted(__first, __middle);
3077 if (__first == __middle || __middle == __last)
3080 _DistanceType __len1 = std::distance(__first, __middle);
3083 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3086 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3088 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3116 inplace_merge(_BidirectionalIterator __first,
3131 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3134 if (__first == __middle || __middle == __last)
3137 const _DistanceType __len1 = std::distance(__first, __middle);
3140 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3143 std::__merge_without_buffer(__first, __middle, __last, __len1,
3146 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3154 __merge_sort_loop(_RandomAccessIterator1 __first,
3161 while (__last - __first >= __two_step)
3164 _GLIBCXX_MAKE_MOVE_ITERATOR(__first),
3165 _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
3166 _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
3167 _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __two_step),
3169 __first += __two_step;
3172 __step_size = std::min(_Distance(__last - __first), __step_size);
3173 _GLIBCXX_STD_P::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
3174 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
3176 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
3185 __merge_sort_loop(_RandomAccessIterator1 __first,
3192 while (__last - __first >= __two_step)
3195 _GLIBCXX_MAKE_MOVE_ITERATOR(__first),
3196 _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
3197 _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
3198 _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __two_step),
3200 __first += __two_step;
3202 __step_size = std::min(_Distance(__last - __first), __step_size);
3204 _GLIBCXX_STD_P::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
3205 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
3207 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
3215 __chunk_insertion_sort(_RandomAccessIterator __first,
3219 while (__last - __first >= __chunk_size)
3221 std::__insertion_sort(__first, __first + __chunk_size);
3222 __first += __chunk_size;
3224 std::__insertion_sort(__first, __last);
3230 __chunk_insertion_sort(_RandomAccessIterator __first,
3234 while (__last - __first >= __chunk_size)
3236 std::__insertion_sort(__first, __first + __chunk_size, __comp);
3237 __first += __chunk_size;
3239 std::__insertion_sort(__first, __last, __comp);
3246 __merge_sort_with_buffer(_RandomAccessIterator __first,
3253 const _Distance __len = __last - __first;
3257 std::__chunk_insertion_sort(__first, __last, __step_size);
3261 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3263 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3270 __merge_sort_with_buffer(_RandomAccessIterator __first,
3277 const _Distance __len = __last - __first;
3281 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3285 std::__merge_sort_loop(__first, __last, __buffer,
3288 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3297 __stable_sort_adaptive(_RandomAccessIterator __first,
3301 const _Distance __len = (__last - __first + 1) / 2;
3302 const _RandomAccessIterator __middle = __first + __len;
3305 std::__stable_sort_adaptive(__first, __middle,
3312 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3315 std::__merge_adaptive(__first, __middle, __last,
3316 _Distance(__middle - __first),
3324 __stable_sort_adaptive(_RandomAccessIterator __first,
3329 const _Distance __len = (__last - __first + 1) / 2;
3330 const _RandomAccessIterator __middle = __first + __len;
3333 std::__stable_sort_adaptive(__first, __middle, __buffer,
3340 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3343 std::__merge_adaptive(__first, __middle, __last,
3344 _Distance(__middle - __first),
3353 __inplace_stable_sort(_RandomAccessIterator __first,
3356 if (__last - __first < 15)
3358 std::__insertion_sort(__first, __last);
3361 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3362 std::__inplace_stable_sort(__first, __middle);
3364 std::__merge_without_buffer(__first, __middle, __last,
3365 __middle - __first,
3372 __inplace_stable_sort(_RandomAccessIterator __first,
3375 if (__last - __first < 15)
3377 std::__insertion_sort(__first, __last, __comp);
3380 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3381 std::__inplace_stable_sort(__first, __middle, __comp);
3383 std::__merge_without_buffer(__first, __middle, __last,
3384 __middle - __first,
3518 next_permutation(_BidirectionalIterator __first,
3526 __glibcxx_requires_valid_range(__first, __last);
3528 if (__first == __last)
3530 _BidirectionalIterator __i = __first;
3550 if (__i == __first)
3552 std::reverse(__first, __last);
3575 next_permutation(_BidirectionalIterator __first,
3584 __glibcxx_requires_valid_range(__first, __last);
3586 if (__first == __last)
3588 _BidirectionalIterator __i = __first;
3608 if (__i == __first)
3610 std::reverse(__first, __last);
3631 prev_permutation(_BidirectionalIterator __first,
3639 __glibcxx_requires_valid_range(__first, __last);
3641 if (__first == __last)
3643 _BidirectionalIterator __i = __first;
3663 if (__i == __first)
3665 std::reverse(__first, __last);
3688 prev_permutation(_BidirectionalIterator __first,
3697 __glibcxx_requires_valid_range(__first, __last);
3699 if (__first == __last)
3701 _BidirectionalIterator __i = __first;
3721 if (__i == __first)
3723 std::reverse(__first, __last);
3748 replace_copy(_InputIterator __first, _InputIterator __last,
3758 __glibcxx_requires_valid_range(__first, __last);
3760 for (; __first != __last; ++__first, ++__result)
3761 if (*__first == __old_value)
3764 *__result = *__first;
3786 replace_copy_if(_InputIterator __first, _InputIterator __last,
3796 __glibcxx_requires_valid_range(__first, __last);
3798 for (; __first != __last; ++__first, ++__result)
3799 if (__pred(*__first))
3802 *__result = *__first;
3816 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3817 { return std::is_sorted_until(__first, __last) == __last; }
3830 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3832 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3844 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3850 __glibcxx_requires_valid_range(__first, __last);
3852 if (__first == __last)
3855 _ForwardIterator __next = __first;
3856 for (++__next; __next != __last; __first = __next, ++__next)
3857 if (*__next < *__first)
3873 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3881 __glibcxx_requires_valid_range(__first, __last);
3883 if (__first == __last)
3886 _ForwardIterator __next = __first;
3887 for (++__next; __next != __last; __first = __next, ++__next)
3888 if (__comp(*__next, *__first))
3940 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3946 __glibcxx_requires_valid_range(__first, __last);
3948 _ForwardIterator __next = __first;
3949 if (__first == __last
3951 return std::make_pair(__first, __first);
3954 if (*__next < *__first)
3957 __max = __first;
3961 __min = __first;
3965 __first = __next;
3966 ++__first;
3968 while (__first != __last)
3970 __next = __first;
3973 if (*__first < *__min)
3974 __min = __first;
3975 else if (!(*__first < *__max))
3976 __max = __first;
3980 if (*__next < *__first)
3984 if (!(*__first < *__max))
3985 __max = __first;
3989 if (*__first < *__min)
3990 __min = __first;
3995 __first = __next;
3996 ++__first;
4016 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4024 __glibcxx_requires_valid_range(__first, __last);
4026 _ForwardIterator __next = __first;
4027 if (__first == __last
4029 return std::make_pair(__first, __first);
4032 if (__comp(*__next, *__first))
4035 __max = __first;
4039 __min = __first;
4043 __first = __next;
4044 ++__first;
4046 while (__first != __last)
4048 __next = __first;
4051 if (__comp(*__first, *__min))
4052 __min = __first;
4053 else if (!__comp(*__first, *__max))
4054 __max = __first;
4058 if (__comp(*__next, *__first))
4062 if (!__comp(*__first, *__max))
4063 __max = __first;
4067 if (__comp(*__first, *__min))
4068 __min = __first;
4073 __first = __next;
4074 ++__first;
4135 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4141 __glibcxx_requires_valid_range(__first, __last);
4143 if (__first == __last)
4154 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4155 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4179 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4183 __glibcxx_requires_valid_range(__first, __last);
4184 for (; __first != __last; ++__first)
4185 __f(*__first);
4200 find(_InputIterator __first, _InputIterator __last,
4207 __glibcxx_requires_valid_range(__first, __last);
4208 return std::__find(__first, __last, __val,
4209 std::__iterator_category(__first));
4224 find_if(_InputIterator __first, _InputIterator __last,
4231 __glibcxx_requires_valid_range(__first, __last);
4232 return std::__find_if(__first, __last, __pred,
4233 std::__iterator_category(__first));
4324 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4330 __glibcxx_requires_valid_range(__first, __last);
4331 if (__first == __last)
4333 _ForwardIterator __next = __first;
4336 if (*__first == *__next)
4337 return __first;
4338 __first = __next;
4356 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4364 __glibcxx_requires_valid_range(__first, __last);
4365 if (__first == __last)
4367 _ForwardIterator __next = __first;
4370 if (__binary_pred(*__first, *__next))
4371 return __first;
4372 __first = __next;
4388 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4394 __glibcxx_requires_valid_range(__first, __last);
4396 for (; __first != __last; ++__first)
4397 if (*__first == __value)
4413 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4419 __glibcxx_requires_valid_range(__first, __last);
4421 for (; __first != __last; ++__first)
4422 if (__pred(*__first))
4598 search_n(_ForwardIterator __first, _ForwardIterator __last,
4605 __glibcxx_requires_valid_range(__first, __last);
4608 return __first;
4610 return _GLIBCXX_STD_P::find(__first, __last, __val);
4611 return std::__search_n(__first, __last, __count, __val,
4612 std::__iterator_category(__first));
4635 search_n(_ForwardIterator __first, _ForwardIterator __last,
4643 __glibcxx_requires_valid_range(__first, __last);
4646 return __first;
4649 while (__first != __last && !bool(__binary_pred(*__first, __val)))
4650 ++__first;
4651 return __first;
4653 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4654 std::__iterator_category(__first));
4677 transform(_InputIterator __first, _InputIterator __last,
4684 __typeof__(__unary_op(*__first))>)
4685 __glibcxx_requires_valid_range(__first, __last);
4687 for (; __first != __last; ++__first, ++__result)
4688 *__result = __unary_op(*__first);
4745 replace(_ForwardIterator __first, _ForwardIterator __last,
4755 __glibcxx_requires_valid_range(__first, __last);
4757 for (; __first != __last; ++__first)
4758 if (*__first == __old_value)
4759 *__first = __new_value;
4777 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4787 __glibcxx_requires_valid_range(__first, __last);
4789 for (; __first != __last; ++__first)
4790 if (__pred(*__first))
4791 *__first = __new_value;
4809 generate(_ForwardIterator __first, _ForwardIterator __last,
4816 __glibcxx_requires_valid_range(__first, __last);
4818 for (; __first != __last; ++__first)
4819 *__first = __gen();
4840 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4847 for (; __n > 0; --__n, ++__first)
4848 *__first = __gen();
4849 return __first;
4876 unique_copy(_InputIterator __first, _InputIterator __last,
4885 __glibcxx_requires_valid_range(__first, __last);
4887 if (__first == __last)
4889 return std::__unique_copy(__first, __last, __result,
4890 std::__iterator_category(__first),
4916 unique_copy(_InputIterator __first, _InputIterator __last,
4924 __glibcxx_requires_valid_range(__first, __last);
4926 if (__first == __last)
4928 return std::__unique_copy(__first, __last, __result, __binary_pred,
4929 std::__iterator_category(__first),
4947 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4952 __glibcxx_requires_valid_range(__first, __last);
4954 if (__first != __last)
4955 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4956 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
4975 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4985 __glibcxx_requires_valid_range(__first, __last);
4987 if (__first == __last)
4989 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4990 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
5011 partition(_ForwardIterator __first, _ForwardIterator __last,
5019 __glibcxx_requires_valid_range(__first, __last);
5021 return std::__partition(__first, __last, __pred,
5022 std::__iterator_category(__first));
5045 partial_sort(_RandomAccessIterator __first,
5056 __glibcxx_requires_valid_range(__first, __middle);
5059 std::__heap_select(__first, __middle, __last);
5060 std::sort_heap(__first, __middle);
5084 partial_sort(_RandomAccessIterator __first,
5097 __glibcxx_requires_valid_range(__first, __middle);
5100 std::__heap_select(__first, __middle, __last, __comp);
5101 std::sort_heap(__first, __middle, __comp);
5122 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5132 __glibcxx_requires_valid_range(__first, __nth);
5135 if (__first == __last || __nth == __last)
5138 std::__introselect(__first, __nth, __last,
5139 std::__lg(__last - __first) * 2);
5161 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5172 __glibcxx_requires_valid_range(__first, __nth);
5175 if (__first == __last || __nth == __last)
5178 std::__introselect(__first, __nth, __last,
5179 std::__lg(__last - __first) * 2, __comp);
5199 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5208 __glibcxx_requires_valid_range(__first, __last);
5210 if (__first != __last)
5212 std::__introsort_loop(__first, __last,
5213 std::__lg(__last - __first) * 2);
5214 std::__final_insertion_sort(__first, __last);
5235 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5246 __glibcxx_requires_valid_range(__first, __last);
5248 if (__first != __last)
5250 std::__introsort_loop(__first, __last,
5251 std::__lg(__last - __first) * 2, __comp);
5252 std::__final_insertion_sort(__first, __last, __comp);
5399 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5410 __glibcxx_requires_valid_range(__first, __last);
5412 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5415 std::__inplace_stable_sort(__first, __last);
5417 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5441 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5455 __glibcxx_requires_valid_range(__first, __last);
5457 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5460 std::__inplace_stable_sort(__first, __last, __comp);
5462 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5978 min_element(_ForwardIterator __first, _ForwardIterator __last)
5984 __glibcxx_requires_valid_range(__first, __last);
5986 if (__first == __last)
5987 return __first;
5988 _ForwardIterator __result = __first;
5989 while (++__first != __last)
5990 if (*__first < *__result)
5991 __result = __first;
6006 min_element(_ForwardIterator __first, _ForwardIterator __last,
6014 __glibcxx_requires_valid_range(__first, __last);
6016 if (__first == __last)
6017 return __first;
6018 _ForwardIterator __result = __first;
6019 while (++__first != __last)
6020 if (__comp(*__first, *__result))
6021 __result = __first;
6034 max_element(_ForwardIterator __first, _ForwardIterator __last)
6040 __glibcxx_requires_valid_range(__first, __last);
6042 if (__first == __last)
6043 return __first;
6044 _ForwardIterator __result = __first;
6045 while (++__first != __last)
6046 if (*__result < *__first)
6047 __result = __first;
6062 max_element(_ForwardIterator __first, _ForwardIterator __last,
6070 __glibcxx_requires_valid_range(__first, __last);
6072 if (__first == __last) return __first;
6073 _ForwardIterator __result = __first;
6074 while (++__first != __last)
6075 if (__comp(*__result, *__first))
6076 __result = __first;