Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

C++20 introduces std::common_reference. What is its purpose? Can someone give an example of using it?

like image 571
康桓瑋 Avatar asked Nov 23 '19 19:11

康桓瑋


1 Answers

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.

like image 53
Eric Niebler Avatar answered Nov 09 '22 09:11

Eric Niebler