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 >= 202002L && __cpp_generic_lambdas >= 201707L 428#define __cpp_lib_to_array 201907L 429 template<typename _Tp, size_t _Nm> 430 [[nodiscard]] 431 constexpr array<remove_cv_t<_Tp>, _Nm> 432 to_array(_Tp (&__a)[_Nm]) 433 noexcept(is_nothrow_constructible_v<_Tp, _Tp&>) 434 { 435 static_assert(!is_array_v<_Tp>); 436 static_assert(is_constructible_v<_Tp, _Tp&>); 437 if constexpr (is_constructible_v<_Tp, _Tp&>) 438 { 439 if constexpr (is_trivial_v<_Tp>) 440 { 441 array<remove_cv_t<_Tp>, _Nm> __arr; 442 if (!__is_constant_evaluated() && _Nm != 0) 443 __builtin_memcpy((void*)__arr.data(), (void*)__a, sizeof(__a)); 444 else 445 for (size_t __i = 0; __i < _Nm; ++__i) 446 __arr._M_elems[__i] = __a[__i]; 447 return __arr; 448 } 449 else 450 return [&__a]<size_t... _Idx>(index_sequence<_Idx...>) { 451 return array<remove_cv_t<_Tp>, _Nm>{{ __a[_Idx]... }}; 452 }(make_index_sequence<_Nm>{}); 453 } 454 else 455 __builtin_unreachable(); // FIXME: see PR c++/91388 456 } 457 458 template<typename _Tp, size_t _Nm> 459 [[nodiscard]] 460 constexpr array<remove_cv_t<_Tp>, _Nm> 461 to_array(_Tp (&&__a)[_Nm]) 462 noexcept(is_nothrow_move_constructible_v<_Tp>) 463 { 464 static_assert(!is_array_v<_Tp>); 465 static_assert(is_move_constructible_v<_Tp>); 466 if constexpr (is_move_constructible_v<_Tp>) 467 { 468 if constexpr (is_trivial_v<_Tp>) 469 { 470 array<remove_cv_t<_Tp>, _Nm> __arr; 471 if (!__is_constant_evaluated() && _Nm != 0) 472 __builtin_memcpy((void*)__arr.data(), (void*)__a, sizeof(__a)); 473 else 474 for (size_t __i = 0; __i < _Nm; ++__i) 475 __arr._M_elems[__i] = __a[__i]; 476 return __arr; 477 } 478 else 479 return [&__a]<size_t... _Idx>(index_sequence<_Idx...>) { 480 return array<remove_cv_t<_Tp>, _Nm>{{ std::move(__a[_Idx])... }}; 481 }(make_index_sequence<_Nm>{}); 482 } 483 else 484 __builtin_unreachable(); // FIXME: see PR c++/91388 485 } 486#endif // C++20 487 488 // Tuple interface to class template array. 489 490 /// Partial specialization for std::array 491 template<typename _Tp, size_t _Nm> 492 struct tuple_size<array<_Tp, _Nm>> 493 : public integral_constant<size_t, _Nm> { }; 494 495 /// Partial specialization for std::array 496 template<size_t _Ind, typename _Tp, size_t _Nm> 497 struct tuple_element<_Ind, array<_Tp, _Nm>> 498 { 499 static_assert(_Ind < _Nm, "array index is in range"); 500 using type = _Tp; 501 }; 502 503#if __cplusplus >= 201703L 504 template<typename _Tp, size_t _Nm> 505 inline constexpr size_t tuple_size_v<array<_Tp, _Nm>> = _Nm; 506 507 template<typename _Tp, size_t _Nm> 508 inline constexpr size_t tuple_size_v<const array<_Tp, _Nm>> = _Nm; 509#endif 510 511 template<typename _Tp, size_t _Nm> 512 struct __is_tuple_like_impl<array<_Tp, _Nm>> : true_type 513 { }; 514 515_GLIBCXX_END_NAMESPACE_VERSION 516} // namespace std 517 518#endif // C++11 519 520#endif // _GLIBCXX_ARRAY 521