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