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