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 201902L
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  using __is_compatible_array = __and_<
127  bool_constant<(_Extent == dynamic_extent || _ArrayExtent == _Extent)>,
128  __is_array_convertible<_Type, _Tp>>;
129 
130  template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
131  using __is_compatible_iterator = __and_<
132  bool_constant<contiguous_iterator<_Iter>>,
133  is_lvalue_reference<iter_reference_t<_Iter>>,
134  is_same<iter_value_t<_Iter>, remove_cvref_t<_Ref>>,
135  __is_array_convertible<_Type, remove_reference_t<_Ref>>>;
136 
137  template<typename _Range>
138  using __is_compatible_range
139  = __is_compatible_iterator<ranges::iterator_t<_Range>>;
140 
141  public:
142  // member types
143  using value_type = remove_cv_t<_Type>;
144  using element_type = _Type;
145  using size_type = size_t;
146  using reference = element_type&;
147  using const_reference = const element_type&;
148  using pointer = _Type*;
149  using const_pointer = const _Type*;
150  using iterator
151  = __gnu_cxx::__normal_iterator<pointer, span>;
152  using const_iterator
153  = __gnu_cxx::__normal_iterator<const_pointer, span>;
154  using reverse_iterator = std::reverse_iterator<iterator>;
155  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
156  using difference_type = ptrdiff_t;
157 
158  // member constants
159  static inline constexpr size_t extent = _Extent;
160 
161  // constructors
162 
163  constexpr
164  span() noexcept
165  requires ((_Extent + 1u) <= 1u)
166  : _M_extent(0), _M_ptr(nullptr)
167  { }
168 
169  constexpr
170  span(const span&) noexcept = default;
171 
172  template<typename _Tp, size_t _ArrayExtent>
173  requires (__is_compatible_array<_Tp, _ArrayExtent>::value)
174  constexpr
175  span(_Tp (&__arr)[_ArrayExtent]) noexcept
176  : span(static_cast<pointer>(__arr), _ArrayExtent)
177  { }
178 
179  template<typename _Tp, size_t _ArrayExtent>
180  requires (__is_compatible_array<_Tp, _ArrayExtent>::value)
181  constexpr
182  span(array<_Tp, _ArrayExtent>& __arr) noexcept
183  : span(static_cast<pointer>(__arr.data()), _ArrayExtent)
184  { }
185 
186  template<typename _Tp, size_t _ArrayExtent>
187  requires (__is_compatible_array<const _Tp, _ArrayExtent>::value)
188  constexpr
189  span(const array<_Tp, _ArrayExtent>& __arr) noexcept
190  : span(static_cast<pointer>(__arr.data()), _ArrayExtent)
191  { }
192 
193  template<ranges::contiguous_range _Range>
194  requires (_Extent == dynamic_extent)
195  && (!__detail::__is_std_span<remove_cvref_t<_Range>>::value)
196  && (!__detail::__is_std_array<remove_cvref_t<_Range>>::value)
197  && (!is_array_v<remove_reference_t<_Range>>)
198  && (__is_compatible_range<_Range>::value)
199  constexpr
200  span(_Range&& __range)
201  noexcept(noexcept(ranges::data(__range))
202  && noexcept(ranges::size(__range)))
203  : span(ranges::data(__range), ranges::size(__range))
204  { }
205 
206  template<contiguous_iterator _ContiguousIterator,
207  sized_sentinel_for<_ContiguousIterator> _Sentinel>
208  requires (__is_compatible_iterator<_ContiguousIterator>::value)
209  && (!is_convertible_v<_Sentinel, size_type>)
210  constexpr
211  span(_ContiguousIterator __first, _Sentinel __last)
212  noexcept(noexcept(__last - __first))
213  : _M_extent(static_cast<size_type>(__last - __first)),
214  _M_ptr(std::to_address(__first))
215  {
216  if (_Extent != dynamic_extent)
217  __glibcxx_assert((__last - __first) == _Extent);
218  }
219 
220  template<contiguous_iterator _ContiguousIterator>
221  requires (__is_compatible_iterator<_ContiguousIterator>::value)
222  constexpr
223  span(_ContiguousIterator __first, size_type __count)
224  noexcept
225  : _M_extent(__count), _M_ptr(std::to_address(__first))
226  { __glibcxx_assert(_Extent == dynamic_extent || __count == _Extent); }
227 
228  template<typename _OType, size_t _OExtent>
229  requires (_Extent == dynamic_extent || _Extent == _OExtent)
230  && (__is_array_convertible<_Type, _OType>::value)
231  constexpr
232  span(const span<_OType, _OExtent>& __s) noexcept
233  : _M_extent(__s.size()), _M_ptr(__s.data())
234  { }
235 
236  // assignment
237 
238  constexpr span&
239  operator=(const span&) noexcept = default;
240 
241  // observers
242 
243  constexpr size_type
244  size() const noexcept
245  { return this->_M_extent._M_extent(); }
246 
247  constexpr size_type
248  size_bytes() const noexcept
249  { return this->_M_extent._M_extent() * sizeof(element_type); }
250 
251  [[nodiscard]] constexpr bool
252  empty() const noexcept
253  { return size() == 0; }
254 
255  // element access
256 
257  constexpr reference
258  front() const noexcept
259  {
260  static_assert(extent != 0);
261  __glibcxx_assert(!empty());
262  return *this->_M_ptr;
263  }
264 
265  constexpr reference
266  back() const noexcept
267  {
268  static_assert(extent != 0);
269  __glibcxx_assert(!empty());
270  return *(this->_M_ptr + (size() - 1));
271  }
272 
273  constexpr reference
274  operator[](size_type __idx) const noexcept
275  {
276  static_assert(extent != 0);
277  __glibcxx_assert(__idx < size());
278  return *(this->_M_ptr + __idx);
279  }
280 
281  constexpr pointer
282  data() const noexcept
283  { return this->_M_ptr; }
284 
285  // iterator support
286 
287  constexpr iterator
288  begin() const noexcept
289  { return iterator(this->_M_ptr); }
290 
291  constexpr const_iterator
292  cbegin() const noexcept
293  { return const_iterator(this->_M_ptr); }
294 
295  constexpr iterator
296  end() const noexcept
297  { return iterator(this->_M_ptr + this->size()); }
298 
299  constexpr const_iterator
300  cend() const noexcept
301  { return const_iterator(this->_M_ptr + this->size()); }
302 
303  constexpr reverse_iterator
304  rbegin() const noexcept
305  { return reverse_iterator(this->end()); }
306 
307  constexpr const_reverse_iterator
308  crbegin() const noexcept
309  { return const_reverse_iterator(this->cend()); }
310 
311  constexpr reverse_iterator
312  rend() const noexcept
313  { return reverse_iterator(this->begin()); }
314 
315  constexpr const_reverse_iterator
316  crend() const noexcept
317  { return const_reverse_iterator(this->cbegin()); }
318 
319  // subviews
320 
321  template<size_t _Count>
322  constexpr span<element_type, _Count>
323  first() const noexcept
324  {
325  if constexpr (_Extent == dynamic_extent)
326  __glibcxx_assert(_Count <= size());
327  else
328  static_assert(_Count <= extent);
329  return { this->data(), _Count };
330  }
331 
332  constexpr span<element_type, dynamic_extent>
333  first(size_type __count) const noexcept
334  {
335  __glibcxx_assert(__count <= size());
336  return { this->data(), __count };
337  }
338 
339  template<size_t _Count>
340  constexpr span<element_type, _Count>
341  last() const noexcept
342  {
343  if constexpr (_Extent == dynamic_extent)
344  __glibcxx_assert(_Count <= size());
345  else
346  static_assert(_Count <= extent);
347  return { this->data() + (this->size() - _Count), _Count };
348  }
349 
350  constexpr span<element_type, dynamic_extent>
351  last(size_type __count) const noexcept
352  {
353  __glibcxx_assert(__count <= size());
354  return { this->data() + (this->size() - __count), __count };
355  }
356 
357  template<size_t _Offset, size_t _Count = dynamic_extent>
358  constexpr auto
359  subspan() const noexcept
360  -> span<element_type, _S_subspan_extent<_Offset, _Count>()>
361  {
362  if constexpr (_Extent == dynamic_extent)
363  __glibcxx_assert(_Offset <= size());
364  else
365  static_assert(_Offset <= extent);
366 
367  if constexpr (_Count == dynamic_extent)
368  return { this->data() + _Offset, this->size() - _Offset };
369  else
370  {
371  if constexpr (_Extent == dynamic_extent)
372  {
373  __glibcxx_assert(_Count <= size());
374  __glibcxx_assert(_Count <= (size() - _Offset));
375  }
376  else
377  {
378  static_assert(_Count <= extent);
379  static_assert(_Count <= (extent - _Offset));
380  }
381  return { this->data() + _Offset, _Count };
382  }
383  }
384 
385  constexpr span<element_type, dynamic_extent>
386  subspan(size_type __offset, size_type __count = dynamic_extent) const
387  noexcept
388  {
389  __glibcxx_assert(__offset <= size());
390  if (__count == dynamic_extent)
391  __count = this->size() - __offset;
392  else
393  {
394  __glibcxx_assert(__count <= size());
395  __glibcxx_assert(__offset + __count <= size());
396  }
397  return {this->data() + __offset, __count};
398  }
399 
400  private:
401  [[no_unique_address]] __detail::__extent_storage<extent> _M_extent;
402  pointer _M_ptr;
403  };
404 
405  // deduction guides
406 
407  template<typename _Type, size_t _ArrayExtent>
408  span(_Type(&)[_ArrayExtent]) -> span<_Type, _ArrayExtent>;
409 
410  template<typename _Type, size_t _ArrayExtent>
411  span(array<_Type, _ArrayExtent>&) -> span<_Type, _ArrayExtent>;
412 
413  template<typename _Type, size_t _ArrayExtent>
414  span(const array<_Type, _ArrayExtent>&)
415  -> span<const _Type, _ArrayExtent>;
416 
417  template<contiguous_iterator _Iter, typename _Sentinel>
418  span(_Iter, _Sentinel)
419  -> span<remove_reference_t<iter_reference_t<_Iter>>>;
420 
421  template<typename _Range>
422  span(_Range &&)
423  -> span<remove_reference_t<ranges::range_reference_t<_Range&>>>;
424 
425  template<typename _Type, size_t _Extent>
426  inline
427  span<const byte, _Extent == dynamic_extent
428  ? dynamic_extent : _Extent * sizeof(_Type)>
429  as_bytes(span<_Type, _Extent> __sp) noexcept
430  {
431  return {reinterpret_cast<const byte*>(__sp.data()), __sp.size_bytes()};
432  }
433 
434  template<typename _Type, size_t _Extent>
435  inline
436  span<byte, _Extent == dynamic_extent
437  ? dynamic_extent : _Extent * sizeof(_Type)>
438  as_writable_bytes(span<_Type, _Extent> __sp) noexcept
439  {
440  return {reinterpret_cast<byte*>(__sp.data()), __sp.size_bytes()};
441  }
442 
443  // tuple helpers
444  template<size_t _Index, typename _Type, size_t _Extent>
445  constexpr _Type&
446  get(span<_Type, _Extent> __sp) noexcept
447  {
448  static_assert(_Extent != dynamic_extent && _Index < _Extent,
449  "get<I> can only be used with a span of non-dynamic (fixed) extent");
450  return __sp[_Index];
451  }
452 
453  template<typename _Tp> struct tuple_size;
454  template<size_t __i, typename _Tp> struct tuple_element;
455 
456  template<typename _Type, size_t _Extent>
457  struct tuple_size<span<_Type, _Extent>>
458  : public integral_constant<size_t, _Extent>
459  {
460  static_assert(_Extent != dynamic_extent, "tuple_size can only "
461  "be used with a span of non-dynamic (fixed) extent");
462  };
463 
464  template<size_t _Index, typename _Type, size_t _Extent>
465  struct tuple_element<_Index, span<_Type, _Extent>>
466  {
467  static_assert(_Extent != dynamic_extent, "tuple_element can only "
468  "be used with a span of non-dynamic (fixed) extent");
469  static_assert(_Index < _Extent, "Index is less than Extent");
470  using type = _Type;
471  };
472 
473  namespace ranges
474  {
475  template<typename> extern inline const bool enable_safe_range;
476  // Opt-in to safe_range concept
477  template<typename _ElementType, size_t _Extent>
478  inline constexpr bool
479  enable_safe_range<span<_ElementType, _Extent>> = true;
480  }
481 _GLIBCXX_END_NAMESPACE_VERSION
482 } // namespace std
483 #endif // concepts
484 #endif // C++20
485 #endif // _GLIBCXX_SPAN
std::cend
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:129
std::cbegin
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:118
std::true_type
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:75
range_access.h
std::false_type
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:78
std::crbegin
constexpr auto crbegin(const _Container &__cont) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
Definition: range_access.h:220
std::reverse_iterator
Definition: bits/stl_iterator.h:110
stl_iterator.h
std::crend
constexpr auto crend(const _Container &__cont) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
Definition: range_access.h:230
std::rbegin
constexpr auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
Definition: range_access.h:140
std
ISO C++ entities toplevel namespace is std.
std::begin
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
std::end
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
std::rend
constexpr auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
Definition: range_access.h:160