libstdc++
array
Go to the documentation of this file.
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_aux1(__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