| 1 |
// Concepts and traits for use with iterators -*- 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 |
// <http://www.gnu.org/licenses/>. |
| 24 |
|
| 25 |
/** @file bits/iterator_concepts.h |
| 26 |
* This is an internal header file, included by other library headers. |
| 27 |
* Do not attempt to use it directly. @headername{iterator} |
| 28 |
*/ |
| 29 |
|
| 30 |
#ifndef _ITERATOR_CONCEPTS_H |
| 31 |
#define _ITERATOR_CONCEPTS_H 1 |
| 32 |
|
| 33 |
#pragma GCC system_header |
| 34 |
|
| 35 |
#include <concepts> |
| 36 |
#include <bits/ptr_traits.h> // to_address |
| 37 |
#include <bits/ranges_cmp.h> // identity, ranges::less |
| 38 |
|
| 39 |
#if __cpp_lib_concepts |
| 40 |
namespace std _GLIBCXX_VISIBILITY(default) |
| 41 |
{ |
| 42 |
_GLIBCXX_BEGIN_NAMESPACE_VERSION |
| 43 |
|
| 44 |
struct input_iterator_tag; |
| 45 |
struct output_iterator_tag; |
| 46 |
struct forward_iterator_tag; |
| 47 |
struct bidirectional_iterator_tag; |
| 48 |
struct random_access_iterator_tag; |
| 49 |
struct contiguous_iterator_tag; |
| 50 |
|
| 51 |
template<typename _Iterator> |
| 52 |
struct iterator_traits; |
| 53 |
|
| 54 |
template<typename _Tp> requires is_object_v<_Tp> |
| 55 |
struct iterator_traits<_Tp*>; |
| 56 |
|
| 57 |
template<typename _Iterator, typename> |
| 58 |
struct __iterator_traits; |
| 59 |
|
| 60 |
namespace __detail |
| 61 |
{ |
| 62 |
template<typename _Tp> |
| 63 |
using __with_ref = _Tp&; |
| 64 |
|
| 65 |
template<typename _Tp> |
| 66 |
concept __can_reference = requires { typename __with_ref<_Tp>; }; |
| 67 |
|
| 68 |
template<typename _Tp> |
| 69 |
concept __dereferenceable = requires(_Tp& __t) |
| 70 |
{ |
| 71 |
{ *__t } -> __can_reference; |
| 72 |
}; |
| 73 |
} // namespace __detail |
| 74 |
|
| 75 |
template<__detail::__dereferenceable _Tp> |
| 76 |
using iter_reference_t = decltype(*std::declval<_Tp&>()); |
| 77 |
|
| 78 |
namespace ranges |
| 79 |
{ |
| 80 |
namespace __cust_imove |
| 81 |
{ |
| 82 |
void iter_move(); |
| 83 |
|
| 84 |
template<typename _Tp> |
| 85 |
concept __adl_imove |
| 86 |
= (std::__detail::__class_or_enum<remove_reference_t<_Tp>>) |
| 87 |
&& requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); }; |
| 88 |
|
| 89 |
struct _IMove |
| 90 |
{ |
| 91 |
private: |
| 92 |
template<typename _Tp> |
| 93 |
struct __result |
| 94 |
{ using type = iter_reference_t<_Tp>; }; |
| 95 |
|
| 96 |
template<typename _Tp> |
| 97 |
requires __adl_imove<_Tp> |
| 98 |
struct __result<_Tp> |
| 99 |
{ using type = decltype(iter_move(std::declval<_Tp>())); }; |
| 100 |
|
| 101 |
template<typename _Tp> |
| 102 |
requires (!__adl_imove<_Tp>) |
| 103 |
&& is_lvalue_reference_v<iter_reference_t<_Tp>> |
| 104 |
struct __result<_Tp> |
| 105 |
{ using type = remove_reference_t<iter_reference_t<_Tp>>&&; }; |
| 106 |
|
| 107 |
template<typename _Tp> |
| 108 |
static constexpr bool |
| 109 |
_S_noexcept() |
| 110 |
{ |
| 111 |
if constexpr (__adl_imove<_Tp>) |
| 112 |
return noexcept(iter_move(std::declval<_Tp>())); |
| 113 |
else |
| 114 |
return noexcept(*std::declval<_Tp>()); |
| 115 |
} |
| 116 |
|
| 117 |
public: |
| 118 |
// The result type of iter_move(std::declval<_Tp>()) |
| 119 |
template<std::__detail::__dereferenceable _Tp> |
| 120 |
using __type = typename __result<_Tp>::type; |
| 121 |
|
| 122 |
template<std::__detail::__dereferenceable _Tp> |
| 123 |
constexpr __type<_Tp> |
| 124 |
operator()(_Tp&& __e) const |
| 125 |
noexcept(_S_noexcept<_Tp>()) |
| 126 |
{ |
| 127 |
if constexpr (__adl_imove<_Tp>) |
| 128 |
return iter_move(static_cast<_Tp&&>(__e)); |
| 129 |
else if constexpr (is_lvalue_reference_v<iter_reference_t<_Tp>>) |
| 130 |
return static_cast<__type<_Tp>>(*__e); |
| 131 |
else |
| 132 |
return *__e; |
| 133 |
} |
| 134 |
}; |
| 135 |
} // namespace __cust_imove |
| 136 |
|
| 137 |
inline namespace __cust |
| 138 |
{ |
| 139 |
inline constexpr __cust_imove::_IMove iter_move{}; |
| 140 |
} // inline namespace __cust |
| 141 |
} // namespace ranges |
| 142 |
|
| 143 |
template<__detail::__dereferenceable _Tp> |
| 144 |
requires __detail:: |
| 145 |
__can_reference<ranges::__cust_imove::_IMove::__type<_Tp&>> |
| 146 |
using iter_rvalue_reference_t |
| 147 |
= ranges::__cust_imove::_IMove::__type<_Tp&>; |
| 148 |
|
| 149 |
template<typename> struct incrementable_traits { }; |
| 150 |
|
| 151 |
template<typename _Tp> requires is_object_v<_Tp> |
| 152 |
struct incrementable_traits<_Tp*> |
| 153 |
{ using difference_type = ptrdiff_t; }; |
| 154 |
|
| 155 |
template<typename _Iter> |
| 156 |
struct incrementable_traits<const _Iter> |
| 157 |
: incrementable_traits<_Iter> { }; |
| 158 |
|
| 159 |
template<typename _Tp> requires requires { typename _Tp::difference_type; } |
| 160 |
struct incrementable_traits<_Tp> |
| 161 |
{ using difference_type = typename _Tp::difference_type; }; |
| 162 |
|
| 163 |
template<typename _Tp> |
| 164 |
requires (!requires { typename _Tp::difference_type; } |
| 165 |
&& requires(const _Tp& __a, const _Tp& __b) |
| 166 |
{ { __a - __b } -> integral; }) |
| 167 |
struct incrementable_traits<_Tp> |
| 168 |
{ |
| 169 |
using difference_type |
| 170 |
= make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>; |
| 171 |
}; |
| 172 |
|
| 173 |
#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__ |
| 174 |
// __int128 is incrementable even if !integral<__int128> |
| 175 |
template<> |
| 176 |
struct incrementable_traits<__int128> |
| 177 |
{ using difference_type = __int128; }; |
| 178 |
|
| 179 |
template<> |
| 180 |
struct incrementable_traits<unsigned __int128> |
| 181 |
{ using difference_type = __int128; }; |
| 182 |
#endif |
| 183 |
|
| 184 |
namespace __detail |
| 185 |
{ |
| 186 |
// An iterator such that iterator_traits<_Iter> names a specialization |
| 187 |
// generated from the primary template. |
| 188 |
template<typename _Iter> |
| 189 |
concept __primary_traits_iter |
| 190 |
= __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>); |
| 191 |
|
| 192 |
template<typename _Iter, typename _Tp> |
| 193 |
struct __iter_traits_impl |
| 194 |
{ using type = iterator_traits<_Iter>; }; |
| 195 |
|
| 196 |
template<typename _Iter, typename _Tp> |
| 197 |
requires __primary_traits_iter<_Iter> |
| 198 |
struct __iter_traits_impl<_Iter, _Tp> |
| 199 |
{ using type = _Tp; }; |
| 200 |
|
| 201 |
// ITER_TRAITS |
| 202 |
template<typename _Iter, typename _Tp = _Iter> |
| 203 |
using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type; |
| 204 |
|
| 205 |
template<typename _Tp> |
| 206 |
using __iter_diff_t = typename |
| 207 |
__iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type; |
| 208 |
} // namespace __detail |
| 209 |
|
| 210 |
template<typename _Tp> |
| 211 |
using iter_difference_t = __detail::__iter_diff_t<remove_cvref_t<_Tp>>; |
| 212 |
|
| 213 |
namespace __detail |
| 214 |
{ |
| 215 |
template<typename> struct __cond_value_type { }; |
| 216 |
|
| 217 |
template<typename _Tp> requires is_object_v<_Tp> |
| 218 |
struct __cond_value_type<_Tp> |
| 219 |
{ using value_type = remove_cv_t<_Tp>; }; |
| 220 |
|
| 221 |
template<typename _Tp> |
| 222 |
concept __has_member_value_type |
| 223 |
= requires { typename _Tp::value_type; }; |
| 224 |
|
| 225 |
template<typename _Tp> |
| 226 |
concept __has_member_element_type |
| 227 |
= requires { typename _Tp::element_type; }; |
| 228 |
|
| 229 |
} // namespace __detail |
| 230 |
|
| 231 |
template<typename> struct indirectly_readable_traits { }; |
| 232 |
|
| 233 |
template<typename _Tp> |
| 234 |
struct indirectly_readable_traits<_Tp*> |
| 235 |
: __detail::__cond_value_type<_Tp> |
| 236 |
{ }; |
| 237 |
|
| 238 |
template<typename _Iter> requires is_array_v<_Iter> |
| 239 |
struct indirectly_readable_traits<_Iter> |
| 240 |
{ using value_type = remove_cv_t<remove_extent_t<_Iter>>; }; |
| 241 |
|
| 242 |
template<typename _Iter> |
| 243 |
struct indirectly_readable_traits<const _Iter> |
| 244 |
: indirectly_readable_traits<_Iter> |
| 245 |
{ }; |
| 246 |
|
| 247 |
template<__detail::__has_member_value_type _Tp> |
| 248 |
struct indirectly_readable_traits<_Tp> |
| 249 |
: __detail::__cond_value_type<typename _Tp::value_type> |
| 250 |
{ }; |
| 251 |
|
| 252 |
template<__detail::__has_member_element_type _Tp> |
| 253 |
struct indirectly_readable_traits<_Tp> |
| 254 |
: __detail::__cond_value_type<typename _Tp::element_type> |
| 255 |
{ }; |
| 256 |
|
| 257 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
| 258 |
// 3446. indirectly_readable_traits ambiguity for types with both [...] |
| 259 |
template<__detail::__has_member_value_type _Tp> |
| 260 |
requires __detail::__has_member_element_type<_Tp> |
| 261 |
&& same_as<remove_cv_t<typename _Tp::element_type>, |
| 262 |
remove_cv_t<typename _Tp::value_type>> |
| 263 |
struct indirectly_readable_traits<_Tp> |
| 264 |
: __detail::__cond_value_type<typename _Tp::value_type> |
| 265 |
{ }; |
| 266 |
|
| 267 |
// LWG 3446 doesn't add this, but it's needed for the case where |
| 268 |
// value_type and element_type are both present, but not the same type. |
| 269 |
template<__detail::__has_member_value_type _Tp> |
| 270 |
requires __detail::__has_member_element_type<_Tp> |
| 271 |
struct indirectly_readable_traits<_Tp> |
| 272 |
{ }; |
| 273 |
|
| 274 |
namespace __detail |
| 275 |
{ |
| 276 |
template<typename _Tp> |
| 277 |
using __iter_value_t = typename |
| 278 |
__iter_traits<_Tp, indirectly_readable_traits<_Tp>>::value_type; |
| 279 |
} // namespace __detail |
| 280 |
|
| 281 |
template<typename _Tp> |
| 282 |
using iter_value_t = __detail::__iter_value_t<remove_cvref_t<_Tp>>; |
| 283 |
|
| 284 |
namespace __detail |
| 285 |
{ |
| 286 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
| 287 |
// 3420. cpp17-iterator should check [type] looks like an iterator first |
| 288 |
template<typename _Iter> |
| 289 |
concept __cpp17_iterator = requires(_Iter __it) |
| 290 |
{ |
| 291 |
{ *__it } -> __can_reference; |
| 292 |
{ ++__it } -> same_as<_Iter&>; |
| 293 |
{ *__it++ } -> __can_reference; |
| 294 |
} && copyable<_Iter>; |
| 295 |
|
| 296 |
template<typename _Iter> |
| 297 |
concept __cpp17_input_iterator = __cpp17_iterator<_Iter> |
| 298 |
&& equality_comparable<_Iter> |
| 299 |
&& requires(_Iter __it) |
| 300 |
{ |
| 301 |
typename incrementable_traits<_Iter>::difference_type; |
| 302 |
typename indirectly_readable_traits<_Iter>::value_type; |
| 303 |
typename common_reference_t<iter_reference_t<_Iter>&&, |
| 304 |
typename indirectly_readable_traits<_Iter>::value_type&>; |
| 305 |
typename common_reference_t<decltype(*__it++)&&, |
| 306 |
typename indirectly_readable_traits<_Iter>::value_type&>; |
| 307 |
requires signed_integral< |
| 308 |
typename incrementable_traits<_Iter>::difference_type>; |
| 309 |
}; |
| 310 |
|
| 311 |
template<typename _Iter> |
| 312 |
concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter> |
| 313 |
&& constructible_from<_Iter> |
| 314 |
&& is_lvalue_reference_v<iter_reference_t<_Iter>> |
| 315 |
&& same_as<remove_cvref_t<iter_reference_t<_Iter>>, |
| 316 |
typename indirectly_readable_traits<_Iter>::value_type> |
| 317 |
&& requires(_Iter __it) |
| 318 |
{ |
| 319 |
{ __it++ } -> convertible_to<const _Iter&>; |
| 320 |
{ *__it++ } -> same_as<iter_reference_t<_Iter>>; |
| 321 |
}; |
| 322 |
|
| 323 |
template<typename _Iter> |
| 324 |
concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter> |
| 325 |
&& requires(_Iter __it) |
| 326 |
{ |
| 327 |
{ --__it } -> same_as<_Iter&>; |
| 328 |
{ __it-- } -> convertible_to<const _Iter&>; |
| 329 |
{ *__it-- } -> same_as<iter_reference_t<_Iter>>; |
| 330 |
}; |
| 331 |
|
| 332 |
template<typename _Iter> |
| 333 |
concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter> |
| 334 |
&& totally_ordered<_Iter> |
| 335 |
&& requires(_Iter __it, |
| 336 |
typename incrementable_traits<_Iter>::difference_type __n) |
| 337 |
{ |
| 338 |
{ __it += __n } -> same_as<_Iter&>; |
| 339 |
{ __it -= __n } -> same_as<_Iter&>; |
| 340 |
{ __it + __n } -> same_as<_Iter>; |
| 341 |
{ __n + __it } -> same_as<_Iter>; |
| 342 |
{ __it - __n } -> same_as<_Iter>; |
| 343 |
{ __it - __it } -> same_as<decltype(__n)>; |
| 344 |
{ __it[__n] } -> convertible_to<iter_reference_t<_Iter>>; |
| 345 |
}; |
| 346 |
|
| 347 |
template<typename _Iter> |
| 348 |
concept __iter_with_nested_types = requires { |
| 349 |
typename _Iter::iterator_category; |
| 350 |
typename _Iter::value_type; |
| 351 |
typename _Iter::difference_type; |
| 352 |
typename _Iter::reference; |
| 353 |
}; |
| 354 |
|
| 355 |
template<typename _Iter> |
| 356 |
concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>; |
| 357 |
|
| 358 |
template<typename _Iter> |
| 359 |
concept __iter_without_category |
| 360 |
= !requires { typename _Iter::iterator_category; }; |
| 361 |
|
| 362 |
} // namespace __detail |
| 363 |
|
| 364 |
template<typename _Iterator> |
| 365 |
requires __detail::__iter_with_nested_types<_Iterator> |
| 366 |
struct __iterator_traits<_Iterator, void> |
| 367 |
{ |
| 368 |
private: |
| 369 |
template<typename _Iter> |
| 370 |
struct __ptr |
| 371 |
{ using type = void; }; |
| 372 |
|
| 373 |
template<typename _Iter> requires requires { typename _Iter::pointer; } |
| 374 |
struct __ptr<_Iter> |
| 375 |
{ using type = typename _Iter::pointer; }; |
| 376 |
|
| 377 |
public: |
| 378 |
using iterator_category = typename _Iterator::iterator_category; |
| 379 |
using value_type = typename _Iterator::value_type; |
| 380 |
using difference_type = typename _Iterator::difference_type; |
| 381 |
using pointer = typename __ptr<_Iterator>::type; |
| 382 |
using reference = typename _Iterator::reference; |
| 383 |
}; |
| 384 |
|
| 385 |
template<typename _Iterator> |
| 386 |
requires __detail::__iter_without_nested_types<_Iterator> |
| 387 |
&& __detail::__cpp17_input_iterator<_Iterator> |
| 388 |
struct __iterator_traits<_Iterator, void> |
| 389 |
{ |
| 390 |
private: |
| 391 |
template<typename _Iter> |
| 392 |
struct __cat |
| 393 |
{ using type = input_iterator_tag; }; |
| 394 |
|
| 395 |
template<typename _Iter> |
| 396 |
requires requires { typename _Iter::iterator_category; } |
| 397 |
struct __cat<_Iter> |
| 398 |
{ using type = typename _Iter::iterator_category; }; |
| 399 |
|
| 400 |
template<typename _Iter> |
| 401 |
requires __detail::__iter_without_category<_Iter> |
| 402 |
&& __detail::__cpp17_randacc_iterator<_Iter> |
| 403 |
struct __cat<_Iter> |
| 404 |
{ using type = random_access_iterator_tag; }; |
| 405 |
|
| 406 |
template<typename _Iter> |
| 407 |
requires __detail::__iter_without_category<_Iter> |
| 408 |
&& __detail::__cpp17_bidi_iterator<_Iter> |
| 409 |
struct __cat<_Iter> |
| 410 |
{ using type = bidirectional_iterator_tag; }; |
| 411 |
|
| 412 |
template<typename _Iter> |
| 413 |
requires __detail::__iter_without_category<_Iter> |
| 414 |
&& __detail::__cpp17_fwd_iterator<_Iter> |
| 415 |
struct __cat<_Iter> |
| 416 |
{ using type = forward_iterator_tag; }; |
| 417 |
|
| 418 |
template<typename _Iter> |
| 419 |
struct __ptr |
| 420 |
{ using type = void; }; |
| 421 |
|
| 422 |
template<typename _Iter> requires requires { typename _Iter::pointer; } |
| 423 |
struct __ptr<_Iter> |
| 424 |
{ using type = typename _Iter::pointer; }; |
| 425 |
|
| 426 |
template<typename _Iter> |
| 427 |
requires (!requires { typename _Iter::pointer; } |
| 428 |
&& requires(_Iter& __it) { __it.operator->(); }) |
| 429 |
struct __ptr<_Iter> |
| 430 |
{ using type = decltype(std::declval<_Iter&>().operator->()); }; |
| 431 |
|
| 432 |
template<typename _Iter> |
| 433 |
struct __ref |
| 434 |
{ using type = iter_reference_t<_Iter>; }; |
| 435 |
|
| 436 |
template<typename _Iter> requires requires { typename _Iter::reference; } |
| 437 |
struct __ref<_Iter> |
| 438 |
{ using type = typename _Iter::reference; }; |
| 439 |
|
| 440 |
public: |
| 441 |
using iterator_category = typename __cat<_Iterator>::type; |
| 442 |
using value_type |
| 443 |
= typename indirectly_readable_traits<_Iterator>::value_type; |
| 444 |
using difference_type |
| 445 |
= typename incrementable_traits<_Iterator>::difference_type; |
| 446 |
using pointer = typename __ptr<_Iterator>::type; |
| 447 |
using reference = typename __ref<_Iterator>::type; |
| 448 |
}; |
| 449 |
|
| 450 |
template<typename _Iterator> |
| 451 |
requires __detail::__iter_without_nested_types<_Iterator> |
| 452 |
&& __detail::__cpp17_iterator<_Iterator> |
| 453 |
struct __iterator_traits<_Iterator, void> |
| 454 |
{ |
| 455 |
private: |
| 456 |
template<typename _Iter> |
| 457 |
struct __diff |
| 458 |
{ using type = void; }; |
| 459 |
|
| 460 |
template<typename _Iter> |
| 461 |
requires requires |
| 462 |
{ typename incrementable_traits<_Iter>::difference_type; } |
| 463 |
struct __diff<_Iter> |
| 464 |
{ |
| 465 |
using type = typename incrementable_traits<_Iter>::difference_type; |
| 466 |
}; |
| 467 |
|
| 468 |
public: |
| 469 |
using iterator_category = output_iterator_tag; |
| 470 |
using value_type = void; |
| 471 |
using difference_type = typename __diff<_Iterator>::type; |
| 472 |
using pointer = void; |
| 473 |
using reference = void; |
| 474 |
}; |
| 475 |
|
| 476 |
namespace __detail |
| 477 |
{ |
| 478 |
template<typename _Iter> |
| 479 |
struct __iter_concept_impl; |
| 480 |
|
| 481 |
// ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid. |
| 482 |
template<typename _Iter> |
| 483 |
requires requires { typename __iter_traits<_Iter>::iterator_concept; } |
| 484 |
struct __iter_concept_impl<_Iter> |
| 485 |
{ using type = typename __iter_traits<_Iter>::iterator_concept; }; |
| 486 |
|
| 487 |
// Otherwise, ITER_TRAITS(I)::iterator_category if that is valid. |
| 488 |
template<typename _Iter> |
| 489 |
requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } |
| 490 |
&& requires { typename __iter_traits<_Iter>::iterator_category; }) |
| 491 |
struct __iter_concept_impl<_Iter> |
| 492 |
{ using type = typename __iter_traits<_Iter>::iterator_category; }; |
| 493 |
|
| 494 |
// Otherwise, random_access_tag if iterator_traits<I> is not specialized. |
| 495 |
template<typename _Iter> |
| 496 |
requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } |
| 497 |
&& !requires { typename __iter_traits<_Iter>::iterator_category; } |
| 498 |
&& __primary_traits_iter<_Iter>) |
| 499 |
struct __iter_concept_impl<_Iter> |
| 500 |
{ using type = random_access_iterator_tag; }; |
| 501 |
|
| 502 |
// Otherwise, there is no ITER_CONCEPT(I) type. |
| 503 |
template<typename _Iter> |
| 504 |
struct __iter_concept_impl |
| 505 |
{ }; |
| 506 |
|
| 507 |
// ITER_CONCEPT |
| 508 |
template<typename _Iter> |
| 509 |
using __iter_concept = typename __iter_concept_impl<_Iter>::type; |
| 510 |
|
| 511 |
template<typename _In> |
| 512 |
concept __indirectly_readable_impl = requires |
| 513 |
{ |
| 514 |
typename iter_value_t<_In>; |
| 515 |
typename iter_reference_t<_In>; |
| 516 |
typename iter_rvalue_reference_t<_In>; |
| 517 |
requires same_as<iter_reference_t<const _In>, |
| 518 |
iter_reference_t<_In>>; |
| 519 |
requires same_as<iter_rvalue_reference_t<const _In>, |
| 520 |
iter_rvalue_reference_t<_In>>; |
| 521 |
} |
| 522 |
&& common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> |
| 523 |
&& common_reference_with<iter_reference_t<_In>&&, |
| 524 |
iter_rvalue_reference_t<_In>&&> |
| 525 |
&& common_reference_with<iter_rvalue_reference_t<_In>&&, |
| 526 |
const iter_value_t<_In>&>; |
| 527 |
|
| 528 |
} // namespace __detail |
| 529 |
|
| 530 |
/// Requirements for types that are readable by applying operator*. |
| 531 |
template<typename _In> |
| 532 |
concept indirectly_readable |
| 533 |
= __detail::__indirectly_readable_impl<remove_cvref_t<_In>>; |
| 534 |
|
| 535 |
template<indirectly_readable _Tp> |
| 536 |
using iter_common_reference_t |
| 537 |
= common_reference_t<iter_reference_t<_Tp>, iter_value_t<_Tp>&>; |
| 538 |
|
| 539 |
/// Requirements for writing a value into an iterator's referenced object. |
| 540 |
template<typename _Out, typename _Tp> |
| 541 |
concept indirectly_writable = requires(_Out&& __o, _Tp&& __t) |
| 542 |
{ |
| 543 |
*__o = std::forward<_Tp>(__t); |
| 544 |
*std::forward<_Out>(__o) = std::forward<_Tp>(__t); |
| 545 |
const_cast<const iter_reference_t<_Out>&&>(*__o) |
| 546 |
= std::forward<_Tp>(__t); |
| 547 |
const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) |
| 548 |
= std::forward<_Tp>(__t); |
| 549 |
}; |
| 550 |
|
| 551 |
namespace ranges::__detail |
| 552 |
{ |
| 553 |
class __max_diff_type; |
| 554 |
class __max_size_type; |
| 555 |
|
| 556 |
template<typename _Tp> |
| 557 |
concept __is_signed_int128 |
| 558 |
#if __SIZEOF_INT128__ |
| 559 |
= same_as<_Tp, __int128>; |
| 560 |
#else |
| 561 |
= false; |
| 562 |
#endif |
| 563 |
|
| 564 |
template<typename _Tp> |
| 565 |
concept __is_unsigned_int128 |
| 566 |
#if __SIZEOF_INT128__ |
| 567 |
= same_as<_Tp, unsigned __int128>; |
| 568 |
#else |
| 569 |
= false; |
| 570 |
#endif |
| 571 |
|
| 572 |
template<typename _Tp> |
| 573 |
concept __cv_bool = same_as<const volatile _Tp, const volatile bool>; |
| 574 |
|
| 575 |
template<typename _Tp> |
| 576 |
concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>; |
| 577 |
|
| 578 |
template<typename _Tp> |
| 579 |
concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>; |
| 580 |
|
| 581 |
template<typename _Tp> |
| 582 |
concept __is_integer_like = __integral_nonbool<_Tp> |
| 583 |
|| __is_int128<_Tp> |
| 584 |
|| same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; |
| 585 |
|
| 586 |
template<typename _Tp> |
| 587 |
concept __is_signed_integer_like = signed_integral<_Tp> |
| 588 |
|| __is_signed_int128<_Tp> |
| 589 |
|| same_as<_Tp, __max_diff_type>; |
| 590 |
|
| 591 |
} // namespace ranges::__detail |
| 592 |
|
| 593 |
namespace __detail { using ranges::__detail::__is_signed_integer_like; } |
| 594 |
|
| 595 |
/// Requirements on types that can be incremented with ++. |
| 596 |
template<typename _Iter> |
| 597 |
concept weakly_incrementable = default_initializable<_Iter> |
| 598 |
&& movable<_Iter> |
| 599 |
&& requires(_Iter __i) |
| 600 |
{ |
| 601 |
typename iter_difference_t<_Iter>; |
| 602 |
requires __detail::__is_signed_integer_like<iter_difference_t<_Iter>>; |
| 603 |
{ ++__i } -> same_as<_Iter&>; |
| 604 |
__i++; |
| 605 |
}; |
| 606 |
|
| 607 |
template<typename _Iter> |
| 608 |
concept incrementable = regular<_Iter> && weakly_incrementable<_Iter> |
| 609 |
&& requires(_Iter __i) { { __i++ } -> same_as<_Iter>; }; |
| 610 |
|
| 611 |
template<typename _Iter> |
| 612 |
concept input_or_output_iterator |
| 613 |
= requires(_Iter __i) { { *__i } -> __detail::__can_reference; } |
| 614 |
&& weakly_incrementable<_Iter>; |
| 615 |
|
| 616 |
template<typename _Sent, typename _Iter> |
| 617 |
concept sentinel_for = semiregular<_Sent> |
| 618 |
&& input_or_output_iterator<_Iter> |
| 619 |
&& __detail::__weakly_eq_cmp_with<_Sent, _Iter>; |
| 620 |
|
| 621 |
template<typename _Sent, typename _Iter> |
| 622 |
inline constexpr bool disable_sized_sentinel_for = false; |
| 623 |
|
| 624 |
template<typename _Sent, typename _Iter> |
| 625 |
concept sized_sentinel_for = sentinel_for<_Sent, _Iter> |
| 626 |
&& !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>> |
| 627 |
&& requires(const _Iter& __i, const _Sent& __s) |
| 628 |
{ |
| 629 |
{ __s - __i } -> same_as<iter_difference_t<_Iter>>; |
| 630 |
{ __i - __s } -> same_as<iter_difference_t<_Iter>>; |
| 631 |
}; |
| 632 |
|
| 633 |
template<typename _Iter> |
| 634 |
concept input_iterator = input_or_output_iterator<_Iter> |
| 635 |
&& indirectly_readable<_Iter> |
| 636 |
&& requires { typename __detail::__iter_concept<_Iter>; } |
| 637 |
&& derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>; |
| 638 |
|
| 639 |
template<typename _Iter, typename _Tp> |
| 640 |
concept output_iterator = input_or_output_iterator<_Iter> |
| 641 |
&& indirectly_writable<_Iter, _Tp> |
| 642 |
&& requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); }; |
| 643 |
|
| 644 |
template<typename _Iter> |
| 645 |
concept forward_iterator = input_iterator<_Iter> |
| 646 |
&& derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag> |
| 647 |
&& incrementable<_Iter> && sentinel_for<_Iter, _Iter>; |
| 648 |
|
| 649 |
template<typename _Iter> |
| 650 |
concept bidirectional_iterator = forward_iterator<_Iter> |
| 651 |
&& derived_from<__detail::__iter_concept<_Iter>, |
| 652 |
bidirectional_iterator_tag> |
| 653 |
&& requires(_Iter __i) |
| 654 |
{ |
| 655 |
{ --__i } -> same_as<_Iter&>; |
| 656 |
{ __i-- } -> same_as<_Iter>; |
| 657 |
}; |
| 658 |
|
| 659 |
template<typename _Iter> |
| 660 |
concept random_access_iterator = bidirectional_iterator<_Iter> |
| 661 |
&& derived_from<__detail::__iter_concept<_Iter>, |
| 662 |
random_access_iterator_tag> |
| 663 |
&& totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter> |
| 664 |
&& requires(_Iter __i, const _Iter __j, |
| 665 |
const iter_difference_t<_Iter> __n) |
| 666 |
{ |
| 667 |
{ __i += __n } -> same_as<_Iter&>; |
| 668 |
{ __j + __n } -> same_as<_Iter>; |
| 669 |
{ __n + __j } -> same_as<_Iter>; |
| 670 |
{ __i -= __n } -> same_as<_Iter&>; |
| 671 |
{ __j - __n } -> same_as<_Iter>; |
| 672 |
{ __j[__n] } -> same_as<iter_reference_t<_Iter>>; |
| 673 |
}; |
| 674 |
|
| 675 |
template<typename _Iter> |
| 676 |
concept contiguous_iterator = random_access_iterator<_Iter> |
| 677 |
&& derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag> |
| 678 |
&& is_lvalue_reference_v<iter_reference_t<_Iter>> |
| 679 |
&& same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>> |
| 680 |
&& requires(const _Iter& __i) |
| 681 |
{ |
| 682 |
{ std::to_address(__i) } |
| 683 |
-> same_as<add_pointer_t<iter_reference_t<_Iter>>>; |
| 684 |
}; |
| 685 |
|
| 686 |
// [indirectcallable], indirect callable requirements |
| 687 |
|
| 688 |
// [indirectcallable.indirectinvocable], indirect callables |
| 689 |
|
| 690 |
template<typename _Fn, typename _Iter> |
| 691 |
concept indirectly_unary_invocable = indirectly_readable<_Iter> |
| 692 |
&& copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&> |
| 693 |
&& invocable<_Fn&, iter_reference_t<_Iter>> |
| 694 |
&& invocable<_Fn&, iter_common_reference_t<_Iter>> |
| 695 |
&& common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, |
| 696 |
invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; |
| 697 |
|
| 698 |
template<typename _Fn, typename _Iter> |
| 699 |
concept indirectly_regular_unary_invocable = indirectly_readable<_Iter> |
| 700 |
&& copy_constructible<_Fn> |
| 701 |
&& regular_invocable<_Fn&, iter_value_t<_Iter>&> |
| 702 |
&& regular_invocable<_Fn&, iter_reference_t<_Iter>> |
| 703 |
&& regular_invocable<_Fn&, iter_common_reference_t<_Iter>> |
| 704 |
&& common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, |
| 705 |
invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; |
| 706 |
|
| 707 |
template<typename _Fn, typename _Iter> |
| 708 |
concept indirect_unary_predicate = indirectly_readable<_Iter> |
| 709 |
&& copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&> |
| 710 |
&& predicate<_Fn&, iter_reference_t<_Iter>> |
| 711 |
&& predicate<_Fn&, iter_common_reference_t<_Iter>>; |
| 712 |
|
| 713 |
template<typename _Fn, typename _I1, typename _I2> |
| 714 |
concept indirect_binary_predicate |
| 715 |
= indirectly_readable<_I1> && indirectly_readable<_I2> |
| 716 |
&& copy_constructible<_Fn> |
| 717 |
&& predicate<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> |
| 718 |
&& predicate<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> |
| 719 |
&& predicate<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> |
| 720 |
&& predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> |
| 721 |
&& predicate<_Fn&, iter_common_reference_t<_I1>, |
| 722 |
iter_common_reference_t<_I2>>; |
| 723 |
|
| 724 |
template<typename _Fn, typename _I1, typename _I2 = _I1> |
| 725 |
concept indirect_equivalence_relation |
| 726 |
= indirectly_readable<_I1> && indirectly_readable<_I2> |
| 727 |
&& copy_constructible<_Fn> |
| 728 |
&& equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> |
| 729 |
&& equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> |
| 730 |
&& equivalence_relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> |
| 731 |
&& equivalence_relation<_Fn&, iter_reference_t<_I1>, |
| 732 |
iter_reference_t<_I2>> |
| 733 |
&& equivalence_relation<_Fn&, iter_common_reference_t<_I1>, |
| 734 |
iter_common_reference_t<_I2>>; |
| 735 |
|
| 736 |
template<typename _Fn, typename _I1, typename _I2 = _I1> |
| 737 |
concept indirect_strict_weak_order |
| 738 |
= indirectly_readable<_I1> && indirectly_readable<_I2> |
| 739 |
&& copy_constructible<_Fn> |
| 740 |
&& strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> |
| 741 |
&& strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> |
| 742 |
&& strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> |
| 743 |
&& strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> |
| 744 |
&& strict_weak_order<_Fn&, iter_common_reference_t<_I1>, |
| 745 |
iter_common_reference_t<_I2>>; |
| 746 |
|
| 747 |
template<typename _Fn, typename... _Is> |
| 748 |
requires (indirectly_readable<_Is> && ...) |
| 749 |
&& invocable<_Fn, iter_reference_t<_Is>...> |
| 750 |
using indirect_result_t = invoke_result_t<_Fn, iter_reference_t<_Is>...>; |
| 751 |
|
| 752 |
/// [projected], projected |
| 753 |
template<indirectly_readable _Iter, |
| 754 |
indirectly_regular_unary_invocable<_Iter> _Proj> |
| 755 |
struct projected |
| 756 |
{ |
| 757 |
using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>; |
| 758 |
|
| 759 |
indirect_result_t<_Proj&, _Iter> operator*() const; // not defined |
| 760 |
}; |
| 761 |
|
| 762 |
template<weakly_incrementable _Iter, typename _Proj> |
| 763 |
struct incrementable_traits<projected<_Iter, _Proj>> |
| 764 |
{ using difference_type = iter_difference_t<_Iter>; }; |
| 765 |
|
| 766 |
// [alg.req], common algorithm requirements |
| 767 |
|
| 768 |
/// [alg.req.ind.move], concept `indirectly_movable` |
| 769 |
|
| 770 |
template<typename _In, typename _Out> |
| 771 |
concept indirectly_movable = indirectly_readable<_In> |
| 772 |
&& indirectly_writable<_Out, iter_rvalue_reference_t<_In>>; |
| 773 |
|
| 774 |
template<typename _In, typename _Out> |
| 775 |
concept indirectly_movable_storable = indirectly_movable<_In, _Out> |
| 776 |
&& indirectly_writable<_Out, iter_value_t<_In>> |
| 777 |
&& movable<iter_value_t<_In>> |
| 778 |
&& constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> |
| 779 |
&& assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>; |
| 780 |
|
| 781 |
/// [alg.req.ind.copy], concept `indirectly_copyable` |
| 782 |
template<typename _In, typename _Out> |
| 783 |
concept indirectly_copyable = indirectly_readable<_In> |
| 784 |
&& indirectly_writable<_Out, iter_reference_t<_In>>; |
| 785 |
|
| 786 |
template<typename _In, typename _Out> |
| 787 |
concept indirectly_copyable_storable = indirectly_copyable<_In, _Out> |
| 788 |
&& indirectly_writable<_Out, iter_value_t<_In>&> |
| 789 |
&& indirectly_writable<_Out, const iter_value_t<_In>&> |
| 790 |
&& indirectly_writable<_Out, iter_value_t<_In>&&> |
| 791 |
&& indirectly_writable<_Out, const iter_value_t<_In>&&> |
| 792 |
&& copyable<iter_value_t<_In>> |
| 793 |
&& constructible_from<iter_value_t<_In>, iter_reference_t<_In>> |
| 794 |
&& assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>; |
| 795 |
|
| 796 |
namespace ranges |
| 797 |
{ |
| 798 |
namespace __cust_iswap |
| 799 |
{ |
| 800 |
template<typename _It1, typename _It2> |
| 801 |
void iter_swap(_It1, _It2) = delete; |
| 802 |
|
| 803 |
template<typename _Tp, typename _Up> |
| 804 |
concept __adl_iswap |
| 805 |
= (std::__detail::__class_or_enum<remove_reference_t<_Tp>> |
| 806 |
|| std::__detail::__class_or_enum<remove_reference_t<_Up>>) |
| 807 |
&& requires(_Tp&& __t, _Up&& __u) { |
| 808 |
iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u)); |
| 809 |
}; |
| 810 |
|
| 811 |
template<typename _Xp, typename _Yp> |
| 812 |
constexpr iter_value_t<_Xp> |
| 813 |
__iter_exchange_move(_Xp&& __x, _Yp&& __y) |
| 814 |
noexcept(noexcept(iter_value_t<_Xp>(iter_move(__x))) |
| 815 |
&& noexcept(*__x = iter_move(__y))) |
| 816 |
{ |
| 817 |
iter_value_t<_Xp> __old_value(iter_move(__x)); |
| 818 |
*__x = iter_move(__y); |
| 819 |
return __old_value; |
| 820 |
} |
| 821 |
|
| 822 |
struct _IterSwap |
| 823 |
{ |
| 824 |
private: |
| 825 |
template<typename _Tp, typename _Up> |
| 826 |
static constexpr bool |
| 827 |
_S_noexcept() |
| 828 |
{ |
| 829 |
if constexpr (__adl_iswap<_Tp, _Up>) |
| 830 |
return noexcept(iter_swap(std::declval<_Tp>(), |
| 831 |
std::declval<_Up>())); |
| 832 |
else if constexpr (indirectly_readable<_Tp> |
| 833 |
&& indirectly_readable<_Up> |
| 834 |
&& swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) |
| 835 |
return noexcept(ranges::swap(*std::declval<_Tp>(), |
| 836 |
*std::declval<_Up>())); |
| 837 |
else |
| 838 |
return noexcept(*std::declval<_Tp>() |
| 839 |
= __iter_exchange_move(std::declval<_Up>(), |
| 840 |
std::declval<_Tp>())); |
| 841 |
} |
| 842 |
|
| 843 |
public: |
| 844 |
template<typename _Tp, typename _Up> |
| 845 |
requires __adl_iswap<_Tp, _Up> |
| 846 |
|| (indirectly_readable<remove_reference_t<_Tp>> |
| 847 |
&& indirectly_readable<remove_reference_t<_Up>> |
| 848 |
&& swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) |
| 849 |
|| (indirectly_movable_storable<_Tp, _Up> |
| 850 |
&& indirectly_movable_storable<_Up, _Tp>) |
| 851 |
constexpr void |
| 852 |
operator()(_Tp&& __e1, _Up&& __e2) const |
| 853 |
noexcept(_S_noexcept<_Tp, _Up>()) |
| 854 |
{ |
| 855 |
if constexpr (__adl_iswap<_Tp, _Up>) |
| 856 |
iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2)); |
| 857 |
else if constexpr (indirectly_readable<_Tp> |
| 858 |
&& indirectly_readable<_Up> |
| 859 |
&& swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) |
| 860 |
ranges::swap(*__e1, *__e2); |
| 861 |
else |
| 862 |
*__e1 = __iter_exchange_move(__e2, __e1); |
| 863 |
} |
| 864 |
}; |
| 865 |
} // namespace __cust_iswap |
| 866 |
|
| 867 |
inline namespace __cust |
| 868 |
{ |
| 869 |
inline constexpr __cust_iswap::_IterSwap iter_swap{}; |
| 870 |
} // inline namespace __cust |
| 871 |
|
| 872 |
} // namespace ranges |
| 873 |
|
| 874 |
/// [alg.req.ind.swap], concept `indirectly_swappable` |
| 875 |
template<typename _I1, typename _I2 = _I1> |
| 876 |
concept indirectly_swappable |
| 877 |
= indirectly_readable<_I1> && indirectly_readable<_I2> |
| 878 |
&& requires(const _I1 __i1, const _I2 __i2) |
| 879 |
{ |
| 880 |
ranges::iter_swap(__i1, __i1); |
| 881 |
ranges::iter_swap(__i2, __i2); |
| 882 |
ranges::iter_swap(__i1, __i2); |
| 883 |
ranges::iter_swap(__i2, __i1); |
| 884 |
}; |
| 885 |
|
| 886 |
/// [alg.req.ind.cmp], concept `indirectly_comparable` |
| 887 |
template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity, |
| 888 |
typename _P2 = identity> |
| 889 |
concept indirectly_comparable |
| 890 |
= indirect_binary_predicate<_Rel, projected<_I1, _P1>, |
| 891 |
projected<_I2, _P2>>; |
| 892 |
|
| 893 |
/// [alg.req.permutable], concept `permutable` |
| 894 |
template<typename _Iter> |
| 895 |
concept permutable = forward_iterator<_Iter> |
| 896 |
&& indirectly_movable_storable<_Iter, _Iter> |
| 897 |
&& indirectly_swappable<_Iter, _Iter>; |
| 898 |
|
| 899 |
/// [alg.req.mergeable], concept `mergeable` |
| 900 |
template<typename _I1, typename _I2, typename _Out, |
| 901 |
typename _Rel = ranges::less, typename _P1 = identity, |
| 902 |
typename _P2 = identity> |
| 903 |
concept mergeable = input_iterator<_I1> && input_iterator<_I2> |
| 904 |
&& weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out> |
| 905 |
&& indirectly_copyable<_I2, _Out> |
| 906 |
&& indirect_strict_weak_order<_Rel, projected<_I1, _P1>, |
| 907 |
projected<_I2, _P2>>; |
| 908 |
|
| 909 |
/// [alg.req.sortable], concept `sortable` |
| 910 |
template<typename _Iter, typename _Rel = ranges::less, |
| 911 |
typename _Proj = identity> |
| 912 |
concept sortable = permutable<_Iter> |
| 913 |
&& indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>; |
| 914 |
|
| 915 |
struct unreachable_sentinel_t |
| 916 |
{ |
| 917 |
template<weakly_incrementable _It> |
| 918 |
friend constexpr bool |
| 919 |
operator==(unreachable_sentinel_t, const _It&) noexcept |
| 920 |
{ return false; } |
| 921 |
}; |
| 922 |
|
| 923 |
inline constexpr unreachable_sentinel_t unreachable_sentinel{}; |
| 924 |
|
| 925 |
struct default_sentinel_t { }; |
| 926 |
inline constexpr default_sentinel_t default_sentinel{}; |
| 927 |
|
| 928 |
// This is the namespace for [range.access] CPOs. |
| 929 |
namespace ranges::__cust_access |
| 930 |
{ |
| 931 |
using std::__detail::__class_or_enum; |
| 932 |
|
| 933 |
struct _Decay_copy final |
| 934 |
{ |
| 935 |
template<typename _Tp> |
| 936 |
constexpr decay_t<_Tp> |
| 937 |
operator()(_Tp&& __t) const |
| 938 |
noexcept(is_nothrow_convertible_v<_Tp, decay_t<_Tp>>) |
| 939 |
{ return std::forward<_Tp>(__t); } |
| 940 |
} inline constexpr __decay_copy{}; |
| 941 |
|
| 942 |
template<typename _Tp> |
| 943 |
concept __member_begin = requires(_Tp& __t) |
| 944 |
{ |
| 945 |
{ __decay_copy(__t.begin()) } -> input_or_output_iterator; |
| 946 |
}; |
| 947 |
|
| 948 |
// Poison pills so that unqualified lookup doesn't find std::begin. |
| 949 |
void begin(auto&) = delete; |
| 950 |
void begin(const auto&) = delete; |
| 951 |
|
| 952 |
template<typename _Tp> |
| 953 |
concept __adl_begin = __class_or_enum<remove_reference_t<_Tp>> |
| 954 |
&& requires(_Tp& __t) |
| 955 |
{ |
| 956 |
{ __decay_copy(begin(__t)) } -> input_or_output_iterator; |
| 957 |
}; |
| 958 |
|
| 959 |
// Simplified version of std::ranges::begin that only supports lvalues, |
| 960 |
// for use by __range_iter_t below. |
| 961 |
template<typename _Tp> |
| 962 |
requires is_array_v<_Tp> || __member_begin<_Tp&> || __adl_begin<_Tp&> |
| 963 |
auto |
| 964 |
__begin(_Tp& __t) |
| 965 |
{ |
| 966 |
if constexpr (is_array_v<_Tp>) |
| 967 |
return __t + 0; |
| 968 |
else if constexpr (__member_begin<_Tp&>) |
| 969 |
return __t.begin(); |
| 970 |
else |
| 971 |
return begin(__t); |
| 972 |
} |
| 973 |
} // namespace ranges::__cust_access |
| 974 |
|
| 975 |
namespace __detail |
| 976 |
{ |
| 977 |
// Implementation of std::ranges::iterator_t, without using ranges::begin. |
| 978 |
template<typename _Tp> |
| 979 |
using __range_iter_t |
| 980 |
= decltype(ranges::__cust_access::__begin(std::declval<_Tp&>())); |
| 981 |
|
| 982 |
} // namespace __detail |
| 983 |
|
| 984 |
_GLIBCXX_END_NAMESPACE_VERSION |
| 985 |
} // namespace std |
| 986 |
#endif // C++20 library concepts |
| 987 |
#endif // _ITERATOR_CONCEPTS_H |
