Issue 2108: No way to identify allocator types that always compare equal (original) (raw)

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

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 whenpropagate_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(i) 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 toallocator_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_equaltrait 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_swapand 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(i)].

Optionally, operator== for std::allocator could be made to return true_type, however if LWG 2103(i) 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 storageallocated from each can bedeallocated via the other. operator== shall be reflexive,symmetric, and transitive, andshall 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::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 derivedfrom true_type or false_type true_type if the expression x1 == x2 isguaranteed to be true for any two (possibly const) values x1, x2 of type X, whenimplicitly converted to bool. See Note B, below. true_type, if is_empty::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 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 allocator;

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

    template 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 struct rebind { typedef allocator other; };
    typedef true_type always_compares_equal;

    […]
    };
    }