libstdc++
bits/alloc_traits.h
Go to the documentation of this file.
1 // Allocator traits -*- C++ -*-
2 
3 // Copyright (C) 2011-2023 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 /** @file bits/alloc_traits.h
26  * This is an internal header file, included by other library headers.
27  * Do not attempt to use it directly. @headername{memory}
28  */
29 
30 #ifndef _ALLOC_TRAITS_H
31 #define _ALLOC_TRAITS_H 1
32 
33 #include <bits/stl_construct.h>
34 #include <bits/memoryfwd.h>
35 #if __cplusplus >= 201103L
36 # include <bits/ptr_traits.h>
37 # include <ext/numeric_traits.h>
38 # if _GLIBCXX_HOSTED
39 # include <bits/allocator.h>
40 # endif
41 #endif
42 
43 namespace std _GLIBCXX_VISIBILITY(default)
44 {
45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
46 
47 #if __cplusplus >= 201103L
48 #define __cpp_lib_allocator_traits_is_always_equal 201411L
49 
50  /// @cond undocumented
51  struct __allocator_traits_base
52  {
53  template<typename _Tp, typename _Up, typename = void>
54  struct __rebind : __replace_first_arg<_Tp, _Up>
55  {
56  static_assert(is_same<
57  typename __replace_first_arg<_Tp, typename _Tp::value_type>::type,
58  _Tp>::value,
59  "allocator_traits<A>::rebind_alloc<A::value_type> must be A");
60  };
61 
62  template<typename _Tp, typename _Up>
63  struct __rebind<_Tp, _Up,
64  __void_t<typename _Tp::template rebind<_Up>::other>>
65  {
66  using type = typename _Tp::template rebind<_Up>::other;
67 
68  static_assert(is_same<
69  typename _Tp::template rebind<typename _Tp::value_type>::other,
70  _Tp>::value,
71  "allocator_traits<A>::rebind_alloc<A::value_type> must be A");
72  };
73 
74  protected:
75  template<typename _Tp>
76  using __pointer = typename _Tp::pointer;
77  template<typename _Tp>
78  using __c_pointer = typename _Tp::const_pointer;
79  template<typename _Tp>
80  using __v_pointer = typename _Tp::void_pointer;
81  template<typename _Tp>
82  using __cv_pointer = typename _Tp::const_void_pointer;
83  template<typename _Tp>
84  using __pocca = typename _Tp::propagate_on_container_copy_assignment;
85  template<typename _Tp>
86  using __pocma = typename _Tp::propagate_on_container_move_assignment;
87  template<typename _Tp>
88  using __pocs = typename _Tp::propagate_on_container_swap;
89  template<typename _Tp>
90  using __equal = __type_identity<typename _Tp::is_always_equal>;
91  };
92 
93  template<typename _Alloc, typename _Up>
94  using __alloc_rebind
95  = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;
96  /// @endcond
97 
98  /**
99  * @brief Uniform interface to all allocator types.
100  * @headerfile memory
101  * @ingroup allocators
102  * @since C++11
103  */
104  template<typename _Alloc>
105  struct allocator_traits : __allocator_traits_base
106  {
107  /// The allocator type
108  typedef _Alloc allocator_type;
109  /// The allocated type
110  typedef typename _Alloc::value_type value_type;
111 
112  /**
113  * @brief The allocator's pointer type.
114  *
115  * @c Alloc::pointer if that type exists, otherwise @c value_type*
116  */
117  using pointer = __detected_or_t<value_type*, __pointer, _Alloc>;
118 
119  private:
120  // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp>
121  template<template<typename> class _Func, typename _Tp, typename = void>
122  struct _Ptr
123  {
124  using type = typename pointer_traits<pointer>::template rebind<_Tp>;
125  };
126 
127  template<template<typename> class _Func, typename _Tp>
128  struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>>
129  {
130  using type = _Func<_Alloc>;
131  };
132 
133  // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type
134  template<typename _A2, typename _PtrT, typename = void>
135  struct _Diff
136  { using type = typename pointer_traits<_PtrT>::difference_type; };
137 
138  template<typename _A2, typename _PtrT>
139  struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>>
140  { using type = typename _A2::difference_type; };
141 
142  // Select _A2::size_type or make_unsigned<_DiffT>::type
143  template<typename _A2, typename _DiffT, typename = void>
144  struct _Size : make_unsigned<_DiffT> { };
145 
146  template<typename _A2, typename _DiffT>
147  struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>>
148  { using type = typename _A2::size_type; };
149 
150  public:
151  /**
152  * @brief The allocator's const pointer type.
153  *
154  * @c Alloc::const_pointer if that type exists, otherwise
155  * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
156  */
157  using const_pointer = typename _Ptr<__c_pointer, const value_type>::type;
158 
159  /**
160  * @brief The allocator's void pointer type.
161  *
162  * @c Alloc::void_pointer if that type exists, otherwise
163  * <tt> pointer_traits<pointer>::rebind<void> </tt>
164  */
165  using void_pointer = typename _Ptr<__v_pointer, void>::type;
166 
167  /**
168  * @brief The allocator's const void pointer type.
169  *
170  * @c Alloc::const_void_pointer if that type exists, otherwise
171  * <tt> pointer_traits<pointer>::rebind<const void> </tt>
172  */
173  using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type;
174 
175  /**
176  * @brief The allocator's difference type
177  *
178  * @c Alloc::difference_type if that type exists, otherwise
179  * <tt> pointer_traits<pointer>::difference_type </tt>
180  */
181  using difference_type = typename _Diff<_Alloc, pointer>::type;
182 
183  /**
184  * @brief The allocator's size type
185  *
186  * @c Alloc::size_type if that type exists, otherwise
187  * <tt> make_unsigned<difference_type>::type </tt>
188  */
189  using size_type = typename _Size<_Alloc, difference_type>::type;
190 
191  /**
192  * @brief How the allocator is propagated on copy assignment
193  *
194  * @c Alloc::propagate_on_container_copy_assignment if that type exists,
195  * otherwise @c false_type
196  */
198  = __detected_or_t<false_type, __pocca, _Alloc>;
199 
200  /**
201  * @brief How the allocator is propagated on move assignment
202  *
203  * @c Alloc::propagate_on_container_move_assignment if that type exists,
204  * otherwise @c false_type
205  */
207  = __detected_or_t<false_type, __pocma, _Alloc>;
208 
209  /**
210  * @brief How the allocator is propagated on swap
211  *
212  * @c Alloc::propagate_on_container_swap if that type exists,
213  * otherwise @c false_type
214  */
216  = __detected_or_t<false_type, __pocs, _Alloc>;
217 
218  /**
219  * @brief Whether all instances of the allocator type compare equal.
220  *
221  * @c Alloc::is_always_equal if that type exists,
222  * otherwise @c is_empty<Alloc>::type
223  */
224  using is_always_equal
225  = typename __detected_or_t<is_empty<_Alloc>, __equal, _Alloc>::type;
226 
227  template<typename _Tp>
228  using rebind_alloc = __alloc_rebind<_Alloc, _Tp>;
229  template<typename _Tp>
231 
232  private:
233  template<typename _Alloc2>
234  static constexpr auto
235  _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
236  -> decltype(__a.allocate(__n, __hint))
237  { return __a.allocate(__n, __hint); }
238 
239  template<typename _Alloc2>
240  static constexpr pointer
241  _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
242  { return __a.allocate(__n); }
243 
244  template<typename _Tp, typename... _Args>
245  struct __construct_helper
246  {
247  template<typename _Alloc2,
248  typename = decltype(std::declval<_Alloc2*>()->construct(
249  std::declval<_Tp*>(), std::declval<_Args>()...))>
250  static true_type __test(int);
251 
252  template<typename>
253  static false_type __test(...);
254 
255  using type = decltype(__test<_Alloc>(0));
256  };
257 
258  template<typename _Tp, typename... _Args>
259  using __has_construct
260  = typename __construct_helper<_Tp, _Args...>::type;
261 
262  template<typename _Tp, typename... _Args>
263  static _GLIBCXX14_CONSTEXPR _Require<__has_construct<_Tp, _Args...>>
264  _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
265  noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
266  { __a.construct(__p, std::forward<_Args>(__args)...); }
267 
268  template<typename _Tp, typename... _Args>
269  static _GLIBCXX14_CONSTEXPR
270  _Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
271  is_constructible<_Tp, _Args...>>>
272  _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
274  {
275 #if __cplusplus <= 201703L
276  ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
277 #else
278  std::construct_at(__p, std::forward<_Args>(__args)...);
279 #endif
280  }
281 
282  template<typename _Alloc2, typename _Tp>
283  static _GLIBCXX14_CONSTEXPR auto
284  _S_destroy(_Alloc2& __a, _Tp* __p, int)
285  noexcept(noexcept(__a.destroy(__p)))
286  -> decltype(__a.destroy(__p))
287  { __a.destroy(__p); }
288 
289  template<typename _Alloc2, typename _Tp>
290  static _GLIBCXX14_CONSTEXPR void
291  _S_destroy(_Alloc2&, _Tp* __p, ...)
292  noexcept(std::is_nothrow_destructible<_Tp>::value)
293  { std::_Destroy(__p); }
294 
295  template<typename _Alloc2>
296  static constexpr auto
297  _S_max_size(_Alloc2& __a, int)
298  -> decltype(__a.max_size())
299  { return __a.max_size(); }
300 
301  template<typename _Alloc2>
302  static constexpr size_type
303  _S_max_size(_Alloc2&, ...)
304  {
305  // _GLIBCXX_RESOLVE_LIB_DEFECTS
306  // 2466. allocator_traits::max_size() default behavior is incorrect
307  return __gnu_cxx::__numeric_traits<size_type>::__max
308  / sizeof(value_type);
309  }
310 
311  template<typename _Alloc2>
312  static constexpr auto
313  _S_select(_Alloc2& __a, int)
314  -> decltype(__a.select_on_container_copy_construction())
315  { return __a.select_on_container_copy_construction(); }
316 
317  template<typename _Alloc2>
318  static constexpr _Alloc2
319  _S_select(_Alloc2& __a, ...)
320  { return __a; }
321 
322  public:
323 
324  /**
325  * @brief Allocate memory.
326  * @param __a An allocator.
327  * @param __n The number of objects to allocate space for.
328  *
329  * Calls @c a.allocate(n)
330  */
331  _GLIBCXX_NODISCARD static _GLIBCXX20_CONSTEXPR pointer
332  allocate(_Alloc& __a, size_type __n)
333  { return __a.allocate(__n); }
334 
335  /**
336  * @brief Allocate memory.
337  * @param __a An allocator.
338  * @param __n The number of objects to allocate space for.
339  * @param __hint Aid to locality.
340  * @return Memory of suitable size and alignment for @a n objects
341  * of type @c value_type
342  *
343  * Returns <tt> a.allocate(n, hint) </tt> if that expression is
344  * well-formed, otherwise returns @c a.allocate(n)
345  */
346  _GLIBCXX_NODISCARD static _GLIBCXX20_CONSTEXPR pointer
347  allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
348  { return _S_allocate(__a, __n, __hint, 0); }
349 
350  /**
351  * @brief Deallocate memory.
352  * @param __a An allocator.
353  * @param __p Pointer to the memory to deallocate.
354  * @param __n The number of objects space was allocated for.
355  *
356  * Calls <tt> a.deallocate(p, n) </tt>
357  */
358  static _GLIBCXX20_CONSTEXPR void
359  deallocate(_Alloc& __a, pointer __p, size_type __n)
360  { __a.deallocate(__p, __n); }
361 
362  /**
363  * @brief Construct an object of type `_Tp`
364  * @param __a An allocator.
365  * @param __p Pointer to memory of suitable size and alignment for Tp
366  * @param __args Constructor arguments.
367  *
368  * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
369  * if that expression is well-formed, otherwise uses placement-new
370  * to construct an object of type @a _Tp at location @a __p from the
371  * arguments @a __args...
372  */
373  template<typename _Tp, typename... _Args>
374  static _GLIBCXX20_CONSTEXPR auto
375  construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
376  noexcept(noexcept(_S_construct(__a, __p,
377  std::forward<_Args>(__args)...)))
378  -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
379  { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
380 
381  /**
382  * @brief Destroy an object of type @a _Tp
383  * @param __a An allocator.
384  * @param __p Pointer to the object to destroy
385  *
386  * Calls @c __a.destroy(__p) if that expression is well-formed,
387  * otherwise calls @c __p->~_Tp()
388  */
389  template<typename _Tp>
390  static _GLIBCXX20_CONSTEXPR void
391  destroy(_Alloc& __a, _Tp* __p)
392  noexcept(noexcept(_S_destroy(__a, __p, 0)))
393  { _S_destroy(__a, __p, 0); }
394 
395  /**
396  * @brief The maximum supported allocation size
397  * @param __a An allocator.
398  * @return @c __a.max_size() or @c numeric_limits<size_type>::max()
399  *
400  * Returns @c __a.max_size() if that expression is well-formed,
401  * otherwise returns @c numeric_limits<size_type>::max()
402  */
403  static _GLIBCXX20_CONSTEXPR size_type
404  max_size(const _Alloc& __a) noexcept
405  { return _S_max_size(__a, 0); }
406 
407  /**
408  * @brief Obtain an allocator to use when copying a container.
409  * @param __rhs An allocator.
410  * @return @c __rhs.select_on_container_copy_construction() or @a __rhs
411  *
412  * Returns @c __rhs.select_on_container_copy_construction() if that
413  * expression is well-formed, otherwise returns @a __rhs
414  */
415  static _GLIBCXX20_CONSTEXPR _Alloc
417  { return _S_select(__rhs, 0); }
418  };
419 
420 #if _GLIBCXX_HOSTED
421 
422 #if __cplusplus > 201703L
423 # define __cpp_lib_constexpr_dynamic_alloc 201907L
424 #endif
425 
426  /// Partial specialization for std::allocator.
427  template<typename _Tp>
429  {
430  /// The allocator type
432 
433  /// The allocated type
434  using value_type = _Tp;
435 
436  /// The allocator's pointer type.
437  using pointer = _Tp*;
438 
439  /// The allocator's const pointer type.
440  using const_pointer = const _Tp*;
441 
442  /// The allocator's void pointer type.
443  using void_pointer = void*;
444 
445  /// The allocator's const void pointer type.
446  using const_void_pointer = const void*;
447 
448  /// The allocator's difference type
449  using difference_type = std::ptrdiff_t;
450 
451  /// The allocator's size type
452  using size_type = std::size_t;
453 
454  /// How the allocator is propagated on copy assignment
456 
457  /// How the allocator is propagated on move assignment
459 
460  /// How the allocator is propagated on swap
462 
463  /// Whether all instances of the allocator type compare equal.
465 
466  template<typename _Up>
468 
469  template<typename _Up>
471 
472  /**
473  * @brief Allocate memory.
474  * @param __a An allocator.
475  * @param __n The number of objects to allocate space for.
476  *
477  * Calls @c a.allocate(n)
478  */
479  [[__nodiscard__,__gnu__::__always_inline__]]
480  static _GLIBCXX20_CONSTEXPR pointer
482  { return __a.allocate(__n); }
483 
484  /**
485  * @brief Allocate memory.
486  * @param __a An allocator.
487  * @param __n The number of objects to allocate space for.
488  * @param __hint Aid to locality.
489  * @return Memory of suitable size and alignment for @a n objects
490  * of type @c value_type
491  *
492  * Returns <tt> a.allocate(n, hint) </tt>
493  */
494  [[__nodiscard__,__gnu__::__always_inline__]]
495  static _GLIBCXX20_CONSTEXPR pointer
497  {
498 #if __cplusplus <= 201703L
499  return __a.allocate(__n, __hint);
500 #else
501  return __a.allocate(__n);
502 #endif
503  }
504 
505  /**
506  * @brief Deallocate memory.
507  * @param __a An allocator.
508  * @param __p Pointer to the memory to deallocate.
509  * @param __n The number of objects space was allocated for.
510  *
511  * Calls <tt> a.deallocate(p, n) </tt>
512  */
513  [[__gnu__::__always_inline__]]
514  static _GLIBCXX20_CONSTEXPR void
516  { __a.deallocate(__p, __n); }
517 
518  /**
519  * @brief Construct an object of type `_Up`
520  * @param __a An allocator.
521  * @param __p Pointer to memory of suitable size and alignment for
522  * an object of type `_Up`.
523  * @param __args Constructor arguments.
524  *
525  * Calls `__a.construct(__p, std::forward<_Args>(__args)...)`
526  * in C++11, C++14 and C++17. Changed in C++20 to call
527  * `std::construct_at(__p, std::forward<_Args>(__args)...)` instead.
528  */
529  template<typename _Up, typename... _Args>
530  [[__gnu__::__always_inline__]]
531  static _GLIBCXX20_CONSTEXPR void
532  construct(allocator_type& __a __attribute__((__unused__)), _Up* __p,
533  _Args&&... __args)
535  {
536 #if __cplusplus <= 201703L
537  __a.construct(__p, std::forward<_Args>(__args)...);
538 #else
539  std::construct_at(__p, std::forward<_Args>(__args)...);
540 #endif
541  }
542 
543  /**
544  * @brief Destroy an object of type @a _Up
545  * @param __a An allocator.
546  * @param __p Pointer to the object to destroy
547  *
548  * Calls @c __a.destroy(__p).
549  */
550  template<typename _Up>
551  [[__gnu__::__always_inline__]]
552  static _GLIBCXX20_CONSTEXPR void
553  destroy(allocator_type& __a __attribute__((__unused__)), _Up* __p)
555  {
556 #if __cplusplus <= 201703L
557  __a.destroy(__p);
558 #else
559  std::destroy_at(__p);
560 #endif
561  }
562 
563  /**
564  * @brief The maximum supported allocation size
565  * @param __a An allocator.
566  * @return @c __a.max_size()
567  */
568  [[__gnu__::__always_inline__]]
569  static _GLIBCXX20_CONSTEXPR size_type
570  max_size(const allocator_type& __a __attribute__((__unused__))) noexcept
571  {
572 #if __cplusplus <= 201703L
573  return __a.max_size();
574 #else
575  return size_t(-1) / sizeof(value_type);
576 #endif
577  }
578 
579  /**
580  * @brief Obtain an allocator to use when copying a container.
581  * @param __rhs An allocator.
582  * @return @c __rhs
583  */
584  [[__gnu__::__always_inline__]]
585  static _GLIBCXX20_CONSTEXPR allocator_type
587  { return __rhs; }
588  };
589 
590  /// Explicit specialization for std::allocator<void>.
591  template<>
593  {
594  /// The allocator type
596 
597  /// The allocated type
598  using value_type = void;
599 
600  /// The allocator's pointer type.
601  using pointer = void*;
602 
603  /// The allocator's const pointer type.
604  using const_pointer = const void*;
605 
606  /// The allocator's void pointer type.
607  using void_pointer = void*;
608 
609  /// The allocator's const void pointer type.
610  using const_void_pointer = const void*;
611 
612  /// The allocator's difference type
613  using difference_type = std::ptrdiff_t;
614 
615  /// The allocator's size type
616  using size_type = std::size_t;
617 
618  /// How the allocator is propagated on copy assignment
620 
621  /// How the allocator is propagated on move assignment
623 
624  /// How the allocator is propagated on swap
626 
627  /// Whether all instances of the allocator type compare equal.
629 
630  template<typename _Up>
632 
633  template<typename _Up>
635 
636  /// allocate is ill-formed for allocator<void>
637  static void*
638  allocate(allocator_type&, size_type, const void* = nullptr) = delete;
639 
640  /// deallocate is ill-formed for allocator<void>
641  static void
642  deallocate(allocator_type&, void*, size_type) = delete;
643 
644  /**
645  * @brief Construct an object of type `_Up`
646  * @param __a An allocator.
647  * @param __p Pointer to memory of suitable size and alignment for
648  * an object of type `_Up`.
649  * @param __args Constructor arguments.
650  *
651  * Calls `__a.construct(__p, std::forward<_Args>(__args)...)`
652  * in C++11, C++14 and C++17. Changed in C++20 to call
653  * `std::construct_at(__p, std::forward<_Args>(__args)...)` instead.
654  */
655  template<typename _Up, typename... _Args>
656  [[__gnu__::__always_inline__]]
657  static _GLIBCXX20_CONSTEXPR void
658  construct(allocator_type&, _Up* __p, _Args&&... __args)
660  { std::_Construct(__p, std::forward<_Args>(__args)...); }
661 
662  /**
663  * @brief Destroy an object of type `_Up`
664  * @param __a An allocator.
665  * @param __p Pointer to the object to destroy
666  *
667  * Invokes the destructor for `*__p`.
668  */
669  template<typename _Up>
670  [[__gnu__::__always_inline__]]
671  static _GLIBCXX20_CONSTEXPR void
674  { std::_Destroy(__p); }
675 
676  /// max_size is ill-formed for allocator<void>
677  static size_type
678  max_size(const allocator_type&) = delete;
679 
680  /**
681  * @brief Obtain an allocator to use when copying a container.
682  * @param __rhs An allocator.
683  * @return `__rhs`
684  */
685  [[__gnu__::__always_inline__]]
686  static _GLIBCXX20_CONSTEXPR allocator_type
688  { return __rhs; }
689  };
690 #endif
691 
692  /// @cond undocumented
693 #if __cplusplus < 201703L
694  template<typename _Alloc>
695  [[__gnu__::__always_inline__]]
696  inline void
697  __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
698  { __one = __two; }
699 
700  template<typename _Alloc>
701  [[__gnu__::__always_inline__]]
702  inline void
703  __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
704  { }
705 #endif
706 
707  template<typename _Alloc>
708  [[__gnu__::__always_inline__]]
709  _GLIBCXX14_CONSTEXPR inline void
710  __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
711  {
712  using __traits = allocator_traits<_Alloc>;
713  using __pocca =
714  typename __traits::propagate_on_container_copy_assignment::type;
715 #if __cplusplus >= 201703L
716  if constexpr (__pocca::value)
717  __one = __two;
718 #else
719  __do_alloc_on_copy(__one, __two, __pocca());
720 #endif
721  }
722 
723  template<typename _Alloc>
724  [[__gnu__::__always_inline__]]
725  constexpr _Alloc
726  __alloc_on_copy(const _Alloc& __a)
727  {
728  typedef allocator_traits<_Alloc> __traits;
729  return __traits::select_on_container_copy_construction(__a);
730  }
731 
732 #if __cplusplus < 201703L
733  template<typename _Alloc>
734  [[__gnu__::__always_inline__]]
735  inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
736  { __one = std::move(__two); }
737 
738  template<typename _Alloc>
739  [[__gnu__::__always_inline__]]
740  inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
741  { }
742 #endif
743 
744  template<typename _Alloc>
745  [[__gnu__::__always_inline__]]
746  _GLIBCXX14_CONSTEXPR inline void
747  __alloc_on_move(_Alloc& __one, _Alloc& __two)
748  {
749  using __traits = allocator_traits<_Alloc>;
750  using __pocma
751  = typename __traits::propagate_on_container_move_assignment::type;
752 #if __cplusplus >= 201703L
753  if constexpr (__pocma::value)
754  __one = std::move(__two);
755 #else
756  __do_alloc_on_move(__one, __two, __pocma());
757 #endif
758  }
759 
760 #if __cplusplus < 201703L
761  template<typename _Alloc>
762  [[__gnu__::__always_inline__]]
763  inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
764  {
765  using std::swap;
766  swap(__one, __two);
767  }
768 
769  template<typename _Alloc>
770  [[__gnu__::__always_inline__]]
771  inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
772  { }
773 #endif
774 
775  template<typename _Alloc>
776  [[__gnu__::__always_inline__]]
777  _GLIBCXX14_CONSTEXPR inline void
778  __alloc_on_swap(_Alloc& __one, _Alloc& __two)
779  {
780  using __traits = allocator_traits<_Alloc>;
781  using __pocs = typename __traits::propagate_on_container_swap::type;
782 #if __cplusplus >= 201703L
783  if constexpr (__pocs::value)
784  {
785  using std::swap;
786  swap(__one, __two);
787  }
788 #else
789  __do_alloc_on_swap(__one, __two, __pocs());
790 #endif
791  }
792 
793  template<typename _Alloc, typename _Tp,
794  typename _ValueT = __remove_cvref_t<typename _Alloc::value_type>,
795  typename = void>
796  struct __is_alloc_insertable_impl
797  : false_type
798  { };
799 
800  template<typename _Alloc, typename _Tp, typename _ValueT>
801  struct __is_alloc_insertable_impl<_Alloc, _Tp, _ValueT,
802  __void_t<decltype(allocator_traits<_Alloc>::construct(
803  std::declval<_Alloc&>(), std::declval<_ValueT*>(),
804  std::declval<_Tp>()))>>
805  : true_type
806  { };
807 
808  // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
809  // (might be wrong if _Alloc::construct exists but is not constrained,
810  // i.e. actually trying to use it would still be invalid. Use with caution.)
811  template<typename _Alloc>
812  struct __is_copy_insertable
813  : __is_alloc_insertable_impl<_Alloc,
814  typename _Alloc::value_type const&>::type
815  { };
816 
817 #if _GLIBCXX_HOSTED
818  // std::allocator<_Tp> just requires CopyConstructible
819  template<typename _Tp>
820  struct __is_copy_insertable<allocator<_Tp>>
821  : is_copy_constructible<_Tp>
822  { };
823 #endif
824 
825  // true if _Alloc::value_type is MoveInsertable into containers using _Alloc
826  // (might be wrong if _Alloc::construct exists but is not constrained,
827  // i.e. actually trying to use it would still be invalid. Use with caution.)
828  template<typename _Alloc>
829  struct __is_move_insertable
830  : __is_alloc_insertable_impl<_Alloc, typename _Alloc::value_type>::type
831  { };
832 
833 #if _GLIBCXX_HOSTED
834  // std::allocator<_Tp> just requires MoveConstructible
835  template<typename _Tp>
836  struct __is_move_insertable<allocator<_Tp>>
837  : is_move_constructible<_Tp>
838  { };
839 #endif
840 
841  // Trait to detect Allocator-like types.
842  template<typename _Alloc, typename = void>
843  struct __is_allocator : false_type { };
844 
845  template<typename _Alloc>
846  struct __is_allocator<_Alloc,
847  __void_t<typename _Alloc::value_type,
848  decltype(std::declval<_Alloc&>().allocate(size_t{}))>>
849  : true_type { };
850 
851  template<typename _Alloc>
852  using _RequireAllocator
853  = typename enable_if<__is_allocator<_Alloc>::value, _Alloc>::type;
854 
855  template<typename _Alloc>
856  using _RequireNotAllocator
857  = typename enable_if<!__is_allocator<_Alloc>::value, _Alloc>::type;
858 
859 #if __cpp_concepts >= 201907L
860  template<typename _Alloc>
861  concept __allocator_like = requires (_Alloc& __a) {
862  typename _Alloc::value_type;
863  __a.deallocate(__a.allocate(1u), 1u);
864  };
865 #endif
866  /// @endcond
867 #endif // C++11
868 
869  /// @cond undocumented
870 
871  // To implement Option 3 of DR 431.
872  template<typename _Alloc, bool = __is_empty(_Alloc)>
873  struct __alloc_swap
874  { static void _S_do_it(_Alloc&, _Alloc&) _GLIBCXX_NOEXCEPT { } };
875 
876  template<typename _Alloc>
877  struct __alloc_swap<_Alloc, false>
878  {
879  static void
880  _S_do_it(_Alloc& __one, _Alloc& __two) _GLIBCXX_NOEXCEPT
881  {
882  // Precondition: swappable allocators.
883  if (__one != __two)
884  swap(__one, __two);
885  }
886  };
887 
888 #if __cplusplus >= 201103L
889  template<typename _Tp, bool
890  = __or_<is_copy_constructible<typename _Tp::value_type>,
891  is_nothrow_move_constructible<typename _Tp::value_type>>::value>
892  struct __shrink_to_fit_aux
893  { static bool _S_do_it(_Tp&) noexcept { return false; } };
894 
895  template<typename _Tp>
896  struct __shrink_to_fit_aux<_Tp, true>
897  {
898  _GLIBCXX20_CONSTEXPR
899  static bool
900  _S_do_it(_Tp& __c) noexcept
901  {
902 #if __cpp_exceptions
903  try
904  {
905  _Tp(__make_move_if_noexcept_iterator(__c.begin()),
906  __make_move_if_noexcept_iterator(__c.end()),
907  __c.get_allocator()).swap(__c);
908  return true;
909  }
910  catch(...)
911  { return false; }
912 #else
913  return false;
914 #endif
915  }
916  };
917 #endif
918 
919  /**
920  * Destroy a range of objects using the supplied allocator. For
921  * non-default allocators we do not optimize away invocation of
922  * destroy() even if _Tp has a trivial destructor.
923  */
924 
925  template<typename _ForwardIterator, typename _Allocator>
926  _GLIBCXX20_CONSTEXPR
927  void
928  _Destroy(_ForwardIterator __first, _ForwardIterator __last,
929  _Allocator& __alloc)
930  {
931  for (; __first != __last; ++__first)
932 #if __cplusplus < 201103L
933  __alloc.destroy(std::__addressof(*__first));
934 #else
936  std::__addressof(*__first));
937 #endif
938  }
939 
940 #if _GLIBCXX_HOSTED
941  template<typename _ForwardIterator, typename _Tp>
942  __attribute__((__always_inline__)) _GLIBCXX20_CONSTEXPR
943  inline void
944  _Destroy(_ForwardIterator __first, _ForwardIterator __last,
945  allocator<_Tp>&)
946  {
947  _Destroy(__first, __last);
948  }
949 #endif
950  /// @endcond
951 
952 _GLIBCXX_END_NAMESPACE_VERSION
953 } // namespace std
954 #endif // _ALLOC_TRAITS_H
std::allocator_traits< allocator< _Tp > >::allocate
static constexpr pointer allocate(allocator_type &__a, size_type __n)
Allocate memory.
Definition: bits/alloc_traits.h:481
std::allocator_traits< allocator< _Tp > >::max_size
static constexpr size_type max_size(const allocator_type &__a) noexcept
The maximum supported allocation size.
Definition: bits/alloc_traits.h:570
std::allocator_traits::construct
static constexpr auto construct(_Alloc &__a, _Tp *__p, _Args &&... __args) noexcept(noexcept(_S_construct(__a, __p, std::forward< _Args >(__args)...))) -> decltype(_S_construct(__a, __p, std::forward< _Args >(__args)...))
Construct an object of type _Tp
Definition: bits/alloc_traits.h:375
std::allocator_traits< allocator< void > >::destroy
static constexpr void destroy(allocator_type &, _Up *__p) noexcept(is_nothrow_destructible< _Up >::value)
Destroy an object of type _Up
Definition: bits/alloc_traits.h:672
std::allocator_traits< allocator< _Tp > >::allocate
static constexpr pointer allocate(allocator_type &__a, size_type __n, const_void_pointer __hint)
Allocate memory.
Definition: bits/alloc_traits.h:496
std::allocator_traits< _Tp_alloc_type >::pointer
__detected_or_t< value_type *, __pointer, _Tp_alloc_type > pointer
The allocator's pointer type.
Definition: bits/alloc_traits.h:117
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:51
std::allocator_traits::difference_type
typename _Diff< _Alloc, pointer >::type difference_type
The allocator's difference type.
Definition: bits/alloc_traits.h:181
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:130
std::allocator_traits< _Tp_alloc_type >::const_pointer
typename _Ptr< __c_pointer, const value_type >::type const_pointer
The allocator's const pointer type.
Definition: bits/alloc_traits.h:157
std::allocator_traits< allocator< _Tp > >::void_pointer
void * void_pointer
The allocator's void pointer type.
Definition: bits/alloc_traits.h:443
std::allocator_traits< allocator< _Tp > >::select_on_container_copy_construction
static constexpr allocator_type select_on_container_copy_construction(const allocator_type &__rhs)
Obtain an allocator to use when copying a container.
Definition: bits/alloc_traits.h:586
std::allocator_traits::allocator_type
_Alloc allocator_type
The allocator type.
Definition: bits/alloc_traits.h:108
std::allocator_traits< _Tp_alloc_type >::const_void_pointer
typename _Ptr< __cv_pointer, const void >::type const_void_pointer
The allocator's const void pointer type.
Definition: bits/alloc_traits.h:173
std::allocator_traits< allocator< _Tp > >::difference_type
std::ptrdiff_t difference_type
The allocator's difference type.
Definition: bits/alloc_traits.h:449
std::allocator_traits::max_size
static constexpr size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.
Definition: bits/alloc_traits.h:404
std::allocator< void >
Definition: allocator.h:75
std::allocator_traits< allocator< void > >::select_on_container_copy_construction
static constexpr allocator_type select_on_container_copy_construction(const allocator_type &__rhs)
Obtain an allocator to use when copying a container.
Definition: bits/alloc_traits.h:687
std::is_nothrow_constructible
is_nothrow_constructible
Definition: type_traits:1113
std::allocator_traits< allocator< _Tp > >::construct
static constexpr void construct(allocator_type &__a, _Up *__p, _Args &&... __args) noexcept(std::is_nothrow_constructible< _Up, _Args... >::value)
Construct an object of type _Up
Definition: bits/alloc_traits.h:532
std::allocator_traits< allocator< void > >::pointer
void * pointer
The allocator's pointer type.
Definition: bits/alloc_traits.h:601
numeric_traits.h
std::true_type
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:82
std::allocator_traits< allocator< _Tp > >::size_type
std::size_t size_type
The allocator's size type.
Definition: bits/alloc_traits.h:452
std::pointer_traits
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:184
std::allocator_traits::allocate
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
Definition: bits/alloc_traits.h:332
std::allocator_traits::deallocate
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
Definition: bits/alloc_traits.h:359
std::allocator_traits< allocator< void > >::difference_type
std::ptrdiff_t difference_type
The allocator's difference type.
Definition: bits/alloc_traits.h:613
std::allocator_traits< allocator< _Tp > >::pointer
_Tp * pointer
The allocator's pointer type.
Definition: bits/alloc_traits.h:437
std::allocator_traits< _Tp_alloc_type >::propagate_on_container_swap
__detected_or_t< false_type, __pocs, _Tp_alloc_type > propagate_on_container_swap
How the allocator is propagated on swap.
Definition: bits/alloc_traits.h:216
memoryfwd.h
std::allocator_traits< allocator< void > >::size_type
std::size_t size_type
The allocator's size type.
Definition: bits/alloc_traits.h:616
std::allocator_traits< allocator< void > >::construct
static constexpr void construct(allocator_type &, _Up *__p, _Args &&... __args) noexcept(std::is_nothrow_constructible< _Up, _Args... >::value)
Construct an object of type _Up
Definition: bits/alloc_traits.h:658
std::allocator_traits< allocator< _Tp > >::destroy
static constexpr void destroy(allocator_type &__a, _Up *__p) noexcept(is_nothrow_destructible< _Up >::value)
Destroy an object of type _Up.
Definition: bits/alloc_traits.h:553
std::allocator_traits< allocator< void > >::value_type
void value_type
The allocated type.
Definition: bits/alloc_traits.h:598
std::_Construct
constexpr void _Construct(_Tp *__p, _Args &&... __args)
Definition: stl_construct.h:109
std::integral_constant
integral_constant
Definition: type_traits:62
allocator.h
std::allocator_traits< allocator< _Tp > >::allocator_type
allocator< _Tp > allocator_type
The allocator type.
Definition: bits/alloc_traits.h:431
std::allocator_traits< allocator< _Tp > >::const_pointer
const _Tp * const_pointer
The allocator's const pointer type.
Definition: bits/alloc_traits.h:440
std::allocator_traits< _Tp_alloc_type >::void_pointer
typename _Ptr< __v_pointer, void >::type void_pointer
The allocator's void pointer type.
Definition: bits/alloc_traits.h:165
std::allocator_traits::value_type
_Alloc::value_type value_type
The allocated type.
Definition: bits/alloc_traits.h:110
std::allocator_traits< _Tp_alloc_type >::propagate_on_container_copy_assignment
__detected_or_t< false_type, __pocca, _Tp_alloc_type > propagate_on_container_copy_assignment
How the allocator is propagated on copy assignment.
Definition: bits/alloc_traits.h:198
std::is_nothrow_destructible
is_nothrow_destructible
Definition: type_traits:1030
std::allocator_traits< allocator< void > >::const_void_pointer
const void * const_void_pointer
The allocator's const void pointer type.
Definition: bits/alloc_traits.h:610
std::false_type
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:85
std::allocator_traits< allocator< void > >::const_pointer
const void * const_pointer
The allocator's const pointer type.
Definition: bits/alloc_traits.h:604
std::_Destroy
constexpr void _Destroy(_ForwardIterator __first, _ForwardIterator __last)
Definition: stl_construct.h:182
std::allocator_traits::destroy
static constexpr void destroy(_Alloc &__a, _Tp *__p) noexcept(noexcept(_S_destroy(__a, __p, 0)))
Destroy an object of type _Tp.
Definition: bits/alloc_traits.h:391
std
ISO C++ entities toplevel namespace is std.
std::allocator_traits
Uniform interface to all allocator types.
Definition: bits/alloc_traits.h:105
std::allocator_traits< allocator< _Tp > >::value_type
_Tp value_type
The allocated type.
Definition: bits/alloc_traits.h:434
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:97
std::allocator_traits::select_on_container_copy_construction
static constexpr _Alloc select_on_container_copy_construction(const _Alloc &__rhs)
Obtain an allocator to use when copying a container.
Definition: bits/alloc_traits.h:416
std::allocator_traits< allocator< _Tp > >::deallocate
static constexpr void deallocate(allocator_type &__a, pointer __p, size_type __n)
Deallocate memory.
Definition: bits/alloc_traits.h:515
ptr_traits.h
std::allocator_traits< allocator< _Tp > >::const_void_pointer
const void * const_void_pointer
The allocator's const void pointer type.
Definition: bits/alloc_traits.h:446
std::allocator_traits< allocator< void > >::void_pointer
void * void_pointer
The allocator's void pointer type.
Definition: bits/alloc_traits.h:607
std::allocator_traits< _Tp_alloc_type >::propagate_on_container_move_assignment
__detected_or_t< false_type, __pocma, _Tp_alloc_type > propagate_on_container_move_assignment
How the allocator is propagated on move assignment.
Definition: bits/alloc_traits.h:207
stl_construct.h
std::allocator_traits< _Tp_alloc_type >::is_always_equal
typename __detected_or_t< is_empty< _Tp_alloc_type >, __equal, _Tp_alloc_type >::type is_always_equal
Whether all instances of the allocator type compare equal.
Definition: bits/alloc_traits.h:225
std::allocator_traits::size_type
typename _Size< _Alloc, difference_type >::type size_type
The allocator's size type.
Definition: bits/alloc_traits.h:189