2108. No way to identify allocator types that always compare equal

Section: 16.4.4.6 [allocator.requirements] Status: Resolved Submitter: Jonathan Wakely Opened: 2011-12-01 Last modified: 2018-12-03

Priority: 3

View other active issues in [allocator.requirements].

View all other issues in [allocator.requirements].

View all issues with Resolved status.

Discussion:

Whether two allocator objects compare equal affects the complexity of container copy and move assignments and also the possibility of an exception being thrown by container move assignments. The latter point means container move assignment cannot be noexcept when propagate_on_container_move_assignment (POCMA) is false for the allocator because there is no way to detect at compile-time if two allocators will compare equal. LWG 2013 means this affects all containers using std::allocator, but even if that is resolved, this affects all stateless allocators which do not explicitly define POCMA to true_type.

One solution would be to add an "always_compare_equal" trait to allocator_traits, but that would be duplicating information that is already defined by the type's equality operator if that operator always returns true. Requiring users to write operator== that simply returns true and also explicitly override a trait to repeat the same information would be unfortunate and risk user errors that allow the trait and actual operator== to disagree.

Dave Abrahams suggested a better solution in message c++std-lib-31532, namely to allow operator== to return true_type, which is convertible to bool but also detectable at compile-time. Adopting this as the recommended way to identify allocator types that always compare equal only requires a slight relaxation of the allocator requirements so that operator== is not required to return bool exactly.

The allocator requirements do not make it clear that it is well-defined to compare non-const values, that should be corrected too.

In message c++std-lib-31615 Pablo Halpern suggested an always_compare_equal trait that could still be defined, but with a sensible default value rather than requiring users to override it, and using that to set sensible values for other allocator traits:

Do we still need always_compare_equal if we can have an operator== that returns true_type? What would its default value be? is_empty<A> || is_convertible<decltype(a == a), true_type>::value, perhaps? One benefit I see to such a definition is that stateless C++03 allocators that don't use the true_type idiom will still benefit from the new trait.

[…]

One point that I want to ensure doesn't get lost is that if we adopt some sort of always_compare_equal-like trait, then propagate_on_container_swap and propagate_on_container_move_assignment should default to always_compare_equal. Doing this will eliminate unnecessary requirements on the container element type, as per [LWG 2103].

Optionally, operator== for std::allocator could be made to return true_type, however if LWG 2103 is adopted that is less important.

Alberto Ganesh Barbati: Suggest either always_compare_equal, all_objects_(are_)equivalent, or all_objects_compare_equal.

[2014-11-07 Urbana]

Resolved by N4258

Proposed resolution:

This wording is relative to the FDIS.

  1. Change Table 27 — "Descriptive variable definitions" in 16.4.4.6 [allocator.requirements]:

    Table 27 — Descriptive variable definitions
    Variable Definition
    a3, a4 an rvalue ofvalues of (possibly const) type X
    b a value of (possibly const) type Y

  2. Change Table 28 — "Allocator requirements" in 16.4.4.6 [allocator.requirements]:

    Table 28 — Allocator requirements
    Expression Return type Assertion/note pre-/post-condition Default
    a1 == a2a3 == a4 convertible to 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 != a2a3 != a4 convertible to bool same as !(a1 == a2)!(a3 == a4)
    a3 == b convertible to bool same as a3 ==
    Y::rebind<T>::other(b)
    a3 != b convertible to bool same as !(a3 == b)
    […]
    a.select_on_-
    container_copy_-
    construction()         		X Typically returns either a or
    X()     		return a;
    X::always_compares_equal Identical to or derived
    from true_type or
    false_type         		true_type if the expression x1 == x2 is
    guaranteed to be true for any two (possibly
    const) values x1, x2 of type X, when
    implicitly converted to bool. See Note B, below.         		true_type, if is_empty<X>::value is true or if
    decltype(declval<const X&>() == declval<const X&>())
    is convertible to true_type, otherwise false_type.
    […]

    Note A: […]

    Note B: If X::always_compares_equal::value or XX::always_compares_equal::value evaluate to true and an expression equivalent to x1 == x2 or x1 != x2 for any two values x1, x2 of type X evaluates to false or true, respectively, the behaviour is undefined.

  3. Change class template allocator_traits synopsis, 20.2.9 [allocator.traits] as indicated:

    namespace std {
  template <class Alloc> struct allocator_traits {
    typedef Alloc allocator_type;
    […]
    typedef see below always_compares_equal;
    typedef see below propagate_on_container_copy_assignment;
    […]
  };
}

  4. Insert the following between 20.2.9.2 [allocator.traits.types] p6 and p7 as indicated:

    typedef see below always_compares_equal;

    -?- Type: Alloc::always_compares_equal if such a type exists; otherwise, true_type if is_empty<Alloc>::value is true or if decltype(declval<const Alloc&>() == declval<const Alloc&>()) is convertible to true_type; otherwise, false_type . 

    typedef see below propagate_on_container_copy_assignment;

    -7- Type: Alloc::propagate_on_container_copy_assignment if such a type exits, otherwise false_type.

  5. Change class template allocator synopsis, 20.2.10 [default.allocator] as indicated:

    namespace std {
  template <class T> class allocator;

  // specialize for void:
  template <> class allocator<void> {
  public:
    typedef void* pointer;
    typedef const void* const_pointer;
    // reference-to-void members are impossible.
    typedef void value_type;
    template <class U> struct rebind { typedef allocator<U> other; };
  };

  template <class T> class allocator {
  public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
    template <class U> struct rebind { typedef allocator<U> other; };
    typedef true_type always_compares_equal;

    […]
  };
}