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