libstdc++-v3/include/std/array

   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