1// Components for manipulating non-owning sequences of objects -*- C++ -*-
2
3// Copyright (C) 2019-2026 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#ifdef _GLIBCXX_SYSHDR
38#pragma GCC system_header
39#endif
40
41#define __glibcxx_want_span
42#define __glibcxx_want_span_initializer_list
43#include <bits/version.h>
44
45#ifdef __cpp_lib_span // C++ >= 20 && concepts
46#include <array>
47#include <cstddef>
48#include <bits/stl_iterator.h>
49#include <bits/ranges_base.h>
50
51namespace std _GLIBCXX_VISIBILITY(default)
52{
53_GLIBCXX_BEGIN_NAMESPACE_VERSION
54
55 inline constexpr size_t dynamic_extent = static_cast<size_t>(-1);
56
57 template<typename _Type, size_t _Extent>
58 class span;
59
60 namespace __detail
61 {
62 template<typename _Tp>
63 inline constexpr bool __is_span = false;
64
65 template<typename _Tp, size_t _Num>
66 inline constexpr bool __is_span<span<_Tp, _Num>> = true;
67
68 template<typename _Tp>
69 inline constexpr bool __is_std_array = false;
70
71 template<typename _Tp, size_t _Num>
72 inline constexpr bool __is_std_array<std::array<_Tp, _Num>> = true;
73
74 template<size_t _Extent>
75 class __extent_storage
76 {
77 public:
78 // Used for runtime sizes that must satisfy the precondition.
79 constexpr
80 __extent_storage([[maybe_unused]] size_t __n) noexcept
81 { __glibcxx_assert(__n == _Extent); }
82
83 // Used for constant sizes that are already known to be correct.
84 consteval
85 __extent_storage(integral_constant<size_t, _Extent>) noexcept
86 { }
87
88 // "I've made a huge mistake" - George Oscar Bluth II
89 template<size_t _Gob>
90 __extent_storage(integral_constant<size_t, _Gob>) = delete;
91
92 [[__gnu__::__always_inline__]]
93 static constexpr size_t
94 _M_extent() noexcept
95 { return _Extent; }
96 };
97
98 template<>
99 class __extent_storage<dynamic_extent>
100 {
101 public:
102 [[__gnu__::__always_inline__]]
103 constexpr
104 __extent_storage(size_t __extent) noexcept
105 : _M_extent_value(__extent)
106 { }
107
108 [[__gnu__::__always_inline__]]
109 constexpr size_t
110 _M_extent() const noexcept
111 { return this->_M_extent_value; }
112
113 private:
114 size_t _M_extent_value;
115 };
116
117 template<typename _Type> struct __span_ptr { _Type* const _M_ptr; };
118
119 } // namespace __detail
120
121 template<typename _Type, size_t _Extent = dynamic_extent>
122 class span
123 {
124 template<size_t _Offset, size_t _Count>
125 static constexpr size_t
126 _S_subspan_extent()
127 {
128 if constexpr (_Count != dynamic_extent)
129 return _Count;
130 else if constexpr (extent != dynamic_extent)
131 return _Extent - _Offset;
132 else
133 return dynamic_extent;
134 }
135
136 // _GLIBCXX_RESOLVE_LIB_DEFECTS
137 // 3255. span's array constructor is too strict
138 template<typename _Tp, size_t _ArrayExtent>
139 requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
140 using __is_compatible_array = __is_array_convertible<_Type, _Tp>;
141
142 template<typename _Ref>
143 using __is_compatible_ref
144 = __is_array_convertible<_Type, remove_reference_t<_Ref>>;
145
146 // Nested type so that _Type is not an associated class of iterator.
147 struct __iter_tag;
148
149 template<size_t _Nm>
150 static inline constexpr integral_constant<size_t, _Nm> __v{};
151
152 public:
153 // member types
154 using element_type = _Type;
155 using value_type = remove_cv_t<_Type>;
156 using size_type = size_t;
157 using difference_type = ptrdiff_t;
158 using pointer = _Type*;
159 using const_pointer = const _Type*;
160 using reference = element_type&;
161 using const_reference = const element_type&;
162 using iterator = __gnu_cxx::__normal_iterator<pointer, __iter_tag>;
163 using reverse_iterator = std::reverse_iterator<iterator>;
164#if __cplusplus > 202002L
165 using const_iterator = std::const_iterator<iterator>;
166 using const_reverse_iterator = std::const_iterator<reverse_iterator>;
167#endif
168
169 // member constants
170 static constexpr size_t extent = _Extent;
171
172 // constructors, copy and assignment
173
174 constexpr
175 span() noexcept
176 requires (_Extent == dynamic_extent || _Extent == 0)
177 : _M_ptr(nullptr), _M_extent(__v<0>)
178 { }
179
180 template<contiguous_iterator _It>
181 requires __is_compatible_ref<iter_reference_t<_It>>::value
182 constexpr explicit(extent != dynamic_extent)
183 span(_It __first, size_type __count)
184 noexcept
185 : _M_ptr(std::to_address(__first)), _M_extent(__count)
186 { __glibcxx_requires_valid_range(__first, __first + __count); }
187
188 template<contiguous_iterator _It, sized_sentinel_for<_It> _End>
189 requires __is_compatible_ref<iter_reference_t<_It>>::value
190 && (!is_convertible_v<_End, size_type>)
191 constexpr explicit(extent != dynamic_extent)
192 span(_It __first, _End __last)
193 noexcept(noexcept(__last - __first))
194 : _M_ptr(std::to_address(__first)),
195 _M_extent(static_cast<size_type>(__last - __first))
196 { __glibcxx_requires_valid_range(__first, __last); }
197
198 template<size_t _ArrayExtent>
199 requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
200 constexpr
201 span(type_identity_t<element_type> (&__arr)[_ArrayExtent]) noexcept
202 : _M_ptr(__arr), _M_extent(__v<_ArrayExtent>)
203 { }
204
205 template<typename _Tp, size_t _ArrayExtent>
206 requires __is_compatible_array<_Tp, _ArrayExtent>::value
207 constexpr
208 span(array<_Tp, _ArrayExtent>& __arr) noexcept
209 : _M_ptr(__arr.data()), _M_extent(__v<_ArrayExtent>)
210 { }
211
212 template<typename _Tp, size_t _ArrayExtent>
213 requires __is_compatible_array<const _Tp, _ArrayExtent>::value
214 constexpr
215 span(const array<_Tp, _ArrayExtent>& __arr) noexcept
216 : _M_ptr(__arr.data()), _M_extent(__v<_ArrayExtent>)
217 { }
218
219 template<typename _Range>
220 requires (!__detail::__is_span<remove_cvref_t<_Range>>)
221 && (!__detail::__is_std_array<remove_cvref_t<_Range>>)
222 && (!is_array_v<remove_cvref_t<_Range>>)
223 && ranges::contiguous_range<_Range> && ranges::sized_range<_Range>
224 && (ranges::borrowed_range<_Range> || is_const_v<element_type>)
225 && __is_compatible_ref<ranges::range_reference_t<_Range>>::value
226 constexpr explicit(extent != dynamic_extent)
227 span(_Range&& __range)
228 noexcept(noexcept(ranges::data(__range))
229 && noexcept(ranges::size(__range)))
230 : _M_ptr(ranges::data(__range)), _M_extent(ranges::size(__range))
231 { }
232
233 constexpr
234 span(const span&) noexcept = default;
235
236 template<typename _OType, size_t _OExtent>
237 requires (_Extent == dynamic_extent || _OExtent == dynamic_extent
238 || _Extent == _OExtent)
239 && (__is_array_convertible<_Type, _OType>::value)
240 constexpr
241 explicit(extent != dynamic_extent && _OExtent == dynamic_extent)
242 span(const span<_OType, _OExtent>& __s) noexcept
243 : _M_ptr(__s.data()), _M_extent(__s.size())
244 { }
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#if __cpp_lib_span >= 202311L // >= C++26
293 [[nodiscard]]
294 constexpr reference
295 at(size_type __idx) const
296 {
297 if (__idx >= size())
298 __throw_out_of_range_fmt(__N("span::at(%zu) out-of-range for span "
299 "of size %zu"), __idx, this->size());
300 return *(this->_M_ptr + __idx);
301 }
302#endif
303
304 [[nodiscard]]
305 constexpr pointer
306 data() const noexcept
307 { return this->_M_ptr; }
308
309 // iterator support
310
311 [[nodiscard]]
312 constexpr iterator
313 begin() const noexcept
314 { return iterator(this->_M_ptr); }
315
316 [[nodiscard]]
317 constexpr iterator
318 end() const noexcept
319 { return iterator(this->_M_ptr + this->size()); }
320
321 [[nodiscard]]
322 constexpr reverse_iterator
323 rbegin() const noexcept
324 { return reverse_iterator(this->end()); }
325
326 [[nodiscard]]
327 constexpr reverse_iterator
328 rend() const noexcept
329 { return reverse_iterator(this->begin()); }
330
331#if __cplusplus > 202002L
332 [[nodiscard]]
333 constexpr const_iterator
334 cbegin() const noexcept
335 { return begin(); }
336
337 [[nodiscard]]
338 constexpr const_iterator
339 cend() const noexcept
340 { return end(); }
341
342 [[nodiscard]]
343 constexpr const_reverse_iterator
344 crbegin() const noexcept
345 { return rbegin(); }
346
347 [[nodiscard]]
348 constexpr const_reverse_iterator
349 crend() const noexcept
350 { return rend(); }
351#endif
352
353 // subviews
354
355 template<size_t _Count>
356 [[nodiscard]]
357 constexpr span<element_type, _Count>
358 first() const noexcept
359 {
360 if constexpr (_Extent == dynamic_extent)
361 __glibcxx_assert(_Count <= size());
362 else
363 static_assert(_Count <= extent);
364 using _Sp = span<element_type, _Count>;
365 return _Sp(_SizedPtr{this->data()});
366 }
367
368 [[nodiscard]]
369 constexpr span<element_type, dynamic_extent>
370 first(size_type __count) const noexcept
371 {
372 __glibcxx_assert(__count <= size());
373 return span<element_type>(this->data(), __count);
374 }
375
376 template<size_t _Count>
377 [[nodiscard]]
378 constexpr span<element_type, _Count>
379 last() const noexcept
380 {
381 if constexpr (_Extent == dynamic_extent)
382 __glibcxx_assert(_Count <= size());
383 else
384 static_assert(_Count <= extent);
385 using _Sp = span<element_type, _Count>;
386 return _Sp(_SizedPtr{this->data() + (this->size() - _Count)});
387 }
388
389 [[nodiscard]]
390 constexpr span<element_type, dynamic_extent>
391 last(size_type __count) const noexcept
392 {
393 __glibcxx_assert(__count <= size());
394 return span<element_type>(this->data() + (this->size() - __count),
395 __count);
396 }
397
398 template<size_t _Offset, size_t _Count = dynamic_extent>
399 [[nodiscard]]
400 constexpr auto
401 subspan() const noexcept
402 -> span<element_type, _S_subspan_extent<_Offset, _Count>()>
403 {
404 if constexpr (_Extent == dynamic_extent)
405 {
406 __glibcxx_assert(_Offset <= size());
407 }
408 else
409 static_assert(_Offset <= extent);
410
411 using _Sp = span<element_type, _S_subspan_extent<_Offset, _Count>()>;
412
413 if constexpr (_Count == dynamic_extent)
414 return _Sp(this->data() + _Offset, this->size() - _Offset);
415 else
416 {
417 if constexpr (_Extent == dynamic_extent)
418 {
419 __glibcxx_assert(_Count <= size());
420 __glibcxx_assert(_Count <= (size() - _Offset));
421 }
422 else
423 {
424 static_assert(_Count <= extent);
425 static_assert(_Count <= (extent - _Offset));
426 }
427 return _Sp(_SizedPtr{this->data() + _Offset});
428 }
429 }
430
431 [[nodiscard]]
432 constexpr span<element_type, dynamic_extent>
433 subspan(size_type __offset, size_type __count = dynamic_extent) const
434 noexcept
435 {
436 __glibcxx_assert(__offset <= size());
437 if (__count == dynamic_extent)
438 __count = this->size() - __offset;
439 else
440 {
441 __glibcxx_assert(__count <= size());
442 __glibcxx_assert(__offset + __count <= size());
443 }
444 return span<element_type>(this->data() + __offset, __count);
445 }
446
447 private:
448 template<typename, size_t> friend class span;
449
450 // Tag type for pointer that has known extent.
451 using _SizedPtr = __detail::__span_ptr<_Type>;
452
453 // Private constructor with an implied extent.
454 [[__gnu__::__always_inline__]]
455 constexpr explicit
456 span(_SizedPtr __ptr) noexcept
457 requires (extent != dynamic_extent)
458 : _M_ptr(__ptr._M_ptr), _M_extent(__v<extent>)
459 { }
460
461 pointer _M_ptr;
462 [[no_unique_address]] __detail::__extent_storage<extent> _M_extent;
463 };
464
465 // deduction guides
466 namespace __detail
467 {
468 // _GLIBCXX_RESOLVE_LIB_DEFECTS
469 // 4351. integral-constant-like needs more remove_cvref_t
470 template<typename _Tp>
471 concept __integral_constant_like =
472 is_integral_v<remove_cvref_t<decltype(_Tp::value)>>
473 && !is_same_v<bool, remove_cvref_t<decltype(_Tp::value)>>
474 && convertible_to<_Tp, decltype(_Tp::value)>
475 && equality_comparable_with<_Tp, decltype(_Tp::value)>
476 && bool_constant<_Tp() == _Tp::value>::value
477 && bool_constant<static_cast<decltype(_Tp::value)>(_Tp()) == _Tp::value>
478 ::value;
479
480 template<typename _Tp>
481 constexpr size_t __maybe_static_ext = dynamic_extent;
482
483 template<__integral_constant_like _Tp>
484 constexpr size_t __maybe_static_ext<_Tp> = {_Tp::value};
485 }
486
487 template<typename _Type, size_t _ArrayExtent>
488 span(_Type(&)[_ArrayExtent]) -> span<_Type, _ArrayExtent>;
489
490 template<typename _Type, size_t _ArrayExtent>
491 span(array<_Type, _ArrayExtent>&) -> span<_Type, _ArrayExtent>;
492
493 template<typename _Type, size_t _ArrayExtent>
494 span(const array<_Type, _ArrayExtent>&)
495 -> span<const _Type, _ArrayExtent>;
496
497 template<contiguous_iterator _Iter, typename _End>
498 span(_Iter, _End)
499 -> span<remove_reference_t<iter_reference_t<_Iter>>,
500 __detail::__maybe_static_ext<_End>>;
501
502 template<ranges::contiguous_range _Range>
503 span(_Range &&)
504 -> span<remove_reference_t<ranges::range_reference_t<_Range&>>>;
505
506 // _GLIBCXX_RESOLVE_LIB_DEFECTS
507 // 4243. as_bytes/as_writable_bytes is broken with span<volatile T>
508 template<typename _Type, size_t _Extent>
509 requires (!is_volatile_v<_Type>)
510 [[nodiscard]]
511 inline
512 span<const byte, _Extent == dynamic_extent
513 ? dynamic_extent : _Extent * sizeof(_Type)>
514 as_bytes(span<_Type, _Extent> __sp) noexcept
515 {
516 auto data = reinterpret_cast<const byte*>(__sp.data());
517 auto size = __sp.size_bytes();
518 constexpr auto extent = _Extent == dynamic_extent
519 ? dynamic_extent : _Extent * sizeof(_Type);
520 return span<const byte, extent>{data, size};
521 }
522
523 template<typename _Type, size_t _Extent>
524 requires (!is_const_v<_Type> && !is_volatile_v<_Type>)
525 inline
526 span<byte, _Extent == dynamic_extent
527 ? dynamic_extent : _Extent * sizeof(_Type)>
528 as_writable_bytes [[nodiscard]] (span<_Type, _Extent> __sp) noexcept
529 {
530 auto data = reinterpret_cast<byte*>(__sp.data());
531 auto size = __sp.size_bytes();
532 constexpr auto extent = _Extent == dynamic_extent
533 ? dynamic_extent : _Extent * sizeof(_Type);
534 return span<byte, extent>{data, size};
535 }
536
537 namespace ranges
538 {
539 // Opt-in to borrowed_range concept
540 template<typename _ElementType, size_t _Extent>
541 inline constexpr bool
542 enable_borrowed_range<span<_ElementType, _Extent>> = true;
543
544 // Opt-in to view concept
545 template<typename _ElementType, size_t _Extent>
546 inline constexpr bool
547 enable_view<span<_ElementType, _Extent>> = true;
548 }
549_GLIBCXX_END_NAMESPACE_VERSION
550} // namespace std
551#endif // __cpp_lib_span
552#endif // _GLIBCXX_SPAN
553