Lines Matching refs:__first
132 __find(_InputIterator __first, _InputIterator __last,
135 while (__first != __last && !(*__first == __val))
136 ++__first;
137 return __first;
143 __find_if(_InputIterator __first, _InputIterator __last,
146 while (__first != __last && !bool(__pred(*__first)))
147 ++__first;
148 return __first;
154 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
158 __trip_count = (__last - __first) >> 2;
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;
174 if (*__first == __val)
175 return __first;
176 ++__first;
179 switch (__last - __first)
182 if (*__first == __val)
183 return __first;
184 ++__first;
186 if (*__first == __val)
187 return __first;
188 ++__first;
190 if (*__first == __val)
191 return __first;
192 ++__first;
202 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
206 __trip_count = (__last - __first) >> 2;
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;
222 if (__pred(*__first))
223 return __first;
224 ++__first;
227 switch (__last - __first)
230 if (__pred(*__first))
231 return __first;
232 ++__first;
234 if (__pred(*__first))
235 return __first;
236 ++__first;
238 if (__pred(*__first))
239 return __first;
240 ++__first;
251 __find_if_not(_InputIterator __first, _InputIterator __last,
254 while (__first != __last && bool(__pred(*__first)))
255 ++__first;
256 return __first;
262 __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
266 __trip_count = (__last - __first) >> 2;
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;
282 if (!bool(__pred(*__first)))
283 return __first;
284 ++__first;
287 switch (__last - __first)
290 if (!bool(__pred(*__first)))
291 return __first;
292 ++__first;
294 if (!bool(__pred(*__first)))
295 return __first;
296 ++__first;
298 if (!bool(__pred(*__first)))
299 return __first;
300 ++__first;
328 __search_n(_ForwardIterator __first, _ForwardIterator __last,
332 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
333 while (__first != __last)
337 _ForwardIterator __i = __first;
345 return __first;
348 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
360 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
368 _DistanceType __tailSize = __last - __first;
375 _RandomAccessIter __lookAhead = __first + __skipOffset;
414 __search_n(_ForwardIterator __first, _ForwardIterator __last,
418 while (__first != __last && !bool(__binary_pred(*__first, __val)))
419 ++__first;
421 while (__first != __last)
425 _ForwardIterator __i = __first;
433 return __first;
436 __first = ++__i;
437 while (__first != __last
438 && !bool(__binary_pred(*__first, __val)))
439 ++__first;
453 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
461 _DistanceType __tailSize = __last - __first;
468 _RandomAccessIter __lookAhead = __first + __skipOffset;
732 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
733 { return __last == std::find_if_not(__first, __last, __pred); }
749 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
750 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
766 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
767 { return !std::none_of(__first, __last, __pred); }
781 find_if_not(_InputIterator __first, _InputIterator __last,
788 __glibcxx_requires_valid_range(__first, __last);
789 return std::__find_if_not(__first, __last, __pred,
790 std::__iterator_category(__first));
805 is_partitioned(_InputIterator __first, _InputIterator __last,
808 __first = std::find_if_not(__first, __last, __pred);
809 return std::none_of(__first, __last, __pred);
823 partition_point(_ForwardIterator __first, _ForwardIterator __last,
832 __glibcxx_requires_valid_range(__first, __last);
837 _DistanceType __len = std::distance(__first, __last);
844 __middle = __first;
848 __first = __middle;
849 ++__first;
855 return __first;
876 remove_copy(_InputIterator __first, _InputIterator __last,
885 __glibcxx_requires_valid_range(__first, __last);
887 for (; __first != __last; ++__first)
888 if (!(*__first == __value))
890 *__result = *__first;
914 remove_copy_if(_InputIterator __first, _InputIterator __last,
923 __glibcxx_requires_valid_range(__first, __last);
925 for (; __first != __last; ++__first)
926 if (!bool(__pred(*__first)))
928 *__result = *__first;
953 copy_if(_InputIterator __first, _InputIterator __last,
962 __glibcxx_requires_valid_range(__first, __last);
964 for (; __first != __last; ++__first)
965 if (__pred(*__first))
967 *__result = *__first;
976 __copy_n(_InputIterator __first, _Size __n,
981 *__result = *__first;
982 ++__first;
991 __copy_n(_RandomAccessIterator __first, _Size __n,
993 { return std::copy(__first, __first + __n, __result); }
1010 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1017 return std::__copy_n(__first, __n, __result,
1018 std::__iterator_category(__first));
1039 partition_copy(_InputIterator __first, _InputIterator __last,
1051 __glibcxx_requires_valid_range(__first, __last);
1053 for (; __first != __last; ++__first)
1054 if (__pred(*__first))
1056 *__out_true = *__first;
1061 *__out_false = *__first;
1088 remove(_ForwardIterator __first, _ForwardIterator __last,
1096 __glibcxx_requires_valid_range(__first, __last);
1098 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1099 if(__first == __last)
1100 return __first;
1101 _ForwardIterator __result = __first;
1102 ++__first;
1103 for(; __first != __last; ++__first)
1104 if(!(*__first == __value))
1106 *__result = _GLIBCXX_MOVE(*__first);
1131 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1139 __glibcxx_requires_valid_range(__first, __last);
1141 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1142 if(__first == __last)
1143 return __first;
1144 _ForwardIterator __result = __first;
1145 ++__first;
1146 for(; __first != __last; ++__first)
1147 if(!bool(__pred(*__first)))
1149 *__result = _GLIBCXX_MOVE(*__first);
1171 unique(_ForwardIterator __first, _ForwardIterator __last)
1178 __glibcxx_requires_valid_range(__first, __last);
1181 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1182 if (__first == __last)
1186 _ForwardIterator __dest = __first;
1187 ++__first;
1188 while (++__first != __last)
1189 if (!(*__dest == *__first))
1190 *++__dest = _GLIBCXX_MOVE(*__first);
1211 unique(_ForwardIterator __first, _ForwardIterator __last,
1220 __glibcxx_requires_valid_range(__first, __last);
1223 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1224 if (__first == __last)
1228 _ForwardIterator __dest = __first;
1229 ++__first;
1230 while (++__first != __last)
1231 if (!bool(__binary_pred(*__dest, *__first)))
1232 *++__dest = _GLIBCXX_MOVE(*__first);
1243 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1248 _ForwardIterator __next = __first;
1249 *__result = *__first;
1251 if (!(*__first == *__next))
1253 __first = __next;
1254 *++__result = *__first;
1266 __unique_copy(_InputIterator __first, _InputIterator __last,
1271 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1273 while (++__first != __last)
1274 if (!(__value == *__first))
1276 __value = *__first;
1289 __unique_copy(_InputIterator __first, _InputIterator __last,
1294 *__result = *__first;
1295 while (++__first != __last)
1296 if (!(*__result == *__first))
1297 *++__result = *__first;
1310 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1319 _ForwardIterator __next = __first;
1320 *__result = *__first;
1322 if (!bool(__binary_pred(*__first, *__next)))
1324 __first = __next;
1325 *++__result = *__first;
1339 __unique_copy(_InputIterator __first, _InputIterator __last,
1348 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1350 while (++__first != __last)
1351 if (!bool(__binary_pred(__value, *__first)))
1353 __value = *__first;
1368 __unique_copy(_InputIterator __first, _InputIterator __last,
1377 *__result = *__first;
1378 while (++__first != __last)
1379 if (!bool(__binary_pred(*__result, *__first)))
1380 *++__result = *__first;
1391 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1395 if (__first == __last || __first == --__last)
1399 std::iter_swap(__first, __last);
1400 ++__first;
1411 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1414 if (__first == __last)
1417 while (__first < __last)
1419 std::iter_swap(__first, __last);
1420 ++__first;
1439 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1444 __glibcxx_requires_valid_range(__first, __last);
1445 std::__reverse(__first, __last, std::__iterator_category(__first));
1466 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1474 __glibcxx_requires_valid_range(__first, __last);
1476 while (__first != __last)
1505 __rotate(_ForwardIterator __first,
1510 if (__first == __middle || __last == __middle)
1516 std::iter_swap(__first, __first2);
1517 ++__first;
1519 if (__first == __middle)
1528 std::iter_swap(__first, __first2);
1529 ++__first;
1531 if (__first == __middle)
1541 __rotate(_BidirectionalIterator __first,
1550 if (__first == __middle || __last == __middle)
1553 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1556 while (__first != __middle && __middle != __last)
1558 std::iter_swap(__first, --__last);
1559 ++__first;
1562 if (__first == __middle)
1565 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1571 __rotate(_RandomAccessIterator __first,
1580 if (__first == __middle || __last == __middle)
1588 _Distance __n = __last - __first;
1589 _Distance __k = __middle - __first;
1593 std::swap_ranges(__first, __middle, __middle);
1597 _RandomAccessIterator __p = __first;
1670 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1676 __glibcxx_requires_valid_range(__first, __middle);
1681 std::__rotate(__first, __middle, __last, _IterType());
1704 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1711 __glibcxx_requires_valid_range(__first, __middle);
1714 return std::copy(__first, __middle,
1721 __partition(_ForwardIterator __first, _ForwardIterator __last,
1724 if (__first == __last)
1725 return __first;
1727 while (__pred(*__first))
1728 if (++__first == __last)
1729 return __first;
1731 _ForwardIterator __next = __first;
1736 std::iter_swap(__first, __next);
1737 ++__first;
1740 return __first;
1746 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1752 if (__first == __last)
1753 return __first;
1754 else if (__pred(*__first))
1755 ++__first;
1760 if (__first == __last)
1761 return __first;
1766 std::iter_swap(__first, __last);
1767 ++__first;
1776 __inplace_stable_partition(_ForwardIterator __first,
1781 return __pred(*__first) ? __last : __first;
1782 _ForwardIterator __middle = __first;
1784 _ForwardIterator __begin = std::__inplace_stable_partition(__first,
1801 __stable_partition_adaptive(_ForwardIterator __first,
1809 _ForwardIterator __result1 = __first;
1811 for (; __first != __last; ++__first)
1812 if (__pred(*__first))
1814 *__result1 = _GLIBCXX_MOVE(*__first);
1819 *__result2 = _GLIBCXX_MOVE(*__first);
1827 _ForwardIterator __middle = __first;
1830 std::__stable_partition_adaptive(__first, __middle, __pred,
1862 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1870 __glibcxx_requires_valid_range(__first, __last);
1872 if (__first == __last)
1873 return __first;
1881 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1885 std::__stable_partition_adaptive(__first, __last, __pred,
1891 std::__inplace_stable_partition(__first, __last, __pred,
1899 __heap_select(_RandomAccessIterator __first,
1903 std::make_heap(__first, __middle);
1905 if (*__i < *__first)
1906 std::__pop_heap(__first, __middle, __i);
1912 __heap_select(_RandomAccessIterator __first,
1916 std::make_heap(__first, __middle, __comp);
1918 if (__comp(*__i, *__first))
1919 std::__pop_heap(__first, __middle, __i, __comp);
1944 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1962 __glibcxx_requires_valid_range(__first, __last);
1968 while(__first != __last && __result_real_last != __result_last)
1970 *__result_real_last = *__first;
1972 ++__first;
1975 while (__first != __last)
1977 if (*__first < *__result_first)
1981 _InputValueType(*__first));
1982 ++__first;
2010 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2032 __glibcxx_requires_valid_range(__first, __last);
2038 while(__first != __last && __result_real_last != __result_last)
2040 *__result_real_last = *__first;
2042 ++__first;
2045 while (__first != __last)
2047 if (__comp(*__first, *__result_first))
2051 _InputValueType(*__first),
2053 ++__first;
2099 __insertion_sort(_RandomAccessIterator __first,
2102 if (__first == __last)
2105 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2107 if (*__i < *__first)
2111 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2112 *__first = _GLIBCXX_MOVE(__val);
2122 __insertion_sort(_RandomAccessIterator __first,
2125 if (__first == __last) return;
2127 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2129 if (__comp(*__i, *__first))
2133 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2134 *__first = _GLIBCXX_MOVE(__val);
2144 __unguarded_insertion_sort(_RandomAccessIterator __first,
2150 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2157 __unguarded_insertion_sort(_RandomAccessIterator __first,
2163 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2176 __final_insertion_sort(_RandomAccessIterator __first,
2179 if (__last - __first > int(_S_threshold))
2181 std::__insertion_sort(__first, __first + int(_S_threshold));
2182 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2185 std::__insertion_sort(__first, __last);
2191 __final_insertion_sort(_RandomAccessIterator __first,
2194 if (__last - __first > int(_S_threshold))
2196 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2197 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2201 std::__insertion_sort(__first, __last, __comp);
2207 __unguarded_partition(_RandomAccessIterator __first,
2212 while (*__first < __pivot)
2213 ++__first;
2217 if (!(__first < __last))
2218 return __first;
2219 std::iter_swap(__first, __last);
2220 ++__first;
2227 __unguarded_partition(_RandomAccessIterator __first,
2233 while (__comp(*__first, __pivot))
2234 ++__first;
2238 if (!(__first < __last))
2239 return __first;
2240 std::iter_swap(__first, __last);
2241 ++__first;
2248 __unguarded_partition_pivot(_RandomAccessIterator __first,
2251 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2252 std::__move_median_first(__first, __mid, (__last - 1));
2253 return std::__unguarded_partition(__first + 1, __last, *__first);
2260 __unguarded_partition_pivot(_RandomAccessIterator __first,
2263 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2264 std::__move_median_first(__first, __mid, (__last - 1), __comp);
2265 return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2271 __introsort_loop(_RandomAccessIterator __first,
2275 while (__last - __first > int(_S_threshold))
2279 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2284 std::__unguarded_partition_pivot(__first, __last);
2293 __introsort_loop(_RandomAccessIterator __first,
2297 while (__last - __first > int(_S_threshold))
2301 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2306 std::__unguarded_partition_pivot(__first, __last, __comp);
2316 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2322 while (__last - __first > 3)
2326 std::__heap_select(__first, __nth + 1, __last);
2329 std::iter_swap(__first, __nth);
2334 std::__unguarded_partition_pivot(__first, __last);
2336 __first = __cut;
2340 std::__insertion_sort(__first, __last);
2345 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2352 while (__last - __first > 3)
2356 std::__heap_select(__first, __nth + 1, __last, __comp);
2358 std::iter_swap(__first, __nth);
2363 std::__unguarded_partition_pivot(__first, __last, __comp);
2365 __first = __cut;
2369 std::__insertion_sort(__first, __last, __comp);
2394 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2406 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2409 _DistanceType __len = std::distance(__first, __last);
2414 _ForwardIterator __middle = __first;
2418 __first = __middle;
2419 ++__first;
2425 return __first;
2441 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2452 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2454 _DistanceType __len = std::distance(__first, __last);
2459 _ForwardIterator __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);
2510 _ForwardIterator __middle = __first;
2516 __first = __middle;
2517 ++__first;
2521 return __first;
2543 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2555 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2556 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2558 _DistanceType __len = std::distance(__first, __last);
2563 _ForwardIterator __middle = __first;
2567 __first = __middle;
2568 ++__first;
2575 _ForwardIterator __left = std::lower_bound(__first, __middle,
2577 std::advance(__first, __len);
2578 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2583 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2605 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2619 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2621 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2624 _DistanceType __len = std::distance(__first, __last);
2629 _ForwardIterator __middle = __first;
2633 __first = __middle;
2634 ++__first;
2641 _ForwardIterator __left = std::lower_bound(__first, __middle,
2643 std::advance(__first, __len);
2644 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2649 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2665 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2674 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2675 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2677 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2698 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2708 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2710 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2713 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2849 __rotate_adaptive(_BidirectionalIterator1 __first,
2860 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2861 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2865 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2866 _GLIBCXX_MOVE3(__middle, __last, __first);
2871 std::rotate(__first, __middle, __last);
2872 std::advance(__first, std::distance(__middle, __last));
2873 return __first;
2881 __merge_adaptive(_BidirectionalIterator __first,
2889 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2890 std::__move_merge(__buffer, __buffer_end, __middle, __last, __first);
2895 std::__move_merge_backward(__first, __middle, __buffer,
2900 _BidirectionalIterator __first_cut = __first;
2916 __first_cut = std::upper_bound(__first, __middle,
2918 __len11 = std::distance(__first, __first_cut);
2924 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2936 __merge_adaptive(_BidirectionalIterator __first,
2945 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2947 __first, __comp);
2952 std::__move_merge_backward(__first, __middle, __buffer, __buffer_end,
2957 _BidirectionalIterator __first_cut = __first;
2973 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
2975 __len11 = std::distance(__first, __first_cut);
2981 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2993 __merge_without_buffer(_BidirectionalIterator __first,
3002 if (*__middle < *__first)
3003 std::iter_swap(__first, __middle);
3006 _BidirectionalIterator __first_cut = __first;
3021 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3022 __len11 = std::distance(__first, __first_cut);
3027 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3037 __merge_without_buffer(_BidirectionalIterator __first,
3047 if (__comp(*__middle, *__first))
3048 std::iter_swap(__first, __middle);
3051 _BidirectionalIterator __first_cut = __first;
3067 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3069 __len11 = std::distance(__first, __first_cut);
3074 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3100 inplace_merge(_BidirectionalIterator __first,
3113 __glibcxx_requires_sorted(__first, __middle);
3116 if (__first == __middle || __middle == __last)
3119 _DistanceType __len1 = std::distance(__first, __middle);
3122 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3125 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3127 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3155 inplace_merge(_BidirectionalIterator __first,
3170 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3173 if (__first == __middle || __middle == __last)
3176 const _DistanceType __len1 = std::distance(__first, __middle);
3179 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3182 std::__merge_without_buffer(__first, __middle, __last, __len1,
3185 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3193 __merge_sort_loop(_RandomAccessIterator1 __first,
3200 while (__last - __first >= __two_step)
3202 __result = std::__move_merge(__first, __first + __step_size,
3203 __first + __step_size,
3204 __first + __two_step, __result);
3205 __first += __two_step;
3208 __step_size = std::min(_Distance(__last - __first), __step_size);
3209 std::__move_merge(__first, __first + __step_size,
3210 __first + __step_size, __last, __result);
3216 __merge_sort_loop(_RandomAccessIterator1 __first,
3223 while (__last - __first >= __two_step)
3225 __result = std::__move_merge(__first, __first + __step_size,
3226 __first + __step_size,
3227 __first + __two_step,
3229 __first += __two_step;
3231 __step_size = std::min(_Distance(__last - __first), __step_size);
3233 std::__move_merge(__first,__first + __step_size,
3234 __first + __step_size, __last, __result, __comp);
3239 __chunk_insertion_sort(_RandomAccessIterator __first,
3243 while (__last - __first >= __chunk_size)
3245 std::__insertion_sort(__first, __first + __chunk_size);
3246 __first += __chunk_size;
3248 std::__insertion_sort(__first, __last);
3254 __chunk_insertion_sort(_RandomAccessIterator __first,
3258 while (__last - __first >= __chunk_size)
3260 std::__insertion_sort(__first, __first + __chunk_size, __comp);
3261 __first += __chunk_size;
3263 std::__insertion_sort(__first, __last, __comp);
3270 __merge_sort_with_buffer(_RandomAccessIterator __first,
3277 const _Distance __len = __last - __first;
3281 std::__chunk_insertion_sort(__first, __last, __step_size);
3285 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3287 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3294 __merge_sort_with_buffer(_RandomAccessIterator __first,
3301 const _Distance __len = __last - __first;
3305 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3309 std::__merge_sort_loop(__first, __last, __buffer,
3312 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3321 __stable_sort_adaptive(_RandomAccessIterator __first,
3325 const _Distance __len = (__last - __first + 1) / 2;
3326 const _RandomAccessIterator __middle = __first + __len;
3329 std::__stable_sort_adaptive(__first, __middle,
3336 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3339 std::__merge_adaptive(__first, __middle, __last,
3340 _Distance(__middle - __first),
3348 __stable_sort_adaptive(_RandomAccessIterator __first,
3353 const _Distance __len = (__last - __first + 1) / 2;
3354 const _RandomAccessIterator __middle = __first + __len;
3357 std::__stable_sort_adaptive(__first, __middle, __buffer,
3364 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3367 std::__merge_adaptive(__first, __middle, __last,
3368 _Distance(__middle - __first),
3377 __inplace_stable_sort(_RandomAccessIterator __first,
3380 if (__last - __first < 15)
3382 std::__insertion_sort(__first, __last);
3385 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3386 std::__inplace_stable_sort(__first, __middle);
3388 std::__merge_without_buffer(__first, __middle, __last,
3389 __middle - __first,
3396 __inplace_stable_sort(_RandomAccessIterator __first,
3399 if (__last - __first < 15)
3401 std::__insertion_sort(__first, __last, __comp);
3404 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3405 std::__inplace_stable_sort(__first, __middle, __comp);
3407 std::__merge_without_buffer(__first, __middle, __last,
3408 __middle - __first,
3542 next_permutation(_BidirectionalIterator __first,
3550 __glibcxx_requires_valid_range(__first, __last);
3552 if (__first == __last)
3554 _BidirectionalIterator __i = __first;
3574 if (__i == __first)
3576 std::reverse(__first, __last);
3599 next_permutation(_BidirectionalIterator __first,
3608 __glibcxx_requires_valid_range(__first, __last);
3610 if (__first == __last)
3612 _BidirectionalIterator __i = __first;
3632 if (__i == __first)
3634 std::reverse(__first, __last);
3655 prev_permutation(_BidirectionalIterator __first,
3663 __glibcxx_requires_valid_range(__first, __last);
3665 if (__first == __last)
3667 _BidirectionalIterator __i = __first;
3687 if (__i == __first)
3689 std::reverse(__first, __last);
3712 prev_permutation(_BidirectionalIterator __first,
3721 __glibcxx_requires_valid_range(__first, __last);
3723 if (__first == __last)
3725 _BidirectionalIterator __i = __first;
3745 if (__i == __first)
3747 std::reverse(__first, __last);
3772 replace_copy(_InputIterator __first, _InputIterator __last,
3782 __glibcxx_requires_valid_range(__first, __last);
3784 for (; __first != __last; ++__first, ++__result)
3785 if (*__first == __old_value)
3788 *__result = *__first;
3810 replace_copy_if(_InputIterator __first, _InputIterator __last,
3820 __glibcxx_requires_valid_range(__first, __last);
3822 for (; __first != __last; ++__first, ++__result)
3823 if (__pred(*__first))
3826 *__result = *__first;
3840 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3841 { return std::is_sorted_until(__first, __last) == __last; }
3854 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3856 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3868 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3874 __glibcxx_requires_valid_range(__first, __last);
3876 if (__first == __last)
3879 _ForwardIterator __next = __first;
3880 for (++__next; __next != __last; __first = __next, ++__next)
3881 if (*__next < *__first)
3897 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3905 __glibcxx_requires_valid_range(__first, __last);
3907 if (__first == __last)
3910 _ForwardIterator __next = __first;
3911 for (++__next; __next != __last; __first = __next, ++__next)
3912 if (__comp(*__next, *__first))
3964 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3970 __glibcxx_requires_valid_range(__first, __last);
3972 _ForwardIterator __next = __first;
3973 if (__first == __last
3975 return std::make_pair(__first, __first);
3978 if (*__next < *__first)
3981 __max = __first;
3985 __min = __first;
3989 __first = __next;
3990 ++__first;
3992 while (__first != __last)
3994 __next = __first;
3997 if (*__first < *__min)
3998 __min = __first;
3999 else if (!(*__first < *__max))
4000 __max = __first;
4004 if (*__next < *__first)
4008 if (!(*__first < *__max))
4009 __max = __first;
4013 if (*__first < *__min)
4014 __min = __first;
4019 __first = __next;
4020 ++__first;
4040 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4048 __glibcxx_requires_valid_range(__first, __last);
4050 _ForwardIterator __next = __first;
4051 if (__first == __last
4053 return std::make_pair(__first, __first);
4056 if (__comp(*__next, *__first))
4059 __max = __first;
4063 __min = __first;
4067 __first = __next;
4068 ++__first;
4070 while (__first != __last)
4072 __next = __first;
4075 if (__comp(*__first, *__min))
4076 __min = __first;
4077 else if (!__comp(*__first, *__max))
4078 __max = __first;
4082 if (__comp(*__next, *__first))
4086 if (!__comp(*__first, *__max))
4087 __max = __first;
4091 if (__comp(*__first, *__min))
4092 __min = __first;
4097 __first = __next;
4098 ++__first;
4252 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4258 __glibcxx_requires_valid_range(__first, __last);
4260 if (__first == __last)
4271 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4272 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4296 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4300 __glibcxx_requires_valid_range(__first, __last);
4301 for (; __first != __last; ++__first)
4302 __f(*__first);
4317 find(_InputIterator __first, _InputIterator __last,
4324 __glibcxx_requires_valid_range(__first, __last);
4325 return std::__find(__first, __last, __val,
4326 std::__iterator_category(__first));
4341 find_if(_InputIterator __first, _InputIterator __last,
4348 __glibcxx_requires_valid_range(__first, __last);
4349 return std::__find_if(__first, __last, __pred,
4350 std::__iterator_category(__first));
4441 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4447 __glibcxx_requires_valid_range(__first, __last);
4448 if (__first == __last)
4450 _ForwardIterator __next = __first;
4453 if (*__first == *__next)
4454 return __first;
4455 __first = __next;
4473 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4481 __glibcxx_requires_valid_range(__first, __last);
4482 if (__first == __last)
4484 _ForwardIterator __next = __first;
4487 if (__binary_pred(*__first, *__next))
4488 return __first;
4489 __first = __next;
4505 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4511 __glibcxx_requires_valid_range(__first, __last);
4513 for (; __first != __last; ++__first)
4514 if (*__first == __value)
4530 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4536 __glibcxx_requires_valid_range(__first, __last);
4538 for (; __first != __last; ++__first)
4539 if (__pred(*__first))
4715 search_n(_ForwardIterator __first, _ForwardIterator __last,
4722 __glibcxx_requires_valid_range(__first, __last);
4725 return __first;
4727 return _GLIBCXX_STD_A::find(__first, __last, __val);
4728 return std::__search_n(__first, __last, __count, __val,
4729 std::__iterator_category(__first));
4752 search_n(_ForwardIterator __first, _ForwardIterator __last,
4760 __glibcxx_requires_valid_range(__first, __last);
4763 return __first;
4766 while (__first != __last && !bool(__binary_pred(*__first, __val)))
4767 ++__first;
4768 return __first;
4770 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4771 std::__iterator_category(__first));
4794 transform(_InputIterator __first, _InputIterator __last,
4801 __typeof__(__unary_op(*__first))>)
4802 __glibcxx_requires_valid_range(__first, __last);
4804 for (; __first != __last; ++__first, ++__result)
4805 *__result = __unary_op(*__first);
4862 replace(_ForwardIterator __first, _ForwardIterator __last,
4872 __glibcxx_requires_valid_range(__first, __last);
4874 for (; __first != __last; ++__first)
4875 if (*__first == __old_value)
4876 *__first = __new_value;
4894 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4904 __glibcxx_requires_valid_range(__first, __last);
4906 for (; __first != __last; ++__first)
4907 if (__pred(*__first))
4908 *__first = __new_value;
4926 generate(_ForwardIterator __first, _ForwardIterator __last,
4933 __glibcxx_requires_valid_range(__first, __last);
4935 for (; __first != __last; ++__first)
4936 *__first = __gen();
4957 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4965 __niter > 0; --__niter, ++__first)
4966 *__first = __gen();
4967 return __first;
4994 unique_copy(_InputIterator __first, _InputIterator __last,
5003 __glibcxx_requires_valid_range(__first, __last);
5005 if (__first == __last)
5007 return std::__unique_copy(__first, __last, __result,
5008 std::__iterator_category(__first),
5034 unique_copy(_InputIterator __first, _InputIterator __last,
5042 __glibcxx_requires_valid_range(__first, __last);
5044 if (__first == __last)
5046 return std::__unique_copy(__first, __last, __result, __binary_pred,
5047 std::__iterator_category(__first),
5065 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5070 __glibcxx_requires_valid_range(__first, __last);
5072 if (__first != __last)
5073 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5074 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5093 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5103 __glibcxx_requires_valid_range(__first, __last);
5105 if (__first == __last)
5107 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5108 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
5129 partition(_ForwardIterator __first, _ForwardIterator __last,
5137 __glibcxx_requires_valid_range(__first, __last);
5139 return std::__partition(__first, __last, __pred,
5140 std::__iterator_category(__first));
5163 partial_sort(_RandomAccessIterator __first,
5174 __glibcxx_requires_valid_range(__first, __middle);
5177 std::__heap_select(__first, __middle, __last);
5178 std::sort_heap(__first, __middle);
5202 partial_sort(_RandomAccessIterator __first,
5215 __glibcxx_requires_valid_range(__first, __middle);
5218 std::__heap_select(__first, __middle, __last, __comp);
5219 std::sort_heap(__first, __middle, __comp);
5240 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5250 __glibcxx_requires_valid_range(__first, __nth);
5253 if (__first == __last || __nth == __last)
5256 std::__introselect(__first, __nth, __last,
5257 std::__lg(__last - __first) * 2);
5279 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5290 __glibcxx_requires_valid_range(__first, __nth);
5293 if (__first == __last || __nth == __last)
5296 std::__introselect(__first, __nth, __last,
5297 std::__lg(__last - __first) * 2, __comp);
5317 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5326 __glibcxx_requires_valid_range(__first, __last);
5328 if (__first != __last)
5330 std::__introsort_loop(__first, __last,
5331 std::__lg(__last - __first) * 2);
5332 std::__final_insertion_sort(__first, __last);
5353 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5364 __glibcxx_requires_valid_range(__first, __last);
5366 if (__first != __last)
5368 std::__introsort_loop(__first, __last,
5369 std::__lg(__last - __first) * 2, __comp);
5370 std::__final_insertion_sort(__first, __last, __comp);
5517 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5528 __glibcxx_requires_valid_range(__first, __last);
5530 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5533 std::__inplace_stable_sort(__first, __last);
5535 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5559 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5573 __glibcxx_requires_valid_range(__first, __last);
5575 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5578 std::__inplace_stable_sort(__first, __last, __comp);
5580 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
6096 min_element(_ForwardIterator __first, _ForwardIterator __last)
6102 __glibcxx_requires_valid_range(__first, __last);
6104 if (__first == __last)
6105 return __first;
6106 _ForwardIterator __result = __first;
6107 while (++__first != __last)
6108 if (*__first < *__result)
6109 __result = __first;
6124 min_element(_ForwardIterator __first, _ForwardIterator __last,
6132 __glibcxx_requires_valid_range(__first, __last);
6134 if (__first == __last)
6135 return __first;
6136 _ForwardIterator __result = __first;
6137 while (++__first != __last)
6138 if (__comp(*__first, *__result))
6139 __result = __first;
6152 max_element(_ForwardIterator __first, _ForwardIterator __last)
6158 __glibcxx_requires_valid_range(__first, __last);
6160 if (__first == __last)
6161 return __first;
6162 _ForwardIterator __result = __first;
6163 while (++__first != __last)
6164 if (*__result < *__first)
6165 __result = __first;
6180 max_element(_ForwardIterator __first, _ForwardIterator __last,
6188 __glibcxx_requires_valid_range(__first, __last);
6190 if (__first == __last) return __first;
6191 _ForwardIterator __result = __first;
6192 while (++__first != __last)
6193 if (__comp(*__result, *__first))
6194 __result = __first;