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