libstdc++
span
Go to the documentation of this file.
1 // Components for manipulating non-owning sequences of objects -*- C++ -*-
2 
3 // Copyright (C) 2019-2023 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 span
26  * This is a Standard C++ Library header.
27  */
28 
29 //
30 // P0122 span library
31 // Contributed by ThePhD
32 //
33 
34 #ifndef _GLIBCXX_SPAN
35 #define _GLIBCXX_SPAN 1
36 
37 #pragma GCC system_header
38 
39 #if __cplusplus > 201703L
40 
41 #include <array>
42 #include <cstddef>
43 #include <bits/stl_iterator.h>
44 #include <bits/ranges_base.h>
45 
46 #if __cpp_lib_concepts
47 namespace std _GLIBCXX_VISIBILITY(default)
48 {
49 _GLIBCXX_BEGIN_NAMESPACE_VERSION
50 
51 #define __cpp_lib_span 202002L
52 
53  inline constexpr size_t dynamic_extent = static_cast<size_t>(-1);
54 
55  template<typename _Type, size_t _Extent>
56  class span;
57 
58  namespace __detail
59  {
60  template<typename _Tp>
61  inline constexpr bool __is_span = false;
62 
63  template<typename _Tp, size_t _Num>
64  inline constexpr bool __is_span<span<_Tp, _Num>> = true;
65 
66  template<typename _Tp>
67  inline constexpr bool __is_std_array = false;
68 
69  template<typename _Tp, size_t _Num>
70  inline constexpr bool __is_std_array<std::array<_Tp, _Num>> = true;
71 
72  template<size_t _Extent>
73  class __extent_storage
74  {
75  public:
76  constexpr
77  __extent_storage(size_t) noexcept
78  { }
79 
80  static constexpr size_t
81  _M_extent() noexcept
82  { return _Extent; }
83  };
84 
85  template<>
86  class __extent_storage<dynamic_extent>
87  {
88  public:
89  constexpr
90  __extent_storage(size_t __extent) noexcept
91  : _M_extent_value(__extent)
92  { }
93 
94  constexpr size_t
95  _M_extent() const noexcept
96  { return this->_M_extent_value; }
97 
98  private:
99  size_t _M_extent_value;
100  };
101  } // namespace __detail
102 
103  template<typename _Type, size_t _Extent = dynamic_extent>
104  class span
105  {
106  template<size_t _Offset, size_t _Count>
107  static constexpr size_t
108  _S_subspan_extent()
109  {
110  if constexpr (_Count != dynamic_extent)
111  return _Count;
112  else if constexpr (extent != dynamic_extent)
113  return _Extent - _Offset;
114  else
115  return dynamic_extent;
116  }
117 
118  // _GLIBCXX_RESOLVE_LIB_DEFECTS
119  // 3255. span's array constructor is too strict
120  template<typename _Tp, size_t _ArrayExtent>
121  requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
122  using __is_compatible_array = __is_array_convertible<_Type, _Tp>;
123 
124  template<typename _Ref>
125  using __is_compatible_ref
126  = __is_array_convertible<_Type, remove_reference_t<_Ref>>;
127 
128  public:
129  // member types
130  using element_type = _Type;
131  using value_type = remove_cv_t<_Type>;
132  using size_type = size_t;
133  using difference_type = ptrdiff_t;
134  using pointer = _Type*;
135  using const_pointer = const _Type*;
136  using reference = element_type&;
137  using const_reference = const element_type&;
138  using iterator = __gnu_cxx::__normal_iterator<pointer, span>;
139  using reverse_iterator = std::reverse_iterator<iterator>;
140 #if __cplusplus > 202002L
141  using const_iterator = std::const_iterator<iterator>;
142  using const_reverse_iterator = std::const_iterator<reverse_iterator>;
143 #endif
144 
145  // member constants
146  static constexpr size_t extent = _Extent;
147 
148  // constructors, copy and assignment
149 
150  constexpr
151  span() noexcept
152  requires (_Extent == dynamic_extent || _Extent == 0)
153  : _M_ptr(nullptr), _M_extent(0)
154  { }
155 
156  template<contiguous_iterator _It>
157  requires __is_compatible_ref<iter_reference_t<_It>>::value
158  constexpr explicit(extent != dynamic_extent)
159  span(_It __first, size_type __count)
160  noexcept
161  : _M_ptr(std::to_address(__first)), _M_extent(__count)
162  {
163  if constexpr (_Extent != dynamic_extent)
164  {
165  __glibcxx_assert(__count == _Extent);
166  }
167  __glibcxx_requires_valid_range(__first, __first + __count);
168  }
169 
170  template<contiguous_iterator _It, sized_sentinel_for<_It> _End>
171  requires __is_compatible_ref<iter_reference_t<_It>>::value
172  && (!is_convertible_v<_End, size_type>)
173  constexpr explicit(extent != dynamic_extent)
174  span(_It __first, _End __last)
175  noexcept(noexcept(__last - __first))
176  : _M_ptr(std::to_address(__first)),
177  _M_extent(static_cast<size_type>(__last - __first))
178  {
179  if constexpr (_Extent != dynamic_extent)
180  {
181  __glibcxx_assert((__last - __first) == _Extent);
182  }
183  __glibcxx_requires_valid_range(__first, __last);
184  }
185 
186  template<size_t _ArrayExtent>
187  requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
188  constexpr
189  span(type_identity_t<element_type> (&__arr)[_ArrayExtent]) noexcept
190  : span(static_cast<pointer>(__arr), _ArrayExtent)
191  { }
192 
193  template<typename _Tp, size_t _ArrayExtent>
194  requires __is_compatible_array<_Tp, _ArrayExtent>::value
195  constexpr
196  span(array<_Tp, _ArrayExtent>& __arr) noexcept
197  : span(static_cast<pointer>(__arr.data()), _ArrayExtent)
198  { }
199 
200  template<typename _Tp, size_t _ArrayExtent>
201  requires __is_compatible_array<const _Tp, _ArrayExtent>::value
202  constexpr
203  span(const array<_Tp, _ArrayExtent>& __arr) noexcept
204  : span(static_cast<pointer>(__arr.data()), _ArrayExtent)
205  { }
206 
207  template<typename _Range>
208  requires (!__detail::__is_span<remove_cvref_t<_Range>>)
209  && (!__detail::__is_std_array<remove_cvref_t<_Range>>)
210  && (!is_array_v<remove_cvref_t<_Range>>)
211  && ranges::contiguous_range<_Range> && ranges::sized_range<_Range>
212  && (ranges::borrowed_range<_Range> || is_const_v<element_type>)
213  && __is_compatible_ref<ranges::range_reference_t<_Range>>::value
214  constexpr explicit(extent != dynamic_extent)
215  span(_Range&& __range)
216  noexcept(noexcept(ranges::data(__range))
217  && noexcept(ranges::size(__range)))
218  : span(ranges::data(__range), ranges::size(__range))
219  {
220  if constexpr (extent != dynamic_extent)
221  {
222  __glibcxx_assert(ranges::size(__range) == extent);
223  }
224  }
225 
226  constexpr
227  span(const span&) noexcept = default;
228 
229  template<typename _OType, size_t _OExtent>
230  requires (_Extent == dynamic_extent || _OExtent == dynamic_extent
231  || _Extent == _OExtent)
232  && (__is_array_convertible<_Type, _OType>::value)
233  constexpr
234  explicit(extent != dynamic_extent && _OExtent == dynamic_extent)
235  span(const span<_OType, _OExtent>& __s) noexcept
236  : _M_extent(__s.size()), _M_ptr(__s.data())
237  {
238  if constexpr (extent != dynamic_extent)
239  {
240  __glibcxx_assert(__s.size() == extent);
241  }
242  }
243 
244  ~span() noexcept = default;
245 
246  constexpr span&
247  operator=(const span&) noexcept = default;
248 
249  // observers
250 
251  [[nodiscard]]
252  constexpr size_type
253  size() const noexcept
254  { return this->_M_extent._M_extent(); }
255 
256  [[nodiscard]]
257  constexpr size_type
258  size_bytes() const noexcept
259  { return this->_M_extent._M_extent() * sizeof(element_type); }
260 
261  [[nodiscard]]
262  constexpr bool
263  empty() const noexcept
264  { return size() == 0; }
265 
266  // element access
267 
268  [[nodiscard]]
269  constexpr reference
270  front() const noexcept
271  {
272  __glibcxx_assert(!empty());
273  return *this->_M_ptr;
274  }
275 
276  [[nodiscard]]
277  constexpr reference
278  back() const noexcept
279  {
280  __glibcxx_assert(!empty());
281  return *(this->_M_ptr + (size() - 1));
282  }
283 
284  [[nodiscard]]
285  constexpr reference
286  operator[](size_type __idx) const noexcept
287  {
288  __glibcxx_assert(__idx < size());
289  return *(this->_M_ptr + __idx);
290  }
291 
292  [[nodiscard]]
293  constexpr pointer
294  data() const noexcept
295  { return this->_M_ptr; }
296 
297  // iterator support
298 
299  [[nodiscard]]
300  constexpr iterator
301  begin() const noexcept
302  { return iterator(this->_M_ptr); }
303 
304  [[nodiscard]]
305  constexpr iterator
306  end() const noexcept
307  { return iterator(this->_M_ptr + this->size()); }
308 
309  [[nodiscard]]
310  constexpr reverse_iterator
311  rbegin() const noexcept
312  { return reverse_iterator(this->end()); }
313 
314  [[nodiscard]]
315  constexpr reverse_iterator
316  rend() const noexcept
317  { return reverse_iterator(this->begin()); }
318 
319 #if __cplusplus > 202002L
320  [[nodiscard]]
321  constexpr const_iterator
322  cbegin() const noexcept
323  { return begin(); }
324 
325  [[nodiscard]]
326  constexpr const_iterator
327  cend() const noexcept
328  { return end(); }
329 
330  [[nodiscard]]
331  constexpr const_reverse_iterator
332  crbegin() const noexcept
333  { return rbegin(); }
334 
335  [[nodiscard]]
336  constexpr const_reverse_iterator
337  crend() const noexcept
338  { return rend(); }
339 #endif
340 
341  // subviews
342 
343  template<size_t _Count>
344  [[nodiscard]]
345  constexpr span<element_type, _Count>
346  first() const noexcept
347  {
348  if constexpr (_Extent == dynamic_extent)
349  __glibcxx_assert(_Count <= size());
350  else
351  static_assert(_Count <= extent);
352  using _Sp = span<element_type, _Count>;
353  return _Sp{ this->data(), _Count };
354  }
355 
356  [[nodiscard]]
357  constexpr span<element_type, dynamic_extent>
358  first(size_type __count) const noexcept
359  {
360  __glibcxx_assert(__count <= size());
361  return { this->data(), __count };
362  }
363 
364  template<size_t _Count>
365  [[nodiscard]]
366  constexpr span<element_type, _Count>
367  last() const noexcept
368  {
369  if constexpr (_Extent == dynamic_extent)
370  __glibcxx_assert(_Count <= size());
371  else
372  static_assert(_Count <= extent);
373  using _Sp = span<element_type, _Count>;
374  return _Sp{ this->data() + (this->size() - _Count), _Count };
375  }
376 
377  [[nodiscard]]
378  constexpr span<element_type, dynamic_extent>
379  last(size_type __count) const noexcept
380  {
381  __glibcxx_assert(__count <= size());
382  return { this->data() + (this->size() - __count), __count };
383  }
384 
385  template<size_t _Offset, size_t _Count = dynamic_extent>
386  [[nodiscard]]
387  constexpr auto
388  subspan() const noexcept
389  -> span<element_type, _S_subspan_extent<_Offset, _Count>()>
390  {
391  if constexpr (_Extent == dynamic_extent)
392  {
393  __glibcxx_assert(_Offset <= size());
394  }
395  else
396  static_assert(_Offset <= extent);
397 
398  using _Sp = span<element_type, _S_subspan_extent<_Offset, _Count>()>;
399 
400  if constexpr (_Count == dynamic_extent)
401  return _Sp{ this->data() + _Offset, this->size() - _Offset };
402  else
403  {
404  if constexpr (_Extent == dynamic_extent)
405  {
406  __glibcxx_assert(_Count <= size());
407  __glibcxx_assert(_Count <= (size() - _Offset));
408  }
409  else
410  {
411  static_assert(_Count <= extent);
412  static_assert(_Count <= (extent - _Offset));
413  }
414  return _Sp{ this->data() + _Offset, _Count };
415  }
416  }
417 
418  [[nodiscard]]
419  constexpr span<element_type, dynamic_extent>
420  subspan(size_type __offset, size_type __count = dynamic_extent) const
421  noexcept
422  {
423  __glibcxx_assert(__offset <= size());
424  if (__count == dynamic_extent)
425  __count = this->size() - __offset;
426  else
427  {
428  __glibcxx_assert(__count <= size());
429  __glibcxx_assert(__offset + __count <= size());
430  }
431  return {this->data() + __offset, __count};
432  }
433 
434  private:
435  pointer _M_ptr;
436  [[no_unique_address]] __detail::__extent_storage<extent> _M_extent;
437  };
438 
439  // deduction guides
440 
441  template<typename _Type, size_t _ArrayExtent>
442  span(_Type(&)[_ArrayExtent]) -> span<_Type, _ArrayExtent>;
443 
444  template<typename _Type, size_t _ArrayExtent>
445  span(array<_Type, _ArrayExtent>&) -> span<_Type, _ArrayExtent>;
446 
447  template<typename _Type, size_t _ArrayExtent>
448  span(const array<_Type, _ArrayExtent>&)
449  -> span<const _Type, _ArrayExtent>;
450 
451  template<contiguous_iterator _Iter, typename _End>
452  span(_Iter, _End)
453  -> span<remove_reference_t<iter_reference_t<_Iter>>>;
454 
455  template<ranges::contiguous_range _Range>
456  span(_Range &&)
457  -> span<remove_reference_t<ranges::range_reference_t<_Range&>>>;
458 
459  template<typename _Type, size_t _Extent>
460  [[nodiscard]]
461  inline
462  span<const byte, _Extent == dynamic_extent
463  ? dynamic_extent : _Extent * sizeof(_Type)>
464  as_bytes(span<_Type, _Extent> __sp) noexcept
465  {
466  auto data = reinterpret_cast<const byte*>(__sp.data());
467  auto size = __sp.size_bytes();
468  constexpr auto extent = _Extent == dynamic_extent
469  ? dynamic_extent : _Extent * sizeof(_Type);
470  return span<const byte, extent>{data, size};
471  }
472 
473  template<typename _Type, size_t _Extent>
474  requires (!is_const_v<_Type>)
475  inline
476  span<byte, _Extent == dynamic_extent
477  ? dynamic_extent : _Extent * sizeof(_Type)>
478  as_writable_bytes [[nodiscard]] (span<_Type, _Extent> __sp) noexcept
479  {
480  auto data = reinterpret_cast<byte*>(__sp.data());
481  auto size = __sp.size_bytes();
482  constexpr auto extent = _Extent == dynamic_extent
483  ? dynamic_extent : _Extent * sizeof(_Type);
484  return span<byte, extent>{data, size};
485  }
486 
487  namespace ranges
488  {
489  // Opt-in to borrowed_range concept
490  template<typename _ElementType, size_t _Extent>
491  inline constexpr bool
492  enable_borrowed_range<span<_ElementType, _Extent>> = true;
493 
494  // Opt-in to view concept
495  template<typename _ElementType, size_t _Extent>
496  inline constexpr bool
497  enable_view<span<_ElementType, _Extent>> = true;
498  }
499 _GLIBCXX_END_NAMESPACE_VERSION
500 } // namespace std
501 #endif // concepts
502 #endif // C++20
503 #endif // _GLIBCXX_SPAN