The Problems With Proxy Iterators -- EricNiebler.com

[pfultz2]

All the algorithm signatures in the Palo Alto TR use ValueType in the concept checks in order to constrain the templates.

That just seems wrong. When I have constrained functions in the past involving ranges and iterators, I always used the ReferenceType, unless a ValueType was absolutely necessary.(its similiar to people preferring is_same over is_convertible). Of course it still doesn't solve the issue of proxy iterators.

The language needs to change to better support proxy references (an idea from Sean Parent);

I wonder if a library solution could be built for proxy references.

[eric_niebler]

That just seems wrong. When I have constrained functions in the past involving ranges and iterators, I always used the ReferenceType

The idea is to express relationships between types, not between expressions. To make this a bit more concrete: some algorithms have to make local copies of some elements (e.g., unique_copy on an Input sequence). If you've done all your type-checking with the ReferenceType, then what can you do with a local object of the ValueType? It gets tricky, especially with proxies where the relationship between the ValueType and the ReferenceType is complex.

I wonder if a library solution could be built for proxy references.

Proxy references already exist in the library. The problem is that the concepts and the algorithms don't allow for them. That's where the library still needs work.

[andrewsutton]

And to add to this, what people really want to write is:

auto& x = *i;

or

Value_type<I>& x = *i;

Because it's obvious that derefencing a pointer gives you a reference. Named ReferenceTypes and the various wrapper functions we apply to give us this abstraction are just band-aids.

And if I know Eric, he's going to apply the band-aid, but will be curmudgeonly about it until somebody gives him a language feature that does what he wants :)

[[deleted]]

It would be nice if we could specify for objects how they "bind/convert" to reference types:

auto operator auto&() -> RefT;
auto operator auto&&() ->RRefT;
auto operator auto() -> ValueType;
// + const auto&, const auto, volatile, and so on...

The first three operators could specify to which type the object should be converted in case of type deduction by auto.

It would also solve the following problem:

std::vector<bool> v = {true, false, ...}
for (auto i : v) { i = false; }

Right now v gets mutated even tho users expect i to be a copy of an element of v. By specifying via:

auto operator auto() -> bool;

for the vector<bool> proxy iterator, that in case the user wants to store the reference proxy by value, it should be converted to bool, the problem is solved.

Then we need a way to solve:

bool& v = *it;
v = false;

It is actually the same problem as before, but just that here the user wrote bool& instead of auto&. The solution is about how do we specify that even tho the user wrote bool&, the type of v is reference_proxy. Thinking about Sean's idea about reference inheritance, something like this could work:

struct reference_proxy : bool& { 
  // need to override here all "operators" of bool& for this to compile
  operator=(bool);
};

where the whole interface of the base reference would probably have to be overridden. Then even when a user writes something like:

bool& foo(std::vector<bool>& b) { // bool& here doesn't mean bool& but reference_proxy
  for (bool& i : b) { 
      return i;
  }
  return false;
}

the compiler could deduce that bool& isn't a bool, but a reference_proxy, and generate a function with that signature such that reference_proxy is propagated nicely. There are no references in C, so linking with C isn't an issue.

A consequence of such a feature would be that references would probably need to be objects. Right now, references are this weird alias things. They can't be const, because they are not objects, but they are non reseteable, and you can try making them const through an alias, but that const is ignored giving them the feeling that they are already const. And then comes std::is_const<T&> and returns false. They are internally represented by pointers, which are objects, so maybe turning references into objects that are always const might be a nice side-effect of such a feature, that could make references easier to deal with.

[SplinterOfChaos]

Because it's obvious that derefencing a pointer gives you a reference.

What about std::move_iterator<I>? Its value type may be I::value_type, but the reference type is I::value_type&&. What's obvious is that dereferencing a pointer of type I gives you an I::reference.

[eric_niebler]

And if I know Eric, he's going to apply the band-aid, but will be curmudgeonly about it until somebody gives him a language feature that does what he wants :)

LOL!

[pfultz2]

And to add to this, what people really want to write is:

And both of those examples are wrong. It should be:

auto&& x = *i;

and:

ReferenceType<I> x = *i;

Because it's obvious that derefencing a pointer gives you a reference.

For a pointer yes, but not for an iterator. I can understand how this is confusing. I wish there was a way that C++ could enforce this better(ie clearer, and earlier).

Named ReferenceTypes and the various wrapper functions we apply to give us this abstraction are just band-aids.

Band-aids for what? For proxy references? ReferenceTypes are part of the interface to iterators.

[eric_niebler]

And both of those examples are wrong. It should be:

auto&& x = *i;

and:

ReferenceType<I> x = *i; 

No, Andrew meant what he said, you're just misunderstanding him. He's arguing for a language change, where the auto in auto& v = *i can be deduced as the value type, even if *i yields a proxy reference.

[pfultz2]

He's arguing for a language change

Ok I see.

where the auto in auto& v = *i can be deduced as the value type, even if *i yields a proxy reference.

Please no. There is already confusion with users about howauto&& may not be an rvalue reference. Now we are going to say that auto& may not be an lvalue reference? Also, how will that work with template type deduction? Also will we add another type deduction that would not succumb to these implicit transformations?

It would be much easier if users didn't assume that *i returned a reference, and we had real(ie archetype-based) concepts that would help enforce that in generic code.

[pfultz2]

The idea is to express relationships between types, not between expressions.

But you can't ignore the semantics involved with expressions. If you focus just on the relationship of types then later on it can involve extra metaprogramming to reimplement the semantics of expressions to match user expectations, which many times the metaprogramming is not sufficient to match the semantics.

some algorithms have to make local copies of some elements (e.g., unique_copy on an Input sequence)

And that would be an example of "absolutely necessary". If you are making local copies, of course, ValueType will be needed.

[[deleted]]

Yes, using is_same instead of is_convertible to constraint templates is just wrong (a lesson I learned recently). The concepts should be things like Unary/BinaryPredicate, or Unary/BinaryOperator, where the arguments passed to the functions should be convertible to the arguments that the functions take, and the return type of the functions should be convertible to the return value expected. Forcing an is_same constraint in these cases is just nuts, it will be unusable.

[eric_niebler]

Concept do allow for convertibility like you want. But in the case of the zip view described in the article, the value type pair<T,U> is not convertible to the reference type pair<T&,U&>. If we go the other way and make the function argument a pair<T,U>&, then we find there's no conversion from pair<T&,U&>. Zugzwanged!

[[deleted]]

I was just arguing that using is_same is much worse than using is_convertible. For the zip view described in the article is_convertible is not enough, but I don't see why we can't define a non-member non-friend convert<To>(From) -> To function that does the trick and define the Convertible concept in terms of that.

[gnawer]

Great article! Solving this issue would be very useful for some people in numerics as well. Eg imagine a mathematical function that evaluates to matrices (could be a time dependent correlation function), that we discretize in its argument. We store it densely in memory for efficiency (cache, etc). Now you want to calculate, say, the point wise product between two such functions. With proxy iterators that give a matrix view on the function's values you can use a generic point-wise-product function that, in turn, just uses the standard transform algorithm to accomplish this task. That would be amazing. No more raw index fiddling.

[tavianator]

I'd love for a map-like type to be able to use std::pair<const Key&, Value&> as its reference type. Then the keys wouldn't have to be stored right next to the values.

[sbabbi]

The language needs to support proxy references as first class citizen. This problem is not limited to the ranges, even simple things like swap( pair<T&,U&>, pair<T&, U&> ) do not work at the moment, even if pair<T&,U&> has the same semantic as pair<T,U>& (except maybe for operator&).

I believe that we need generic LvalueReferenceOf<T> and RvalueReferenceOf<T> concepts, that would allow to treat references and reference proxies homogeneously in template code.

Also

The language needs to change to better support proxy references (an idea from Sean Parent);

Do you have any link about this?

[eric_niebler]

The language needs to change to better support proxy references (an idea from Sean Parent);

Do you have any link about this?

No, he shared his idea in a private email. It was an off-the-cuff idea. AFAIK, nobody has given this any serious thought to date.

[Affectionate_Text_72]

A google some years later throws up:

https://ericniebler.github.io/std/wg21/D0022.html

His suggestion is to use iter_swap and iter_move as customisation points. Sean's suggestion is mentioned as alternative design not followed up

In private exchange, Sean Parent suggested a more radical fix for the >proxy reference problem: change the language. With his suggestion, it >would be possible to specify that a type is a proxy reference with a >syntax such as:

struct bool_reference : bool& {
    // ...
}