1// Raw memory manipulators -*- C++ -*- 2 3// Copyright (C) 2001-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/* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51/** @file bits/stl_uninitialized.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{memory} 54 */ 55 56#ifndef _STL_UNINITIALIZED_H 57#define _STL_UNINITIALIZED_H 1 58 59#if __cplusplus >= 201103L 60#include <type_traits> 61#endif 62 63#include <bits/stl_algobase.h> // copy 64#include <ext/alloc_traits.h> // __alloc_traits 65 66#if __cplusplus >= 201703L 67#include <bits/stl_pair.h> 68#endif 69 70namespace std _GLIBCXX_VISIBILITY(default) 71{ 72_GLIBCXX_BEGIN_NAMESPACE_VERSION 73 74 /** @addtogroup memory 75 * @{ 76 */ 77 78 /// @cond undocumented 79 80#if __cplusplus >= 201103L 81 template<typename _ValueType, typename _Tp> 82 constexpr bool 83 __check_constructible() 84 { 85 // Trivial types can have deleted constructors, but std::copy etc. 86 // only use assignment (or memmove) not construction, so we need an 87 // explicit check that construction from _Tp is actually valid, 88 // otherwise some ill-formed uses of std::uninitialized_xxx would 89 // compile without errors. This gives a nice clear error message. 90 static_assert(is_constructible<_ValueType, _Tp>::value, 91 "result type must be constructible from input type"); 92 93 return true; 94 } 95 96// If the type is trivial we don't need to construct it, just assign to it. 97// But trivial types can still have deleted or inaccessible assignment, 98// so don't try to use std::copy or std::fill etc. if we can't assign. 99# define _GLIBCXX_USE_ASSIGN_FOR_INIT(T, U) \ 100 __is_trivial(T) && __is_assignable(T&, U) \ 101 && std::__check_constructible<T, U>() 102#else 103// No need to check if is_constructible<T, U> for C++98. Trivial types have 104// no user-declared constructors, so if the assignment is valid, construction 105// should be too. 106# define _GLIBCXX_USE_ASSIGN_FOR_INIT(T, U) \ 107 __is_trivial(T) && __is_assignable(T&, U) 108#endif 109 110 template<typename _InputIterator, typename _ForwardIterator> 111 _GLIBCXX20_CONSTEXPR 112 _ForwardIterator 113 __do_uninit_copy(_InputIterator __first, _InputIterator __last, 114 _ForwardIterator __result) 115 { 116 _ForwardIterator __cur = __result; 117 __try 118 { 119 for (; __first != __last; ++__first, (void)++__cur) 120 std::_Construct(std::__addressof(*__cur), *__first); 121 return __cur; 122 } 123 __catch(...) 124 { 125 std::_Destroy(__result, __cur); 126 __throw_exception_again; 127 } 128 } 129 130 template<bool _TrivialValueTypes> 131 struct __uninitialized_copy 132 { 133 template<typename _InputIterator, typename _ForwardIterator> 134 static _ForwardIterator 135 __uninit_copy(_InputIterator __first, _InputIterator __last, 136 _ForwardIterator __result) 137 { return std::__do_uninit_copy(__first, __last, __result); } 138 }; 139 140 template<> 141 struct __uninitialized_copy<true> 142 { 143 template<typename _InputIterator, typename _ForwardIterator> 144 static _ForwardIterator 145 __uninit_copy(_InputIterator __first, _InputIterator __last, 146 _ForwardIterator __result) 147 { return std::copy(__first, __last, __result); } 148 }; 149 150 /// @endcond 151 152 /** 153 * @brief Copies the range [first,last) into result. 154 * @param __first An input iterator. 155 * @param __last An input iterator. 156 * @param __result An output iterator. 157 * @return __result + (__first - __last) 158 * 159 * Like copy(), but does not require an initialized output range. 160 */ 161 template<typename _InputIterator, typename _ForwardIterator> 162 inline _ForwardIterator 163 uninitialized_copy(_InputIterator __first, _InputIterator __last, 164 _ForwardIterator __result) 165 { 166 typedef typename iterator_traits<_InputIterator>::value_type 167 _ValueType1; 168 typedef typename iterator_traits<_ForwardIterator>::value_type 169 _ValueType2; 170 171 // _ValueType1 must be trivially-copyable to use memmove, so don't 172 // bother optimizing to std::copy if it isn't. 173 // XXX Unnecessary because std::copy would check it anyway? 174 const bool __can_memmove = __is_trivial(_ValueType1); 175 176#if __cplusplus < 201103L 177 typedef typename iterator_traits<_InputIterator>::reference _From; 178#else 179 using _From = decltype(*__first); 180#endif 181 const bool __assignable 182 = _GLIBCXX_USE_ASSIGN_FOR_INIT(_ValueType2, _From); 183 184 return std::__uninitialized_copy<__can_memmove && __assignable>:: 185 __uninit_copy(__first, __last, __result); 186 } 187 188 /// @cond undocumented 189 190 template<typename _ForwardIterator, typename _Tp> 191 _GLIBCXX20_CONSTEXPR void 192 __do_uninit_fill(_ForwardIterator __first, _ForwardIterator __last, 193 const _Tp& __x) 194 { 195 _ForwardIterator __cur = __first; 196 __try 197 { 198 for (; __cur != __last; ++__cur) 199 std::_Construct(std::__addressof(*__cur), __x); 200 } 201 __catch(...) 202 { 203 std::_Destroy(__first, __cur); 204 __throw_exception_again; 205 } 206 } 207 208 template<bool _TrivialValueType> 209 struct __uninitialized_fill 210 { 211 template<typename _ForwardIterator, typename _Tp> 212 static void 213 __uninit_fill(_ForwardIterator __first, _ForwardIterator __last, 214 const _Tp& __x) 215 { std::__do_uninit_fill(__first, __last, __x); } 216 }; 217 218 template<> 219 struct __uninitialized_fill<true> 220 { 221 template<typename _ForwardIterator, typename _Tp> 222 static void 223 __uninit_fill(_ForwardIterator __first, _ForwardIterator __last, 224 const _Tp& __x) 225 { std::fill(__first, __last, __x); } 226 }; 227 228 /// @endcond 229 230 /** 231 * @brief Copies the value x into the range [first,last). 232 * @param __first An input iterator. 233 * @param __last An input iterator. 234 * @param __x The source value. 235 * @return Nothing. 236 * 237 * Like fill(), but does not require an initialized output range. 238 */ 239 template<typename _ForwardIterator, typename _Tp> 240 inline void 241 uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, 242 const _Tp& __x) 243 { 244 typedef typename iterator_traits<_ForwardIterator>::value_type 245 _ValueType; 246 247 // Trivial types do not need a constructor to begin their lifetime, 248 // so try to use std::fill to benefit from its memset optimization. 249 const bool __can_fill 250 = _GLIBCXX_USE_ASSIGN_FOR_INIT(_ValueType, const _Tp&); 251 252 std::__uninitialized_fill<__can_fill>:: 253 __uninit_fill(__first, __last, __x); 254 } 255 256 /// @cond undocumented 257 258 template<typename _ForwardIterator, typename _Size, typename _Tp> 259 _GLIBCXX20_CONSTEXPR 260 _ForwardIterator 261 __do_uninit_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) 262 { 263 _ForwardIterator __cur = __first; 264 __try 265 { 266 for (; __n > 0; --__n, (void) ++__cur) 267 std::_Construct(std::__addressof(*__cur), __x); 268 return __cur; 269 } 270 __catch(...) 271 { 272 std::_Destroy(__first, __cur); 273 __throw_exception_again; 274 } 275 } 276 277 template<bool _TrivialValueType> 278 struct __uninitialized_fill_n 279 { 280 template<typename _ForwardIterator, typename _Size, typename _Tp> 281 static _ForwardIterator 282 __uninit_fill_n(_ForwardIterator __first, _Size __n, 283 const _Tp& __x) 284 { return std::__do_uninit_fill_n(__first, __n, __x); } 285 }; 286 287 template<> 288 struct __uninitialized_fill_n<true> 289 { 290 template<typename _ForwardIterator, typename _Size, typename _Tp> 291 static _ForwardIterator 292 __uninit_fill_n(_ForwardIterator __first, _Size __n, 293 const _Tp& __x) 294 { return std::fill_n(__first, __n, __x); } 295 }; 296 297 /// @endcond 298 299 // _GLIBCXX_RESOLVE_LIB_DEFECTS 300 // DR 1339. uninitialized_fill_n should return the end of its range 301 /** 302 * @brief Copies the value x into the range [first,first+n). 303 * @param __first An input iterator. 304 * @param __n The number of copies to make. 305 * @param __x The source value. 306 * @return Nothing. 307 * 308 * Like fill_n(), but does not require an initialized output range. 309 */ 310 template<typename _ForwardIterator, typename _Size, typename _Tp> 311 inline _ForwardIterator 312 uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) 313 { 314 typedef typename iterator_traits<_ForwardIterator>::value_type 315 _ValueType; 316 317 // Trivial types do not need a constructor to begin their lifetime, 318 // so try to use std::fill_n to benefit from its optimizations. 319 const bool __can_fill 320 = _GLIBCXX_USE_ASSIGN_FOR_INIT(_ValueType, const _Tp&) 321 // For arbitrary class types and floating point types we can't assume 322 // that __n > 0 and std::__size_to_integer(__n) > 0 are equivalent, 323 // so only use std::fill_n when _Size is already an integral type. 324 && __is_integer<_Size>::__value; 325 326 return __uninitialized_fill_n<__can_fill>:: 327 __uninit_fill_n(__first, __n, __x); 328 } 329 330#undef _GLIBCXX_USE_ASSIGN_FOR_INIT 331 332 /// @cond undocumented 333 334 // Extensions: versions of uninitialized_copy, uninitialized_fill, 335 // and uninitialized_fill_n that take an allocator parameter. 336 // We dispatch back to the standard versions when we're given the 337 // default allocator. For nondefault allocators we do not use 338 // any of the POD optimizations. 339 340 template<typename _InputIterator, typename _ForwardIterator, 341 typename _Allocator> 342 _GLIBCXX20_CONSTEXPR 343 _ForwardIterator 344 __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, 345 _ForwardIterator __result, _Allocator& __alloc) 346 { 347 _ForwardIterator __cur = __result; 348 __try 349 { 350 typedef __gnu_cxx::__alloc_traits<_Allocator> __traits; 351 for (; __first != __last; ++__first, (void)++__cur) 352 __traits::construct(__alloc, std::__addressof(*__cur), *__first); 353 return __cur; 354 } 355 __catch(...) 356 { 357 std::_Destroy(__result, __cur, __alloc); 358 __throw_exception_again; 359 } 360 } 361 362 template<typename _InputIterator, typename _ForwardIterator, typename _Tp> 363 _GLIBCXX20_CONSTEXPR 364 inline _ForwardIterator 365 __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, 366 _ForwardIterator __result, allocator<_Tp>&) 367 { 368#ifdef __cpp_lib_is_constant_evaluated 369 if (std::is_constant_evaluated()) 370 return std::__do_uninit_copy(__first, __last, __result); 371#endif 372 return std::uninitialized_copy(__first, __last, __result); 373 } 374 375 template<typename _InputIterator, typename _ForwardIterator, 376 typename _Allocator> 377 _GLIBCXX20_CONSTEXPR 378 inline _ForwardIterator 379 __uninitialized_move_a(_InputIterator __first, _InputIterator __last, 380 _ForwardIterator __result, _Allocator& __alloc) 381 { 382 return std::__uninitialized_copy_a(_GLIBCXX_MAKE_MOVE_ITERATOR(__first), 383 _GLIBCXX_MAKE_MOVE_ITERATOR(__last), 384 __result, __alloc); 385 } 386 387 template<typename _InputIterator, typename _ForwardIterator, 388 typename _Allocator> 389 _GLIBCXX20_CONSTEXPR 390 inline _ForwardIterator 391 __uninitialized_move_if_noexcept_a(_InputIterator __first, 392 _InputIterator __last, 393 _ForwardIterator __result, 394 _Allocator& __alloc) 395 { 396 return std::__uninitialized_copy_a 397 (_GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(__first), 398 _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(__last), __result, __alloc); 399 } 400 401 template<typename _ForwardIterator, typename _Tp, typename _Allocator> 402 _GLIBCXX20_CONSTEXPR 403 void 404 __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last, 405 const _Tp& __x, _Allocator& __alloc) 406 { 407 _ForwardIterator __cur = __first; 408 __try 409 { 410 typedef __gnu_cxx::__alloc_traits<_Allocator> __traits; 411 for (; __cur != __last; ++__cur) 412 __traits::construct(__alloc, std::__addressof(*__cur), __x); 413 } 414 __catch(...) 415 { 416 std::_Destroy(__first, __cur, __alloc); 417 __throw_exception_again; 418 } 419 } 420 421 template<typename _ForwardIterator, typename _Tp, typename _Tp2> 422 _GLIBCXX20_CONSTEXPR 423 inline void 424 __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last, 425 const _Tp& __x, allocator<_Tp2>&) 426 { 427#ifdef __cpp_lib_is_constant_evaluated 428 if (std::is_constant_evaluated()) 429 return std::__do_uninit_fill(__first, __last, __x); 430#endif 431 std::uninitialized_fill(__first, __last, __x); 432 } 433 434 template<typename _ForwardIterator, typename _Size, typename _Tp, 435 typename _Allocator> 436 _GLIBCXX20_CONSTEXPR 437 _ForwardIterator 438 __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 439 const _Tp& __x, _Allocator& __alloc) 440 { 441 _ForwardIterator __cur = __first; 442 __try 443 { 444 typedef __gnu_cxx::__alloc_traits<_Allocator> __traits; 445 for (; __n > 0; --__n, (void) ++__cur) 446 __traits::construct(__alloc, std::__addressof(*__cur), __x); 447 return __cur; 448 } 449 __catch(...) 450 { 451 std::_Destroy(__first, __cur, __alloc); 452 __throw_exception_again; 453 } 454 } 455 456 template<typename _ForwardIterator, typename _Size, typename _Tp, 457 typename _Tp2> 458 _GLIBCXX20_CONSTEXPR 459 inline _ForwardIterator 460 __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 461 const _Tp& __x, allocator<_Tp2>&) 462 { 463#ifdef __cpp_lib_is_constant_evaluated 464 if (std::is_constant_evaluated()) 465 return std::__do_uninit_fill_n(__first, __n, __x); 466#endif 467 return std::uninitialized_fill_n(__first, __n, __x); 468 } 469 470 471 // Extensions: __uninitialized_copy_move, __uninitialized_move_copy, 472 // __uninitialized_fill_move, __uninitialized_move_fill. 473 // All of these algorithms take a user-supplied allocator, which is used 474 // for construction and destruction. 475 476 // __uninitialized_copy_move 477 // Copies [first1, last1) into [result, result + (last1 - first1)), and 478 // move [first2, last2) into 479 // [result, result + (last1 - first1) + (last2 - first2)). 480 template<typename _InputIterator1, typename _InputIterator2, 481 typename _ForwardIterator, typename _Allocator> 482 inline _ForwardIterator 483 __uninitialized_copy_move(_InputIterator1 __first1, 484 _InputIterator1 __last1, 485 _InputIterator2 __first2, 486 _InputIterator2 __last2, 487 _ForwardIterator __result, 488 _Allocator& __alloc) 489 { 490 _ForwardIterator __mid = std::__uninitialized_copy_a(__first1, __last1, 491 __result, 492 __alloc); 493 __try 494 { 495 return std::__uninitialized_move_a(__first2, __last2, __mid, __alloc); 496 } 497 __catch(...) 498 { 499 std::_Destroy(__result, __mid, __alloc); 500 __throw_exception_again; 501 } 502 } 503 504 // __uninitialized_move_copy 505 // Moves [first1, last1) into [result, result + (last1 - first1)), and 506 // copies [first2, last2) into 507 // [result, result + (last1 - first1) + (last2 - first2)). 508 template<typename _InputIterator1, typename _InputIterator2, 509 typename _ForwardIterator, typename _Allocator> 510 inline _ForwardIterator 511 __uninitialized_move_copy(_InputIterator1 __first1, 512 _InputIterator1 __last1, 513 _InputIterator2 __first2, 514 _InputIterator2 __last2, 515 _ForwardIterator __result, 516 _Allocator& __alloc) 517 { 518 _ForwardIterator __mid = std::__uninitialized_move_a(__first1, __last1, 519 __result, 520 __alloc); 521 __try 522 { 523 return std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc); 524 } 525 __catch(...) 526 { 527 std::_Destroy(__result, __mid, __alloc); 528 __throw_exception_again; 529 } 530 } 531 532 // __uninitialized_fill_move 533 // Fills [result, mid) with x, and moves [first, last) into 534 // [mid, mid + (last - first)). 535 template<typename _ForwardIterator, typename _Tp, typename _InputIterator, 536 typename _Allocator> 537 inline _ForwardIterator 538 __uninitialized_fill_move(_ForwardIterator __result, _ForwardIterator __mid, 539 const _Tp& __x, _InputIterator __first, 540 _InputIterator __last, _Allocator& __alloc) 541 { 542 std::__uninitialized_fill_a(__result, __mid, __x, __alloc); 543 __try 544 { 545 return std::__uninitialized_move_a(__first, __last, __mid, __alloc); 546 } 547 __catch(...) 548 { 549 std::_Destroy(__result, __mid, __alloc); 550 __throw_exception_again; 551 } 552 } 553 554 // __uninitialized_move_fill 555 // Moves [first1, last1) into [first2, first2 + (last1 - first1)), and 556 // fills [first2 + (last1 - first1), last2) with x. 557 template<typename _InputIterator, typename _ForwardIterator, typename _Tp, 558 typename _Allocator> 559 inline void 560 __uninitialized_move_fill(_InputIterator __first1, _InputIterator __last1, 561 _ForwardIterator __first2, 562 _ForwardIterator __last2, const _Tp& __x, 563 _Allocator& __alloc) 564 { 565 _ForwardIterator __mid2 = std::__uninitialized_move_a(__first1, __last1, 566 __first2, 567 __alloc); 568 __try 569 { 570 std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc); 571 } 572 __catch(...) 573 { 574 std::_Destroy(__first2, __mid2, __alloc); 575 __throw_exception_again; 576 } 577 } 578 579 /// @endcond 580 581#if __cplusplus >= 201103L 582 /// @cond undocumented 583 584 // Extensions: __uninitialized_default, __uninitialized_default_n, 585 // __uninitialized_default_a, __uninitialized_default_n_a. 586 587 template<bool _TrivialValueType> 588 struct __uninitialized_default_1 589 { 590 template<typename _ForwardIterator> 591 static void 592 __uninit_default(_ForwardIterator __first, _ForwardIterator __last) 593 { 594 _ForwardIterator __cur = __first; 595 __try 596 { 597 for (; __cur != __last; ++__cur) 598 std::_Construct(std::__addressof(*__cur)); 599 } 600 __catch(...) 601 { 602 std::_Destroy(__first, __cur); 603 __throw_exception_again; 604 } 605 } 606 }; 607 608 template<> 609 struct __uninitialized_default_1<true> 610 { 611 template<typename _ForwardIterator> 612 static void 613 __uninit_default(_ForwardIterator __first, _ForwardIterator __last) 614 { 615 if (__first == __last) 616 return; 617 618 typename iterator_traits<_ForwardIterator>::value_type* __val 619 = std::__addressof(*__first); 620 std::_Construct(__val); 621 if (++__first != __last) 622 std::fill(__first, __last, *__val); 623 } 624 }; 625 626 template<bool _TrivialValueType> 627 struct __uninitialized_default_n_1 628 { 629 template<typename _ForwardIterator, typename _Size> 630 _GLIBCXX20_CONSTEXPR 631 static _ForwardIterator 632 __uninit_default_n(_ForwardIterator __first, _Size __n) 633 { 634 _ForwardIterator __cur = __first; 635 __try 636 { 637 for (; __n > 0; --__n, (void) ++__cur) 638 std::_Construct(std::__addressof(*__cur)); 639 return __cur; 640 } 641 __catch(...) 642 { 643 std::_Destroy(__first, __cur); 644 __throw_exception_again; 645 } 646 } 647 }; 648 649 template<> 650 struct __uninitialized_default_n_1<true> 651 { 652 template<typename _ForwardIterator, typename _Size> 653 _GLIBCXX20_CONSTEXPR 654 static _ForwardIterator 655 __uninit_default_n(_ForwardIterator __first, _Size __n) 656 { 657 if (__n > 0) 658 { 659 typename iterator_traits<_ForwardIterator>::value_type* __val 660 = std::__addressof(*__first); 661 std::_Construct(__val); 662 ++__first; 663 __first = std::fill_n(__first, __n - 1, *__val); 664 } 665 return __first; 666 } 667 }; 668 669 // __uninitialized_default 670 // Fills [first, last) with value-initialized value_types. 671 template<typename _ForwardIterator> 672 inline void 673 __uninitialized_default(_ForwardIterator __first, 674 _ForwardIterator __last) 675 { 676 typedef typename iterator_traits<_ForwardIterator>::value_type 677 _ValueType; 678 // trivial types can have deleted assignment 679 const bool __assignable = is_copy_assignable<_ValueType>::value; 680 681 std::__uninitialized_default_1<__is_trivial(_ValueType) 682 && __assignable>:: 683 __uninit_default(__first, __last); 684 } 685 686 // __uninitialized_default_n 687 // Fills [first, first + n) with value-initialized value_types. 688 template<typename _ForwardIterator, typename _Size> 689 _GLIBCXX20_CONSTEXPR 690 inline _ForwardIterator 691 __uninitialized_default_n(_ForwardIterator __first, _Size __n) 692 { 693#ifdef __cpp_lib_is_constant_evaluated 694 if (std::is_constant_evaluated()) 695 return __uninitialized_default_n_1<false>:: 696 __uninit_default_n(__first, __n); 697#endif 698 699 typedef typename iterator_traits<_ForwardIterator>::value_type 700 _ValueType; 701 // See uninitialized_fill_n for the conditions for using std::fill_n. 702 constexpr bool __can_fill 703 = __and_<is_integral<_Size>, is_copy_assignable<_ValueType>>::value; 704 705 return __uninitialized_default_n_1<__is_trivial(_ValueType) 706 && __can_fill>:: 707 __uninit_default_n(__first, __n); 708 } 709 710 711 // __uninitialized_default_a 712 // Fills [first, last) with value_types constructed by the allocator 713 // alloc, with no arguments passed to the construct call. 714 template<typename _ForwardIterator, typename _Allocator> 715 void 716 __uninitialized_default_a(_ForwardIterator __first, 717 _ForwardIterator __last, 718 _Allocator& __alloc) 719 { 720 _ForwardIterator __cur = __first; 721 __try 722 { 723 typedef __gnu_cxx::__alloc_traits<_Allocator> __traits; 724 for (; __cur != __last; ++__cur) 725 __traits::construct(__alloc, std::__addressof(*__cur)); 726 } 727 __catch(...) 728 { 729 std::_Destroy(__first, __cur, __alloc); 730 __throw_exception_again; 731 } 732 } 733 734 template<typename _ForwardIterator, typename _Tp> 735 inline void 736 __uninitialized_default_a(_ForwardIterator __first, 737 _ForwardIterator __last, 738 allocator<_Tp>&) 739 { std::__uninitialized_default(__first, __last); } 740 741 742 // __uninitialized_default_n_a 743 // Fills [first, first + n) with value_types constructed by the allocator 744 // alloc, with no arguments passed to the construct call. 745 template<typename _ForwardIterator, typename _Size, typename _Allocator> 746 _GLIBCXX20_CONSTEXPR _ForwardIterator 747 __uninitialized_default_n_a(_ForwardIterator __first, _Size __n, 748 _Allocator& __alloc) 749 { 750 _ForwardIterator __cur = __first; 751 __try 752 { 753 typedef __gnu_cxx::__alloc_traits<_Allocator> __traits; 754 for (; __n > 0; --__n, (void) ++__cur) 755 __traits::construct(__alloc, std::__addressof(*__cur)); 756 return __cur; 757 } 758 __catch(...) 759 { 760 std::_Destroy(__first, __cur, __alloc); 761 __throw_exception_again; 762 } 763 } 764 765 // __uninitialized_default_n_a specialization for std::allocator, 766 // which ignores the allocator and value-initializes the elements. 767 template<typename _ForwardIterator, typename _Size, typename _Tp> 768 _GLIBCXX20_CONSTEXPR 769 inline _ForwardIterator 770 __uninitialized_default_n_a(_ForwardIterator __first, _Size __n, 771 allocator<_Tp>&) 772 { return std::__uninitialized_default_n(__first, __n); } 773 774 template<bool _TrivialValueType> 775 struct __uninitialized_default_novalue_1 776 { 777 template<typename _ForwardIterator> 778 static void 779 __uninit_default_novalue(_ForwardIterator __first, 780 _ForwardIterator __last) 781 { 782 _ForwardIterator __cur = __first; 783 __try 784 { 785 for (; __cur != __last; ++__cur) 786 std::_Construct_novalue(std::__addressof(*__cur)); 787 } 788 __catch(...) 789 { 790 std::_Destroy(__first, __cur); 791 __throw_exception_again; 792 } 793 } 794 }; 795 796 template<> 797 struct __uninitialized_default_novalue_1<true> 798 { 799 template<typename _ForwardIterator> 800 static void 801 __uninit_default_novalue(_ForwardIterator __first, 802 _ForwardIterator __last) 803 { 804 } 805 }; 806 807 template<bool _TrivialValueType> 808 struct __uninitialized_default_novalue_n_1 809 { 810 template<typename _ForwardIterator, typename _Size> 811 static _ForwardIterator 812 __uninit_default_novalue_n(_ForwardIterator __first, _Size __n) 813 { 814 _ForwardIterator __cur = __first; 815 __try 816 { 817 for (; __n > 0; --__n, (void) ++__cur) 818 std::_Construct_novalue(std::__addressof(*__cur)); 819 return __cur; 820 } 821 __catch(...) 822 { 823 std::_Destroy(__first, __cur); 824 __throw_exception_again; 825 } 826 } 827 }; 828 829 template<> 830 struct __uninitialized_default_novalue_n_1<true> 831 { 832 template<typename _ForwardIterator, typename _Size> 833 static _ForwardIterator 834 __uninit_default_novalue_n(_ForwardIterator __first, _Size __n) 835 { return std::next(__first, __n); } 836 }; 837 838 // __uninitialized_default_novalue 839 // Fills [first, last) with default-initialized value_types. 840 template<typename _ForwardIterator> 841 inline void 842 __uninitialized_default_novalue(_ForwardIterator __first, 843 _ForwardIterator __last) 844 { 845 typedef typename iterator_traits<_ForwardIterator>::value_type 846 _ValueType; 847 848 std::__uninitialized_default_novalue_1< 849 is_trivially_default_constructible<_ValueType>::value>:: 850 __uninit_default_novalue(__first, __last); 851 } 852 853 // __uninitialized_default_novalue_n 854 // Fills [first, first + n) with default-initialized value_types. 855 template<typename _ForwardIterator, typename _Size> 856 inline _ForwardIterator 857 __uninitialized_default_novalue_n(_ForwardIterator __first, _Size __n) 858 { 859 typedef typename iterator_traits<_ForwardIterator>::value_type 860 _ValueType; 861 862 return __uninitialized_default_novalue_n_1< 863 is_trivially_default_constructible<_ValueType>::value>:: 864 __uninit_default_novalue_n(__first, __n); 865 } 866 867 template<typename _InputIterator, typename _Size, 868 typename _ForwardIterator> 869 _ForwardIterator 870 __uninitialized_copy_n(_InputIterator __first, _Size __n, 871 _ForwardIterator __result, input_iterator_tag) 872 { 873 _ForwardIterator __cur = __result; 874 __try 875 { 876 for (; __n > 0; --__n, (void) ++__first, ++__cur) 877 std::_Construct(std::__addressof(*__cur), *__first); 878 return __cur; 879 } 880 __catch(...) 881 { 882 std::_Destroy(__result, __cur); 883 __throw_exception_again; 884 } 885 } 886 887 template<typename _RandomAccessIterator, typename _Size, 888 typename _ForwardIterator> 889 inline _ForwardIterator 890 __uninitialized_copy_n(_RandomAccessIterator __first, _Size __n, 891 _ForwardIterator __result, 892 random_access_iterator_tag) 893 { return std::uninitialized_copy(__first, __first + __n, __result); } 894 895 template<typename _InputIterator, typename _Size, 896 typename _ForwardIterator> 897 pair<_InputIterator, _ForwardIterator> 898 __uninitialized_copy_n_pair(_InputIterator __first, _Size __n, 899 _ForwardIterator __result, input_iterator_tag) 900 { 901 _ForwardIterator __cur = __result; 902 __try 903 { 904 for (; __n > 0; --__n, (void) ++__first, ++__cur) 905 std::_Construct(std::__addressof(*__cur), *__first); 906 return {__first, __cur}; 907 } 908 __catch(...) 909 { 910 std::_Destroy(__result, __cur); 911 __throw_exception_again; 912 } 913 } 914 915 template<typename _RandomAccessIterator, typename _Size, 916 typename _ForwardIterator> 917 inline pair<_RandomAccessIterator, _ForwardIterator> 918 __uninitialized_copy_n_pair(_RandomAccessIterator __first, _Size __n, 919 _ForwardIterator __result, 920 random_access_iterator_tag) 921 { 922 auto __second_res = uninitialized_copy(__first, __first + __n, __result); 923 auto __first_res = std::next(__first, __n); 924 return {__first_res, __second_res}; 925 } 926 927 /// @endcond 928 929 /** 930 * @brief Copies the range [first,first+n) into result. 931 * @param __first An input iterator. 932 * @param __n The number of elements to copy. 933 * @param __result An output iterator. 934 * @return __result + __n 935 * @since C++11 936 * 937 * Like copy_n(), but does not require an initialized output range. 938 */ 939 template<typename _InputIterator, typename _Size, typename _ForwardIterator> 940 inline _ForwardIterator 941 uninitialized_copy_n(_InputIterator __first, _Size __n, 942 _ForwardIterator __result) 943 { return std::__uninitialized_copy_n(__first, __n, __result, 944 std::__iterator_category(__first)); } 945 946 /// @cond undocumented 947 template<typename _InputIterator, typename _Size, typename _ForwardIterator> 948 inline pair<_InputIterator, _ForwardIterator> 949 __uninitialized_copy_n_pair(_InputIterator __first, _Size __n, 950 _ForwardIterator __result) 951 { 952 return 953 std::__uninitialized_copy_n_pair(__first, __n, __result, 954 std::__iterator_category(__first)); 955 } 956 /// @endcond 957#endif 958 959#if __cplusplus >= 201703L 960# define __cpp_lib_raw_memory_algorithms 201606L 961 962 /** 963 * @brief Default-initializes objects in the range [first,last). 964 * @param __first A forward iterator. 965 * @param __last A forward iterator. 966 * @since C++17 967 */ 968 template <typename _ForwardIterator> 969 inline void 970 uninitialized_default_construct(_ForwardIterator __first, 971 _ForwardIterator __last) 972 { 973 __uninitialized_default_novalue(__first, __last); 974 } 975 976 /** 977 * @brief Default-initializes objects in the range [first,first+count). 978 * @param __first A forward iterator. 979 * @param __count The number of objects to construct. 980 * @return __first + __count 981 * @since C++17 982 */ 983 template <typename _ForwardIterator, typename _Size> 984 inline _ForwardIterator 985 uninitialized_default_construct_n(_ForwardIterator __first, _Size __count) 986 { 987 return __uninitialized_default_novalue_n(__first, __count); 988 } 989 990 /** 991 * @brief Value-initializes objects in the range [first,last). 992 * @param __first A forward iterator. 993 * @param __last A forward iterator. 994 * @since C++17 995 */ 996 template <typename _ForwardIterator> 997 inline void 998 uninitialized_value_construct(_ForwardIterator __first, 999 _ForwardIterator __last) 1000 { 1001 return __uninitialized_default(__first, __last); 1002 } 1003 1004 /** 1005 * @brief Value-initializes objects in the range [first,first+count). 1006 * @param __first A forward iterator. 1007 * @param __count The number of objects to construct. 1008 * @return __result + __count 1009 * @since C++17 1010 */ 1011 template <typename _ForwardIterator, typename _Size> 1012 inline _ForwardIterator 1013 uninitialized_value_construct_n(_ForwardIterator __first, _Size __count) 1014 { 1015 return __uninitialized_default_n(__first, __count); 1016 } 1017 1018 /** 1019 * @brief Move-construct from the range [first,last) into result. 1020 * @param __first An input iterator. 1021 * @param __last An input iterator. 1022 * @param __result An output iterator. 1023 * @return __result + (__first - __last) 1024 * @since C++17 1025 */ 1026 template <typename _InputIterator, typename _ForwardIterator> 1027 inline _ForwardIterator 1028 uninitialized_move(_InputIterator __first, _InputIterator __last, 1029 _ForwardIterator __result) 1030 { 1031 return std::uninitialized_copy 1032 (_GLIBCXX_MAKE_MOVE_ITERATOR(__first), 1033 _GLIBCXX_MAKE_MOVE_ITERATOR(__last), __result); 1034 } 1035 1036 /** 1037 * @brief Move-construct from the range [first,first+count) into result. 1038 * @param __first An input iterator. 1039 * @param __count The number of objects to initialize. 1040 * @param __result An output iterator. 1041 * @return __result + __count 1042 * @since C++17 1043 */ 1044 template <typename _InputIterator, typename _Size, typename _ForwardIterator> 1045 inline pair<_InputIterator, _ForwardIterator> 1046 uninitialized_move_n(_InputIterator __first, _Size __count, 1047 _ForwardIterator __result) 1048 { 1049 auto __res = std::__uninitialized_copy_n_pair 1050 (_GLIBCXX_MAKE_MOVE_ITERATOR(__first), 1051 __count, __result); 1052 return {__res.first.base(), __res.second}; 1053 } 1054#endif // C++17 1055 1056#if __cplusplus >= 201103L 1057 /// @cond undocumented 1058 1059 template<typename _Tp, typename _Up, typename _Allocator> 1060 _GLIBCXX20_CONSTEXPR 1061 inline void 1062 __relocate_object_a(_Tp* __restrict __dest, _Up* __restrict __orig, 1063 _Allocator& __alloc) 1064 noexcept(noexcept(std::allocator_traits<_Allocator>::construct(__alloc, 1065 __dest, std::move(*__orig))) 1066 && noexcept(std::allocator_traits<_Allocator>::destroy( 1067 __alloc, std::__addressof(*__orig)))) 1068 { 1069 typedef std::allocator_traits<_Allocator> __traits; 1070 __traits::construct(__alloc, __dest, std::move(*__orig)); 1071 __traits::destroy(__alloc, std::__addressof(*__orig)); 1072 } 1073 1074 // This class may be specialized for specific types. 1075 // Also known as is_trivially_relocatable. 1076 template<typename _Tp, typename = void> 1077 struct __is_bitwise_relocatable 1078 : is_trivial<_Tp> { }; 1079 1080 template <typename _InputIterator, typename _ForwardIterator, 1081 typename _Allocator> 1082 _GLIBCXX20_CONSTEXPR 1083 inline _ForwardIterator 1084 __relocate_a_1(_InputIterator __first, _InputIterator __last, 1085 _ForwardIterator __result, _Allocator& __alloc) 1086 noexcept(noexcept(std::__relocate_object_a(std::addressof(*__result), 1087 std::addressof(*__first), 1088 __alloc))) 1089 { 1090 typedef typename iterator_traits<_InputIterator>::value_type 1091 _ValueType; 1092 typedef typename iterator_traits<_ForwardIterator>::value_type 1093 _ValueType2; 1094 static_assert(std::is_same<_ValueType, _ValueType2>::value, 1095 "relocation is only possible for values of the same type"); 1096 _ForwardIterator __cur = __result; 1097 for (; __first != __last; ++__first, (void)++__cur) 1098 std::__relocate_object_a(std::__addressof(*__cur), 1099 std::__addressof(*__first), __alloc); 1100 return __cur; 1101 } 1102 1103 template <typename _Tp, typename _Up> 1104 _GLIBCXX20_CONSTEXPR 1105 inline __enable_if_t<std::__is_bitwise_relocatable<_Tp>::value, _Tp*> 1106 __relocate_a_1(_Tp* __first, _Tp* __last, 1107 _Tp* __result, 1108 [[__maybe_unused__]] allocator<_Up>& __alloc) noexcept 1109 { 1110 ptrdiff_t __count = __last - __first; 1111 if (__count > 0) 1112 { 1113#ifdef __cpp_lib_is_constant_evaluated 1114 if (std::is_constant_evaluated()) 1115 { 1116 // Can't use memmove. Wrap the pointer so that __relocate_a_1 1117 // resolves to the non-trivial overload above. 1118 __gnu_cxx::__normal_iterator<_Tp*, void> __out(__result); 1119 __out = std::__relocate_a_1(__first, __last, __out, __alloc); 1120 return __out.base(); 1121 } 1122#endif 1123 __builtin_memmove(__result, __first, __count * sizeof(_Tp)); 1124 } 1125 return __result + __count; 1126 } 1127 1128 1129 template <typename _InputIterator, typename _ForwardIterator, 1130 typename _Allocator> 1131 _GLIBCXX20_CONSTEXPR 1132 inline _ForwardIterator 1133 __relocate_a(_InputIterator __first, _InputIterator __last, 1134 _ForwardIterator __result, _Allocator& __alloc) 1135 noexcept(noexcept(__relocate_a_1(std::__niter_base(__first), 1136 std::__niter_base(__last), 1137 std::__niter_base(__result), __alloc))) 1138 { 1139 return std::__relocate_a_1(std::__niter_base(__first), 1140 std::__niter_base(__last), 1141 std::__niter_base(__result), __alloc); 1142 } 1143 1144 /// @endcond 1145#endif 1146 1147 /// @} group memory 1148 1149_GLIBCXX_END_NAMESPACE_VERSION 1150} // namespace 1151 1152#endif /* _STL_UNINITIALIZED_H */ 1153