libstdc++-v3/include/bits/stl_uninitialized.h

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