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