Way back in 1999, when the ink on the first C++ standard was still damp, Herb Sutter posed a GoTW puzzler in the still extant C++ Report (RIP): When Is a Container Not a Container? In that article, Herb described the problems of the now-infamous vector<bool>
. According to the standard’s own container requirements, vector<bool>
is not a container.
In a nutshell, it’s because vector<bool>
‘s iterators claim to be random-access, but they’re not. Random-access iterators, when you dereference them, must return a real reference. They can only do that if the thing they point to really exists somewhere. But the bool
that a vector<bool>::iterator
points to does not exist anywhere. It’s actually a bit in a packed integer, and dereferencing a vector<bool>
‘s iterator returns an object of some type that merely acts like a bool&
without actually being a bool&
.
Herb goes so far as to say this:
[…] although a proxied collection can be an important and useful tool, by definition it must violate the standard’s container requirements and therefore can never be a conforming container.
At the end of his article, Herb suggests that people stop using vector<bool>
and use std::bitset
if they want bit-packing. But that just pushes the problem around. Why shouldn’t std::bitset
be a conforming container with random-access iterators? If proxied collections are so useful, why should we content ourselves with a standard library that treats them like second-class citizens?
A Brief History of Proxy Iterators
Herb wrote his article in 1999, so we’ve been living with this problem for a long time. Many have tried to fix it and ultimately failed for one reason or another. Mostly it’s because all the solutions have tried to be backwards compatible, shoehorning a richer iterator hierarchy into a standard that doesn’t easily allow it, or else breaking iterators themselves apart into separate objects that control traversal and element access. Each time the committee has balked, preferring instead the devil it knew.
An interesting historical note: the original STL design didn’t have the “true reference” requirement that causes the problem. Take a look at the SGI docs for the Forward Iterator concept. Nowhere does it say that *it
should be a real reference. The docs for Trivial Iterators specifically mention proxy references and say they’re legit.
Recently, a who’s who of C++ luminaries put their names on N3351, the so-called Palo Alto TR, which proposes a concept-based redesign of the STL, using the syntax of Concepts Lite. Interestingly, the Palo Alto TR is a throw-back to the original SGI design: there is no “true-reference” requirement on the return type of *it
; it merely must be convertible to const ValueType<I> &
:
// This must work, according to the Palo Alto TR const ValueType<I> & val = *it;
It’s not hard for a proxy reference type to provide such a conversion. For instance, the following compiles today:
std::vector<bool> vb{true, false, true, false}; auto it = vb.begin(); const bool & val = *it;
*it
has an implicit conversion to bool
, which binds to a const bool&
. Awesome! So the problem is solved, right? Not quite.
A Panoply of Proxy Problems
To better see the problems with proxy iterators, let’s look at a more interesting example: a zip
view. When you zip two sequences together, you get a single sequence where each element is a std::pair
of elements from the two source sequences. This can be done lazily, creating pairs on demand as the zip view is iterated:
std::vector<int> v1 { 1,2,3 }; std::vector<int> v2 { 9,8,7 }; auto z = view::zip( v1, v2 ); auto it = z.begin(); assert( *it == std::make_pair(1,9) ); assert( *++it == std::make_pair(2,8) ); assert( *++it == std::make_pair(3,7) );
Since the zip view is generating the pairs on demand, they don’t exist anywhere in memory. But the elements they refer to do! See?
std::pair<int&,int&> p = *z.begin(); assert( &p.first == &v1[0] ); assert( &p.second == &v2[0] );
The zip view is a very interesting beastie. Its reference type is pair<T&,U&>
and its value type is pair<T,U>
. This poses some very interesting challenges for the iterator concepts.
1. Values and References
Recall that the Palo Alto TR requires *it
to be convertible to const ValueType<I>&
. So we should be able to do this:
auto z = view::zip( v1, v2 ); const pair<int,int>& val = *z.begin();
That works! As it so happens, there is a conversion from std::pair<T&,U&>
to std::pair<T,U>
— but there’s a catch: it only works if T
and U
are copyable! And even when they’re not, it’s clear that copying is not the behavior one would expect when using *it
to initialize a const reference. If T
or U
is expensive to copy, you’re not going to get the performance or the behavior you expect, and if it’s unique_ptr
it’s not going to compile at all. 🙁
Requiring that an iterator’s reference type be convertible to const ValueType<I>&
is over-constraining. But then what useful thing can we say about the relationship between these two types?
2. Algorithm Constraints
All the algorithm signatures in the Palo Alto TR use ValueType
in the concept checks in order to constrain the templates. For example, here’s the constrained signature of for_each
:
template<InputIterator I, Semiregular F> requires Function<F, ValueType<I>> F for_each(I first, I last, F f);
If you’re not familiar with C++ concepts, what lines 1 and 2 say is: first
and last
must satisfy the requirements of the InputIterator
concept, F
must be Semiregular
(I’ll gloss over this bit), and it must be callable with one argument of the iterator’s value type.
Now imagine code like this:
// As before, v1 and v2 are vectors of ints: auto z = view::zip( v1, v2 ); // Let Ref be the zip iterator's reference type: using Ref = decltype(*z.begin()); // Use for_each to increment all the ints: for_each( z.begin(), z.end(), [](Ref r) { ++r.first; ++r.second; });
This seems perfectly reasonable. The lambda accepts an object of the zip view’s reference type, which is a pair<int&,int&>
, and then it increments both first and second members. But this doesn’t type-check. Why?
Remember the concept check: Function<F, ValueType<I>>
. The function we pass to for_each
must be callable with an object of the iterator’s value type. In this case, the value type is pair<int,int>
. There is no conversion from that to the type the function expects, which is pair<int&,int&>
. Bummer.
If we change the lambda to take a pair<int,int>&
, then the concept check passes, but the template will fail to instantiate correctly. It’s easy to see why when you look at a typical for_each
implementation:
template<InputIterator I, Semiregular F> requires Function<F, ValueType<I>> F for_each(I first, I last, F f) { for(; first != last; ++first) f(*first); return f; }
The lambda is called with *first
which has type pair<int&,int&>
, but that doesn’t convert to pair<int,int>&
. Gah!!!
The most galling bit is that the code we wrote above — the code with the lambda that takes the reference type — works just fine if we simply delete the requires Function<F, ValueType<I>>
constraint. Clearly something is wrong with the constraints, the concepts, or our expectations.
I should add that the problem is not specific to the zip
view. Any sequence with a proxy reference type has this problem, vector<bool>
included. If we just slap these constraints on the existing algorithms, some code that works today will break, and the only “fix” would be to stop using the standard algorithms. 🙁
3. Permutability of Move-Only Types
Unfortunately, the problems don’t end there. The sort
algorithm requires a sequence to be permutable; that is, you should be able to shuffle its elements around. And since it should support move-only types, that means that the sequence’s iterators should be indirectly-movable. The Palo Alto TR has this to say about it:
The
IndirectlyMovable
andIndirectlyCopyable
concepts describe copy and move relationships between the values of an input iterator,I
, and an output iteratorOut
. For an output iteratorout
and an input iteratorin
, their syntactic requirements expand to:
IndirectlyMovable
requires*out = move(*in)
But what if *in
returns a proxy? Then move(*in)
is moving the proxy, not the object to which the proxy refers. In the case of sorting a zip view, we’re trying to move a (temporary) pair<T&,U&>
into a pair<T&,U&>
. As with issue (1), that won’t work at all for move-only types. But you would probably fail before that, at the sort
requires clause, because of issue (2). Sheesh!
Summary, For Now…
Even though the Palo Alto TR lifts the over-constraining requirement that ForwardIterator
s return real references, the proxy iterator problem remains. On the one hand, it says that proxy iterators are OK. On the other hand, some interesting proxy iterators fail to model the Iterator
concept or satisfy the algorithm constraints, and those that do don’t have the right semantics or performance characteristics. What are our options?
- The
zip
view,vector<bool>
, and its ilk are useful, but are not legitimate containers and ranges, and the STL can’t support them, full stop; or - The iterator concepts (and probably the algorithm constraints) as specified in the Palo Alto TR need to be tweaked somehow to support proxy iterators, and some algorithm implementations probably need to change, too; or
- The language needs to change to better support proxy references (an idea from Sean Parent); or
- Something else.
I really don’t like option (1); there are too many interesting forward iterators that can’t return true references, and I’m tired of doing without. I have some rudimentary ideas about option (2) that I plan to describe in my next post. Option (3) can’t be ruled out, but IANALL (I Am Not A Language Lawyer) and have no idea what would be involved. It’s clear that with C++17 shaping up, and with the Concepts Lite TR finally reaching PDTS status
I’d agree with option 3) ( provided to be feasible ), because this phenomenon does not occur only with iterators, but everytime a programmer is looking for an “augmented” reference semantics ( like viewing a
std::pair<U,V>&
as astd::pair<U&,V&>
, anstd::vector<Derived*>&
asstd::vector<Base*>&
, etc… etc… eg. whenever subsitutability is technically possible but non trivially implementable or has non trivial sideeffects ).One option could be to allow classes to “inherit” from references and behave like references :
where the
T&
acts like a pure abstract interface with respect toT
‘s public members ( but no check is performed until bounded to some concreteT&
), but with the same aliasing/memory rules of references ( eg. the compiler should not create vtables when not needed, and inlining should be favaroed somehow )This is the essential gist of the idea of Sean Parent. I think it’s intriguing, but I don’t have the language designer chops to evaluate it. It would certainly necessitate changes to template type deduction, overload resolution,
auto
anddecltype
, and probably lots more. It’s a big and scary change.by the way, when you say ( in “1. Values and References” ) that “it only works if T and U are copyable! And even when they’re not, it’s clear that copying is not the behavior one would expect when using *it to initialize a const reference”
then, I’ d say that neither moving is:
when I see code like “value_type const& v = *forward_iter;” I read it as “let v be an alias for the ( /some real existing ) element referred by forward_iter”; so moving that element would certainly not be the right thing to do anyway, IMHO.
And, this suggests a possible way of generalizing references that does not involve chaging overloading/decltype/etc… rules, but just the temporaries-to-references life-time bounding rules. Let me exaplain,
taking the above semantics of forward-iterator-to-reference conversion as correct, we could just require that the expression
value_type const& v = *forward_iter;
1) retains its meaning only up to the lifetime of the object v is bounded to
2) that v bounds not just to temporaries of type value_type ( as currently is ) but also to temporaries of type “inheriting” from value_type&.
For example, in the zip case, when T,V are copyable the usual conversion is used. If T or V are movable the pair is converted to a pair proxy 1) moving its member, 2) inheriting ( and hence bounding to ) pair<T,V>& and 3) re-moving back the elements when destroyed ( yes, 2) may require tuning the conversion rules and 3) will require noexcept destructors, not a big deal though ).
thinking about it ( sorry for the double post 🙂 ),
if the view above is correct, we don’t even need to change reference lifetime rules.
We could just introduce a new parallel hierarchy of iterator concepts ( where A<-B means A is a refinement of B )
ForwardIterator <- TransactionalForwardIterator
BidrectionalIterator <- TransactionalBidrectionalIterator
…
where the transactional concept simply requires that whenever the result of the conversion reference_type -> value_type const& is a temporary no more such conversions should occur ( for a given iterator ) up to that temporary lifetime.
For example, suppose we’re given a random access mutable sequence of non negative numbers, and we want a lazy view of squares of that sequence. Clearly, as of now that view cannot even expose forward iterators, but it do can expose transactional read/write random access iterators, used as
{ // some scope
value_type const& v = *iter; // creates a temporary of value_type == squared_proxy, having a member value initialized to iter.base().value * iter.base().value
// do something to v (aka on the square stored in the temporary )
} // here the temporary dies, setting iter.base().value to sqrt(temporary.value) in its destructor
note that, unless I’m missing something ( and I surely can miss something 🙂 ) standard algorithms should be implementable in such a way to work on such “transactional” iterators, hence being backward compatible with the refined hierarchy of old iterator concepts.
Something similar is already considered in the Committee: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4173.pdf
I wonder if this “operator dot” would satisfy the needs of iterator proxies.
It wouldn’t appear so to me. Consider this:
The idea would be for
T
to be deduced asbool
, even though the expression*v.begin()
returns a temporarybool_proxy
object. This doesn’t really have anything to do with operator dot as far as I can see.Very nice post, can’t wait to hear your thoughts about how to tweak the iterator concepts and algorithm constraints. Proxy iterators have to be fixed once and for all, they are way to useful to be second class citizens. There is also the problem of iterating over a vector bool using range-based for:
for (auto i : vec_bool) { i = false; }
For any other vector, its elements won’t be modified; one needs to use auto&& i to take a reference. But for vector bool i will be a proxy object, and this will actually modify the vector elements. For proxies to be truly first class, this huge inconsistency has to be fixed too somehow.
Another thing I also find annoying is that a transformed view has to return input iterators. It is just nuts, but everyone knows it already, so I hope it will be fixed too.
Huh, that never occurred to me. I’m not sure if there is a library fix for that. I think we would need Sean’s language change.
Yup!
Option 2 is absolutely the right solution, IMO.
Option 1 is just bad. Zipping two ranges together and doing interesting things is just so incredibly useful. For my range library, the guiding example for my concept design was
sort(zip(r1, r2)); // sort r1 and r2 combined
This comes up again and again on stackoverflow. The suggested solution is usually something along the lines of “create a vector of pairs of pointers, sort that” or “create a vector of indices, sort that”.
I didn’t get the concepts right, though, because of the move-only problem you pointed out, so that is something that needs to be looked into more. Possibly a change to how std::move works, so that a move of a tuple of references does the right thing. I’m not sure.
Option 3 might be worth exploring. Built-in references are very weird entities in C++, and a way to create things that are more like them might be worthwhile. Nothing comes immediately to mind, though.
Yes, this was the example that motivated me. As of a few weeks ago, range-v3 can sort a zip view, even when the elements are move-only. I’ll describe my approach in the next post. Then I want to hear your thoughts.
Can we create a pair_ref<T,U> that is basically pair<T&,U&> with custom move/swap implementations and is copyable to pair<T,U> ?
You’re getting warmer!
The ValueType issue shows a problem we are going to see more of with the introduction of Concepts. They are super useful, but there will be a repeated problem with overconstraining templates. In this example there’s just no reason to specify the ValueType parameter on the callable, but in an attempt to communicate requirements to the user we’ve accidentally prevented legitimate use cases. I anticipate a lot more articles about this issue in the future.
Is the move issue actually a problem with std::pair and std::tuple rather than the concept of proxies? I can pretty easily whip up my own pair class that defines a move assignment operator that correctly moves it’s contents. This issue doesn’t seem like a problem of concepts since the concept is just defining what the code does, and any proxies involved have to conform.
Concepts will over-constrain in some cases, but it should be rare, and in those cases, it will be to ensure that operations are principled and sound, and so that implementers have more freedom.
In this case, it’s very important that the concept check enforces that the function is callable in the way the function body calls it. Otherwise, you’ll get nasty errors from within the body of
for_each
instead of a readable error at the bogus call site. The question is how to formulate the concept check to accommodate proxy iterators.Awesome post (again). Thank you. You seem to be able to tease out and make concrete some of the issues I’ve had with C++ since the STL began. So much power… but there’s this massive hole where proxies should be.
Having come from Objective-C and Smalltalk where I could amazing freaking things with proxies and views to massively simplify my code and solve complex problems with relative aplomb, I find C++ to have this horrible need to stop all of that… some core failure to support the fundamentals required to enable proxies.
I’m just not smart enough to solve these issues – but I can say without hesitation that they make my life suck and complicate the hell out of code (or at least require generating custom solutions over & over) because I can’t just use a proxy / view to accomplish my goals.
Keep up the great work. I’m psyched to see how concepts lite will evolve into something that rather than being a straight jacket, becomes a sensible framework that liberates the standard library into becoming more – rather than less – powerful.
The requirements on
for_each
,Function<F, ValueType<I>>
, seem very wrong to me, especially sincefor_each
is often used to modify the elements of a container, or observing, which means passing by reference. I would thinkFunction<F, ReferenceType<I>>
should be more accurate. Looking through the Palo Alto TR, the assumption thatValueType<I>
can be used instead ofReferenceType<I>
seems pervasive and I don’t see any justification. Perhaps it’s an oversight.“Permutability of Move-Only Types […] But what if *in returns a proxy?”
Maybe
std::pair
isn’t a good proxy. How about a type with anoperator=
defined such that, when moved, the underlying value gets moved, or with an implicit conversion operator declared with a&&
qualifier to move the values?I’m still not an expert on Concepts Lite, but in my understanding (which could be wrong!), when you say, “
requires Foo<T>
“, then ifT
is a reference, it is checked exactly. If it’s not, it’s as if you had saidT &
. So in that sense, constrainingfor_each
withFunction<F, ValueType<I>>
doesn’t prohibit the use of functions that mutate the values.Like the guy who suggested a
pair_ref
type above, you’re warm. But this is hackish and undisciplined until there is a formal, enforceable relationship between the value type and the reference type. Algorithm implementers need to know what expressions are guaranteed to be valid.I must be missing something as far as calling std::sort on lazily-evaluated zip iterators is concerned: I don’t see any way it makes sense to do that. The iterators are lazily evaluated and therefore don’t belong to a container to sort.
The semantics of sorting a
zip
view are clear. Imagine copying the view into avector<pair<T,U>>
, sorting that, and then copying the elements element-wise back into thezip
view. Since the view is only storing references to elements stored elsewhere, the sorted values would get written through.That’s the semantics. There is no need to create the
vector<pair<T,U>>
. Thezip
view can be sorted directly. The primitive operations —operator<
, move, swap — can all be defined for azip
view’s reference and value types. It just takes some thought.D’s Phobos library seems to have a workable solution to this problem (I’m not a D-expert). I was curious why their library could do this easily and this was the answer I got: #post-leoihj:241q7t:241:40digitalmars.com" rel="nofollow ugc">http://forum.dlang.org/thread/#post-leoihj:241q7t:241:40digitalmars.com
It sounds like operator= is something controlled by the range, rather than the underlying elements, so your zip::view woudl know how to assign or swap in terms of the underlying individual ranges.
C++ has something similar with
iter_swap
but it is not sufficient, underspecified, and not required to be used by any of the algorithms besidesreverse
. But the basic idea is the same: give the range (or the iterator) some say in the question of how values of the range are to be manipulated.but in my understanding (which could be wrong!), when you say, “requires Foo< T>“, then if T is a reference, it is checked exactly. […] constraining for_each with Function<F, ValueType> doesn’t prohibit the use of functions that mutate the values.
That agrees with my reading as well, although I feel it worth noting that constraining it with
Function<F, ReferenceType< I>>
would not prohibit functions that pass by value. However, it defines theFunction
concept like this:concept Function =
// [...]
requires callable(F f, Args args...) {
ResultType<F, Args...> == { f(args...) };
// [...]
}
};
I notice that the arguments aren’t perfectly forwarded, so in fact if I had a function that could only take an rvalue reference, it would not meet the
callable
requirement because{ f(args...) }
would fail to compile sinceargs...
decays to references. Even an identity function wouldn’t conform sinceResultType<Id(X&&)> == X&&
and{ id(x) } == X&
.But if we assume that’s an oversight as well or that
{ f(args..) }
implicitly perfect forwards, then we have the opposite problem:f
doesn’t meet thecallable
requirement if it accepts values by non-const reference and is passed aValueType
because the expression type,std::result_of_t<F(ValueType&&)>
, would fail to compile.So if it doesn’t perfect forward, then
Function<F, ValueType>
would not restrict passing by reference, but it would restrict perfectly valid code involving a pass-by-rvalue function and move iterators. If it does perfect forward, then valid code that requires pass-by-reference would be restricted. If I’m right, no matter what way you look at it, the constraint should beFunction<F, ReferenceType>
and the axiom should perfectly forward its arguments.Oops, I meant this as a response to http://104.154.63.30/2015/01/28/to-be-or-not-to-be-an-iterator/#comment-110303
I have two questions:
1. Why ValueType for the zip iterator needs to be std::pair<int,int> insted of pair<int&, int&>?
2. Could you provide us a link to Sean Parent proxy language change description if it is published?
Think of it from the perspective of
std::sort
, which wants to move elements around. That doesn’t just mean swapping elements, but moving elements into temporary storage, and then moving them back. The temporary storage is one or more objects of the range’s value type. If you want to move elements out of azip
view, you actually need to move the elements, not just references to the elements. Try it an you’ll see. The value type needs to bepair<int,int>
, notpair<int&,int&>
or else the semantics come out all wrong.Aside: I know Boost’s
zip_iterator
usespair<int&,int&>
as the value type. That would be wrong ifstd::sort
worked with proxy reference types. It doesn’t, so nobody is complaining.It’s not published anywhere, sorry.
Ok, I see it now. But does that mean we actually need to separate ReferenceType concept from the ValueType concept to support proxy iteratiors. I mean that we should have:
ValueType – used to declare a temprary storage for copy of the elements
ReferenceType – used to swap, and modyfy elements (default ValueType&)
ConstReferenceType – used to create a view for the element. (default ValueType const&)
There is really nothing new in above statment. The C++98 STL was aware of the need to separate this concepts, and the typedefs from allocators was used inside of container.
For the discussed zip iterators, the concept would be as follows:
ValueType – pair<int, int>
ReferenceType – pair<int&, int&>
ConstReferenceType – pair
And for vector bool:
ValueType – bool
ReferenceType – bit_reference
ConstReferenceType – const_bit_reference
Just add ability to swap temporary pairs of references and you are done.
Now we need to change a requirements of container a bit. For example for_each shall use Function<ReferenceType>, while find_if Function<ConstReferenceType>.
Something like that, yeah, but the callability requirements get a little more complicated than that. For example, a QuickSort might move an element into a local value (the pivot), and then do:
So, you have to take care of asymmetric calls like this to the comparison function. The algorithm requirements can’t just check
Function<Cmp, Ref<I>, Ref<I>>
, see? The rabbit hole goes very deep…I think that it should be Function<Cmp, CRef, CRef>. But I understand your point. We need something like IterComparator<Cmp, I, J> that would check if all combinations:
Function<Cmp, X, Y>
Where X is [ValueType const&, ConstReferenceType] and
Y = [ValueType const&, ConstReferenceType]. And set of types for X and Y would contain only ValueType const& for TrivialIterators.
Please let me know if I am just trying to extract from you the text of upcoming post.
Or rather the ConstReferenceType for the iterator should be implictly constructible from both ValueType const& and RerferenceType. That means that the ConstReferenceType for vector of bool shall be const bool, but pair of const references works for zip.
Pingback: Learn and let learn | Writing 201: The Rhetoric of Blogging
I think the problem, at least when dealing with forward iterators, relies on thinking about “ranges” as a two layered thing: the container and the iterator.
Anything out of this couple causes trouble, because we have actually three things, the container (optional for generators), the range, but in the middle is the sequence, which is what the iterators shows.
What about if each layer has its own type?
We don’t need the
sequence_type
actually (we don’t need a new member toiterator_trais
).If a STL algorithm needs local storage, it can assigns what
*it
returns to a newvalue_type
object. It’s the only situation thevalue_type
needs to be used. The reference must be explicitely convertible tovalue_type
, and must allow assignments ofvalue_type
objects.I have added the “explicitely convertible” requirement to avoid pitfalls like issue (1). Since the idea is to have a storage type, it’s the only situation you need a copy (the big-view::zip problem of issue (1)). If user code explicitely cast the
reference
tovalue_type
is because he wants to. It can be implicitely convertible though.For the
for_each
case, the concept requirement will be the operator can receiveconst remove_cv_t<reference>&
objects, like the STL’s. Thereference
is what actually defines the type of the sequence type; what the user sees. Thevalue_type
is just for local storage!About issue (3), the
std::pair<T&, U&>
isn’t a goodreference
type according to the semantics ofzip
, because it is not a proxy object (it doesn’t act like a proxy with the pretended behaviour, but like a reference transport). It will need to provide its own overloads ofoperator=
to move the proxied objects.In short
view::zip
?std::vector<bool>
?