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 <__config> 18 #include <__utility/swap.h> 19 #include <memory> 20 21 #if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) 22 # include <__algorithm/shuffle.h> 23 #endif 24 25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26 # pragma GCC system_header 27 #endif 28 29 _LIBCPP_BEGIN_NAMESPACE_STD 30 31 // stable, 2-3 compares, 0-2 swaps 32 33 template <class _Compare, class _ForwardIterator> 34 _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned 35 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) 36 { 37 unsigned __r = 0; 38 if (!__c(*__y, *__x)) // if x <= y 39 { 40 if (!__c(*__z, *__y)) // if y <= z 41 return __r; // x <= y && y <= z 42 // x <= y && y > z 43 swap(*__y, *__z); // x <= z && y < z 44 __r = 1; 45 if (__c(*__y, *__x)) // if x > y 46 { 47 swap(*__x, *__y); // x < y && y <= z 48 __r = 2; 49 } 50 return __r; // x <= y && y < z 51 } 52 if (__c(*__z, *__y)) // x > y, if y > z 53 { 54 swap(*__x, *__z); // x < y && y < z 55 __r = 1; 56 return __r; 57 } 58 swap(*__x, *__y); // x > y && y <= z 59 __r = 1; // x < y && x <= z 60 if (__c(*__z, *__y)) // if y > z 61 { 62 swap(*__y, *__z); // x <= y && y < z 63 __r = 2; 64 } 65 return __r; 66 } // x <= y && y <= z 67 68 // stable, 3-6 compares, 0-5 swaps 69 70 template <class _Compare, class _ForwardIterator> 71 unsigned 72 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 73 _ForwardIterator __x4, _Compare __c) 74 { 75 unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); 76 if (__c(*__x4, *__x3)) 77 { 78 swap(*__x3, *__x4); 79 ++__r; 80 if (__c(*__x3, *__x2)) 81 { 82 swap(*__x2, *__x3); 83 ++__r; 84 if (__c(*__x2, *__x1)) 85 { 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 98 unsigned 99 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 100 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) 101 { 102 unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 103 if (__c(*__x5, *__x4)) 104 { 105 swap(*__x4, *__x5); 106 ++__r; 107 if (__c(*__x4, *__x3)) 108 { 109 swap(*__x3, *__x4); 110 ++__r; 111 if (__c(*__x3, *__x2)) 112 { 113 swap(*__x2, *__x3); 114 ++__r; 115 if (__c(*__x2, *__x1)) 116 { 117 swap(*__x1, *__x2); 118 ++__r; 119 } 120 } 121 } 122 } 123 return __r; 124 } 125 126 template <class _Tp> 127 struct __is_simple_comparator : false_type {}; 128 template <class _Tp> 129 struct __is_simple_comparator<__less<_Tp>&> : true_type {}; 130 template <class _Tp> 131 struct __is_simple_comparator<less<_Tp>&> : true_type {}; 132 template <class _Tp> 133 struct __is_simple_comparator<greater<_Tp>&> : true_type {}; 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 219 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 220 { 221 _BidirectionalIterator __lm1 = __last; 222 for (--__lm1; __first != __lm1; ++__first) 223 { 224 _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp); 225 if (__i != __first) 226 swap(*__first, *__i); 227 } 228 } 229 230 template <class _Compare, class _BidirectionalIterator> 231 void 232 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 233 { 234 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 235 if (__first != __last) 236 { 237 _BidirectionalIterator __i = __first; 238 for (++__i; __i != __last; ++__i) 239 { 240 _BidirectionalIterator __j = __i; 241 value_type __t(_VSTD::move(*__j)); 242 for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 243 *__j = _VSTD::move(*__k); 244 *__j = _VSTD::move(__t); 245 } 246 } 247 } 248 249 template <class _Compare, class _RandomAccessIterator> 250 void 251 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 252 { 253 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 254 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 255 _RandomAccessIterator __j = __first+difference_type(2); 256 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); 257 for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i) 258 { 259 if (__comp(*__i, *__j)) 260 { 261 value_type __t(_VSTD::move(*__i)); 262 _RandomAccessIterator __k = __j; 263 __j = __i; 264 do 265 { 266 *__j = _VSTD::move(*__k); 267 __j = __k; 268 } while (__j != __first && __comp(__t, *--__k)); 269 *__j = _VSTD::move(__t); 270 } 271 __j = __i; 272 } 273 } 274 275 template <class _Compare, class _RandomAccessIterator> 276 bool 277 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 278 { 279 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 280 switch (__last - __first) 281 { 282 case 0: 283 case 1: 284 return true; 285 case 2: 286 if (__comp(*--__last, *__first)) 287 swap(*__first, *__last); 288 return true; 289 case 3: 290 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); 291 return true; 292 case 4: 293 _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 294 --__last, __comp); 295 return true; 296 case 5: 297 _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 298 __first + difference_type(3), --__last, __comp); 299 return true; 300 } 301 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 302 _RandomAccessIterator __j = __first+difference_type(2); 303 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); 304 const unsigned __limit = 8; 305 unsigned __count = 0; 306 for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i) 307 { 308 if (__comp(*__i, *__j)) 309 { 310 value_type __t(_VSTD::move(*__i)); 311 _RandomAccessIterator __k = __j; 312 __j = __i; 313 do 314 { 315 *__j = _VSTD::move(*__k); 316 __j = __k; 317 } while (__j != __first && __comp(__t, *--__k)); 318 *__j = _VSTD::move(__t); 319 if (++__count == __limit) 320 return ++__i == __last; 321 } 322 __j = __i; 323 } 324 return true; 325 } 326 327 template <class _Compare, class _BidirectionalIterator> 328 void 329 __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, 330 typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) 331 { 332 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 333 if (__first1 != __last1) 334 { 335 __destruct_n __d(0); 336 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 337 value_type* __last2 = __first2; 338 ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); 339 __d.template __incr<value_type>(); 340 for (++__last2; ++__first1 != __last1; ++__last2) 341 { 342 value_type* __j2 = __last2; 343 value_type* __i2 = __j2; 344 if (__comp(*__first1, *--__i2)) 345 { 346 ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); 347 __d.template __incr<value_type>(); 348 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 349 *__j2 = _VSTD::move(*__i2); 350 *__j2 = _VSTD::move(*__first1); 351 } 352 else 353 { 354 ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); 355 __d.template __incr<value_type>(); 356 } 357 } 358 __h.release(); 359 } 360 } 361 362 template <class _Compare, class _RandomAccessIterator> 363 void 364 __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 365 typename iterator_traits<_RandomAccessIterator>::difference_type __depth) 366 { 367 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 368 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 369 const difference_type __limit = is_trivially_copy_constructible<value_type>::value && 370 is_trivially_copy_assignable<value_type>::value ? 30 : 6; 371 while (true) 372 { 373 __restart: 374 difference_type __len = __last - __first; 375 switch (__len) 376 { 377 case 0: 378 case 1: 379 return; 380 case 2: 381 if (__comp(*--__last, *__first)) 382 swap(*__first, *__last); 383 return; 384 case 3: 385 _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); 386 return; 387 case 4: 388 _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 389 --__last, __comp); 390 return; 391 case 5: 392 _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), 393 __first + difference_type(3), --__last, __comp); 394 return; 395 } 396 if (__len <= __limit) 397 { 398 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 399 return; 400 } 401 // __len > 5 402 if (__depth == 0) 403 { 404 // Fallback to heap sort as Introsort suggests. 405 _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp); 406 return; 407 } 408 --__depth; 409 _RandomAccessIterator __m = __first; 410 _RandomAccessIterator __lm1 = __last; 411 --__lm1; 412 unsigned __n_swaps; 413 { 414 difference_type __delta; 415 if (__len >= 1000) 416 { 417 __delta = __len/2; 418 __m += __delta; 419 __delta /= 2; 420 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 421 } 422 else 423 { 424 __delta = __len/2; 425 __m += __delta; 426 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 427 } 428 } 429 // *__m is median 430 // partition [__first, __m) < *__m and *__m <= [__m, __last) 431 // (this inhibits tossing elements equivalent to __m around unnecessarily) 432 _RandomAccessIterator __i = __first; 433 _RandomAccessIterator __j = __lm1; 434 // j points beyond range to be tested, *__m is known to be <= *__lm1 435 // The search going up is known to be guarded but the search coming down isn't. 436 // Prime the downward search with a guard. 437 if (!__comp(*__i, *__m)) // if *__first == *__m 438 { 439 // *__first == *__m, *__first doesn't go in first part 440 // manually guard downward moving __j against __i 441 while (true) 442 { 443 if (__i == --__j) 444 { 445 // *__first == *__m, *__m <= all other elements 446 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 447 ++__i; // __first + 1 448 __j = __last; 449 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 450 { 451 while (true) 452 { 453 if (__i == __j) 454 return; // [__first, __last) all equivalent elements 455 if (__comp(*__first, *__i)) 456 { 457 swap(*__i, *__j); 458 ++__n_swaps; 459 ++__i; 460 break; 461 } 462 ++__i; 463 } 464 } 465 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 466 if (__i == __j) 467 return; 468 while (true) 469 { 470 while (!__comp(*__first, *__i)) 471 ++__i; 472 while (__comp(*__first, *--__j)) 473 ; 474 if (__i >= __j) 475 break; 476 swap(*__i, *__j); 477 ++__n_swaps; 478 ++__i; 479 } 480 // [__first, __i) == *__first and *__first < [__i, __last) 481 // The first part is sorted, sort the second part 482 // _VSTD::__sort<_Compare>(__i, __last, __comp); 483 __first = __i; 484 goto __restart; 485 } 486 if (__comp(*__j, *__m)) 487 { 488 swap(*__i, *__j); 489 ++__n_swaps; 490 break; // found guard for downward moving __j, now use unguarded partition 491 } 492 } 493 } 494 // It is known that *__i < *__m 495 ++__i; 496 // j points beyond range to be tested, *__m is known to be <= *__lm1 497 // if not yet partitioned... 498 if (__i < __j) 499 { 500 // known that *(__i - 1) < *__m 501 // known that __i <= __m 502 while (true) 503 { 504 // __m still guards upward moving __i 505 while (__comp(*__i, *__m)) 506 ++__i; 507 // It is now known that a guard exists for downward moving __j 508 while (!__comp(*--__j, *__m)) 509 ; 510 if (__i > __j) 511 break; 512 swap(*__i, *__j); 513 ++__n_swaps; 514 // It is known that __m != __j 515 // If __m just moved, follow it 516 if (__m == __i) 517 __m = __j; 518 ++__i; 519 } 520 } 521 // [__first, __i) < *__m and *__m <= [__i, __last) 522 if (__i != __m && __comp(*__m, *__i)) 523 { 524 swap(*__i, *__m); 525 ++__n_swaps; 526 } 527 // [__first, __i) < *__i and *__i <= [__i+1, __last) 528 // If we were given a perfect partition, see if insertion sort is quick... 529 if (__n_swaps == 0) 530 { 531 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 532 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+difference_type(1), __last, __comp)) 533 { 534 if (__fs) 535 return; 536 __last = __i; 537 continue; 538 } 539 else 540 { 541 if (__fs) 542 { 543 __first = ++__i; 544 continue; 545 } 546 } 547 } 548 // sort smaller range with recursive call and larger with tail recursion elimination 549 if (__i - __first < __last - __i) 550 { 551 _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth); 552 __first = ++__i; 553 } 554 else 555 { 556 _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth); 557 __last = __i; 558 } 559 } 560 } 561 562 template <typename _Number> 563 inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { 564 _Number __log2 = 0; 565 while (__n > 1) { 566 __log2++; 567 __n >>= 1; 568 } 569 return __log2; 570 } 571 572 template <class _Compare, class _RandomAccessIterator> 573 void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 574 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 575 difference_type __depth_limit = 2 * __log2i(__last - __first); 576 _VSTD::__introsort<_Compare>(__first, __last, __comp, __depth_limit); 577 } 578 579 template <class _Compare, class _Tp> 580 inline _LIBCPP_INLINE_VISIBILITY 581 void 582 __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) 583 { 584 __less<uintptr_t> __comp; 585 _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); 586 } 587 588 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) 589 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 590 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 591 #endif 592 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 593 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 594 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) 595 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 596 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) 597 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 598 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) 599 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 600 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 601 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) 602 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) 603 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) 604 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 605 606 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) 607 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 608 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 609 #endif 610 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 611 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 612 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) 613 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 614 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) 615 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 616 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) 617 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 618 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 619 _LIBCPP_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>&)) 620 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) 621 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) 622 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 623 624 _LIBCPP_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>&)) 625 626 template <class _RandomAccessIterator, class _Compare> 627 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 628 void 629 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 630 { 631 _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); 632 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 633 if (__libcpp_is_constant_evaluated()) { 634 _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); 635 } else { 636 _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp)); 637 } 638 } 639 640 template <class _RandomAccessIterator> 641 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 642 void 643 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 644 { 645 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 646 } 647 648 _LIBCPP_END_NAMESPACE_STD 649 650 #endif // _LIBCPP___ALGORITHM_SORT_H 651