libstdc++
ranges_util.h
Go to the documentation of this file.
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 // <http://www.gnu.org/licenses/>.
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 <bits/ranges_base.h>
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<typename _Range>
47  concept __simple_view = view<_Range> && range<const _Range>
48  && same_as<iterator_t<_Range>, iterator_t<const _Range>>
49  && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
50 
51  template<typename _It>
52  concept __has_arrow = input_iterator<_It>
53  && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
54 
55  template<typename _Tp, typename _Up>
56  concept __not_same_as
57  = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
58  } // namespace __detail
59 
60  /// The ranges::view_interface class template
61  template<typename _Derived>
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<const _Derived&>(*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<const _Derived>
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<iterator_t<_Derived>>
99  { return to_address(ranges::begin(_M_derived())); }
100 
101  constexpr auto
102  data() const
103  requires range<const _Derived>
104  && contiguous_iterator<iterator_t<const _Derived>>
105  { return to_address(ranges::begin(_M_derived())); }
106 
107  constexpr auto
108  size()
109  requires forward_range<_Derived>
110  && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
111  { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
112 
113  constexpr auto
114  size() const
115  requires forward_range<const _Derived>
116  && sized_sentinel_for<sentinel_t<const _Derived>,
117  iterator_t<const _Derived>>
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<const _Derived>
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<const _Derived>
145  && common_range<const _Derived>
146  {
147  __glibcxx_assert(!empty());
148  return *ranges::prev(ranges::end(_M_derived()));
149  }
150 
151  template<random_access_range _Range = _Derived>
152  constexpr decltype(auto)
153  operator[](range_difference_t<_Range> __n)
154  { return ranges::begin(_M_derived())[__n]; }
155 
156  template<random_access_range _Range = const _Derived>
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<class _From, class _To>
165  concept __convertible_to_non_slicing = convertible_to<_From, _To>
166  && !(is_pointer_v<decay_t<_From>> && is_pointer_v<decay_t<_To>>
167  && __not_same_as<remove_pointer_t<decay_t<_From>>,
168  remove_pointer_t<decay_t<_To>>>);
169 
170  template<typename _Tp>
171  concept __pair_like
172  = !is_reference_v<_Tp> && requires(_Tp __t)
173  {
174  typename tuple_size<_Tp>::type;
175  requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
176  typename tuple_element_t<0, remove_const_t<_Tp>>;
177  typename tuple_element_t<1, remove_const_t<_Tp>>;
178  { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
179  { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
180  };
181 
182  template<typename _Tp, typename _Up, typename _Vp>
183  concept __pair_like_convertible_from
184  = !range<_Tp> && __pair_like<_Tp>
185  && constructible_from<_Tp, _Up, _Vp>
186  && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
187  && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
188 
189  } // namespace __detail
190 
191  enum class subrange_kind : bool { unsized, sized };
192 
193  /// The ranges::subrange class template
194  template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
195  subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
196  ? subrange_kind::sized : subrange_kind::unsized>
197  requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
198  class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
199  {
200  private:
201  // XXX: gcc complains when using constexpr here
202  static const bool _S_store_size
203  = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
204 
205  _It _M_begin = _It();
206  [[no_unique_address]] _Sent _M_end = _Sent();
207 
208  using __size_type
209  = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
210 
211  template<typename, bool = _S_store_size>
212  struct _Size
213  { };
214 
215  template<typename _Tp>
216  struct _Size<_Tp, true>
217  { _Tp _M_size; };
218 
219  [[no_unique_address]] _Size<__size_type> _M_size = {};
220 
221  public:
222  subrange() = default;
223 
224  constexpr
225  subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
226  requires (!_S_store_size)
227  : _M_begin(std::move(__i)), _M_end(__s)
228  { }
229 
230  constexpr
231  subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
232  __size_type __n)
233  requires (_Kind == subrange_kind::sized)
234  : _M_begin(std::move(__i)), _M_end(__s)
235  {
236  if constexpr (_S_store_size)
237  _M_size._M_size = __n;
238  }
239 
240  template<__detail::__not_same_as<subrange> _Rng>
241  requires borrowed_range<_Rng>
242  && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
243  && convertible_to<sentinel_t<_Rng>, _Sent>
244  constexpr
245  subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng>
246  : subrange(__r, ranges::size(__r))
247  { }
248 
249  template<__detail::__not_same_as<subrange> _Rng>
250  requires borrowed_range<_Rng>
251  && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
252  && convertible_to<sentinel_t<_Rng>, _Sent>
253  constexpr
254  subrange(_Rng&& __r) requires (!_S_store_size)
255  : subrange(ranges::begin(__r), ranges::end(__r))
256  { }
257 
258  template<borrowed_range _Rng>
259  requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
260  && convertible_to<sentinel_t<_Rng>, _Sent>
261  constexpr
262  subrange(_Rng&& __r, __size_type __n)
263  requires (_Kind == subrange_kind::sized)
264  : subrange{ranges::begin(__r), ranges::end(__r), __n}
265  { }
266 
267  template<__detail::__not_same_as<subrange> _PairLike>
268  requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
269  const _Sent&>
270  constexpr
271  operator _PairLike() const
272  { return _PairLike(_M_begin, _M_end); }
273 
274  constexpr _It
275  begin() const requires copyable<_It>
276  { return _M_begin; }
277 
278  [[nodiscard]] constexpr _It
279  begin() requires (!copyable<_It>)
280  { return std::move(_M_begin); }
281 
282  constexpr _Sent end() const { return _M_end; }
283 
284  constexpr bool empty() const { return _M_begin == _M_end; }
285 
286  constexpr __size_type
287  size() const requires (_Kind == subrange_kind::sized)
288  {
289  if constexpr (_S_store_size)
290  return _M_size._M_size;
291  else
292  return __detail::__to_unsigned_like(_M_end - _M_begin);
293  }
294 
295  [[nodiscard]] constexpr subrange
296  next(iter_difference_t<_It> __n = 1) const &
297  requires forward_iterator<_It>
298  {
299  auto __tmp = *this;
300  __tmp.advance(__n);
301  return __tmp;
302  }
303 
304  [[nodiscard]] constexpr subrange
305  next(iter_difference_t<_It> __n = 1) &&
306  {
307  advance(__n);
308  return std::move(*this);
309  }
310 
311  [[nodiscard]] constexpr subrange
312  prev(iter_difference_t<_It> __n = 1) const
313  requires bidirectional_iterator<_It>
314  {
315  auto __tmp = *this;
316  __tmp.advance(-__n);
317  return __tmp;
318  }
319 
320  constexpr subrange&
321  advance(iter_difference_t<_It> __n)
322  {
323  // _GLIBCXX_RESOLVE_LIB_DEFECTS
324  // 3433. subrange::advance(n) has UB when n < 0
325  if constexpr (bidirectional_iterator<_It>)
326  if (__n < 0)
327  {
328  ranges::advance(_M_begin, __n);
329  if constexpr (_S_store_size)
330  _M_size._M_size += __detail::__to_unsigned_like(-__n);
331  return *this;
332  }
333 
334  __glibcxx_assert(__n >= 0);
335  auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
336  if constexpr (_S_store_size)
337  _M_size._M_size -= __detail::__to_unsigned_like(__d);
338  return *this;
339  }
340  };
341 
342  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
343  subrange(_It, _Sent) -> subrange<_It, _Sent>;
344 
345  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
346  subrange(_It, _Sent,
347  __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
348  -> subrange<_It, _Sent, subrange_kind::sized>;
349 
350  template<borrowed_range _Rng>
351  subrange(_Rng&&)
352  -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
353  (sized_range<_Rng>
354  || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
355  ? subrange_kind::sized : subrange_kind::unsized>;
356 
357  template<borrowed_range _Rng>
358  subrange(_Rng&&,
359  __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
360  -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
361 
362  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
363  requires (_Num < 2)
364  constexpr auto
365  get(const subrange<_It, _Sent, _Kind>& __r)
366  {
367  if constexpr (_Num == 0)
368  return __r.begin();
369  else
370  return __r.end();
371  }
372 
373  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
374  requires (_Num < 2)
375  constexpr auto
376  get(subrange<_It, _Sent, _Kind>&& __r)
377  {
378  if constexpr (_Num == 0)
379  return __r.begin();
380  else
381  return __r.end();
382  }
383 
384  template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
385  subrange_kind _Kind>
386  inline constexpr bool
387  enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
388 
389  template<range _Range>
390  using borrowed_subrange_t = conditional_t<borrowed_range<_Range>,
391  subrange<iterator_t<_Range>>,
392  dangling>;
393 
394 } // namespace ranges
395 
396  using ranges::get;
397 
398  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
399  struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
400  : integral_constant<size_t, 2>
401  { };
402 
403  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
404  struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
405  { using type = _Iter; };
406 
407  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
408  struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
409  { using type = _Sent; };
410 
411  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
412  struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
413  { using type = _Iter; };
414 
415  template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
416  struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
417  { using type = _Sent; };
418 
419 _GLIBCXX_END_NAMESPACE_VERSION
420 } // namespace std
421 #endif // library concepts
422 #endif // C++20
423 #endif // _RANGES_UTIL_H
typename conditional< _Cond, _Iftrue, _Iffalse >::type conditional_t
Alias template for conditional.
Definition: type_traits:2518
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:263
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:245
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
Definition: range_access.h:290