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