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.

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 of values 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;

   >         […]
   >       };
   >     }