1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___ALGORITHM_SORT_H 10 #define _LIBCPP___ALGORITHM_SORT_H 11 12 #include <__algorithm/comp.h> 13 #include <__algorithm/comp_ref_type.h> 14 #include <__algorithm/min_element.h> 15 #include <__algorithm/partial_sort.h> 16 #include <__algorithm/unwrap_iter.h> 17 #include <__bits> 18 #include <__config> 19 #include <__debug> 20 #include <__debug_utils/randomize_range.h> 21 #include <__functional/operations.h> 22 #include <__functional/ranges_operations.h> 23 #include <__iterator/iterator_traits.h> 24 #include <__utility/swap.h> 25 #include <climits> 26 #include <memory> 27 28 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 29 # pragma GCC system_header 30 #endif 31 32 _LIBCPP_BEGIN_NAMESPACE_STD 33 34 // stable, 2-3 compares, 0-2 swaps 35 36 template <class _Compare, class _ForwardIterator> 37 _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, 38 _Compare __c) { 39 unsigned __r = 0; 40 if (!__c(*__y, *__x)) // if x <= y 41 { 42 if (!__c(*__z, *__y)) // if y <= z 43 return __r; // x <= y && y <= z 44 // x <= y && y > z 45 swap(*__y, *__z); // x <= z && y < z 46 __r = 1; 47 if (__c(*__y, *__x)) // if x > y 48 { 49 swap(*__x, *__y); // x < y && y <= z 50 __r = 2; 51 } 52 return __r; // x <= y && y < z 53 } 54 if (__c(*__z, *__y)) // x > y, if y > z 55 { 56 swap(*__x, *__z); // x < y && y < z 57 __r = 1; 58 return __r; 59 } 60 swap(*__x, *__y); // x > y && y <= z 61 __r = 1; // x < y && x <= z 62 if (__c(*__z, *__y)) // if y > z 63 { 64 swap(*__y, *__z); // x <= y && y < z 65 __r = 2; 66 } 67 return __r; 68 } // x <= y && y <= z 69 70 // stable, 3-6 compares, 0-5 swaps 71 72 template <class _Compare, class _ForwardIterator> 73 unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, 74 _Compare __c) { 75 unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); 76 if (__c(*__x4, *__x3)) { 77 swap(*__x3, *__x4); 78 ++__r; 79 if (__c(*__x3, *__x2)) { 80 swap(*__x2, *__x3); 81 ++__r; 82 if (__c(*__x2, *__x1)) { 83 swap(*__x1, *__x2); 84 ++__r; 85 } 86 } 87 } 88 return __r; 89 } 90 91 // stable, 4-10 compares, 0-9 swaps 92 93 template <class _Compare, class _ForwardIterator> 94 _LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 95 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { 96 unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 97 if (__c(*__x5, *__x4)) { 98 swap(*__x4, *__x5); 99 ++__r; 100 if (__c(*__x4, *__x3)) { 101 swap(*__x3, *__x4); 102 ++__r; 103 if (__c(*__x3, *__x2)) { 104 swap(*__x2, *__x3); 105 ++__r; 106 if (__c(*__x2, *__x1)) { 107 swap(*__x1, *__x2); 108 ++__r; 109 } 110 } 111 } 112 } 113 return __r; 114 } 115 116 // The comparator being simple is a prerequisite for using the branchless optimization. 117 template <class _Tp> 118 struct __is_simple_comparator : false_type {}; 119 template <class _Tp> 120 struct __is_simple_comparator<__less<_Tp>&> : true_type {}; 121 template <class _Tp> 122 struct __is_simple_comparator<less<_Tp>&> : true_type {}; 123 template <class _Tp> 124 struct __is_simple_comparator<greater<_Tp>&> : true_type {}; 125 #if _LIBCPP_STD_VER > 17 126 template <> 127 struct __is_simple_comparator<ranges::less&> : true_type {}; 128 template <> 129 struct __is_simple_comparator<ranges::greater&> : true_type {}; 130 #endif 131 132 template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type> 133 using __use_branchless_sort = 134 integral_constant<bool, __is_cpp17_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) && 135 is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>; 136 137 // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. 138 template <class _Compare, class _RandomAccessIterator> 139 inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) { 140 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 141 bool __r = __c(*__x, *__y); 142 value_type __tmp = __r ? *__x : *__y; 143 *__y = __r ? *__y : *__x; 144 *__x = __tmp; 145 } 146 147 // Ensures that *__x, *__y and *__z are ordered according to the comparator __c, 148 // under the assumption that *__y and *__z are already ordered. 149 template <class _Compare, class _RandomAccessIterator> 150 inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, 151 _RandomAccessIterator __z, _Compare __c) { 152 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 153 bool __r = __c(*__z, *__x); 154 value_type __tmp = __r ? *__z : *__x; 155 *__z = __r ? *__x : *__z; 156 __r = __c(__tmp, *__y); 157 *__x = __r ? *__x : *__y; 158 *__y = __r ? *__y : __tmp; 159 } 160 161 template <class _Compare, class _RandomAccessIterator> 162 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 163 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 164 _Compare __c) { 165 _VSTD::__cond_swap<_Compare>(__x2, __x3, __c); 166 _VSTD::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c); 167 } 168 169 template <class _Compare, class _RandomAccessIterator> 170 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 171 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 172 _Compare __c) { 173 _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); 174 } 175 176 template <class _Compare, class _RandomAccessIterator> 177 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 178 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 179 _RandomAccessIterator __x4, _Compare __c) { 180 _VSTD::__cond_swap<_Compare>(__x1, __x3, __c); 181 _VSTD::__cond_swap<_Compare>(__x2, __x4, __c); 182 _VSTD::__cond_swap<_Compare>(__x1, __x2, __c); 183 _VSTD::__cond_swap<_Compare>(__x3, __x4, __c); 184 _VSTD::__cond_swap<_Compare>(__x2, __x3, __c); 185 } 186 187 template <class _Compare, class _RandomAccessIterator> 188 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 189 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 190 _RandomAccessIterator __x4, _Compare __c) { 191 _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 192 } 193 194 template <class _Compare, class _RandomAccessIterator> 195 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 196 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 197 _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { 198 _VSTD::__cond_swap<_Compare>(__x1, __x2, __c); 199 _VSTD::__cond_swap<_Compare>(__x4, __x5, __c); 200 _VSTD::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c); 201 _VSTD::__cond_swap<_Compare>(__x2, __x5, __c); 202 _VSTD::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c); 203 _VSTD::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c); 204 } 205 206 template <class _Compare, class _RandomAccessIterator> 207 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 208 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 209 _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { 210 _VSTD::__sort5<_Compare>(__x1, __x2, __x3, __x4, __x5, __c); 211 } 212 213 // Assumes size > 0 214 template <class _Compare, class _BidirectionalIterator> 215 _LIBCPP_CONSTEXPR_AFTER_CXX11 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, 216 _Compare __comp) { 217 _BidirectionalIterator __lm1 = __last; 218 for (--__lm1; __first != __lm1; ++__first) { 219 _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp); 220 if (__i != __first) 221 swap(*__first, *__i); 222 } 223 } 224 225 template <class _Compare, class _BidirectionalIterator> 226 void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { 227 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 228 if (__first != __last) { 229 _BidirectionalIterator __i = __first; 230 for (++__i; __i != __last; ++__i) { 231 _BidirectionalIterator __j = __i; 232 value_type __t(_VSTD::move(*__j)); 233 for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 234 *__j = _VSTD::move(*__k); 235 *__j = _VSTD::move(__t); 236 } 237 } 238 } 239 240 template <class _Compare, class _RandomAccessIterator> 241 void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 242 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 243 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 244 _RandomAccessIterator __j = __first + difference_type(2); 245 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); 246 for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { 247 if (__comp(*__i, *__j)) { 248 value_type __t(_VSTD::move(*__i)); 249 _RandomAccessIterator __k = __j; 250 __j = __i; 251 do { 252 *__j = _VSTD::move(*__k); 253 __j = __k; 254 } while (__j != __first && __comp(__t, *--__k)); 255 *__j = _VSTD::move(__t); 256 } 257 __j = __i; 258 } 259 } 260 261 template <class _Compare, class _RandomAccessIterator> 262 bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 263 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 264 switch (__last - __first) { 265 case 0: 266 case 1: 267 return true; 268 case 2: 269 if (__comp(*--__last, *__first)) 270 swap(*__first, *__last); 271 return true; 272 case 3: 273 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); 274 return true; 275 case 4: 276 _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 277 --__last, __comp); 278 return true; 279 case 5: 280 _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 281 __first + difference_type(3), --__last, __comp); 282 return true; 283 } 284 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 285 _RandomAccessIterator __j = __first + difference_type(2); 286 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); 287 const unsigned __limit = 8; 288 unsigned __count = 0; 289 for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { 290 if (__comp(*__i, *__j)) { 291 value_type __t(_VSTD::move(*__i)); 292 _RandomAccessIterator __k = __j; 293 __j = __i; 294 do { 295 *__j = _VSTD::move(*__k); 296 __j = __k; 297 } while (__j != __first && __comp(__t, *--__k)); 298 *__j = _VSTD::move(__t); 299 if (++__count == __limit) 300 return ++__i == __last; 301 } 302 __j = __i; 303 } 304 return true; 305 } 306 307 template <class _Compare, class _BidirectionalIterator> 308 void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, 309 typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) { 310 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 311 if (__first1 != __last1) { 312 __destruct_n __d(0); 313 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 314 value_type* __last2 = __first2; 315 ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); 316 __d.template __incr<value_type>(); 317 for (++__last2; ++__first1 != __last1; ++__last2) { 318 value_type* __j2 = __last2; 319 value_type* __i2 = __j2; 320 if (__comp(*__first1, *--__i2)) { 321 ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); 322 __d.template __incr<value_type>(); 323 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 324 *__j2 = _VSTD::move(*__i2); 325 *__j2 = _VSTD::move(*__first1); 326 } else { 327 ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); 328 __d.template __incr<value_type>(); 329 } 330 } 331 __h.release(); 332 } 333 } 334 335 template <class _Compare, class _RandomAccessIterator> 336 void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 337 typename iterator_traits<_RandomAccessIterator>::difference_type __depth) { 338 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 339 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 340 const difference_type __limit = 341 is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6; 342 while (true) { 343 __restart: 344 difference_type __len = __last - __first; 345 switch (__len) { 346 case 0: 347 case 1: 348 return; 349 case 2: 350 if (__comp(*--__last, *__first)) 351 swap(*__first, *__last); 352 return; 353 case 3: 354 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); 355 return; 356 case 4: 357 _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 358 --__last, __comp); 359 return; 360 case 5: 361 _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 362 __first + difference_type(3), --__last, __comp); 363 return; 364 } 365 if (__len <= __limit) { 366 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 367 return; 368 } 369 // __len > 5 370 if (__depth == 0) { 371 // Fallback to heap sort as Introsort suggests. 372 _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp); 373 return; 374 } 375 --__depth; 376 _RandomAccessIterator __m = __first; 377 _RandomAccessIterator __lm1 = __last; 378 --__lm1; 379 unsigned __n_swaps; 380 { 381 difference_type __delta; 382 if (__len >= 1000) { 383 __delta = __len / 2; 384 __m += __delta; 385 __delta /= 2; 386 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp); 387 } else { 388 __delta = __len / 2; 389 __m += __delta; 390 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 391 } 392 } 393 // *__m is median 394 // partition [__first, __m) < *__m and *__m <= [__m, __last) 395 // (this inhibits tossing elements equivalent to __m around unnecessarily) 396 _RandomAccessIterator __i = __first; 397 _RandomAccessIterator __j = __lm1; 398 // j points beyond range to be tested, *__m is known to be <= *__lm1 399 // The search going up is known to be guarded but the search coming down isn't. 400 // Prime the downward search with a guard. 401 if (!__comp(*__i, *__m)) // if *__first == *__m 402 { 403 // *__first == *__m, *__first doesn't go in first part 404 // manually guard downward moving __j against __i 405 while (true) { 406 if (__i == --__j) { 407 // *__first == *__m, *__m <= all other elements 408 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 409 ++__i; // __first + 1 410 __j = __last; 411 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 412 { 413 while (true) { 414 if (__i == __j) 415 return; // [__first, __last) all equivalent elements 416 if (__comp(*__first, *__i)) { 417 swap(*__i, *__j); 418 ++__n_swaps; 419 ++__i; 420 break; 421 } 422 ++__i; 423 } 424 } 425 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 426 if (__i == __j) 427 return; 428 while (true) { 429 while (!__comp(*__first, *__i)) 430 ++__i; 431 while (__comp(*__first, *--__j)) 432 ; 433 if (__i >= __j) 434 break; 435 swap(*__i, *__j); 436 ++__n_swaps; 437 ++__i; 438 } 439 // [__first, __i) == *__first and *__first < [__i, __last) 440 // The first part is sorted, sort the second part 441 // _VSTD::__sort<_Compare>(__i, __last, __comp); 442 __first = __i; 443 goto __restart; 444 } 445 if (__comp(*__j, *__m)) { 446 swap(*__i, *__j); 447 ++__n_swaps; 448 break; // found guard for downward moving __j, now use unguarded partition 449 } 450 } 451 } 452 // It is known that *__i < *__m 453 ++__i; 454 // j points beyond range to be tested, *__m is known to be <= *__lm1 455 // if not yet partitioned... 456 if (__i < __j) { 457 // known that *(__i - 1) < *__m 458 // known that __i <= __m 459 while (true) { 460 // __m still guards upward moving __i 461 while (__comp(*__i, *__m)) 462 ++__i; 463 // It is now known that a guard exists for downward moving __j 464 while (!__comp(*--__j, *__m)) 465 ; 466 if (__i > __j) 467 break; 468 swap(*__i, *__j); 469 ++__n_swaps; 470 // It is known that __m != __j 471 // If __m just moved, follow it 472 if (__m == __i) 473 __m = __j; 474 ++__i; 475 } 476 } 477 // [__first, __i) < *__m and *__m <= [__i, __last) 478 if (__i != __m && __comp(*__m, *__i)) { 479 swap(*__i, *__m); 480 ++__n_swaps; 481 } 482 // [__first, __i) < *__i and *__i <= [__i+1, __last) 483 // If we were given a perfect partition, see if insertion sort is quick... 484 if (__n_swaps == 0) { 485 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 486 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + difference_type(1), __last, __comp)) { 487 if (__fs) 488 return; 489 __last = __i; 490 continue; 491 } else { 492 if (__fs) { 493 __first = ++__i; 494 continue; 495 } 496 } 497 } 498 // sort smaller range with recursive call and larger with tail recursion elimination 499 if (__i - __first < __last - __i) { 500 _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth); 501 __first = ++__i; 502 } else { 503 _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth); 504 __last = __i; 505 } 506 } 507 } 508 509 template <typename _Number> 510 inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { 511 if (__n == 0) 512 return 0; 513 if (sizeof(__n) <= sizeof(unsigned)) 514 return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned>(__n)); 515 if (sizeof(__n) <= sizeof(unsigned long)) 516 return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n)); 517 if (sizeof(__n) <= sizeof(unsigned long long)) 518 return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n)); 519 520 _Number __log2 = 0; 521 while (__n > 1) { 522 __log2++; 523 __n >>= 1; 524 } 525 return __log2; 526 } 527 528 template <class _Compare, class _RandomAccessIterator> 529 void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 530 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 531 difference_type __depth_limit = 2 * __log2i(__last - __first); 532 _VSTD::__introsort<_Compare>(__first, __last, __comp, __depth_limit); 533 } 534 535 template <class _Compare, class _Tp> 536 inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) { 537 __less<uintptr_t> __comp; 538 _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); 539 } 540 541 extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&); 542 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 543 extern template _LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 544 #endif 545 extern template _LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 546 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 547 extern template _LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&); 548 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 549 extern template _LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&); 550 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 551 extern template _LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&); 552 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 553 extern template _LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 554 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); 555 extern template _LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&); 556 extern template _LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&); 557 extern template _LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 558 559 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&); 560 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 561 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 562 #endif 563 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 564 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 565 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&); 566 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 567 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&); 568 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 569 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&); 570 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 571 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 572 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); 573 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&); 574 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&); 575 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 576 577 extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&); 578 579 template <class _RandomAccessIterator, class _Comp> 580 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 581 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { 582 std::__debug_randomize_range(__first, __last); 583 using _Comp_ref = typename __comp_ref_type<_Comp>::type; 584 if (__libcpp_is_constant_evaluated()) { 585 std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); 586 } else { 587 std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp)); 588 } 589 } 590 591 template <class _RandomAccessIterator, class _Comp> 592 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 593 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { 594 std::__sort_impl(std::move(__first), std::move(__last), __comp); 595 } 596 597 template <class _RandomAccessIterator> 598 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 599 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { 600 std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 601 } 602 603 _LIBCPP_END_NAMESPACE_STD 604 605 #endif // _LIBCPP___ALGORITHM_SORT_H 606