What is the purpose of C++20 std::common_reference?

common_reference came out of my efforts to come up with a conceptualization of STL's iterators that accommodates proxy iterators.

In the STL, iterators have two associated types of particular interest: reference and value_type. The former is the return type of the iterator's operator*, and the value_type is the (non-const, non-reference) type of the elements of the sequence.

Generic algorithms often have a need to do things like this:

value_type tmp = *it;

... so we know that there must be some relationship between these two types. For non-proxy iterators the relationship is simple: reference is always value_type, optionally const and reference qualified. Early attempts at defining the InputIterator concept required that the expression *it was convertible to const value_type &, and for most interesting iterators that is sufficient.

I wanted iterators in C++20 to be more powerful than this. For example, consider the needs of a zip_iterator that iterates two sequences in lock-step. When you dereference a zip_iterator, you get a temporary pair of the two iterators' reference types. So, zip'ing a vector<int> and a vector<double> would have these associated types:

zip iterator's reference : pair<int &, double &>
zip iterator's value_type: pair<int, double>

As you can see, these two types are not related to each other simply by adding top-level cv- and ref qualification. And yet letting the two types be arbitrarily different feels wrong. Clearly there is some relationship here. But what is the relationship, and what can generic algorithms that operate on iterators safely assume about the two types?

The answer in C++20 is that for any valid iterator type, proxy or not, the types reference && and value_type & share a common reference. In other words, for some iterator it there is some type CR which makes the following well-formed:

void foo(CR) // CR is the common reference for iterator I
{}

void algo( I it, iter_value_t<I> val )
{
  foo(val); // OK, lvalue to value_type convertible to CR
  foo(*it); // OK, reference convertible to CR
}

CR is the common reference. All algorithms can rely on the fact that this type exists, and can use std::common_reference to compute it.

So, that is the role that common_reference plays in the STL in C++20. Generally, unless you are writing generic algorithms or proxy iterators, you can safely ignore it. It's there under the covers ensuring that your iterators are meeting their contractual obligations.

---

EDIT: The OP also asked for an example. This is a little contrived, but imagine it's C++20 and you are given a random-access range r of type R about which you know nothing, and you want to sort the range.

Further imagine that for some reason, you want to use a monomorphic comparison function, like std::less<T>. (Maybe you've type-erased the range, and you need to also type-erase the comparison function and pass it through a virtual? Again, a stretch.) What should T be in std::less<T>? For that you would use common_reference, or the helper iter_common_reference_t which is implemented in terms of it.

using CR = std::iter_common_reference_t<std::ranges::iterator_t<R>>;
std::ranges::sort(r, std::less<CR>{});

That is guaranteed to work, even if range r has proxy iterators.

No type named 'type' in 'struct std::common_reference<Ref&&, const Val&>'

In this case, you need to partial specialize std::basic_common_reference to define the common reference of the two, similar to this:

template<template<class> class TQual, template<class> class UQual>
struct std::basic_common_reference<Ref, Val, TQual, UQual> { 
  using type = Val;
};

template<template<class> class TQual, template<class> class UQual>
struct std::basic_common_reference<Val, Ref, TQual, UQual> { 
  using type = Val;
};

Demo.

Some issues worth noting:

• Val's member functions need to be public.
• Val's constructor should not be explicit to satisfy indirectly_readable.
• Val's operator=(Ref ref) needs to return Val& to meet sortable.
• Ref needs to add operator=(Val) const overload to satisfy indirectly_writable.

Does `equality_­comparable_with` need to require `common_reference`?

This goes all the way back to the Palo Alto report, §3.3 and D.2.

For the cross-type concepts to be mathematically sound, you need to define what the cross-type comparison means. For equality_comparable_with, t == u generally means that t and u are equal, but what does it even mean for two values of different types to be equal? The design says that cross-type equality is defined by mapping them to the common (reference) type (this conversion is required to preserve the value).

Where the strong axioms of equality_comparable_with is not desirable, the standard uses the exposition-only concept weakly-equality-comparable-with, and that concept doesn't require a common reference. It is, however, a "semantic abomination" (in the words of Casey Carter) and is exposition-only for that reason: it allows having t == u and t2 == u but t != t2 (this is actually necessary for sentinels).

std::ranges::find_if - no type in std::common_reference

Why does the combination of const range and const auto& lambda
argument fail to compile, while pasing a mutable range works and
taking the lambda argument by value works?

First, the operator*() of the iterator of flat_map is defined as follows:

reference operator*() const {
  return reference{*kit_, *vit_};
}

And the type of reference is pair, this means that operator*() will return a prvalue of pair, so the parameter type of the lambda cannot be auto&, that is, an lvalue reference, because it cannot bind rvalue.

Second, const flat_map does not model the input_range concept, that is, its iterator does not model input_iterator which requires indirectly_readable which requires common_reference_with<iter_reference_t<In>&&, iter_value_t<In>&>, the former is pair<const int&, const int&>&&, and the latter is pair<const int, int>&, there is no common_reference for the two.

The workaround is to just define common_reference for them, just like P2321 does (which also means that your code is well-formed in C++23):

template<class T1, class T2, class U1, class U2,
         template<class> class TQual, template<class> class UQual>
  requires requires { typename pair<common_reference_t<TQual<T1>, UQual<U1>>,
                                    common_reference_t<TQual<T2>, UQual<U2>>>; }
struct basic_common_reference<pair<T1, T2>, pair<U1, U2>, TQual, UQual> {
  using type = pair<common_reference_t<TQual<T1>, UQual<U1>>,
                    common_reference_t<TQual<T2>, UQual<U2>>>;
};

For details on common_reference, you can refer to this question.

Why is unique_ptr not equality_comparable_with nullptr_t in C++20?

TL;DR: std::equality_comparable_with<T, U> requires that both T and U are convertible to the common reference of T and U. For the case of std::unique_ptr<T> and std::nullptr_t, this requires that std::unique_ptr<T> is copy-constructible, which it is not.

---

Buckle in. This is quite the ride. Consider me nerd-sniped.

Why don't we satisfy the concept?

std::equality_comparable_with requires:

template <class T, class U>
concept equality_comparable_with =
  std::equality_comparable<T> &&
  std::equality_comparable<U> &&
  std::common_reference_with<
    const std::remove_reference_t<T>&,
    const std::remove_reference_t<U>&> &&
  std::equality_comparable<
    std::common_reference_t<
      const std::remove_reference_t<T>&,
      const std::remove_reference_t<U>&>> &&
  __WeaklyEqualityComparableWith<T, U>;

That's a mouthful. Breaking apart the concept into its parts, std::equality_comparable_with<std::unique_ptr<int>, std::nullptr_t> fails for std::common_reference_with<const std::unique_ptr<int>&, const std::nullptr_t&>:

<source>:6:20: note: constraints not satisfied
In file included from <source>:1: 
/…/concepts:72:13:   required for the satisfaction of
    'convertible_to<_Tp, typename std::common_reference<_Tp1, _Tp2>::type>'
    [with _Tp = const std::unique_ptr<int, std::default_delete<int> >&; _Tp2 = const std::nullptr_t&; _Tp1 = const std::unique_ptr<int, std::default_delete<int> >&]
/…/concepts:72:30: note: the expression 'is_convertible_v<_From, _To>
    [with _From = const std::unique_ptr<int, std::default_delete<int> >&; _To = std::unique_ptr<int, std::default_delete<int> >]' evaluated to 'false'
   72 |     concept convertible_to = is_convertible_v<_From, _To>
      |                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~

(edited for legibility) Compiler Explorer link.

std::common_reference_with requires:

template < class T, class U >
concept common_reference_with =
  std::same_as<std::common_reference_t<T, U>, std::common_reference_t<U, T>> &&
  std::convertible_to<T, std::common_reference_t<T, U>> &&
  std::convertible_to<U, std::common_reference_t<T, U>>;

std::common_reference_t<const std::unique_ptr<int>&, const std::nullptr_t&> is std::unique_ptr<int> (see compiler explorer link).

Putting this together, there is a transitive requirement that std::convertible_to<const std::unique_ptr<int>&, std::unique_ptr<int>>, which is equivalent to requiring that std::unique_ptr<int> is copy-constructible.

Why is the std::common_reference_t not a reference?

Why is std::common_reference_t<const std::unique_ptr<T>&, const std::nullptr_t&> = std::unique_ptr<T> instead of const std::unique_ptr<T>&? The documentation for std::common_reference_t for two types (sizeof...(T) is two) says:

• If T1 and T2 are both reference types, and the simple common reference type S of T1 and T2 (as defined below) exists, then the
  member type type names S;
• Otherwise, if std::basic_common_reference<std::remove_cvref_t<T1>, std::remove_cvref_t<T2>, T1Q, T2Q>::type exists, where TiQ is a unary
  alias template such that TiQ<U> is U with the addition of Ti's cv- and
  reference qualifiers, then the member type type names that type;
• Otherwise, if decltype(false? val<T1>() : val<T2>()), where val is a function template template<class T> T val();, is a valid type, then
  the member type type names that type;
• Otherwise, if std::common_type_t<T1, T2> is a valid type, then the member type type names that type;
• Otherwise, there is no member type.

const std::unique_ptr<T>& and const std::nullptr_t& don't have a simple common reference type, since the references are not immediately convertible to a common base type (i.e. false ? crefUPtr : crefNullptrT is ill-formed). There is no std::basic_common_reference specialization for std::unique_ptr<T>. The third option also fails, but we trigger std::common_type_t<const std::unique_ptr<T>&, const std::nullptr_t&>.

For std::common_type, std::common_type<const std::unique_ptr<T>&, const std::nullptr_t&> = std::common_type<std::unique_ptr<T>, std::nullptr_t>, because:

If applying std::decay to at least one of T1 and T2 produces a
different type, the member type names the same type as
std::common_type<std::decay<T1>::type, std::decay<T2>::type>::type, if
it exists; if not, there is no member type.

std::common_type<std::unique_ptr<T>, std::nullptr_t> does in fact exist; it is std::unique_ptr<T>. This is why the reference gets stripped.

---

Can we fix the standard to support cases like this?

This has turned into P2404, which proposes changes to std::equality_comparable_with, std::totally_ordered_with, and std::three_way_comparable_with to support move-only types.

Why do we even have these common-reference requirements?

In Does `equality_­comparable_with` need to require `common_reference`?, the justification given by T.C. (originally sourced from n3351 pages 15-16) for the common-reference requirements on equality_comparable_with is:

[W]hat does it even mean for two values of different types to be equal? The design says that cross-type equality is defined by mapping them to the common (reference) type (this conversion is required to preserve the value).

Just requiring the == operations that might naively be expected of the concept doesn't work, because:

[I]t allows having t == u and t2 == u but t != t2

So the common-reference requirements are there for mathematical soundness, simultaneously allowing for a possible implementation of:

using common_ref_t = std::common_reference_t<const Lhs&, const Rhs&>;
common_ref_t lhs = lhs_;
common_ref_t rhs = rhs_;
return lhs == rhs;

With the C++0X concepts that n3351 supported, this implementation would actually be used as a fallback if there was no heterogeneous operator==(T, U).
With C++20 concepts, we require a heterogeneous operator==(T, U) to exist, so this implementation will never be used.

Note that n3351 expresses that this kind of heterogeneous equality is already an extension of equality, which is only rigorously mathematically defined within a single type. Indeed, when we write heterogeneous equality operations, we are pretending that the two types share a common super-type, with the operation happening inside that common type.

Can the common-reference requirements support this case?

Perhaps the common-reference requirements for std::equality_comparable are too strict. Importantly, the mathematical requirement is only that there exists a common supertype in which this lifted operator== is an equality, but what the common reference requirements require is something stricter, additionally requiring:

1. The common supertype must be the one acquired through std::common_reference_t.
2. We must be able to form a common supertype reference to both types.

Relaxing the first point is basically just providing an explicit customization point for std::equality_comparable_with in which you could explicitly opt-in a pair of types to meet the concept. For the second point, mathematically, a "reference" is meaningless. As such, this second point can also be relaxed to allow the common supertype to be implicitly convertible from both types.

Can we relax the common-reference requirements to more closely follow the intended common-supertype requirements?

This is tricky to get right. Importantly, we actually only care that the common supertype exists, but we never actually need to use it in the code. As such, we do not need to worry about efficiency or even whether the implementation would be impossible when codifying a common supertype conversion.

This can be accomplished by changing the std::common_reference_with part of equality_comparable_with:

template <class T, class U>
concept equality_comparable_with =
  __WeaklyEqualityComparableWith<T, U> &&
  std::equality_comparable<T> &&
  std::equality_comparable<U> &&
  std::equality_comparable<
    std::common_reference_t<
      const std::remove_reference_t<T>&,
      const std::remove_reference_t<U>&>> &&
  __CommonSupertypeWith<T, U>;

template <class T, class U>
concept __CommonSupertypeWith = 
  std::same_as<
    std::common_reference_t<
      const std::remove_cvref_t<T>&,
      const std::remove_cvref_t<U>&>,
    std::common_reference_t<
      const std::remove_cvref_t<U>&,
      const std::remove_cvref_t<T>&>> &&
  (std::convertible_to<const std::remove_cvref_t<T>&,
    std::common_reference_t<
      const std::remove_cvref_t<T>&,
      const std::remove_cvref_t<U>&>> ||
   std::convertible_to<std::remove_cvref_t<T>&&,
    std::common_reference_t<
      const std::remove_cvref_t<T>&,
      const std::remove_cvref_t<U>&>>) &&
  (std::convertible_to<const std::remove_cvref_t<U>&,
    std::common_reference_t<
      const std::remove_cvref_t<T>&,
      const std::remove_cvref_t<U>&>> ||
   std::convertible_to<std::remove_cvref_t<U>&&,
    std::common_reference_t<
      const std::remove_cvref_t<T>&,
      const std::remove_cvref_t<U>&>>);

In particular, the change is changing common_reference_with to this hypothetical __CommonSupertypeWith where __CommonSupertypeWith differs by allowing for std::common_reference_t<T, U> to produce a reference-stripped version of T or U and also by trying both C(T&&) and C(const T&) to create the common reference. For more details, see P2404.

---

How do I work around std::equality_comparable_with before this gets merged into the standard?

Change which overload you use

For all of the uses of std::equality_comparable_with (or any of the other *_with concepts) in the standard library, there is helpfully a predicate overload which you can pass a function to. That means that you can just pass std::equal_to() to the predicate overload and get the desired behavior (not std::ranges::equal_to, which is constrained, but the unconstrained std::equal_to).

This doesn't mean that it would be a good idea to not fix std::equality_comparable_with, however.

Can I extend my own types to meet std::equality_comparable_with?

The common-reference requirements use std::common_reference_t, which has a customization point of std::basic_common_reference, for the purpose of:

The class template basic_common_reference is a customization point that allows users to influence the result of common_reference for user-defined types (typically proxy references).

It is a horrible hack, but if we write a proxy reference that supports both types we want to compare, we can specialize std::basic_common_reference for our types, enabling our types to meet std::equality_comparable_with. See also How can I tell the compiler that MyCustomType is equality_comparable_with SomeOtherType? . If you choose to do this, beware; std::common_reference_t is not only used by std::equality_comparable_with or the other comparison_relation_with concepts, you risk causing cascading problems down the road. It is best if you ensure that the common reference is actually a common reference, e.g.:

template <typename T>
class custom_vector { ... };

template <typename T>
class custom_vector_ref { ... };

custom_vector_ref<T> could be a good option for a common reference between custom_vector<T> and custom_vector_ref<T>, or possibly even between custom_vector<T> and std::array<T, N>. Tread carefully.

How can I extend types I don't control std::equality_comparable_with?

You can't. Specializing std::basic_common_reference for types you don't own (either std:: types or some third-party library) is at best bad practice and at worst undefined behavior. The safest choice would be to use a proxy type you own that you can compare through or else write your own extension of std::equality_comparable_with that has an explicit customization point for your custom spelling of equality.

---

Okay, I get that the idea of these requirements is mathematical soundness, but how do these requirements acheive mathematical soundness, and why is it so important?

Mathematically, equality is an equivalence relation. However, equivalence relations are defined over a single set. So how can we define an equivalence relation between two sets A and B? Simply put, we instead define the equivalence relation over C = A∪B. That is to say, we take a common supertype of A and B and define the equivalence relation over this supertype.

This means that our relation c1 == c2 must be defined no matter where c1 and c2 come from, so we must have a1 == a2, a == b, and b1 == b2 (where ai is from A and bi is from B). Translating to C++, this means that all of operator==(A, A), operator==(A, B), operator==(B, B), and operator==(C, C) must be part of the same equality.

This is why iterator/sentinels do not meet std::equality_comparable_with: while operator==(iterator, sentinel) may actually be part of some equivalence relation, it is not part of the same equivalence relation as operator==(iterator, iterator) (otherwise iterator equality would only answer the question of "Are either both iterators at the end or both iterators not at the end?").

It is actually quite easy to write an operator== that is not actually equality, because you must remember that the heterogeneous equality is not the single operator==(A, B) you are writing, but is instead four different operator==s that must all be coheisve.

Wait a minute, why do we need all four operator==s; why can't we just have operator==(C, C) and operator==(A, B) for optimization purposes?

This is a valid model, and we could do this. However, C++ is not a platonic reality. Although concepts try their hardest to only accept types that truly meet the semantic requirements, it cannot actually acheive this goal. As such, if we were to only check operator==(A, B) and operator==(C, C), we run the risk that operator==(A, A) and operator==(B, B) do something different. Besides, if we can have operator==(C, C), then this means that it is trivial to write operator==(A, A) and operator==(B, B) based on what we have in operator==(C, C). That is to say, the harm of requiring operator==(A, A) and operator==(B, B) is quite low, and in return we get a higher confidence that we actually have an equality.

There are some circumstances where this runs into rough edges, however; see P2405.

How exhausting. Can't we just require that operator==(A, B) is an actual equality? I'm never going to actually use the operator==(A, A) or operator==(B, B) anyway; I only cared about being able to do the cross-type comparison.

Actually, a model where we require operator==(A, B) is an actual equality would probably work. Under this model, we would have std::equality_comparable_with<iterator, sentinel>, but what precisely that means in all known contexts could be hammered out. However, there was a reason why this is not the direction the standard went with, and before one can understand if or how to change it, they must first understand why the standard's model was chosen.

How to use std::ranges on a vector for a function that needs two arguments?

The algorithm you're looking for is combinations - but there's no range adaptor for that (neither in C++20 nor range-v3 nor will be in C++23).

However, we can manually construct it in this case using an algorithm usually called flat-map:

inline constexpr auto flat_map = [](auto f){
    return std::views::transform(f) | std::views::join;
};

which we can use as follows:

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    return std::ranges::max(
        rv::iota(0u, points.size())
        | flat_map([&](size_t i){
            return rv::iota(i+1, points.size())
                 | rv::transform([&](size_t j){
                     return ComputeDistance(points[i], points[j]);
                 });
          }));
}

The outer iota is our first loop. And then for each i, we get a sequence from i+1 onwards to get our j. And then for each (i,j) we calculate ComputeDistance.

Or if you want the transform at top level (arguably cleaner):

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    return std::ranges::max(
        rv::iota(0u, points.size())
        | flat_map([&](size_t i){
            return rv::iota(i+1, points.size())
                 | rv::transform([&](size_t j){
                     return std::pair(i, j);
                 });
          })
        | rv::transform([&](auto p){
            return ComputeDistance(points[p.first], points[p.second]);
          }));
}

or even (this version produces a range of pairs of references to Point, to allow a more direct transform):

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    namespace hof = boost::hof;

    return std::ranges::max(
        rv::iota(0u, points.size())
        | flat_map([&](size_t i){
            return rv::iota(i+1, points.size())
                 | rv::transform([&](size_t j){
                     return std::make_pair(
                         std::ref(points[i]),
                         std::ref(points[j]));
                 });
          })
        | rv::transform(hof::unpack(ComputeDistance)));
}

These all basically do the same thing, it's just a question of where and how the ComputeDistance function is called.

---

C++23 will add cartesian_product and chunk (range-v3 has them now) , and just recently added zip_transform, which also will allow:

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    namespace hof = boost::hof;

    return std::ranges::max(
        rv::zip_transform(
           rv::drop,
           rv::cartesian_product(points, points)
           | rv::chunk(points.size()),
           rv::iota(1))
        | rv::join
        | rv::transform(hof::unpack(ComputeDistance))
    );
}

cartesian_product by itself would give you all pairs - which both includes (x, x) for all x and both (x, y) and (y, x), neither of which you want. When we chunk it by points.size() (produces N ranges of length N).

---

Related Topics