1// <array> -*- C++ -*-
2
3// Copyright (C) 2007-2024 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 include/array
26 * This is a Standard C++ Library header.
27 */
28
29#ifndef _GLIBCXX_ARRAY
30#define _GLIBCXX_ARRAY 1
31
32#pragma GCC system_header
33
34#if __cplusplus < 201103L
35# include <bits/c++0x_warning.h>
36#else
37
38#include <compare>
39#include <initializer_list>
40
41#include <type_traits>
42#include <bits/functexcept.h>
43#include <bits/stl_algobase.h>
44#include <bits/range_access.h> // std::begin, std::end etc.
45#include <bits/utility.h> // std::index_sequence, std::tuple_size
46#include <debug/assertions.h>
47
48#define __glibcxx_want_array_constexpr
49#define __glibcxx_want_freestanding_array
50#define __glibcxx_want_nonmember_container_access
51#define __glibcxx_want_to_array
52#include <bits/version.h>
53
54namespace std _GLIBCXX_VISIBILITY(default)
55{
56_GLIBCXX_BEGIN_NAMESPACE_VERSION
57
58 template<typename _Tp, size_t _Nm>
59 struct __array_traits
60 {
61 using _Type = _Tp[_Nm];
62 using _Is_swappable = __is_swappable<_Tp>;
63 using _Is_nothrow_swappable = __is_nothrow_swappable<_Tp>;
64 };
65
66 template<typename _Tp>
67 struct __array_traits<_Tp, 0>
68 {
69 // Empty type used instead of _Tp[0] for std::array<_Tp, 0>.
70 struct _Type
71 {
72 // Indexing is undefined.
73 __attribute__((__always_inline__,__noreturn__))
74 _Tp& operator[](size_t) const noexcept { __builtin_trap(); }
75
76 // Conversion to a pointer produces a null pointer.
77 __attribute__((__always_inline__))
78 constexpr explicit operator _Tp*() const noexcept { return nullptr; }
79 };
80
81 using _Is_swappable = true_type;
82 using _Is_nothrow_swappable = true_type;
83 };
84
85 /**
86 * @brief A standard container for storing a fixed size sequence of elements.
87 *
88 * @ingroup sequences
89 *
90 * Meets the requirements of a <a href="tables.html#65">container</a>, a
91 * <a href="tables.html#66">reversible container</a>, and a
92 * <a href="tables.html#67">sequence</a>.
93 *
94 * Sets support random access iterators.
95 *
96 * @tparam Tp Type of element. Required to be a complete type.
97 * @tparam Nm Number of elements.
98 */
99 template<typename _Tp, std::size_t _Nm>
100 struct array
101 {
102 typedef _Tp value_type;
103 typedef value_type* pointer;
104 typedef const value_type* const_pointer;
105 typedef value_type& reference;
106 typedef const value_type& const_reference;
107 typedef value_type* iterator;
108 typedef const value_type* const_iterator;
109 typedef std::size_t size_type;
110 typedef std::ptrdiff_t difference_type;
111 typedef std::reverse_iterator<iterator> reverse_iterator;
112 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
113
114 // Support for zero-sized arrays mandatory.
115 typename __array_traits<_Tp, _Nm>::_Type _M_elems;
116
117 // No explicit construct/copy/destroy for aggregate type.
118
119 // DR 776.
120 _GLIBCXX20_CONSTEXPR void
121 fill(const value_type& __u)
122 { std::fill_n(begin(), size(), __u); }
123
124 _GLIBCXX20_CONSTEXPR void
125 swap(array& __other)
126 noexcept(__array_traits<_Tp, _Nm>::_Is_nothrow_swappable::value)
127 { std::swap_ranges(begin(), end(), __other.begin()); }
128
129 // Iterators.
130 [[__gnu__::__const__, __nodiscard__]]
131 _GLIBCXX17_CONSTEXPR iterator
132 begin() noexcept
133 { return iterator(data()); }
134
135 [[__nodiscard__]]
136 _GLIBCXX17_CONSTEXPR const_iterator
137 begin() const noexcept
138 { return const_iterator(data()); }
139
140 [[__gnu__::__const__, __nodiscard__]]
141 _GLIBCXX17_CONSTEXPR iterator
142 end() noexcept
143 { return iterator(data() + _Nm); }
144
145 [[__nodiscard__]]
146 _GLIBCXX17_CONSTEXPR const_iterator
147 end() const noexcept
148 { return const_iterator(data() + _Nm); }
149
150 [[__gnu__::__const__, __nodiscard__]]
151 _GLIBCXX17_CONSTEXPR reverse_iterator
152 rbegin() noexcept
153 { return reverse_iterator(end()); }
154
155 [[__nodiscard__]]
156 _GLIBCXX17_CONSTEXPR const_reverse_iterator
157 rbegin() const noexcept
158 { return const_reverse_iterator(end()); }
159
160 [[__gnu__::__const__, __nodiscard__]]
161 _GLIBCXX17_CONSTEXPR reverse_iterator
162 rend() noexcept
163 { return reverse_iterator(begin()); }
164
165 [[__nodiscard__]]
166 _GLIBCXX17_CONSTEXPR const_reverse_iterator
167 rend() const noexcept
168 { return const_reverse_iterator(begin()); }
169
170 [[__nodiscard__]]
171 _GLIBCXX17_CONSTEXPR const_iterator
172 cbegin() const noexcept
173 { return const_iterator(data()); }
174
175 [[__nodiscard__]]
176 _GLIBCXX17_CONSTEXPR const_iterator
177 cend() const noexcept
178 { return const_iterator(data() + _Nm); }
179
180 [[__nodiscard__]]
181 _GLIBCXX17_CONSTEXPR const_reverse_iterator
182 crbegin() const noexcept
183 { return const_reverse_iterator(end()); }
184
185 [[__nodiscard__]]
186 _GLIBCXX17_CONSTEXPR const_reverse_iterator
187 crend() const noexcept
188 { return const_reverse_iterator(begin()); }
189
190 // Capacity.
191 [[__nodiscard__, __gnu__::__const__, __gnu__::__always_inline__]]
192 constexpr size_type
193 size() const noexcept { return _Nm; }
194
195 [[__nodiscard__, __gnu__::__const__, __gnu__::__always_inline__]]
196 constexpr size_type
197 max_size() const noexcept { return _Nm; }
198
199 [[__nodiscard__, __gnu__::__const__, __gnu__::__always_inline__]]
200 constexpr bool
201 empty() const noexcept { return size() == 0; }
202
203 // Element access.
204 [[__nodiscard__]]
205 _GLIBCXX17_CONSTEXPR reference
206 operator[](size_type __n) noexcept
207 {
208 __glibcxx_requires_subscript(__n);
209 return _M_elems[__n];
210 }
211
212 [[__nodiscard__]]
213 constexpr const_reference
214 operator[](size_type __n) const noexcept
215 {
216#if __cplusplus >= 201402L
217 __glibcxx_requires_subscript(__n);
218#endif
219 return _M_elems[__n];
220 }
221
222 _GLIBCXX17_CONSTEXPR reference
223 at(size_type __n)
224 {
225 if (__n >= _Nm)
226 std::__throw_out_of_range_fmt(__N("array::at: __n (which is %zu) "
227 ">= _Nm (which is %zu)"),
228 __n, _Nm);
229 return _M_elems[__n];
230 }
231
232 constexpr const_reference
233 at(size_type __n) const
234 {
235 // Result of conditional expression must be an lvalue so use
236 // boolean ? lvalue : (throw-expr, lvalue)
237 return __n < _Nm ? _M_elems[__n]
238 : (std::__throw_out_of_range_fmt(__N("array::at: __n (which is %zu) "
239 ">= _Nm (which is %zu)"),
240 __n, _Nm),
241 _M_elems[__n]);
242 }
243
244 [[__nodiscard__]]
245 _GLIBCXX17_CONSTEXPR reference
246 front() noexcept
247 {
248 __glibcxx_requires_nonempty();
249 return _M_elems[(size_type)0];
250 }
251
252 [[__nodiscard__]]
253 constexpr const_reference
254 front() const noexcept
255 {
256#if __cplusplus >= 201402L
257 __glibcxx_requires_nonempty();
258#endif
259 return _M_elems[(size_type)0];
260 }
261
262 [[__nodiscard__]]
263 _GLIBCXX17_CONSTEXPR reference
264 back() noexcept
265 {
266 __glibcxx_requires_nonempty();
267 return _M_elems[_Nm - 1];
268 }
269
270 [[__nodiscard__]]
271 constexpr const_reference
272 back() const noexcept
273 {
274#if __cplusplus >= 201402L
275 __glibcxx_requires_nonempty();
276#endif
277 return _M_elems[_Nm - 1];
278 }
279
280 [[__nodiscard__, __gnu__::__const__, __gnu__::__always_inline__]]
281 _GLIBCXX17_CONSTEXPR pointer
282 data() noexcept
283 { return static_cast<pointer>(_M_elems); }
284
285 [[__nodiscard__]]
286 _GLIBCXX17_CONSTEXPR const_pointer
287 data() const noexcept
288 { return static_cast<const_pointer>(_M_elems); }
289 };
290
291#if __cpp_deduction_guides >= 201606
292 template<typename _Tp, typename... _Up>
293 array(_Tp, _Up...)
294 -> array<enable_if_t<(is_same_v<_Tp, _Up> && ...), _Tp>,
295 1 + sizeof...(_Up)>;
296#endif
297
298 // Array comparisons.
299 template<typename _Tp, std::size_t _Nm>
300 [[__nodiscard__]]
301 _GLIBCXX20_CONSTEXPR
302 inline bool
303 operator==(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
304 { return std::equal(__one.begin(), __one.end(), __two.begin()); }
305
306#if __cpp_lib_three_way_comparison // C++ >= 20 && lib_concepts
307 template<typename _Tp, size_t _Nm>
308 [[nodiscard]]
309 constexpr __detail::__synth3way_t<_Tp>
310 operator<=>(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
311 {
312 if constexpr (_Nm && __is_memcmp_ordered<_Tp>::__value)
313 if (!std::__is_constant_evaluated())
314 {
315 constexpr size_t __n = _Nm * sizeof(_Tp);
316 return __builtin_memcmp(__a.data(), __b.data(), __n) <=> 0;
317 }
318
319 for (size_t __i = 0; __i < _Nm; ++__i)
320 {
321 auto __c = __detail::__synth3way(__a[__i], __b[__i]);
322 if (__c != 0)
323 return __c;
324 }
325 return strong_ordering::equal;
326 }
327#else
328 template<typename _Tp, std::size_t _Nm>
329 [[__nodiscard__]]
330 _GLIBCXX20_CONSTEXPR
331 inline bool
332 operator!=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
333 { return !(__one == __two); }
334
335 template<typename _Tp, std::size_t _Nm>
336 [[__nodiscard__]]
337 _GLIBCXX20_CONSTEXPR
338 inline bool
339 operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
340 {
341 return std::lexicographical_compare(__a.begin(), __a.end(),
342 __b.begin(), __b.end());
343 }
344
345 template<typename _Tp, std::size_t _Nm>
346 [[__nodiscard__]]
347 _GLIBCXX20_CONSTEXPR
348 inline bool
349 operator>(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
350 { return __two < __one; }
351
352 template<typename _Tp, std::size_t _Nm>
353 [[__nodiscard__]]
354 _GLIBCXX20_CONSTEXPR
355 inline bool
356 operator<=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
357 { return !(__one > __two); }
358
359 template<typename _Tp, std::size_t _Nm>
360 [[__nodiscard__]]
361 _GLIBCXX20_CONSTEXPR
362 inline bool
363 operator>=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
364 { return !(__one < __two); }
365#endif // three_way_comparison && concepts
366
367 // Specialized algorithms.
368 template<typename _Tp, std::size_t _Nm>
369 _GLIBCXX20_CONSTEXPR
370 inline
371#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
372 // Constrained free swap overload, see p0185r1
373 __enable_if_t<__array_traits<_Tp, _Nm>::_Is_swappable::value>
374#else
375 void
376#endif
377 swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two)
378 noexcept(noexcept(__one.swap(__two)))
379 { __one.swap(__two); }
380
381#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
382 template<typename _Tp, std::size_t _Nm>
383 __enable_if_t<!__array_traits<_Tp, _Nm>::_Is_swappable::value>
384 swap(array<_Tp, _Nm>&, array<_Tp, _Nm>&) = delete;
385#endif
386
387 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
388 [[__nodiscard__]]
389 constexpr _Tp&
390 get(array<_Tp, _Nm>& __arr) noexcept
391 {
392 static_assert(_Int < _Nm, "array index is within bounds");
393 return __arr._M_elems[_Int];
394 }
395
396 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
397 [[__nodiscard__]]
398 constexpr _Tp&&
399 get(array<_Tp, _Nm>&& __arr) noexcept
400 {
401 static_assert(_Int < _Nm, "array index is within bounds");
402 return std::move(std::get<_Int>(__arr));
403 }
404
405 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
406 [[__nodiscard__]]
407 constexpr const _Tp&
408 get(const array<_Tp, _Nm>& __arr) noexcept
409 {
410 static_assert(_Int < _Nm, "array index is within bounds");
411 return __arr._M_elems[_Int];
412 }
413
414 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
415 [[__nodiscard__]]
416 constexpr const _Tp&&
417 get(const array<_Tp, _Nm>&& __arr) noexcept
418 {
419 static_assert(_Int < _Nm, "array index is within bounds");
420 return std::move(std::get<_Int>(__arr));
421 }
422
423#ifdef __cpp_lib_to_array // C++ >= 20 && __cpp_generic_lambdas >= 201707L
424 template<typename _Tp, size_t _Nm>
425 [[nodiscard]]
426 constexpr array<remove_cv_t<_Tp>, _Nm>
427 to_array(_Tp (&__a)[_Nm])
428 noexcept(is_nothrow_constructible_v<_Tp, _Tp&>)
429 {
430 static_assert(!is_array_v<_Tp>);
431 static_assert(is_constructible_v<_Tp, _Tp&>);
432 if constexpr (is_constructible_v<_Tp, _Tp&>)
433 {
434 if constexpr (is_trivially_copyable_v<_Tp>
435 && is_trivially_default_constructible_v<_Tp>
436 && is_copy_assignable_v<_Tp>)
437 {
438 array<remove_cv_t<_Tp>, _Nm> __arr;
439 if (!__is_constant_evaluated() && _Nm != 0)
440 __builtin_memcpy((void*)__arr.data(), (void*)__a, sizeof(__a));
441 else
442 for (size_t __i = 0; __i < _Nm; ++__i)
443 __arr._M_elems[__i] = __a[__i];
444 return __arr;
445 }
446 else
447 return [&__a]<size_t... _Idx>(index_sequence<_Idx...>) {
448 return array<remove_cv_t<_Tp>, _Nm>{{ __a[_Idx]... }};
449 }(make_index_sequence<_Nm>{});
450 }
451 else
452 __builtin_unreachable(); // FIXME: see PR c++/91388
453 }
454
455 template<typename _Tp, size_t _Nm>
456 [[nodiscard]]
457 constexpr array<remove_cv_t<_Tp>, _Nm>
458 to_array(_Tp (&&__a)[_Nm])
459 noexcept(is_nothrow_move_constructible_v<_Tp>)
460 {
461 static_assert(!is_array_v<_Tp>);
462 static_assert(is_move_constructible_v<_Tp>);
463 if constexpr (is_move_constructible_v<_Tp>)
464 {
465 if constexpr (is_trivially_copyable_v<_Tp>
466 && is_trivially_default_constructible_v<_Tp>
467 && is_copy_assignable_v<_Tp>)
468 {
469 array<remove_cv_t<_Tp>, _Nm> __arr;
470 if (!__is_constant_evaluated() && _Nm != 0)
471 __builtin_memcpy((void*)__arr.data(), (void*)__a, sizeof(__a));
472 else
473 for (size_t __i = 0; __i < _Nm; ++__i)
474 __arr._M_elems[__i] = __a[__i];
475 return __arr;
476 }
477 else
478 return [&__a]<size_t... _Idx>(index_sequence<_Idx...>) {
479 return array<remove_cv_t<_Tp>, _Nm>{{ std::move(__a[_Idx])... }};
480 }(make_index_sequence<_Nm>{});
481 }
482 else
483 __builtin_unreachable(); // FIXME: see PR c++/91388
484 }
485#endif // __cpp_lib_to_array
486
487 // Tuple interface to class template array.
488
489 /// Partial specialization for std::array
490 template<typename _Tp, size_t _Nm>
491 struct tuple_size<array<_Tp, _Nm>>
492 : public integral_constant<size_t, _Nm> { };
493
494 /// Partial specialization for std::array
495 template<size_t _Ind, typename _Tp, size_t _Nm>
496 struct tuple_element<_Ind, array<_Tp, _Nm>>
497 {
498 static_assert(_Ind < _Nm, "array index is in range");
499 using type = _Tp;
500 };
501
502#if __cplusplus >= 201703L
503 template<typename _Tp, size_t _Nm>
504 inline constexpr size_t tuple_size_v<array<_Tp, _Nm>> = _Nm;
505
506 template<typename _Tp, size_t _Nm>
507 inline constexpr size_t tuple_size_v<const array<_Tp, _Nm>> = _Nm;
508#endif
509
510 template<typename _Tp, size_t _Nm>
511 struct __is_tuple_like_impl<array<_Tp, _Nm>> : true_type
512 { };
513
514_GLIBCXX_END_NAMESPACE_VERSION
515} // namespace std
516
517#endif // C++11
518
519#endif // _GLIBCXX_ARRAY
520