1// <array> -*- C++ -*-
2
3// Copyright (C) 2007-2022 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
48namespace std _GLIBCXX_VISIBILITY(default)
49{
50_GLIBCXX_BEGIN_NAMESPACE_VERSION
51
52 template<typename _Tp, std::size_t _Nm>
53 struct __array_traits
54 {
55 typedef _Tp _Type[_Nm];
56 typedef __is_swappable<_Tp> _Is_swappable;
57 typedef __is_nothrow_swappable<_Tp> _Is_nothrow_swappable;
58
59 static constexpr _Tp&
60 _S_ref(const _Type& __t, std::size_t __n) noexcept
61 { return const_cast<_Tp&>(__t[__n]); }
62
63 static constexpr _Tp*
64 _S_ptr(const _Type& __t) noexcept
65 { return const_cast<_Tp*>(__t); }
66 };
67
68 template<typename _Tp>
69 struct __array_traits<_Tp, 0>
70 {
71 struct _Type { };
72 typedef true_type _Is_swappable;
73 typedef true_type _Is_nothrow_swappable;
74
75 static constexpr _Tp&
76 _S_ref(const _Type&, std::size_t) noexcept
77 { return *static_cast<_Tp*>(nullptr); }
78
79 static constexpr _Tp*
80 _S_ptr(const _Type&) noexcept
81 { return nullptr; }
82 };
83
84 /**
85 * @brief A standard container for storing a fixed size sequence of elements.
86 *
87 * @ingroup sequences
88 *
89 * Meets the requirements of a <a href="tables.html#65">container</a>, a
90 * <a href="tables.html#66">reversible container</a>, and a
91 * <a href="tables.html#67">sequence</a>.
92 *
93 * Sets support random access iterators.
94 *
95 * @tparam Tp Type of element. Required to be a complete type.
96 * @tparam Nm Number of elements.
97 */
98 template<typename _Tp, std::size_t _Nm>
99 struct array
100 {
101 typedef _Tp value_type;
102 typedef value_type* pointer;
103 typedef const value_type* const_pointer;
104 typedef value_type& reference;
105 typedef const value_type& const_reference;
106 typedef value_type* iterator;
107 typedef const value_type* const_iterator;
108 typedef std::size_t size_type;
109 typedef std::ptrdiff_t difference_type;
110 typedef std::reverse_iterator<iterator> reverse_iterator;
111 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
112
113 // Support for zero-sized arrays mandatory.
114 typedef __array_traits<_Tp, _Nm> _AT_Type;
115 typename _AT_Type::_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(_AT_Type::_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 [[__gnu__::__const__, __nodiscard__]]
192 constexpr size_type
193 size() const noexcept { return _Nm; }
194
195 [[__gnu__::__const__, __nodiscard__]]
196 constexpr size_type
197 max_size() const noexcept { return _Nm; }
198
199 [[__gnu__::__const__, __nodiscard__]]
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 _AT_Type::_S_ref(_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 _AT_Type::_S_ref(_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 _AT_Type::_S_ref(_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 ? _AT_Type::_S_ref(_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 _AT_Type::_S_ref(_M_elems, 0));
242 }
243
244 [[__nodiscard__]]
245 _GLIBCXX17_CONSTEXPR reference
246 front() noexcept
247 {
248 __glibcxx_requires_nonempty();
249 return *begin();
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 _AT_Type::_S_ref(_M_elems, 0);
260 }
261
262 [[__nodiscard__]]
263 _GLIBCXX17_CONSTEXPR reference
264 back() noexcept
265 {
266 __glibcxx_requires_nonempty();
267 return _Nm ? *(end() - 1) : *end();
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 _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1)
278 : _AT_Type::_S_ref(_M_elems, 0);
279 }
280
281 [[__gnu__::__const__, __nodiscard__]]
282 _GLIBCXX17_CONSTEXPR pointer
283 data() noexcept
284 { return _AT_Type::_S_ptr(_M_elems); }
285
286 [[__nodiscard__]]
287 _GLIBCXX17_CONSTEXPR const_pointer
288 data() const noexcept
289 { return _AT_Type::_S_ptr(_M_elems); }
290 };
291
292#if __cpp_deduction_guides >= 201606
293 template<typename _Tp, typename... _Up>
294 array(_Tp, _Up...)
295 -> array<enable_if_t<(is_same_v<_Tp, _Up> && ...), _Tp>,
296 1 + sizeof...(_Up)>;
297#endif
298
299 // Array comparisons.
300 template<typename _Tp, std::size_t _Nm>
301 [[__nodiscard__]]
302 _GLIBCXX20_CONSTEXPR
303 inline bool
304 operator==(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
305 { return std::equal(__one.begin(), __one.end(), __two.begin()); }
306
307#if __cpp_lib_three_way_comparison && __cpp_lib_concepts
308 template<typename _Tp, size_t _Nm>
309 [[nodiscard]]
310 constexpr __detail::__synth3way_t<_Tp>
311 operator<=>(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
312 {
313 if constexpr (_Nm && __is_memcmp_ordered<_Tp>::__value)
314 if (!std::__is_constant_evaluated())
315 {
316 constexpr size_t __n = _Nm * sizeof(_Tp);
317 return __builtin_memcmp(__a.data(), __b.data(), __n) <=> 0;
318 }
319
320 for (size_t __i = 0; __i < _Nm; ++__i)
321 {
322 auto __c = __detail::__synth3way(__a[__i], __b[__i]);
323 if (__c != 0)
324 return __c;
325 }
326 return strong_ordering::equal;
327 }
328#else
329 template<typename _Tp, std::size_t _Nm>
330 [[__nodiscard__]]
331 _GLIBCXX20_CONSTEXPR
332 inline bool
333 operator!=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
334 { return !(__one == __two); }
335
336 template<typename _Tp, std::size_t _Nm>
337 [[__nodiscard__]]
338 _GLIBCXX20_CONSTEXPR
339 inline bool
340 operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
341 {
342 return std::lexicographical_compare(__a.begin(), __a.end(),
343 __b.begin(), __b.end());
344 }
345
346 template<typename _Tp, std::size_t _Nm>
347 [[__nodiscard__]]
348 _GLIBCXX20_CONSTEXPR
349 inline bool
350 operator>(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
351 { return __two < __one; }
352
353 template<typename _Tp, std::size_t _Nm>
354 [[__nodiscard__]]
355 _GLIBCXX20_CONSTEXPR
356 inline bool
357 operator<=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
358 { return !(__one > __two); }
359
360 template<typename _Tp, std::size_t _Nm>
361 [[__nodiscard__]]
362 _GLIBCXX20_CONSTEXPR
363 inline bool
364 operator>=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
365 { return !(__one < __two); }
366#endif // three_way_comparison && concepts
367
368 // Specialized algorithms.
369 template<typename _Tp, std::size_t _Nm>
370 _GLIBCXX20_CONSTEXPR
371 inline
372#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
373 // Constrained free swap overload, see p0185r1
374 typename enable_if<
375 __array_traits<_Tp, _Nm>::_Is_swappable::value
376 >::type
377#else
378 void
379#endif
380 swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two)
381 noexcept(noexcept(__one.swap(__two)))
382 { __one.swap(__two); }
383
384#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
385 template<typename _Tp, std::size_t _Nm>
386 typename enable_if<
387 !__array_traits<_Tp, _Nm>::_Is_swappable::value>::type
388 swap(array<_Tp, _Nm>&, array<_Tp, _Nm>&) = delete;
389#endif
390
391 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
392 [[__nodiscard__]]
393 constexpr _Tp&
394 get(array<_Tp, _Nm>& __arr) noexcept
395 {
396 static_assert(_Int < _Nm, "array index is within bounds");
397 return __array_traits<_Tp, _Nm>::_S_ref(__arr._M_elems, _Int);
398 }
399
400 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
401 [[__nodiscard__]]
402 constexpr _Tp&&
403 get(array<_Tp, _Nm>&& __arr) noexcept
404 {
405 static_assert(_Int < _Nm, "array index is within bounds");
406 return std::move(std::get<_Int>(__arr));
407 }
408
409 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
410 [[__nodiscard__]]
411 constexpr const _Tp&
412 get(const array<_Tp, _Nm>& __arr) noexcept
413 {
414 static_assert(_Int < _Nm, "array index is within bounds");
415 return __array_traits<_Tp, _Nm>::_S_ref(__arr._M_elems, _Int);
416 }
417
418 template<std::size_t _Int, typename _Tp, std::size_t _Nm>
419 [[__nodiscard__]]
420 constexpr const _Tp&&
421 get(const array<_Tp, _Nm>&& __arr) noexcept
422 {
423 static_assert(_Int < _Nm, "array index is within bounds");
424 return std::move(std::get<_Int>(__arr));
425 }
426
427#if __cplusplus > 201703L
428#define __cpp_lib_to_array 201907L
429
430 template<bool _Move = false, typename _Tp, size_t... _Idx>
431 constexpr array<remove_cv_t<_Tp>, sizeof...(_Idx)>
432 __to_array(_Tp (&__a)[sizeof...(_Idx)], index_sequence<_Idx...>)
433 {
434 if constexpr (_Move)
435 return {{std::move(__a[_Idx])...}};
436 else
437 return {{__a[_Idx]...}};
438 }
439
440 template<typename _Tp, size_t _Nm>
441 [[nodiscard]]
442 constexpr array<remove_cv_t<_Tp>, _Nm>
443 to_array(_Tp (&__a)[_Nm])
444 noexcept(is_nothrow_constructible_v<_Tp, _Tp&>)
445 {
446 static_assert(!is_array_v<_Tp>);
447 static_assert(is_constructible_v<_Tp, _Tp&>);
448 if constexpr (is_constructible_v<_Tp, _Tp&>)
449 return __to_array(__a, make_index_sequence<_Nm>{});
450 __builtin_unreachable(); // FIXME: see PR c++/91388
451 }
452
453 template<typename _Tp, size_t _Nm>
454 [[nodiscard]]
455 constexpr array<remove_cv_t<_Tp>, _Nm>
456 to_array(_Tp (&&__a)[_Nm])
457 noexcept(is_nothrow_move_constructible_v<_Tp>)
458 {
459 static_assert(!is_array_v<_Tp>);
460 static_assert(is_move_constructible_v<_Tp>);
461 if constexpr (is_move_constructible_v<_Tp>)
462 return __to_array<1>(__a, make_index_sequence<_Nm>{});
463 __builtin_unreachable(); // FIXME: see PR c++/91388
464 }
465#endif // C++20
466
467 // Tuple interface to class template array.
468
469 /// Partial specialization for std::array
470 template<typename _Tp, size_t _Nm>
471 struct tuple_size<array<_Tp, _Nm>>
472 : public integral_constant<size_t, _Nm> { };
473
474 /// Partial specialization for std::array
475 template<size_t _Ind, typename _Tp, size_t _Nm>
476 struct tuple_element<_Ind, array<_Tp, _Nm>>
477 {
478 static_assert(_Ind < _Nm, "array index is in range");
479 using type = _Tp;
480 };
481
482#if __cplusplus >= 201703L
483 template<typename _Tp, size_t _Nm>
484 inline constexpr size_t tuple_size_v<array<_Tp, _Nm>> = _Nm;
485
486 template<typename _Tp, size_t _Nm>
487 inline constexpr size_t tuple_size_v<const array<_Tp, _Nm>> = _Nm;
488#endif
489
490 template<typename _Tp, size_t _Nm>
491 struct __is_tuple_like_impl<array<_Tp, _Nm>> : true_type
492 { };
493
494_GLIBCXX_END_NAMESPACE_VERSION
495} // namespace std
496
497#endif // C++11
498
499#endif // _GLIBCXX_ARRAY
500