Lines Matching refs:__first
130 __find(_InputIterator __first, _InputIterator __last,
133 while (__first != __last && !(*__first == __val))
134 ++__first;
135 return __first;
141 __find_if(_InputIterator __first, _InputIterator __last,
144 while (__first != __last && !bool(__pred(*__first)))
145 ++__first;
146 return __first;
152 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
156 __trip_count = (__last - __first) >> 2;
160 if (*__first == __val)
161 return __first;
162 ++__first;
164 if (*__first == __val)
165 return __first;
166 ++__first;
168 if (*__first == __val)
169 return __first;
170 ++__first;
172 if (*__first == __val)
173 return __first;
174 ++__first;
177 switch (__last - __first)
180 if (*__first == __val)
181 return __first;
182 ++__first;
184 if (*__first == __val)
185 return __first;
186 ++__first;
188 if (*__first == __val)
189 return __first;
190 ++__first;
200 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
204 __trip_count = (__last - __first) >> 2;
208 if (__pred(*__first))
209 return __first;
210 ++__first;
212 if (__pred(*__first))
213 return __first;
214 ++__first;
216 if (__pred(*__first))
217 return __first;
218 ++__first;
220 if (__pred(*__first))
221 return __first;
222 ++__first;
225 switch (__last - __first)
228 if (__pred(*__first))
229 return __first;
230 ++__first;
232 if (__pred(*__first))
233 return __first;
234 ++__first;
236 if (__pred(*__first))
237 return __first;
238 ++__first;
248 __find_if_not(_InputIterator __first, _InputIterator __last,
251 while (__first != __last && bool(__pred(*__first)))
252 ++__first;
253 return __first;
259 __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
263 __trip_count = (__last - __first) >> 2;
267 if (!bool(__pred(*__first)))
268 return __first;
269 ++__first;
271 if (!bool(__pred(*__first)))
272 return __first;
273 ++__first;
275 if (!bool(__pred(*__first)))
276 return __first;
277 ++__first;
279 if (!bool(__pred(*__first)))
280 return __first;
281 ++__first;
284 switch (__last - __first)
287 if (!bool(__pred(*__first)))
288 return __first;
289 ++__first;
291 if (!bool(__pred(*__first)))
292 return __first;
293 ++__first;
295 if (!bool(__pred(*__first)))
296 return __first;
297 ++__first;
307 __find_if_not(_InputIterator __first, _InputIterator __last,
310 return std::__find_if_not(__first, __last, __pred,
311 std::__iterator_category(__first));
319 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
321 for (; __len; --__len, ++__first)
322 if (!bool(__pred(*__first)))
324 return __first;
347 __search_n(_ForwardIterator __first, _ForwardIterator __last,
351 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
352 while (__first != __last)
356 _ForwardIterator __i = __first;
364 return __first;
367 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
379 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
387 _DistanceType __tailSize = __last - __first;
394 _RandomAccessIter __lookAhead = __first + __skipOffset;
433 __search_n(_ForwardIterator __first, _ForwardIterator __last,
437 while (__first != __last && !bool(__binary_pred(*__first, __val)))
438 ++__first;
440 while (__first != __last)
444 _ForwardIterator __i = __first;
452 return __first;
455 __first = ++__i;
456 while (__first != __last
457 && !bool(__binary_pred(*__first, __val)))
458 ++__first;
472 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
480 _DistanceType __tailSize = __last - __first;
487 _RandomAccessIter __lookAhead = __first + __skipOffset;
657 * [__first2,__last2) and returns an iterator to the __first
660 * subsequence contained in [__first,__last1).
707 * last such subsequence contained in [__first,__last1).
743 * @param __first An input iterator.
749 * @p [__first,__last), and false otherwise.
753 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
754 { return __last == std::find_if_not(__first, __last, __pred); }
760 * @param __first An input iterator.
766 * @p [__first,__last), and false otherwise.
770 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
771 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
777 * @param __first An input iterator.
783 * [__first,__last) such that @p __pred is true, and false
788 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
789 { return !std::none_of(__first, __last, __pred); }
795 * @param __first An input iterator.
798 * @return The first iterator @c i in the range @p [__first,__last)
803 find_if_not(_InputIterator __first, _InputIterator __last,
810 __glibcxx_requires_valid_range(__first, __last);
811 return std::__find_if_not(__first, __last, __pred);
817 * @param __first An input iterator.
820 * @return True if the range @p [__first,__last) is partioned by @p __pred,
826 is_partitioned(_InputIterator __first, _InputIterator __last,
829 __first = std::find_if_not(__first, __last, __pred);
830 return std::none_of(__first, __last, __pred);
836 * @param __first An iterator.
839 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
844 partition_point(_ForwardIterator __first, _ForwardIterator __last,
853 __glibcxx_requires_valid_range(__first, __last);
858 _DistanceType __len = std::distance(__first, __last);
865 __middle = __first;
869 __first = __middle;
870 ++__first;
876 return __first;
884 * @param __first An input iterator.
890 * Copies each element in the range @p [__first,__last) not equal
897 remove_copy(_InputIterator __first, _InputIterator __last,
906 __glibcxx_requires_valid_range(__first, __last);
908 for (; __first != __last; ++__first)
909 if (!(*__first == __value))
911 *__result = *__first;
920 * @param __first An input iterator.
926 * Copies each element in the range @p [__first,__last) for which
935 remove_copy_if(_InputIterator __first, _InputIterator __last,
944 __glibcxx_requires_valid_range(__first, __last);
946 for (; __first != __last; ++__first)
947 if (!bool(__pred(*__first)))
949 *__result = *__first;
959 * @param __first An input iterator.
965 * Copies each element in the range @p [__first,__last) for which
974 copy_if(_InputIterator __first, _InputIterator __last,
983 __glibcxx_requires_valid_range(__first, __last);
985 for (; __first != __last; ++__first)
986 if (__pred(*__first))
988 *__result = *__first;
997 __copy_n(_InputIterator __first, _Size __n,
1004 *__result = *__first;
1007 ++__first;
1018 __copy_n(_RandomAccessIterator __first, _Size __n,
1020 { return std::copy(__first, __first + __n, __result); }
1025 * @param __first An input iterator.
1037 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1044 return std::__copy_n(__first, __n, __result,
1045 std::__iterator_category(__first));
1052 * @param __first An input iterator.
1059 * Copies each element in the range @p [__first,__last) for which
1066 partition_copy(_InputIterator __first, _InputIterator __last,
1078 __glibcxx_requires_valid_range(__first, __last);
1080 for (; __first != __last; ++__first)
1081 if (__pred(*__first))
1083 *__out_true = *__first;
1088 *__out_false = *__first;
1099 * @param __first An input iterator.
1105 * @p [__first,__last).
1115 remove(_ForwardIterator __first, _ForwardIterator __last,
1123 __glibcxx_requires_valid_range(__first, __last);
1125 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1126 if(__first == __last)
1127 return __first;
1128 _ForwardIterator __result = __first;
1129 ++__first;
1130 for(; __first != __last; ++__first)
1131 if(!(*__first == __value))
1133 *__result = _GLIBCXX_MOVE(*__first);
1142 * @param __first A forward iterator.
1148 * @p [__first,__last).
1158 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1166 __glibcxx_requires_valid_range(__first, __last);
1168 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1169 if(__first == __last)
1170 return __first;
1171 _ForwardIterator __result = __first;
1172 ++__first;
1173 for(; __first != __last; ++__first)
1174 if(!bool(__pred(*__first)))
1176 *__result = _GLIBCXX_MOVE(*__first);
1185 * @param __first A forward iterator.
1198 unique(_ForwardIterator __first, _ForwardIterator __last)
1205 __glibcxx_requires_valid_range(__first, __last);
1208 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1209 if (__first == __last)
1213 _ForwardIterator __dest = __first;
1214 ++__first;
1215 while (++__first != __last)
1216 if (!(*__dest == *__first))
1217 *++__dest = _GLIBCXX_MOVE(*__first);
1224 * @param __first A forward iterator.
1238 unique(_ForwardIterator __first, _ForwardIterator __last,
1247 __glibcxx_requires_valid_range(__first, __last);
1250 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1251 if (__first == __last)
1255 _ForwardIterator __dest = __first;
1256 ++__first;
1257 while (++__first != __last)
1258 if (!bool(__binary_pred(*__dest, *__first)))
1259 *++__dest = _GLIBCXX_MOVE(*__first);
1270 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1275 _ForwardIterator __next = __first;
1276 *__result = *__first;
1278 if (!(*__first == *__next))
1280 __first = __next;
1281 *++__result = *__first;
1293 __unique_copy(_InputIterator __first, _InputIterator __last,
1298 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1300 while (++__first != __last)
1301 if (!(__value == *__first))
1303 __value = *__first;
1316 __unique_copy(_InputIterator __first, _InputIterator __last,
1321 *__result = *__first;
1322 while (++__first != __last)
1323 if (!(*__result == *__first))
1324 *++__result = *__first;
1337 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1346 _ForwardIterator __next = __first;
1347 *__result = *__first;
1349 if (!bool(__binary_pred(*__first, *__next)))
1351 __first = __next;
1352 *++__result = *__first;
1366 __unique_copy(_InputIterator __first, _InputIterator __last,
1375 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1377 while (++__first != __last)
1378 if (!bool(__binary_pred(__value, *__first)))
1380 __value = *__first;
1395 __unique_copy(_InputIterator __first, _InputIterator __last,
1404 *__result = *__first;
1405 while (++__first != __last)
1406 if (!bool(__binary_pred(*__result, *__first)))
1407 *++__result = *__first;
1418 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1422 if (__first == __last || __first == --__last)
1426 std::iter_swap(__first, __last);
1427 ++__first;
1438 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1441 if (__first == __last)
1444 while (__first < __last)
1446 std::iter_swap(__first, __last);
1447 ++__first;
1455 * @param __first A bidirectional iterator.
1459 * Reverses the order of the elements in the range @p [__first,__last),
1461 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1462 * swaps @p *(__first+i) and @p *(__last-(i+1))
1466 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1471 __glibcxx_requires_valid_range(__first, __last);
1472 std::__reverse(__first, __last, std::__iterator_category(__first));
1478 * @param __first A bidirectional iterator.
1483 * Copies the elements in the range @p [__first,__last) to the
1484 * range @p [__result,__result+(__last-__first)) such that the
1486 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1487 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1488 * The ranges @p [__first,__last) and @p
1489 * [__result,__result+(__last-__first)) must not overlap.
1493 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1501 __glibcxx_requires_valid_range(__first, __last);
1503 while (__first != __last)
1532 __rotate(_ForwardIterator __first,
1537 if (__first == __middle || __last == __middle)
1543 std::iter_swap(__first, __first2);
1544 ++__first;
1546 if (__first == __middle)
1555 std::iter_swap(__first, __first2);
1556 ++__first;
1558 if (__first == __middle)
1568 __rotate(_BidirectionalIterator __first,
1577 if (__first == __middle || __last == __middle)
1580 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1583 while (__first != __middle && __middle != __last)
1585 std::iter_swap(__first, --__last);
1586 ++__first;
1589 if (__first == __middle)
1592 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1598 __rotate(_RandomAccessIterator __first,
1607 if (__first == __middle || __last == __middle)
1615 _Distance __n = __last - __first;
1616 _Distance __k = __middle - __first;
1620 std::swap_ranges(__first, __middle, __middle);
1624 _RandomAccessIterator __p = __first;
1679 * @param __first A forward iterator.
1684 * Rotates the elements of the range @p [__first,__last) by
1685 * @p (__middle - __first) positions so that the element at @p __middle
1686 * is moved to @p __first, the element at @p __middle+1 is moved to
1687 * @p __first+1 and so on for each element in the range
1688 * @p [__first,__last).
1690 * This effectively swaps the ranges @p [__first,__middle) and
1694 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1695 * for each @p n in the range @p [0,__last-__first).
1699 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1705 __glibcxx_requires_valid_range(__first, __middle);
1710 std::__rotate(__first, __middle, __last, _IterType());
1716 * @param __first A forward iterator.
1722 * Copies the elements of the range @p [__first,__last) to the
1724 * @p (__middle-__first) positions so that the element at @p __middle
1727 * [__first,__last).
1730 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1731 * for each @p n in the range @p [0,__last-__first).
1735 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1742 __glibcxx_requires_valid_range(__first, __middle);
1745 return std::copy(__first, __middle,
1752 __partition(_ForwardIterator __first, _ForwardIterator __last,
1755 if (__first == __last)
1756 return __first;
1758 while (__pred(*__first))
1759 if (++__first == __last)
1760 return __first;
1762 _ForwardIterator __next = __first;
1767 std::iter_swap(__first, __next);
1768 ++__first;
1771 return __first;
1777 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1783 if (__first == __last)
1784 return __first;
1785 else if (__pred(*__first))
1786 ++__first;
1791 if (__first == __last)
1792 return __first;
1797 std::iter_swap(__first, __last);
1798 ++__first;
1805 /// Requires __len != 0 and !__pred(*__first),
1809 __inplace_stable_partition(_ForwardIterator __first,
1813 return __first;
1814 _ForwardIterator __middle = __first;
1817 std::__inplace_stable_partition(__first, __pred, __len / 2);
1833 /// Requires __first != __last and !__pred(*__first)
1834 /// and __len == distance(__first, __last).
1836 /// !__pred(*__first) allows us to guarantee that we don't
1841 __stable_partition_adaptive(_ForwardIterator __first,
1849 _ForwardIterator __result1 = __first;
1851 // The precondition guarantees that !__pred(*__first), so
1854 *__result2 = _GLIBCXX_MOVE(*__first);
1856 ++__first;
1857 for (; __first != __last; ++__first)
1858 if (__pred(*__first))
1860 *__result1 = _GLIBCXX_MOVE(*__first);
1865 *__result2 = _GLIBCXX_MOVE(*__first);
1873 _ForwardIterator __middle = __first;
1876 std::__stable_partition_adaptive(__first, __middle, __pred,
1899 * @param __first A forward iterator.
1909 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1914 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1922 __glibcxx_requires_valid_range(__first, __last);
1924 __first = std::__find_if_not(__first, __last, __pred);
1926 if (__first == __last)
1927 return __first;
1935 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1939 std::__stable_partition_adaptive(__first, __last, __pred,
1945 std::__inplace_stable_partition(__first, __pred,
1953 __heap_select(_RandomAccessIterator __first,
1957 std::make_heap(__first, __middle);
1959 if (*__i < *__first)
1960 std::__pop_heap(__first, __middle, __i);
1966 __heap_select(_RandomAccessIterator __first,
1970 std::make_heap(__first, __middle, __comp);
1972 if (__comp(*__i, *__first))
1973 std::__pop_heap(__first, __middle, __i, __comp);
1981 * @param __first An iterator.
1987 * Copies and sorts the smallest N values from the range @p [__first,__last)
1989 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1998 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2016 __glibcxx_requires_valid_range(__first, __last);
2022 while(__first != __last && __result_real_last != __result_last)
2024 *__result_real_last = *__first;
2026 ++__first;
2029 while (__first != __last)
2031 if (*__first < *__result_first)
2035 _InputValueType(*__first));
2036 ++__first;
2046 * @param __first An input iterator.
2053 * Copies and sorts the smallest N values from the range @p [__first,__last)
2055 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
2064 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2086 __glibcxx_requires_valid_range(__first, __last);
2092 while(__first != __last && __result_real_last != __result_last)
2094 *__result_real_last = *__first;
2096 ++__first;
2099 while (__first != __last)
2101 if (__comp(*__first, *__result_first))
2105 _InputValueType(*__first),
2107 ++__first;
2153 __insertion_sort(_RandomAccessIterator __first,
2156 if (__first == __last)
2159 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2161 if (*__i < *__first)
2165 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2166 *__first = _GLIBCXX_MOVE(__val);
2176 __insertion_sort(_RandomAccessIterator __first,
2179 if (__first == __last) return;
2181 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2183 if (__comp(*__i, *__first))
2187 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2188 *__first = _GLIBCXX_MOVE(__val);
2198 __unguarded_insertion_sort(_RandomAccessIterator __first,
2204 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2211 __unguarded_insertion_sort(_RandomAccessIterator __first,
2217 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2230 __final_insertion_sort(_RandomAccessIterator __first,
2233 if (__last - __first > int(_S_threshold))
2235 std::__insertion_sort(__first, __first + int(_S_threshold));
2236 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2239 std::__insertion_sort(__first, __last);
2245 __final_insertion_sort(_RandomAccessIterator __first,
2248 if (__last - __first > int(_S_threshold))
2250 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2251 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2255 std::__insertion_sort(__first, __last, __comp);
2261 __unguarded_partition(_RandomAccessIterator __first,
2266 while (*__first < __pivot)
2267 ++__first;
2271 if (!(__first < __last))
2272 return __first;
2273 std::iter_swap(__first, __last);
2274 ++__first;
2281 __unguarded_partition(_RandomAccessIterator __first,
2287 while (__comp(*__first, __pivot))
2288 ++__first;
2292 if (!(__first < __last))
2293 return __first;
2294 std::iter_swap(__first, __last);
2295 ++__first;
2302 __unguarded_partition_pivot(_RandomAccessIterator __first,
2305 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2306 std::__move_median_first(__first, __mid, (__last - 1));
2307 return std::__unguarded_partition(__first + 1, __last, *__first);
2314 __unguarded_partition_pivot(_RandomAccessIterator __first,
2317 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2318 std::__move_median_first(__first, __mid, (__last - 1), __comp);
2319 return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2325 __introsort_loop(_RandomAccessIterator __first,
2329 while (__last - __first > int(_S_threshold))
2333 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2338 std::__unguarded_partition_pivot(__first, __last);
2347 __introsort_loop(_RandomAccessIterator __first,
2351 while (__last - __first > int(_S_threshold))
2355 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2360 std::__unguarded_partition_pivot(__first, __last, __comp);
2370 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2376 while (__last - __first > 3)
2380 std::__heap_select(__first, __nth + 1, __last);
2383 std::iter_swap(__first, __nth);
2388 std::__unguarded_partition_pivot(__first, __last);
2390 __first = __cut;
2394 std::__insertion_sort(__first, __last);
2399 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2406 while (__last - __first > 3)
2410 std::__heap_select(__first, __nth + 1, __last, __comp);
2412 std::iter_swap(__first, __nth);
2417 std::__unguarded_partition_pivot(__first, __last, __comp);
2419 __first = __cut;
2423 std::__insertion_sort(__first, __last, __comp);
2434 * @param __first An iterator.
2448 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2460 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2463 _DistanceType __len = std::distance(__first, __last);
2468 _ForwardIterator __middle = __first;
2472 __first = __middle;
2473 ++__first;
2479 return __first;
2486 * @param __first An iterator.
2495 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2506 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2508 _DistanceType __len = std::distance(__first, __last);
2513 _ForwardIterator __middle = __first;
2519 __first = __middle;
2520 ++__first;
2524 return __first;
2531 * @param __first An iterator.
2544 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2556 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2559 _DistanceType __len = std::distance(__first, __last);
2564 _ForwardIterator __middle = __first;
2570 __first = __middle;
2571 ++__first;
2575 return __first;
2582 * @param __first An iterator.
2590 * std::make_pair(lower_bound(__first, __last, __val),
2591 * upper_bound(__first, __last, __val))
2597 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2609 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2610 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2612 _DistanceType __len = std::distance(__first, __last);
2617 _ForwardIterator __middle = __first;
2621 __first = __middle;
2622 ++__first;
2629 _ForwardIterator __left = std::lower_bound(__first, __middle,
2631 std::advance(__first, __len);
2632 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2637 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2643 * @param __first An iterator.
2652 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2653 * upper_bound(__first, __last, __val, __comp))
2659 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2673 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2675 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2678 _DistanceType __len = std::distance(__first, __last);
2683 _ForwardIterator __middle = __first;
2687 __first = __middle;
2688 ++__first;
2695 _ForwardIterator __left = std::lower_bound(__first, __middle,
2697 std::advance(__first, __len);
2698 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2703 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2709 * @param __first An iterator.
2713 * __first,@p __last ].
2720 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2729 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2730 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2732 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2739 * @param __first An iterator.
2743 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2753 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2763 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2765 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2768 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2915 __rotate_adaptive(_BidirectionalIterator1 __first,
2928 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2929 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2932 return __first;
2938 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2939 _GLIBCXX_MOVE3(__middle, __last, __first);
2947 std::rotate(__first, __middle, __last);
2948 std::advance(__first, std::distance(__middle, __last));
2949 return __first;
2957 __merge_adaptive(_BidirectionalIterator __first,
2965 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2967 __first);
2972 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2977 _BidirectionalIterator __first_cut = __first;
2993 __first_cut = std::upper_bound(__first, __middle,
2995 __len11 = std::distance(__first, __first_cut);
3001 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3013 __merge_adaptive(_BidirectionalIterator __first,
3022 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3024 __first, __comp);
3029 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
3034 _BidirectionalIterator __first_cut = __first;
3050 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3052 __len11 = std::distance(__first, __first_cut);
3058 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3070 __merge_without_buffer(_BidirectionalIterator __first,
3079 if (*__middle < *__first)
3080 std::iter_swap(__first, __middle);
3083 _BidirectionalIterator __first_cut = __first;
3098 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3099 __len11 = std::distance(__first, __first_cut);
3104 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3114 __merge_without_buffer(_BidirectionalIterator __first,
3124 if (__comp(*__middle, *__first))
3125 std::iter_swap(__first, __middle);
3128 _BidirectionalIterator __first_cut = __first;
3144 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3146 __len11 = std::distance(__first, __first_cut);
3151 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3160 * @param __first An iterator.
3165 * Merges two sorted and consecutive ranges, [__first,__middle) and
3166 * [__middle,__last), and puts the result in [__first,__last). The
3171 * If enough additional memory is available, this takes (__last-__first)-1
3173 * distance(__first,__last).
3177 inplace_merge(_BidirectionalIterator __first,
3190 __glibcxx_requires_sorted(__first, __middle);
3193 if (__first == __middle || __middle == __last)
3196 _DistanceType __len1 = std::distance(__first, __middle);
3199 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3202 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3204 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3211 * @param __first An iterator.
3217 * Merges two sorted and consecutive ranges, [__first,__middle) and
3218 * [middle,last), and puts the result in [__first,__last). The output will
3223 * If enough additional memory is available, this takes (__last-__first)-1
3225 * distance(__first,__last).
3232 inplace_merge(_BidirectionalIterator __first,
3247 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3250 if (__first == __middle || __middle == __last)
3253 const _DistanceType __len1 = std::distance(__first, __middle);
3256 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3259 std::__merge_without_buffer(__first, __middle, __last, __len1,
3262 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3325 __merge_sort_loop(_RandomAccessIterator1 __first,
3332 while (__last - __first >= __two_step)
3334 __result = std::__move_merge(__first, __first + __step_size,
3335 __first + __step_size,
3336 __first + __two_step, __result);
3337 __first += __two_step;
3340 __step_size = std::min(_Distance(__last - __first), __step_size);
3341 std::__move_merge(__first, __first + __step_size,
3342 __first + __step_size, __last, __result);
3348 __merge_sort_loop(_RandomAccessIterator1 __first,
3355 while (__last - __first >= __two_step)
3357 __result = std::__move_merge(__first, __first + __step_size,
3358 __first + __step_size,
3359 __first + __two_step,
3361 __first += __two_step;
3363 __step_size = std::min(_Distance(__last - __first), __step_size);
3365 std::__move_merge(__first,__first + __step_size,
3366 __first + __step_size, __last, __result, __comp);
3371 __chunk_insertion_sort(_RandomAccessIterator __first,
3375 while (__last - __first >= __chunk_size)
3377 std::__insertion_sort(__first, __first + __chunk_size);
3378 __first += __chunk_size;
3380 std::__insertion_sort(__first, __last);
3386 __chunk_insertion_sort(_RandomAccessIterator __first,
3390 while (__last - __first >= __chunk_size)
3392 std::__insertion_sort(__first, __first + __chunk_size, __comp);
3393 __first += __chunk_size;
3395 std::__insertion_sort(__first, __last, __comp);
3402 __merge_sort_with_buffer(_RandomAccessIterator __first,
3409 const _Distance __len = __last - __first;
3413 std::__chunk_insertion_sort(__first, __last, __step_size);
3417 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3419 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3426 __merge_sort_with_buffer(_RandomAccessIterator __first,
3433 const _Distance __len = __last - __first;
3437 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3441 std::__merge_sort_loop(__first, __last, __buffer,
3444 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3453 __stable_sort_adaptive(_RandomAccessIterator __first,
3457 const _Distance __len = (__last - __first + 1) / 2;
3458 const _RandomAccessIterator __middle = __first + __len;
3461 std::__stable_sort_adaptive(__first, __middle,
3468 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3471 std::__merge_adaptive(__first, __middle, __last,
3472 _Distance(__middle - __first),
3480 __stable_sort_adaptive(_RandomAccessIterator __first,
3485 const _Distance __len = (__last - __first + 1) / 2;
3486 const _RandomAccessIterator __middle = __first + __len;
3489 std::__stable_sort_adaptive(__first, __middle, __buffer,
3496 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3499 std::__merge_adaptive(__first, __middle, __last,
3500 _Distance(__middle - __first),
3509 __inplace_stable_sort(_RandomAccessIterator __first,
3512 if (__last - __first < 15)
3514 std::__insertion_sort(__first, __last);
3517 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3518 std::__inplace_stable_sort(__first, __middle);
3520 std::__merge_without_buffer(__first, __middle, __last,
3521 __middle - __first,
3528 __inplace_stable_sort(_RandomAccessIterator __first,
3531 if (__last - __first < 15)
3533 std::__insertion_sort(__first, __last, __comp);
3536 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3537 std::__inplace_stable_sort(__first, __middle, __comp);
3539 std::__merge_without_buffer(__first, __middle, __last,
3540 __middle - __first,
3666 * @param __first Start of range.
3677 next_permutation(_BidirectionalIterator __first,
3685 __glibcxx_requires_valid_range(__first, __last);
3687 if (__first == __last)
3689 _BidirectionalIterator __i = __first;
3709 if (__i == __first)
3711 std::reverse(__first, __last);
3721 * @param __first Start of range.
3726 * Treats all permutations of the range [__first,__last) as a set of
3734 next_permutation(_BidirectionalIterator __first,
3743 __glibcxx_requires_valid_range(__first, __last);
3745 if (__first == __last)
3747 _BidirectionalIterator __i = __first;
3767 if (__i == __first)
3769 std::reverse(__first, __last);
3778 * @param __first Start of range.
3790 prev_permutation(_BidirectionalIterator __first,
3798 __glibcxx_requires_valid_range(__first, __last);
3800 if (__first == __last)
3802 _BidirectionalIterator __i = __first;
3822 if (__i == __first)
3824 std::reverse(__first, __last);
3834 * @param __first Start of range.
3839 * Treats all permutations of the range [__first,__last) as a set of
3847 prev_permutation(_BidirectionalIterator __first,
3856 __glibcxx_requires_valid_range(__first, __last);
3858 if (__first == __last)
3860 _BidirectionalIterator __i = __first;
3880 if (__i == __first)
3882 std::reverse(__first, __last);
3894 * @param __first An input iterator.
3901 * Copies each element in the input range @p [__first,__last) to the
3902 * output range @p [__result,__result+(__last-__first)) replacing elements
3907 replace_copy(_InputIterator __first, _InputIterator __last,
3917 __glibcxx_requires_valid_range(__first, __last);
3919 for (; __first != __last; ++__first, ++__result)
3920 if (*__first == __old_value)
3923 *__result = *__first;
3931 * @param __first An input iterator.
3936 * @return The end of the output sequence, @p __result+(__last-__first).
3938 * Copies each element in the range @p [__first,__last) to the range
3939 * @p [__result,__result+(__last-__first)) replacing elements for which
3945 replace_copy_if(_InputIterator __first, _InputIterator __last,
3955 __glibcxx_requires_valid_range(__first, __last);
3957 for (; __first != __last; ++__first, ++__result)
3958 if (__pred(*__first))
3961 *__result = *__first;
3969 * @param __first An iterator.
3975 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3976 { return std::is_sorted_until(__first, __last) == __last; }
3982 * @param __first An iterator.
3989 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3991 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3996 * @param __first An iterator.
3998 * @return An iterator pointing to the last iterator i in [__first, __last)
3999 * for which the range [__first, i) is sorted.
4003 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
4009 __glibcxx_requires_valid_range(__first, __last);
4011 if (__first == __last)
4014 _ForwardIterator __next = __first;
4015 for (++__next; __next != __last; __first = __next, ++__next)
4016 if (*__next < *__first)
4024 * @param __first An iterator.
4027 * @return An iterator pointing to the last iterator i in [__first, __last)
4028 * for which the range [__first, i) is sorted.
4032 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4040 __glibcxx_requires_valid_range(__first, __last);
4042 if (__first == __last)
4045 _ForwardIterator __next = __first;
4046 for (++__next; __next != __last; __first = __next, ++__next)
4047 if (__comp(*__next, *__first))
4092 * @param __first Start of range.
4095 * [__first, __last) such that no other element in the range is
4096 * smaller, and where M is the last iterator i in [__first, __last)
4101 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4107 __glibcxx_requires_valid_range(__first, __last);
4109 _ForwardIterator __next = __first;
4110 if (__first == __last
4112 return std::make_pair(__first, __first);
4115 if (*__next < *__first)
4118 __max = __first;
4122 __min = __first;
4126 __first = __next;
4127 ++__first;
4129 while (__first != __last)
4131 __next = __first;
4134 if (*__first < *__min)
4135 __min = __first;
4136 else if (!(*__first < *__max))
4137 __max = __first;
4141 if (*__next < *__first)
4145 if (!(*__first < *__max))
4146 __max = __first;
4150 if (*__first < *__min)
4151 __min = __first;
4156 __first = __next;
4157 ++__first;
4167 * @param __first Start of range.
4171 * [__first, __last) such that no other element in the range is
4172 * smaller, and where M is the last iterator i in [__first, __last)
4177 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4185 __glibcxx_requires_valid_range(__first, __last);
4187 _ForwardIterator __next = __first;
4188 if (__first == __last
4190 return std::make_pair(__first, __first);
4193 if (__comp(*__next, *__first))
4196 __max = __first;
4200 __min = __first;
4204 __first = __next;
4205 ++__first;
4207 while (__first != __last)
4209 __next = __first;
4212 if (__comp(*__first, *__min))
4213 __min = __first;
4214 else if (!__comp(*__first, *__max))
4215 __max = __first;
4219 if (__comp(*__next, *__first))
4223 if (!__comp(*__first, *__max))
4224 __max = __first;
4228 if (__comp(*__first, *__min))
4229 __min = __first;
4234 __first = __next;
4235 ++__first;
4379 * @param __first A forward iterator.
4384 * Reorders the elements in the range @p [__first,__last) using @p __g to
4390 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4396 __glibcxx_requires_valid_range(__first, __last);
4398 if (__first == __last)
4409 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4410 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4423 * @param __first An input iterator.
4434 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4438 __glibcxx_requires_valid_range(__first, __last);
4439 for (; __first != __last; ++__first)
4440 __f(*__first);
4447 * @param __first An input iterator.
4450 * @return The first iterator @c i in the range @p [__first,__last)
4455 find(_InputIterator __first, _InputIterator __last,
4462 __glibcxx_requires_valid_range(__first, __last);
4463 return std::__find(__first, __last, __val,
4464 std::__iterator_category(__first));
4471 * @param __first An input iterator.
4474 * @return The first iterator @c i in the range @p [__first,__last)
4479 find_if(_InputIterator __first, _InputIterator __last,
4486 __glibcxx_requires_valid_range(__first, __last);
4487 return std::__find_if(__first, __last, __pred,
4488 std::__iterator_category(__first));
4573 * @param __first A forward iterator.
4576 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4581 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4587 __glibcxx_requires_valid_range(__first, __last);
4588 if (__first == __last)
4590 _ForwardIterator __next = __first;
4593 if (*__first == *__next)
4594 return __first;
4595 __first = __next;
4603 * @param __first A forward iterator.
4607 * valid iterators in @p [__first,__last) and such that
4613 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4621 __glibcxx_requires_valid_range(__first, __last);
4622 if (__first == __last)
4624 _ForwardIterator __next = __first;
4627 if (__binary_pred(*__first, *__next))
4628 return __first;
4629 __first = __next;
4637 * @param __first An input iterator.
4640 * @return The number of iterators @c i in the range @p [__first,__last)
4645 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4651 __glibcxx_requires_valid_range(__first, __last);
4653 for (; __first != __last; ++__first)
4654 if (*__first == __value)
4662 * @param __first An input iterator.
4665 * @return The number of iterators @c i in the range @p [__first,__last)
4670 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4676 __glibcxx_requires_valid_range(__first, __last);
4678 for (; __first != __last; ++__first)
4679 if (__pred(*__first))
4844 * @param __first A forward iterator.
4849 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4853 * Searches the range @p [__first,__last) for @p count consecutive elements
4858 search_n(_ForwardIterator __first, _ForwardIterator __last,
4865 __glibcxx_requires_valid_range(__first, __last);
4868 return __first;
4870 return _GLIBCXX_STD_A::find(__first, __last, __val);
4871 return std::__search_n(__first, __last, __count, __val,
4872 std::__iterator_category(__first));
4880 * @param __first A forward iterator.
4886 * [__first,__last-__count) such that @p
4890 * Searches the range @p [__first,__last) for @p __count
4896 search_n(_ForwardIterator __first, _ForwardIterator __last,
4904 __glibcxx_requires_valid_range(__first, __last);
4907 return __first;
4910 while (__first != __last && !bool(__binary_pred(*__first, __val)))
4911 ++__first;
4912 return __first;
4914 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4915 std::__iterator_category(__first));
4922 * @param __first An input iterator.
4926 * @return An output iterator equal to @p __result+(__last-__first).
4930 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4931 * range @p [0,__last-__first).
4938 transform(_InputIterator __first, _InputIterator __last,
4945 __typeof__(__unary_op(*__first))>)
4946 __glibcxx_requires_valid_range(__first, __last);
4948 for (; __first != __last; ++__first, ++__result)
4949 *__result = __unary_op(*__first);
4996 * @param __first A forward iterator.
5002 * For each iterator @c i in the range @p [__first,__last) if @c *i ==
5007 replace(_ForwardIterator __first, _ForwardIterator __last,
5017 __glibcxx_requires_valid_range(__first, __last);
5019 for (; __first != __last; ++__first)
5020 if (*__first == __old_value)
5021 *__first = __new_value;
5028 * @param __first A forward iterator.
5034 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
5039 replace_if(_ForwardIterator __first, _ForwardIterator __last,
5049 __glibcxx_requires_valid_range(__first, __last);
5051 for (; __first != __last; ++__first)
5052 if (__pred(*__first))
5053 *__first = __new_value;
5060 * @param __first A forward iterator.
5067 * @p [__first,__last).
5071 generate(_ForwardIterator __first, _ForwardIterator __last,
5078 __glibcxx_requires_valid_range(__first, __last);
5080 for (; __first != __last; ++__first)
5081 *__first = __gen();
5088 * @param __first A forward iterator.
5092 * @return The end of the sequence, @p __first+__n
5095 * @p [__first,__first+__n).
5102 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5110 __niter > 0; --__niter, ++__first)
5111 *__first = __gen();
5112 return __first;
5119 * @param __first An input iterator.
5124 * Copies each element in the range @p [__first,__last) to the range
5139 unique_copy(_InputIterator __first, _InputIterator __last,
5148 __glibcxx_requires_valid_range(__first, __last);
5150 if (__first == __last)
5152 return std::__unique_copy(__first, __last, __result,
5153 std::__iterator_category(__first),
5160 * @param __first An input iterator.
5166 * Copies each element in the range @p [__first,__last) to the range
5179 unique_copy(_InputIterator __first, _InputIterator __last,
5187 __glibcxx_requires_valid_range(__first, __last);
5189 if (__first == __last)
5191 return std::__unique_copy(__first, __last, __result, __binary_pred,
5192 std::__iterator_category(__first),
5200 * @param __first A forward iterator.
5204 * Reorder the elements in the range @p [__first,__last) using a random
5210 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5215 __glibcxx_requires_valid_range(__first, __last);
5217 if (__first != __last)
5218 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5219 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5226 * @param __first A forward iterator.
5231 * Reorders the elements in the range @p [__first,__last) using @p __rand to
5238 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5248 __glibcxx_requires_valid_range(__first, __last);
5250 if (__first == __last)
5252 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5253 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
5261 * @param __first A forward iterator.
5265 * iterator @p i in the range @p [__first,middle) and false for each @p i
5274 partition(_ForwardIterator __first, _ForwardIterator __last,
5282 __glibcxx_requires_valid_range(__first, __last);
5284 return std::__partition(__first, __last, __pred,
5285 std::__iterator_category(__first));
5293 * @param __first An iterator.
5298 * Sorts the smallest @p (__middle-__first) elements in the range
5299 * @p [first,last) and moves them to the range @p [__first,__middle). The
5303 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5308 partial_sort(_RandomAccessIterator __first,
5319 __glibcxx_requires_valid_range(__first, __middle);
5322 std::__heap_select(__first, __middle, __last);
5323 std::sort_heap(__first, __middle);
5330 * @param __first An iterator.
5336 * Sorts the smallest @p (__middle-__first) elements in the range
5337 * @p [__first,__last) and moves them to the range @p [__first,__middle). The
5341 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5347 partial_sort(_RandomAccessIterator __first,
5360 __glibcxx_requires_valid_range(__first, __middle);
5363 std::__heap_select(__first, __middle, __last, __comp);
5364 std::sort_heap(__first, __middle, __comp);
5370 * @param __first An iterator.
5375 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5379 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5384 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5394 __glibcxx_requires_valid_range(__first, __nth);
5397 if (__first == __last || __nth == __last)
5400 std::__introselect(__first, __nth, __last,
5401 std::__lg(__last - __first) * 2);
5408 * @param __first An iterator.
5414 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5418 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5423 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5434 __glibcxx_requires_valid_range(__first, __nth);
5437 if (__first == __last || __nth == __last)
5440 std::__introselect(__first, __nth, __last,
5441 std::__lg(__last - __first) * 2, __comp);
5448 * @param __first An iterator.
5452 * Sorts the elements in the range @p [__first,__last) in ascending order,
5453 * such that for each iterator @e i in the range @p [__first,__last-1),
5461 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5470 __glibcxx_requires_valid_range(__first, __last);
5472 if (__first != __last)
5474 std::__introsort_loop(__first, __last,
5475 std::__lg(__last - __first) * 2);
5476 std::__final_insertion_sort(__first, __last);
5483 * @param __first An iterator.
5488 * Sorts the elements in the range @p [__first,__last) in ascending order,
5490 * range @p [__first,__last-1).
5497 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5508 __glibcxx_requires_valid_range(__first, __last);
5510 if (__first != __last)
5512 std::__introsort_loop(__first, __last,
5513 std::__lg(__last - __first) * 2, __comp);
5514 std::__final_insertion_sort(__first, __last, __comp);
5648 * @param __first An iterator.
5652 * Sorts the elements in the range @p [__first,__last) in ascending order,
5653 * such that for each iterator @p i in the range @p [__first,__last-1),
5657 * elements @p x and @p y in the range @p [__first,__last) such that
5663 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5674 __glibcxx_requires_valid_range(__first, __last);
5676 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5679 std::__inplace_stable_sort(__first, __last);
5681 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5689 * @param __first An iterator.
5694 * Sorts the elements in the range @p [__first,__last) in ascending order,
5695 * such that for each iterator @p i in the range @p [__first,__last-1),
5699 * elements @p x and @p y in the range @p [__first,__last) such that
5705 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5719 __glibcxx_requires_valid_range(__first, __last);
5721 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5724 std::__inplace_stable_sort(__first, __last, __comp);
5726 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
6236 * @param __first Start of range.
6242 min_element(_ForwardIterator __first, _ForwardIterator __last)
6248 __glibcxx_requires_valid_range(__first, __last);
6250 if (__first == __last)
6251 return __first;
6252 _ForwardIterator __result = __first;
6253 while (++__first != __last)
6254 if (*__first < *__result)
6255 __result = __first;
6262 * @param __first Start of range.
6270 min_element(_ForwardIterator __first, _ForwardIterator __last,
6278 __glibcxx_requires_valid_range(__first, __last);
6280 if (__first == __last)
6281 return __first;
6282 _ForwardIterator __result = __first;
6283 while (++__first != __last)
6284 if (__comp(*__first, *__result))
6285 __result = __first;
6292 * @param __first Start of range.
6298 max_element(_ForwardIterator __first, _ForwardIterator __last)
6304 __glibcxx_requires_valid_range(__first, __last);
6306 if (__first == __last)
6307 return __first;
6308 _ForwardIterator __result = __first;
6309 while (++__first != __last)
6310 if (*__result < *__first)
6311 __result = __first;
6318 * @param __first Start of range.
6326 max_element(_ForwardIterator __first, _ForwardIterator __last,
6334 __glibcxx_requires_valid_range(__first, __last);
6336 if (__first == __last) return __first;
6337 _ForwardIterator __result = __first;
6338 while (++__first != __last)
6339 if (__comp(*__result, *__first))
6340 __result = __first;