Proposed resolution:

This wording is relative to N4917.

1. Modify [allocator.requirements] as indicated:

   typename X::template rebind<U>::other
   

   -16- Result: Y

   -17- Postconditions: For all U (including T), Y::template rebind<T>::other is X. All of XX::is_always_equal::value == YY::is_always_equal::value, XX::propagate_on_container_copy_assignment::value == YY::propagate_on_container_copy_assignment::value, XX::propagate_on_container_move_assignment::value == YY::propagate_on_container_move_assignment::value, and XX::propagate_on_container_swap::value == YY::propagate_on_container_swap::value are true.

   -18- Remarks: 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.

   -19- [Note 1: The member class template rebind of X is effectively a typedef template. In general, if the name Allocator is bound to SomeAllocator<T>, then Allocator::rebind<U>::other is the same type as SomeAllocator<U>, where SomeAllocator<T>::value_type is T and SomeAllocator<U>::value_type is U. — end note]

[ 2023-01-08; Jiang An comments and provides improved wording ]

Exception specifications of some container operations (added by N4258 and LWG 3778) are specified with the propagation properties of template parameter Allocator. However, for node-based containers and std::deque (and common implementations of std::vector<bool, A>), rebound allocators are needed to be propagated, and common implementations are currently detecting the propagation properties of rebound allocators.

I think if the allocator provided as template argument and the rebound have different propagation properties and behaves differently on propagation, then it is difficult or impossible for implementations to follow the current exception specifications.

[ 2022-04-24; Daniel rebases wording on N4910 ]

Previous resolution [SUPERSEDED]:

This wording is relative to N4910.

[Drafting note: Additional questions: Is it necessary to ensure that
XX::propagate_on_container_copy_assignment::value == YY::propagate_on_container_copy_assignment::value is true as well?]

1. Modify [allocator.requirements] as indicated:

   typename X::template rebind<U>::other
   

   -16- Result: Y

   -17- Postconditions: For all U (including T), Y::template rebind<T>::other is X. XX::is_always_equal::value == YY::is_always_equal::value is true.

   -18- Remarks: 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.

   -19- [Note 1: The member class template rebind of X is effectively a typedef template. In general, if the name Allocator is bound to SomeAllocator<T>, then Allocator::rebind<U>::other is the same type as SomeAllocator<U>, where SomeAllocator<T>::value_type is T and SomeAllocator<U>::value_type is U. — end note]

[ 2019-10 Priority set to 4 after reflector discussion ]

Previous resolution [SUPERSEDED]:

This wording is relative to N4830.

[Drafting note: Additional questions: Is it necessary to ensure that
XX::propagate_on_container_copy_assignment::value == YY::propagate_on_container_copy_assignment::value is true as well?]

1. Modify [allocator.requirements], Table [tab:cpp17.allocator] "Cpp17Allocator requirements" as indicated:

   Table 34 — Cpp17Allocator requirements [tab:cpp17.allocator]

   Expression	Return type	Assertion/note pre-/post-condition	Default
   …
   typename X::template rebind<U>::other	Y	For all U (including T), Y::template rebind<T>::other is X. XX::is_always_equal::value == YY::is_always_equal::value is true.	See Note A, below.
   …

[allocator.requirements] does not mention the interaction between is_always_equal and allocator rebinding. As the result, a rebound allocator may have different is_always_equal::value to the original allocator.

Further, for an allocator type X satisfying std::allocator_type<X>::is_always_equal::value == true, rebound allocators of X with same type are not guaranteed equal.

Consider:

1. X is used as an allocator for value_type used in a node-based container;

2. Y is the rebound allocator type for the node type used in the implementation;

3. b1 and b2 are values of Y from different allocator objects.

Then, std::allocator_type<X>::is_always_equal::value == true does not necessarily imply b1 == b2.

Since some of containers in the standard have already explicitly relied on is_always_equal of allocators for their value_type (notably, in the exception specification of the move assignment), this can cause subtle problems.

In general, the implementation of the move assignment operator of such a container can not avoid allocation for new nodes when !std::allocator_traits<Y>::propagate_on_container_move_assignment::value && b1 != b2. This can throw, and it can clash with the required exception specification based on std::allocator_traits<value_type>::is_always_equal:

#include <utility>
#include <memory>
#include <new>
#include <map>
#include <functional> 
#include <type_traits> 

using K = int;
using V = int;
using P = std::pair<const K, V>; 

bool stop_alloc; 

template<typename T>
struct AT
{
  using value_type = T; 

  std::shared_ptr<void> sp = {}; 

  template<typename U>
  struct rebind
  {
    using other = AT<U>;
  }; 

  using is_always_equal = std::is_same<T, P>; 

  AT() : sp(is_always_equal::value ? nullptr : new T*()) {}

  AT(const AT& a) = default;

  template<typename U>
  AT(const AT<U>& a) noexcept : sp(a.sp) {} 

  T* allocate(std::size_t size)
  {
    if (stop_alloc)
      throw std::bad_alloc();
    return static_cast<T*>(::operator new(size * sizeof(T)));
  } 

  void deallocate(T* p, std::size_t)
  {
    ::operator delete(p);
  }

  friend bool operator==(const AT& x, const AT& y) noexcept
  {
    return !x.sp.owner_before(y.sp) && !y.sp.owner_before(x.sp);
  } 

  friend bool operator!=(const AT& x, const AT& y) noexcept 
  {
    return !(x == y);
  }

};

using A = AT<P>; 

int main()
{
  // Some sanity checks:
  static_assert(std::is_same_v<A::template rebind<A::value_type>::other, A>);
  // For any U:
  using U = int;
  static_assert(std::is_same_v<A::template rebind<U>::other::template rebind<A::value_type>::other, A>); 

  using C = std::less<>;
  using M = std::map<K, V, C, A>; 

  // As required by the current wording of the container move operator:
  using always_equal = std::allocator_traits<A>::is_always_equal;
  constexpr bool std_nothrow = always_equal::value && std::is_nothrow_move_assignable_v<C>;
  static_assert(std_nothrow);

  // For conforming implementations:
  // static_assert(!(std_nothrow && !std::is_nothrow_move_assignable<M>::value)); 

  M m{{K(), V()}}, m2;
  auto a = m.get_allocator(); 

  a.sp = std::make_shared<int>(42);
  stop_alloc = true;

  try
  {
    // Call terminate with conforming implementations. This does not work on libstdc++.
    m2 = std::move(m);
    // For libstdc++, terminate on allocator-extended move constructor call.
    //    M m3(std::move(m), a);
  }
  catch(...)
  {}
}