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