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