xref: /netbsd-src/external/gpl3/gcc/dist/libstdc++-v3/include/bits/stl_uninitialized.h (revision 0a3071956a3a9fdebdbf7f338cf2d439b45fc728)
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 
_GLIBCXX_VISIBILITY(default)70 namespace 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