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