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