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