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