Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/11/bits/ranges_util.h
$ cat -n /usr/include/c++/11/bits/ranges_util.h 1 // Utilities for representing and manipulating ranges -*- C++ -*- 2 3 // Copyright (C) 2019-2021 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 //
. 24 25 /** @file bits/ranges_util.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{ranges} 28 */ 29 30 #ifndef _RANGES_UTIL_H 31 #define _RANGES_UTIL_H 1 32 33 #if __cplusplus > 201703L 34 # include
35 36 #ifdef __cpp_lib_ranges 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 _GLIBCXX_BEGIN_NAMESPACE_VERSION 40 namespace ranges 41 { 42 // C++20 24.5 [range.utility] Range utilities 43 44 namespace __detail 45 { 46 template
47 concept __simple_view = view<_Range> && range
48 && same_as
, iterator_t
> 49 && same_as
, sentinel_t
>; 50 51 template
52 concept __has_arrow = input_iterator<_It> 53 && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); }); 54 55 template
56 concept __not_same_as 57 = !same_as
, remove_cvref_t<_Up>>; 58 } // namespace __detail 59 60 /// The ranges::view_interface class template 61 template
62 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>> 63 class view_interface : public view_base 64 { 65 private: 66 constexpr _Derived& _M_derived() noexcept 67 { 68 static_assert(derived_from<_Derived, view_interface<_Derived>>); 69 static_assert(view<_Derived>); 70 return static_cast<_Derived&>(*this); 71 } 72 73 constexpr const _Derived& _M_derived() const noexcept 74 { 75 static_assert(derived_from<_Derived, view_interface<_Derived>>); 76 static_assert(view<_Derived>); 77 return static_cast
(*this); 78 } 79 80 public: 81 constexpr bool 82 empty() requires forward_range<_Derived> 83 { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); } 84 85 constexpr bool 86 empty() const requires forward_range
87 { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); } 88 89 constexpr explicit 90 operator bool() requires requires { ranges::empty(_M_derived()); } 91 { return !ranges::empty(_M_derived()); } 92 93 constexpr explicit 94 operator bool() const requires requires { ranges::empty(_M_derived()); } 95 { return !ranges::empty(_M_derived()); } 96 97 constexpr auto 98 data() requires contiguous_iterator
> 99 { return to_address(ranges::begin(_M_derived())); } 100 101 constexpr auto 102 data() const 103 requires range
104 && contiguous_iterator
> 105 { return to_address(ranges::begin(_M_derived())); } 106 107 constexpr auto 108 size() 109 requires forward_range<_Derived> 110 && sized_sentinel_for
, iterator_t<_Derived>> 111 { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); } 112 113 constexpr auto 114 size() const 115 requires forward_range
116 && sized_sentinel_for
, 117 iterator_t
> 118 { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); } 119 120 constexpr decltype(auto) 121 front() requires forward_range<_Derived> 122 { 123 __glibcxx_assert(!empty()); 124 return *ranges::begin(_M_derived()); 125 } 126 127 constexpr decltype(auto) 128 front() const requires forward_range
129 { 130 __glibcxx_assert(!empty()); 131 return *ranges::begin(_M_derived()); 132 } 133 134 constexpr decltype(auto) 135 back() 136 requires bidirectional_range<_Derived> && common_range<_Derived> 137 { 138 __glibcxx_assert(!empty()); 139 return *ranges::prev(ranges::end(_M_derived())); 140 } 141 142 constexpr decltype(auto) 143 back() const 144 requires bidirectional_range
145 && common_range
146 { 147 __glibcxx_assert(!empty()); 148 return *ranges::prev(ranges::end(_M_derived())); 149 } 150 151 template
152 constexpr decltype(auto) 153 operator[](range_difference_t<_Range> __n) 154 { return ranges::begin(_M_derived())[__n]; } 155 156 template
157 constexpr decltype(auto) 158 operator[](range_difference_t<_Range> __n) const 159 { return ranges::begin(_M_derived())[__n]; } 160 }; 161 162 namespace __detail 163 { 164 template
165 concept __uses_nonqualification_pointer_conversion 166 = is_pointer_v<_From> && is_pointer_v<_To> 167 && !convertible_to
(*)[], 168 remove_pointer_t<_To>(*)[]>; 169 170 template
171 concept __convertible_to_non_slicing = convertible_to<_From, _To> 172 && !__uses_nonqualification_pointer_conversion
, 173 decay_t<_To>>; 174 175 template
176 concept __pair_like 177 = !is_reference_v<_Tp> && requires(_Tp __t) 178 { 179 typename tuple_size<_Tp>::type; 180 requires derived_from
, integral_constant
>; 181 typename tuple_element_t<0, remove_const_t<_Tp>>; 182 typename tuple_element_t<1, remove_const_t<_Tp>>; 183 { get<0>(__t) } -> convertible_to
&>; 184 { get<1>(__t) } -> convertible_to
&>; 185 }; 186 187 template
188 concept __pair_like_convertible_from 189 = !range<_Tp> && __pair_like<_Tp> 190 && constructible_from<_Tp, _Up, _Vp> 191 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>> 192 && convertible_to<_Vp, tuple_element_t<1, _Tp>>; 193 194 } // namespace __detail 195 196 enum class subrange_kind : bool { unsized, sized }; 197 198 /// The ranges::subrange class template 199 template
_Sent = _It, 200 subrange_kind _Kind = sized_sentinel_for<_Sent, _It> 201 ? subrange_kind::sized : subrange_kind::unsized> 202 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>) 203 class subrange : public view_interface
> 204 { 205 private: 206 // XXX: gcc complains when using constexpr here 207 static const bool _S_store_size 208 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>; 209 210 _It _M_begin = _It(); 211 [[no_unique_address]] _Sent _M_end = _Sent(); 212 213 using __size_type 214 = __detail::__make_unsigned_like_t
>; 215 216 template
217 struct _Size 218 { }; 219 220 template
221 struct _Size<_Tp, true> 222 { _Tp _M_size; }; 223 224 [[no_unique_address]] _Size<__size_type> _M_size = {}; 225 226 public: 227 subrange() requires default_initializable<_It> = default; 228 229 constexpr 230 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s) 231 requires (!_S_store_size) 232 : _M_begin(std::move(__i)), _M_end(__s) 233 { } 234 235 constexpr 236 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s, 237 __size_type __n) 238 requires (_Kind == subrange_kind::sized) 239 : _M_begin(std::move(__i)), _M_end(__s) 240 { 241 if constexpr (_S_store_size) 242 _M_size._M_size = __n; 243 } 244 245 template<__detail::__not_same_as
_Rng> 246 requires borrowed_range<_Rng> 247 && __detail::__convertible_to_non_slicing
, _It> 248 && convertible_to
, _Sent> 249 constexpr 250 subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng> 251 : subrange(__r, ranges::size(__r)) 252 { } 253 254 template<__detail::__not_same_as
_Rng> 255 requires borrowed_range<_Rng> 256 && __detail::__convertible_to_non_slicing
, _It> 257 && convertible_to
, _Sent> 258 constexpr 259 subrange(_Rng&& __r) requires (!_S_store_size) 260 : subrange(ranges::begin(__r), ranges::end(__r)) 261 { } 262 263 template
264 requires __detail::__convertible_to_non_slicing
, _It> 265 && convertible_to
, _Sent> 266 constexpr 267 subrange(_Rng&& __r, __size_type __n) 268 requires (_Kind == subrange_kind::sized) 269 : subrange{ranges::begin(__r), ranges::end(__r), __n} 270 { } 271 272 template<__detail::__not_same_as
_PairLike> 273 requires __detail::__pair_like_convertible_from<_PairLike, const _It&, 274 const _Sent&> 275 constexpr 276 operator _PairLike() const 277 { return _PairLike(_M_begin, _M_end); } 278 279 constexpr _It 280 begin() const requires copyable<_It> 281 { return _M_begin; } 282 283 [[nodiscard]] constexpr _It 284 begin() requires (!copyable<_It>) 285 { return std::move(_M_begin); } 286 287 constexpr _Sent end() const { return _M_end; } 288 289 constexpr bool empty() const { return _M_begin == _M_end; } 290 291 constexpr __size_type 292 size() const requires (_Kind == subrange_kind::sized) 293 { 294 if constexpr (_S_store_size) 295 return _M_size._M_size; 296 else 297 return __detail::__to_unsigned_like(_M_end - _M_begin); 298 } 299 300 [[nodiscard]] constexpr subrange 301 next(iter_difference_t<_It> __n = 1) const & 302 requires forward_iterator<_It> 303 { 304 auto __tmp = *this; 305 __tmp.advance(__n); 306 return __tmp; 307 } 308 309 [[nodiscard]] constexpr subrange 310 next(iter_difference_t<_It> __n = 1) && 311 { 312 advance(__n); 313 return std::move(*this); 314 } 315 316 [[nodiscard]] constexpr subrange 317 prev(iter_difference_t<_It> __n = 1) const 318 requires bidirectional_iterator<_It> 319 { 320 auto __tmp = *this; 321 __tmp.advance(-__n); 322 return __tmp; 323 } 324 325 constexpr subrange& 326 advance(iter_difference_t<_It> __n) 327 { 328 // _GLIBCXX_RESOLVE_LIB_DEFECTS 329 // 3433. subrange::advance(n) has UB when n < 0 330 if constexpr (bidirectional_iterator<_It>) 331 if (__n < 0) 332 { 333 ranges::advance(_M_begin, __n); 334 if constexpr (_S_store_size) 335 _M_size._M_size += __detail::__to_unsigned_like(-__n); 336 return *this; 337 } 338 339 __glibcxx_assert(__n >= 0); 340 auto __d = __n - ranges::advance(_M_begin, __n, _M_end); 341 if constexpr (_S_store_size) 342 _M_size._M_size -= __detail::__to_unsigned_like(__d); 343 return *this; 344 } 345 }; 346 347 template
_Sent> 348 subrange(_It, _Sent) -> subrange<_It, _Sent>; 349 350 template
_Sent> 351 subrange(_It, _Sent, 352 __detail::__make_unsigned_like_t
>) 353 -> subrange<_It, _Sent, subrange_kind::sized>; 354 355 template
356 subrange(_Rng&&) 357 -> subrange
, sentinel_t<_Rng>, 358 (sized_range<_Rng> 359 || sized_sentinel_for
, iterator_t<_Rng>>) 360 ? subrange_kind::sized : subrange_kind::unsized>; 361 362 template
363 subrange(_Rng&&, 364 __detail::__make_unsigned_like_t
>) 365 -> subrange
, sentinel_t<_Rng>, subrange_kind::sized>; 366 367 template
368 requires (_Num < 2) 369 constexpr auto 370 get(const subrange<_It, _Sent, _Kind>& __r) 371 { 372 if constexpr (_Num == 0) 373 return __r.begin(); 374 else 375 return __r.end(); 376 } 377 378 template
379 requires (_Num < 2) 380 constexpr auto 381 get(subrange<_It, _Sent, _Kind>&& __r) 382 { 383 if constexpr (_Num == 0) 384 return __r.begin(); 385 else 386 return __r.end(); 387 } 388 389 template
_Sent, 390 subrange_kind _Kind> 391 inline constexpr bool 392 enable_borrowed_range
> = true; 393 394 template
395 using borrowed_subrange_t = conditional_t
, 396 subrange
>, 397 dangling>; 398 } // namespace ranges 399 400 // The following ranges algorithms are used by
, and are defined here 401 // so that
can avoid including all of
. 402 namespace ranges 403 { 404 struct __find_fn 405 { 406 template
_Sent, typename _Tp, 407 typename _Proj = identity> 408 requires indirect_binary_predicate
, const _Tp*> 410 constexpr _Iter 411 operator()(_Iter __first, _Sent __last, 412 const _Tp& __value, _Proj __proj = {}) const 413 { 414 while (__first != __last 415 && !(std::__invoke(__proj, *__first) == __value)) 416 ++__first; 417 return __first; 418 } 419 420 template
421 requires indirect_binary_predicate
, _Proj>, 423 const _Tp*> 424 constexpr borrowed_iterator_t<_Range> 425 operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const 426 { 427 return (*this)(ranges::begin(__r), ranges::end(__r), 428 __value, std::move(__proj)); 429 } 430 }; 431 432 inline constexpr __find_fn find{}; 433 434 struct __find_if_fn 435 { 436 template
_Sent, 437 typename _Proj = identity, 438 indirect_unary_predicate
> _Pred> 439 constexpr _Iter 440 operator()(_Iter __first, _Sent __last, 441 _Pred __pred, _Proj __proj = {}) const 442 { 443 while (__first != __last 444 && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) 445 ++__first; 446 return __first; 447 } 448 449 template
, _Proj>> 451 _Pred> 452 constexpr borrowed_iterator_t<_Range> 453 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 454 { 455 return (*this)(ranges::begin(__r), ranges::end(__r), 456 std::move(__pred), std::move(__proj)); 457 } 458 }; 459 460 inline constexpr __find_if_fn find_if{}; 461 462 struct __find_if_not_fn 463 { 464 template
_Sent, 465 typename _Proj = identity, 466 indirect_unary_predicate
> _Pred> 467 constexpr _Iter 468 operator()(_Iter __first, _Sent __last, 469 _Pred __pred, _Proj __proj = {}) const 470 { 471 while (__first != __last 472 && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) 473 ++__first; 474 return __first; 475 } 476 477 template
, _Proj>> 479 _Pred> 480 constexpr borrowed_iterator_t<_Range> 481 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 482 { 483 return (*this)(ranges::begin(__r), ranges::end(__r), 484 std::move(__pred), std::move(__proj)); 485 } 486 }; 487 488 inline constexpr __find_if_not_fn find_if_not{}; 489 490 template
491 struct in_in_result 492 { 493 [[no_unique_address]] _Iter1 in1; 494 [[no_unique_address]] _Iter2 in2; 495 496 template
497 requires convertible_to
498 && convertible_to
499 constexpr 500 operator in_in_result<_IIter1, _IIter2>() const & 501 { return {in1, in2}; } 502 503 template
504 requires convertible_to<_Iter1, _IIter1> 505 && convertible_to<_Iter2, _IIter2> 506 constexpr 507 operator in_in_result<_IIter1, _IIter2>() && 508 { return {std::move(in1), std::move(in2)}; } 509 }; 510 511 template
512 using mismatch_result = in_in_result<_Iter1, _Iter2>; 513 514 struct __mismatch_fn 515 { 516 template
_Sent1, 517 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 518 typename _Pred = ranges::equal_to, 519 typename _Proj1 = identity, typename _Proj2 = identity> 520 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 521 constexpr mismatch_result<_Iter1, _Iter2> 522 operator()(_Iter1 __first1, _Sent1 __last1, 523 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, 524 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 525 { 526 while (__first1 != __last1 && __first2 != __last2 527 && (bool)std::__invoke(__pred, 528 std::__invoke(__proj1, *__first1), 529 std::__invoke(__proj2, *__first2))) 530 { 531 ++__first1; 532 ++__first2; 533 } 534 return { std::move(__first1), std::move(__first2) }; 535 } 536 537 template
540 requires indirectly_comparable
, iterator_t<_Range2>, 541 _Pred, _Proj1, _Proj2> 542 constexpr mismatch_result
, iterator_t<_Range2>> 543 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, 544 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 545 { 546 return (*this)(ranges::begin(__r1), ranges::end(__r1), 547 ranges::begin(__r2), ranges::end(__r2), 548 std::move(__pred), 549 std::move(__proj1), std::move(__proj2)); 550 } 551 }; 552 553 inline constexpr __mismatch_fn mismatch{}; 554 555 struct __search_fn 556 { 557 template
_Sent1, 558 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 559 typename _Pred = ranges::equal_to, 560 typename _Proj1 = identity, typename _Proj2 = identity> 561 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 562 constexpr subrange<_Iter1> 563 operator()(_Iter1 __first1, _Sent1 __last1, 564 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, 565 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 566 { 567 if (__first1 == __last1 || __first2 == __last2) 568 return {__first1, __first1}; 569 570 for (;;) 571 { 572 for (;;) 573 { 574 if (__first1 == __last1) 575 return {__first1, __first1}; 576 if (std::__invoke(__pred, 577 std::__invoke(__proj1, *__first1), 578 std::__invoke(__proj2, *__first2))) 579 break; 580 ++__first1; 581 } 582 auto __cur1 = __first1; 583 auto __cur2 = __first2; 584 for (;;) 585 { 586 if (++__cur2 == __last2) 587 return {__first1, ++__cur1}; 588 if (++__cur1 == __last1) 589 return {__cur1, __cur1}; 590 if (!(bool)std::__invoke(__pred, 591 std::__invoke(__proj1, *__cur1), 592 std::__invoke(__proj2, *__cur2))) 593 { 594 ++__first1; 595 break; 596 } 597 } 598 } 599 } 600 601 template
604 requires indirectly_comparable
, iterator_t<_Range2>, 605 _Pred, _Proj1, _Proj2> 606 constexpr borrowed_subrange_t<_Range1> 607 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, 608 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 609 { 610 return (*this)(ranges::begin(__r1), ranges::end(__r1), 611 ranges::begin(__r2), ranges::end(__r2), 612 std::move(__pred), 613 std::move(__proj1), std::move(__proj2)); 614 } 615 }; 616 617 inline constexpr __search_fn search{}; 618 } // namespace ranges 619 620 using ranges::get; 621 622 template
623 struct tuple_size
> 624 : integral_constant
625 { }; 626 627 template
628 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>> 629 { using type = _Iter; }; 630 631 template
632 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>> 633 { using type = _Sent; }; 634 635 template
636 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>> 637 { using type = _Iter; }; 638 639 template
640 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>> 641 { using type = _Sent; }; 642 643 _GLIBCXX_END_NAMESPACE_VERSION 644 } // namespace std 645 #endif // library concepts 646 #endif // C++20 647 #endif // _RANGES_UTIL_H
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™