Doc. no. P0177R2
Date: 2016-03-21
Project: Programming Language C++
Audience: Library Evolution Working Group
Reply to: Alisdair Meredith <>

Cleaning up allocator_traits

Table of Contents

  1. Revision History
  2. Introduction
  3. Problems with allocator_traits>
  4. Ideas not Pursued
  5. Drive-by Fixes
  6. Library Evolution Review
  7. Proposed Wording
  8. Acknowledgements
  9. References

Revision History

Revision 0

Original version of the paper for the 2016 pre-Jacksonville mailing.

Revision 1

Update reviewed at the Jacksonville 2016 meeting.

Revision 2

Update for the 2016 post-Jacksonville mailing.


The C++11 standard introduced allocator_traits with great flexibility as a way to generically customize allocator behavior. With experience, we have learned that some of this generality comes at great cost, but little benefit. This paper proposed cleaning up the wilder corners of the traits behavior.

Problems with allocator_traits

The addition of allocator_traits to C++11 brought relatively simple support for a wide variety of allocator models to the C++ standard library. It provides a consistent interface for containers and other types that require memory allocation services to be customized non-intrusively by their users. This traits template is deliberately designed to be flexible to support a wide variety of allocator models, as described in paper P0176R0. However, not all of that generality is useful, and some creates needless complexity when implementing types that use allocators.

Consistency of propagation traits

One of the important customizations for stateful allocators is the ability to control the propagation of allocators, that is, to control which allocator is used after an assignment operator, or a swap operation. When all allocators of the same type are interchangable, and so always compare equal, these traits have little value. If all allocator objects are interchangable, then the only effect of propagation is potentially making a few more assignment or swaps. However, when allocators have state that affects allocation behavior, this can become critically important.

The first model, that drives the current default behavior that allocators do not propagate, is that all subcomponents of a data structure should use the same allocator. For example, a container would pass its own allocator down to its elements, and they in turn would pass that allocator down to their bases and members. Once this invariant is established, we do not want to lose it by swapping with elements for elsewhere that use a different allocator, or change allocator when assigned-to from an external source. This allows us to reason about the lifetime of the allocator and the data structure, see P0176R0 for further details.

A second model is that the allocator move with the allocated memory, so every move-assignment and swap should propgate the allocator to maintain a non-throwing wide contract, and not risk an allocation or undefined behavior when the allocators do not match, but without any guarantee that a given data structure will have a consistent allocation strategy using such allocators.

There is no clear model that benefits from requiring container implementations to support allocators that propagate on move assignemnt, but not on swap (or vice-versa). The cost in terms of complexity this burdens container implementers with is considerable, and every operation involving another object that uses the same allocator famuily must document whether any potentially moving operation explicitly in terms whether it uses move-assignment, swap, or both. Use of an undocumented operation would result in a surprising allocator propagation which is distinctly observable.

The issue with copy-assignment is a little more subtle, but for a type that provides a copy-assignment operator but no move- assignment operator, then, when move-assignment is requested, the copy-assignment operator will be called. If the propagation traits of the user-supplied allocator differ, then problems will follow.

The proposed solution of this paper is to require that all three propagation traits be equivalent, and change the type-computation in the trait to simply delegate to a preferred trait. Customizing that one trait would change the behavior of all three. Note that this is a breaking change if anyone has successfully made use of diverging these traits, although the author has no experience of such allocators outside of standard conformance suites.

Once we mandate consistency, we could go further and deprecate the two names that are simply aliases of the first. Similarly, we would update all standard wording that references the two deprecated traits to use the one remaining propagation trait instead. Ideally, we would have a new trait with a simpler name, but that would break all existing code where users have correctly customized the existing traits (consistently). Therefore, as we must pick one of the three existing names, we will pick the one that is shorter to type, as these names are infamously long when used (typically seen only by users implementing their own custom containers).

Inconsistent propagation traits are hard to deal with

This is the other side to 2.1, highlighting the burden on library implementers to handle inconsistent propagation traits. First, as we have three independant binary traits, that is 23 combinations of different behavior that must be tested, just for the allocator parameter of any container. These traits can have a subtle impact on many operations. As an example, consider the copy-assignment operator for vector. This has the strong exception safety guarantee, so we would like to use the copy and swap idiom, but how does that work if the propagation traits are different for copy-assignment and swap? Here is a sample implementation, relying on compiler optimizations to eliminate the dead branches (as the if expressions all yield a compile-time result).

template <typename T, typename A>
auto vector<T, A>::operator=(vector const& other) -> vector&
   using Traits = allocator_traits<A>

   if (!AT::propagate_on_copy_assignment) {
      vector temp(other, this->get_allocator());
   else if (AT::propagate_on_swap) {
      vector temp(other, other.>get_allocator());
   else if ( AT::propagate_on_copy_assignment && !AT::propagate_on_swap) {
      // This is the really awkward case
      vector temp(::std::move(*this));
      try {
         new(this) vector(other, other.get_allocator());
      catch(...) {
         new(this) vector(::std::move(temp));

   return *this;

As an alternative to the destory/in-place new idiom, the moved-from vector could be cleared, then use a private member function to rebind the allocator, followed by a range-insertion, and reverse the operation in the catch clause (as moving back after rebinding the allocator is a simple pointer operation, and cannot throw).

Note the return of an explicit try/catch block, or its moral equivalent by introducing some other guard class or scopeguard. This is exactly the kind of code construct that the copy/swap idiom is supposed to save us from, preferring to throw freely but catch rarely.

With the changes proposed in this paper, the example becomes a lot simpler (and there are fewer configurations to validate in a test driver):

template <typename T, typename A>
auto vector<T, A>::operator=(vector const& other) -> vector&
   using Traits = allocator_traits<A>
   Allocator alloc = AT::propagate
                   ? other.get_allocator()
                   : this->get_allocator();

   vector temp(other, alloc);

   return *this;

Default for propagation traits


  • LWG #2103 std::allocator_traits<std::allocator<T>>::propagate_on_container_move_assignment
  • LWG #2108 No way to identify allocator types that always compare equal
  • N4258 Cleaning‐up noexcept in the Library, Nicolai Josuttis
  • noexcept Move Operations

    Two of the key operations of a container are its move-assignment operator and its swap overload. While it is important that these are efficient, it is also important that callers can observe whether they have the no-throw guarantee, or if they need to code defensively around these operations. Nicolai Jossutis made an important contribution earlier in the C++17 process, introducing the is_always_equal predicate to identify the case where allocators that do not propagate can still give the no-throw guarantee for their container's operations. Unfortunately, this makes the signature of these key operations appear much more complex than necessary. This is also very visible in the specification, as these are the important operations that will be advertized frequently. Worse, we expect implementers of their own containers to duplicate this logic and spelling in their own implementations of these functions.

    This paper proposes adding a new constexpr variable template with a simpler spelling in the std namespace, that should also be clearer to read in the specification of the critical operations. Finding a good name, that is simple, short, and precise, is difficult. The initially suggest name is propagate_may_throw_v, although it is expected that the Library Evolution Working Group will brainstorm something better.

    In addition to basic_string and vector, there are several other containers that provide a no-throw guarantee when the allocators guarantee to compare equal, should we use this new propagate_may_throw_v exception-specification there as well? While the consistency is appealing, it would also break some existing implementations, as mentioned in Nico's paper.

    The key to the issue is that, even if allocators can propagate on move-assignment, we expect them to propagate in only one direction. For containers that need a sentry node to maintain their invariants, a new sentry must be allocated with the moved allocator, which might throw. This should not be an issue for swap operations though, as allocators are expected to be exchanged, along with two data structures that satisfy the invariants. A second issue arises for containers that hold predicates or other function objects in addition to the stored elements, as even though a swap may not need to allocate, the functor objects may throw on move/swap. This limits our scope to make changes, although it looks like deque::swap should take advantage.

    Ideas not Pursued

    There were a few additional ideas that occurred during the writing of this paper that the author ultimately rejected.

    Introduce a new name for the propagation trait

    Retaining a single propagation trait with the term swap as part of its name is not ideal, as it suggests the original, more specific meaning of the trait. This could be resolved by having a single propagate_allocator trait, possible as a free-standing variable template, propagate_allocator_v. Its default value could be computed in some way from the existing three (deprecated) legacy traits, in an attempt to provide some backwards-compatiblity scheme for existing allocators. Alternatively, the three deprecated traits in allocator_traits could simply check this value, supporting existing container implementations (which are likely to be more numerous).

    Ultimately this idea was rejected as being too big a change, providing a much more awkward period of transition. Generally, a feature is not simplified by adding more redundant names for the existing behavior.

    However, a new propagate_may_throw_v trait is proposed, that simplifies the frequent combination of checking for an allocator that either propagates, or for which comparison is_alwaty_true. This case is encountered frequently enough in the standard that it should be simplified.

    Drive-by Fixes

    The Library Active Issues Lists was consulted for any allocator related issues that might be resolved as part of this clean-up exercise. In addition to issues directly addressing allocators, a few issues addressing class definitions that would be partially addressed by fixing allocator support were, instead, fully addressed to avoid confusion with multple resolutions interacting on the same wording.

    Tidying the Allocator Requirements Table

    The allocator requirements table in clause 17 is long, so long that it spreads over three pages of the standard. It is also complex with a lot of small identifiers used to simplify the specification, and there are so many of these that they have their own table in advance of the allocator requirements table that is the key to that table. Unfortunately, the spelling of the short identifiers is not always obvious, which necessitates srolling up and down a few pages, every time the reader wants to clarify their understanding. Worse, in some cases it is outright missleading, where X is the type of an allocator, but x is an object of a pointer type, not an allocator. Instead, and allocator of type X is spelled a. This paper proposes a more intuitive set of spellings that are similarly terse, but will give the reader an intuition they can trust without scrolling back to the table key each time. This becomes consistent with the allocator-aware containre requirement tables, where X denotes a container using allocator-type A, reducing confusion when switching between tables. Note that the container requirements still use a as the name of a container object, rather than allocator object, so additional clean-up in the container tables may be useful.

    Old name New name Meaning
    X A an Allocator class for type T
    Y B the corresponding Allocator class for type U
    XX AT the type allocator_traits<A>
    YY BT the type allocator_traits<B>
    p p No change: a value of type AT::pointer, obtained by calling a1.allocate, where a1 == a
    q cp a value of type AT::const_pointer obtained by conversion from a value p
    w vp a value of type AT::void_pointer obtained by conversion from a value p
    x cvp a value of type AT::const_void_pointer obtained by conversion from a value cp or a value vp
    y cvq a value of type AT::const_void_pointer obtained by conversion from a result value of BT::allocate, or else a value of type (possibly const) std::nullptr_t

    Secondly, around half of the entries in the allocator requirements table are optional, denoted by the presence of the Defaults column. However, most operations are specified directly in terms of the allocator member, when really they should be specified in terms of the default, which is obtained through allocator_traits. There would be a risk of a circular definition if the specification of allocator_traits were in terms of this table, but that is not the case. The specifcation for allocator_traits gives a formula for the default in each case without (normatively) referring back to the allocator requirements table. This paper substitues the allocator_traits name for every optional property that is used in the specification of dependent requirements.

    Annex C was not updated for C++11

  • LWG #2178 Annex C update for C++11 on allocators

    Regex match_results does not use noexcept

  • LWG #2183 regex match_results missing allocator-aware ctors
  • LWG #2184 regex match_results assigment and allocator propagation

    Regex match_results does not use noexcept

  • LWG #2490 <regex> needs lots of noexcept Note that this issue is not fully addressed by this paper, but only one class.

    vector<bool> does not use noexcept

    The vector<bool> specialization doea not have the allocator-specific noexcept specifications of the primary template. This appears to have been a simple oversight, each time the exception specifications were revised.

    Library Evolution Review

    The initial review liked the idea of clean-up in general, removing un-necessary freedoms, and more consistent naming of terms across the tables. Concerns were raised that at least some present in the discussion were already supporting customers using allocator models with propagation traits that were not uniformly true or false, so that aspect of the proposal was dropped. Otherwise, there was support for it to proceed to LWG for C++17.

    Subsequent discussion showed continued interest in simplifying the propagation traits, but there would not be time to discuss it further in the C++17 schedule. That aspect of the proposal may come back for a future standard.


    Require specializations of allocator_traits to match allocator members?

    SF F N A SA
    4 7 1 0 0

    Require allocator pointer type members to be related through pointer traits?

    SF F N A SA
    3 5 3 0 0

    Forward these parts of P0177 to LWG for the IS?

    SF F N A SA
    6 4 0 0 0

    Do we want to see a separate, new paper on propagation traits?

    SF F N A SA
    3 7 1 0 0

    Proposed Wording

    Amend existing library clauses as below: Allocator requirements [allocator.requirements]

    1. The library describes a standard set of requirements for allocators, which are class-type objects that encapsulate the information about an allocation model. This information includes the knowledge of pointer types, the type of their difference, the type of the size of objects in this allocation model, as well as the memory allocation and deallocation primitives for it. All of the string types (Clause 21), containers (Clause 23) (except array), string buffers and string streams (Clause 27), and match_results (Clause 28) are parameterized in terms of allocators.
    2. The class template allocator_traits (20.7.8) supplies a uniform interface to all allocator types. Table 27 describes the types manipulated through allocators. Table 28 describes the requirements on allocator types and thus on types used to instantiate allocator_traits. A requirement is optional if the last column of Table 28 specifies a default for a given expression. Within the standard library allocator_traits template, an optional requirement that is not supplied by an allocator is replaced by the specified default expression. A user specialization of allocator_traits may provide different defaults and may provide defaults for different requirements than the primary template. Within Tables 27 and 28, the use of move and forward always refers to std::move and std::forward, respectively.
    3. Table 27 — Descriptive variable definitions
      Variable Definition
      T, U, C any cv-unqualified object type (3.9)
      XA an Allocator class for type T
      YB the corresponding Allocator class for type U
      XXAT the type allocator_traits<AX>
      YYBT the type allocator_traits<BY>
      a, a1, a2 lvalues of type AX
      u the name of a variable being declared
      b a value of type BY
      c* a pointer of type C* through which indirection is valid
      p a value of type XXAT::pointer, obtained by calling a1.allocate, where a1 == a
      qcp a value of type XXAT::const_pointer obtained by conversion from a value p.
      wvp a value of type XXAT::void_pointer obtained by conversion from a value p
      xcvp a value of type XXAT::const_void_pointer obtained by conversion from a value qcp or a value wvp
      ycvq a value of type XXAT:const_void_pointer obtained by conversion from a result value of YYBT::allocate, or else a value of type (possibly const) std::nullptr_t.
      n a value of type XXAT::size_type.
      Args a template parameter pack
      args a function parameter pack with the pattern Args&&
      Table 28 — Allocator requirements
      Expression Return type Assertion/note pre-/post-condition Default
      XA::pointer T*
      XAT::const_pointer pointer_traits<AT::pointer>::rebind<const T> XAT::pointer is convertible to XAT::const_pointer pointer_traits<X::pointer>::rebind<const T>
      pointer_traits<AT::pointer>::rebind<void> XAT::pointer is convertible to XAT::void_pointer. XAT::void_pointer and YBT::void_pointer are the same type. pointer_traits<X::pointer>::rebind<void>
      pointer_traits<AT::void_pointer>::rebind<const void> XAT::pointer, XAT::const_pointer, and XAT::void_pointer are convertible to XAT::const_void_pointer. X::const_void_pointer and Y::const_void_pointer are the same type. pointer_traits<X::pointer>::rebind<const void>
      XA::value_type Identical to T
      XA::size_type unsigned integer type make_unsigned_t<AT::difference_type> a type that can represent the size of the largest object in the allocation model. make_unsigned_t<X::difference_type>
      XA::difference_type signed integer type a type that can represent the difference between any two pointers in the allocation model. pointer_traits<XAT::pointer>::difference_type
      typename XA::template rebind<U>::other YB For all U (including T), YB::template rebind<T>::other is XA See Note A, below.
      *p T&
      *qcp const T& *qcp refers to the same object as *p
      p->m type of T::m pre: (*p).m is well-defined. equivalent to (*p).m
      qcp->m type of T::m pre: (*qcp).m is well-defined. equivalent to (*qcp).m
      static_cast<XAT::pointer>(wvp) pointer static_cast<XAT::pointer>(wvp) == p
      static_cast<XAT::const_pointer>(xcvp) const_pointer static_cast<XAT::const_pointer>(xcvp) == p
      a.allocate(n) pointer Memory is allocated for n objects of type T but objects are not constructed. allocate may raise an appropriate exception.180[ Note: If n == 0, the return value is unspecified. — end note ]
      a.allocate(n, ycvq) pointer Same as a.allocate(n). The use of ycvq is unspecified, but it is intended as an aid to locality. a.allocate(n)
      a.deallocate(p,n) (not used) pre: p shall be a value returned by an earlier call to allocate that has not been invalidated by an intervening call to deallocate. n shall match the value passed to allocate to obtain this memory. Throws: Nothing.
      a.max_size() XAT::size_type the largest value that can meaningfully be passed to XA::allocate() numeric_limits<size_type>::max()/sizeof(value_type)
      a1 == a2 bool returns true only if storage allocated from each can be deallocated via the other. operator== shall be reflexive, symmetric, and transitive, and shall not exit via an exception.
      a1 != a2 bool same as !(a1 == a2)
      a == b bool same as a == YBT::rebind_alloc<T>::other(b)
      a != b bool same as !(a == b)
      XA ua1(a);
      XA ua1 = a;
      Shall not exit via an exception. post: a1 == a
      XA ua(b); Shall not exit via an exception. post: YB(a) == b, a == XA(b)
      XA ua1(move(a));
      XA ua1 = move(a);
      Shall not exit via an exception. post: a1 equals the prior value of a.
      XA ua(move(b)); Shall not exit via an exception. post: a equals the prior value of XA(b).
      a.construct(c,args) (not used) Effect: Constructs an object of type C at c ::new ((void*)c) C(forward<Args>(args)...)
      a.destroy(c) (not used) Effect: Destroys the object at c c->~C()
      a.select_on_container_copy_construction() XA Typically returns either a or XA() return a;
      propagate_on_container_copy_assignment Identical to or derived from true_type or false_type true_type only if an allocator of type XA should be copied when the client container is copy-assigned. See Note B, below. false_type
      propagate_on_container_move_assignment Identical to or derived from true_type or false_type true_type only if an allocator of type XA should be moved when the client container is move-assigned. See Note B, below. false_type
      propagate_on_container_swap Identical to or derived from true_type or false_type true_type only if an allocator of type XA should be swapped when the client container is swapped. See Note B, below. false_type
      is_always_equal Identical to or derived from true_type or false_type true_type only if the expression a1 == a2 is guaranteed to be true for any two (possibly const) values a1, a2 of type XA. is_empty<XA>::type
    4. Note A: The member class template rebind in the table above is effectively a typedef template. [ Note: In general, if the name Allocator is bound to SomeAllocator<T>, then Allocator::rebind<U&g;::other is the same type as SomeAllocator<U>, where SomeAllocator<T>::value_type is T and SomeAllocator<U>::value_type is U. — end note ] If Allocator is a class template instantiation of the form SomeAllocator<T, Args>, where Args is zero or more type arguments, and Allocator does not supply a rebind member template, the standard allocator_traits template uses SomeAllocator<U, Args> in place of Allocator::rebind<U>::other by default. For allocator types that are not template instantiations of the above form, no default is provided.
    5. Note B: If X::propagate_on_container_copy_assignment::value is true, X shall satisfy the CopyAssignable requirements (Table 23) and the copy operation shall not throw exceptions. If X::propagate_on_container_move_assignment::value is true, X shall satisfy the MoveAssignable requirements (Table 22) and the move operation shall not throw exceptions. If X::propagate_on_container_swap::value is true, lvalues of type X shall be swappable ( and the swap operation shall not throw exceptions.
    6. An allocator type XA shall satisfy the requirements of CopyConstructible ( The XAT::pointer, XAT::const_pointer, XAT::void_pointer, and XAT::const_void_pointer types shall satisfy the requirements of NullablePointer ( No constructor, comparison operator, copy operation, move operation, or swap operation on these pointer types shall exit via an exception. XAT::pointer and XAT::const_pointer shall also satisfy the requirements for a random access iterator (24.2).
    7. Let x1 and x2 denote objects of (possibly different) types XAT::void_pointer, XAT::const_void_pointer, XAT::pointer, or XAT::const_pointer. Then, x1 and x2 are equivalently-valued pointer values, if and only if both x1 and x2 can be explicitly converted to the two corresponding objects px1 and px2 of type XAT::const_pointer, using a sequence of static_casts using only these four types, and the expression px1 == px2 evaluates to true.
    8. Let w1 and w2 denote objects of type XAT::void_pointer. Then for the expressions
      w1 == w2
      w1 != w2
      either or both objects may be replaced by an equivalently-valued object of type XAT::const_void_pointer with no change in semantics.
    9. Let p1 and p2 denote objects of type XAT::pointer. Then for the expressions
      p1 == p2
      p1 != p2
      p1 < p2
      p1 <= p2
      p1 >= p2
      p1 > p2
      p1 - p2
      either or both objects may be replaced by an equivalently-valued object of type XAT::const_pointer with no change in semantics.
    10. An allocator may constrain the types on which it can be instantiated and the arguments for which its construct or destroy members may be called. If a type cannot be used with a particular allocator, the allocator class or the call to construct or destroy may fail to instantiate. [Example: the following is an allocator class template supporting the minimal interface that satisfies the requirements of Table 28:
      template <class Tp>
      struct SimpleAllocator {
        typedef Tp value_type;
        SimpleAllocator(ctor args);
        template <class T> SimpleAllocator(const SimpleAllocator<T>& other);
        Tp* allocate(std::size_t n);
        void deallocate(Tp* p, std::size_t n);
      template <class T, class U>
      bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&);
      template <class T, class U>
      bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&);
      — end example ]
    11. If the alignment associated with a specific over-aligned type is not supported by an allocator, instantiation of the allocator for that type may fail. The allocator also may silently ignore the requested alignment. [Note: Additionally, the member function allocate for that type may fail by throwing an object of type std::bad_alloc. — end note ] Allocator completeness requirements [allocator.requirements.completeness]

    1. If XA is an allocator class for type T, XA additionally satisfies the allocator completeness requirements if, whether or not T is a complete type:
      1. XA is a complete type, and
      2. all the member types of allocator_traits<XA> 20.7.8 other than value_type are complete types

    20.7.8 Allocator traits [allocator.traits]

    1. The class template allocator_traits supplies a uniform interface to all allocator types. An allocator cannot be a non-class type, however, even if allocator_traits supplies the entire required interface. [ Note: Thus, it is always possible to create a derived class from an allocator. - end note ]
    2. User specializations of allocator_traits are permitted only if they provide exactly the same behavior as an instantiation of the primary template. [ Note: Such specializations might be provided as an aid to the compiler, e.g., where it is simpler to directly provide the specified type aliases than to compute them afresh each time. - end note ]
    namespace std {
      template <class Alloc> struct allocator_traits {
        typedef Alloc allocator_type;
        typedef typename Alloc::value_type value_type;
        typedef see below                                                           pointer;
        typedef see belowtypename pointer_traits<pointer>::rebind<const value_type> const_pointer;
        typedef see belowtypename pointer_traits<pointer>::rebind<void>             void_pointer;
        typedef see belowtypename pointer_traits<pointer>::rebind<const void>       const_void_pointer;
        typedef see below                                 difference_type;
        typedef see belowmake_unsigned_t<difference_type> size_type;
        typedef see below propagate_on_container_copy_assignment;
        typedef see below propagate_on_container_move_assignment;
        typedef see below propagate_on_container_swap;
        typedef see below is_always_equal;
        template <class T> using rebind_alloc = see below;
        template <class T> using rebind_traits = allocator_traits<rebind_alloc<T> >;
        static pointer allocate(Alloc& a, size_type n);
        static pointer allocate(Alloc& a, size_type n, const_void_pointer hint);
        static void deallocate(Alloc& a, pointer p, size_type n);
        template <class T, class... Args>
          static void construct(Alloc& a, T* p, Args&&... args);
        template <class T>
          static void destroy(Alloc& a, T* p);
        static size_type max_size(const Alloc& a) noexcept;
        static Alloc select_on_container_copy_construction(const Alloc& rhs);
 Allocator traits member types [allocator.traits.types]

      typedef see below pointer;
    1. Type: Alloc::pointer if the qualified-id Alloc::pointer is valid and denotes a type (14.8.2); otherwise, value_type*.
    2. typedef see below const_pointer;
    3. Type: Alloc::const_pointer if the qualified-id Alloc::const_pointer is valid and denotes a type (14.8.2); otherwise, pointer_traits<pointer>::rebind<const value_type>.
    4. typedef see below void_pointer;
    5. Type: Alloc::void_pointer if the qualified-id Alloc::void_pointer is valid and denotes a type (14.8.2); otherwise, pointer_traits<pointer>::rebind<void>.
    6. typedef see below const_void_pointer;
    7. Type: Alloc::const_void_pointer if the qualified-id Alloc::const_void_pointer is valid and de- notes a type (14.8.2); otherwise, pointer_traits<pointer>::rebind<const void>.
    8. typedef see below difference_type;
    9. Type: Alloc::difference_type if the qualified-id Alloc::difference_type is valid and denotes a type (14.8.2); otherwise, pointer_traits<pointer>::difference_type.
    10. typedef see below size_type;
    11. Type: Alloc::size_type if the qualified-id Alloc::size_type is valid and denotes a type (14.8.2); otherwise, make_unsigned_t<difference_type>.

    23.2.1 General container requirements [container.requirements.general]

    Table 98 — Allocator-aware container requirements
    Expression Return type Assertion/note pre-/post-condition Complexity
    X u(rv)
    Requires: move construction of A shall not exit via an exception. post: u shall have the same elements as rv had before this construction; the value of u.get_allocator() shall be the same as the value of rv.get_allocator() before this construction. constant
    a = rv X& Requires: If allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is false, T is MoveInsertable into X and MoveAssignable.

    Effects: All existing elements of a are either move assigned to or destroyed.

    post: a shall be equal to the value that rv had before this assignment.


    23.3.7 Class vector<bool> [vector.bool]

    1. To optimize space allocation, a specialization of vector for bool elements is provided:
    2. namespace std {
        template <class Allocator> class vector<bool, Allocator> {
          // construct/copy/destroy:
          vector() noexcept(noexcept(Allocator())) : vector(Allocator()) { }
          explicit vector(const Allocator&) noexcept;
          explicit vector(size_type n, const Allocator& = Allocator());
          vector(size_type n, const bool& value,
                 const Allocator& = Allocator());
          template <class InputIterator>
            vector(InputIterator first, InputIterator last,
                   const Allocator& = Allocator());
          vector(const vector<bool, Allocator>& x);
          vector(vector<bool, Allocator>&& x) noexcept;
          vector(const vector&, const Allocator&);
          vector(vector&&, const Allocator&);
          vector(initializer_list<bool>, const Allocator& = Allocator()));
          vector<bool, Allocator>& operator=(const vector<bool, Allocator>& x);
          vector<bool, Allocator>& operator=(vector<bool, Allocator>&& x)
            noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
          vector& operator=(initializer_list<bool>);
          template <class InputIterator>
            void assign(InputIterator first, InputIterator last);
          void assign(size_type n, const bool& t);
          void assign(initializer_list<bool>);
          allocator_type get_allocator() const noexcept;
          iterator erase(const_iterator position);
          iterator erase(const_iterator first, const_iterator last)
          void swap(vector<bool, Allocator>&)
            noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
          static void swap(reference x, reference y) noexcept;
          void flip() noexcept; // flips all bits
          void clear() noexcept;

      28.10 Class template match_results [re.results]

      namespace std {
        template <class BidirectionalIterator,
                  class Allocator = allocator<sub_match<BidirectionalIterator>>>
        class match_results {
          typedef sub_match<BidirectionalIterator>                     value_type;
          typedef const value_type&                                    const_reference;
          typedef value_type&                                          reference;
          typedef implementation-defined                               const_iterator;
          typedef const_iterator                                       iterator;
          typedef typename
            iterator_traits<BidirectionalIterator>::difference_type    difference_type;
          typedef typename allocator_traits<Allocator>::size_type      size_type;
          typedef Allocator                                            allocator_type;
          typedef typename iterator_traits<BidirectionalIterator>::
            value_type                                                 char_type;
          typedef basic_string<char_type>                              string_type;
          // 28.10.1, construct/copy/destroy:
          explicit match_results(const Allocator& a = Allocator());
          match_results(const match_results& m);
          match_results(match_results&& m) noexcept;
          match_results(const match_results& m, const Allocator& a);
          match_results(match_results&& m, const Allocator& a);
          match_results& operator=(const match_results& m);
          match_results& operator=(match_results&& m)
            noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
          // 28.10.2, state:
          bool ready() const noexcept;
          // 28.10.3, size:
          size_type size() const noexcept;
          size_type max_size() const noexcept;
          bool empty() const noexcept;
          // 28.10.4, element access:
          difference_type length(size_type sub = 0) const;
          difference_type position(size_type sub = 0) const;
          string_type str(size_type sub = 0) const;
          const_reference operator[](size_type n) const;
          const_reference prefix() const;
          const_reference suffix() const;
          const_iterator begin() const noexcept;
          const_iterator end() const noexcept;
          const_iterator cbegin() const noexcept;
          const_iterator cend() const noexcept;
          // 28.10.5, format:
          template <class OutputIter>
            format(OutputIter out,
                   const char_type* fmt_first, const char_type* fmt_last,
                   regex_constants::match_flag_type flags =
                    regex_constants::format_default) const;
           template <class OutputIter, class ST, class SA>
             format(OutputIter out,
                    const basic_string<char_type, ST, SA>& fmt,
                    regex_constants::match_flag_type flags =
                      regex_constants::format_default) const;
           template <class ST, class SA>
            basic_string<char_type, ST, SA>
            format(const basic_string<char_type, ST, SA>& fmt,
                   regex_constants::match_flag_type flags =
                     regex_constants::format_default) const;
           format(const char_type* fmt,
                  regex_constants::match_flag_type flags =
                    regex_constants::format_default) const;
          // 28.10.6, allocator:
          allocator_type get_allocator() const noexcept;
          // 28.10.7, swap:
          void swap(match_results& that)
            noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||

    Add the following to Annex C:

    C.2.11 Clause 20: general utilities library [diff.cpp03.utilities]


    Change: Containers now access their allocators through the allocator_traits template.

    Rationale: Simplifies writing new allocators.

    Effect on original feature: allocator_traits supplies default definitions for many allocator type names and operations. Containers written by users conforming to the original allocator requirements will not necessarily support allocators written to the simpler set of requirements in this standard.


    Change: Minimal support for garbage-collected regions

    Rationale: Required by new feature.

    Effect on original feature: Valid C++ 2003 code, compiled without traceable pointer support, that interacts with newer C++ code using regions declared reachable may have different runtime behavior.

    C.4.X Clause 17: library introduction [diff.cpp14.library]

    Change: allocator_traits requires consistency of computed types, such as pointer and const_pointer.

    Rationale: Combinations of inconsistent traits added significant complexity to containers, without demonstrating any real benefit.

    Effect on original feature: Allocators that provided inconsistent pointer, connst_pointer, void_pointer, and const_void_pointer types may no longer work with standard containers, and similiarly for inconsisent difference_type and size_type.

    C.4.Y Clause 20: general utilities library [diff.cpp03.utilities]


    Change: allocator_traits cannot be specialized to provide results not discovered from the allocator template parameter.

    Rationale: Simplify writing containers by having a more consistent allocator model.

    Effect on original feature: users could specialize allocator_traits for an allocator type in order to satisy the allocator requirements in a manner inconsistent with the allocator type itself.


    Thanks to Howard Hinnant for the example of an alloctor model that propagates allocators on move-assignment and swap, but not on copy assignment.