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 | |
54 | namespace 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 | |