Issue 2108: No way to identify allocator types that always compare equal

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 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.

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

Table 27 — Descriptive variable definitions
Variable Definition

a3, a4 ~~an rvalue of~~values of (possibly const) type X

b a value of (possibly const) type Y

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

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.

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;
    […]
  };
}

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.

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;

    […]
  };
}