To Be or Not to Be (an Iterator)

Posted on January 28, 2015 by Eric Niebler — 31 Comments ↓

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 &:

// 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&. 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& 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>. 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> 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 and IndirectlyCopyable concepts describe copy and move relationships between the values of an input iterator, I, and an output iterator Out. For an output iterator out and an input iterator in, 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 ForwardIterators 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 , and a range-ified, concept-ified STL in the works, the time to start making decisions about this stuff is now.

"\e"

31 Replies to “To Be or Not to Be (an Iterator)”

mjanes on January 29, 2015 at 1:02 am said:
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 a std::pair<U&,V&>, an std::vector<Derived*>& as std::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 :
```
template< class T > class Proxy: T& { };
```
where the T& acts like a pure abstract interface with respect to T‘s public members ( but no check is performed until bounded to some concrete T& ), 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 )
Reply ↓
- Eric Niebler on January 29, 2015 at 8:01 am said:
 
 One option could be to allow classes to “inherit” from references and behave like references
 
 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 and decltype, and probably lots more. It’s a big and scary change.
 
 Reply ↓
 - mjanes on January 31, 2015 at 2:22 am said:
 
 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 ).
 
 Reply ↓
 - mjanes on February 2, 2015 at 3:28 am said:
 
 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.
 
 Reply ↓
- Andrzej Krzemieński on February 18, 2015 at 4:19 am said:
 
 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.
 
 Reply ↓
 - Eric Niebler on February 18, 2015 at 10:40 am said:
 It wouldn’t appear so to me. Consider this:
 
 template<typename T> void foo( T & t ) {...} vector<bool> v{true,false,true,false}; foo( *v.begin() );
 
 The idea would be for T to be deduced as bool, even though the expression *v.begin() returns a temporary bool_proxy object. This doesn’t really have anything to do with operator dot as far as I can see.
 Reply ↓
gnzlbg on January 29, 2015 at 1:26 am said:

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.

Reply ↓
- Eric Niebler on January 29, 2015 at 8:06 am said:
  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
  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.
  
  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.
  
  Yup!
  Reply ↓
Sebastian Redl on January 29, 2015 at 4:07 am said:

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.

Reply ↓
- Eric Niebler on January 29, 2015 at 8:11 am said:
  For my range library, the guiding example for my concept design was
  
  sort(zip(r1, r2)); // sort r1 and r2 combined
  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.
  Reply ↓
Sky on January 29, 2015 at 5:51 am said:

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> ?

Reply ↓
- Eric Niebler on January 29, 2015 at 8:12 am said:
 
 You’re getting warmer!
 
 Reply ↓
Jay Miller on January 29, 2015 at 7:53 am said:

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.

Reply ↓
- Eric Niebler on January 29, 2015 at 8:22 am said:
  
  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
  
  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.
  
  Reply ↓
Steve on January 29, 2015 at 8:14 am said:

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.

Reply ↓
Scott Prager on January 29, 2015 at 9:22 am said:

The requirements on for_each, Function<F, ValueType>, seem very wrong to me, especially since for_each is often used to modify the elements of a container, or observing, which means passing by reference. I would think Function<F, ReferenceType> should be more accurate. Looking through the Palo Alto TR, the assumption that ValueType can be used instead of ReferenceType 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 an operator= defined such that, when moved, the underlying value gets moved, or with an implicit conversion operator declared with a && qualifier to move the values?

Reply ↓
- Eric Niebler on January 29, 2015 at 9:32 am said:
 
 The requirements on for_each, Function<F, ValueType>, seem very wrong to me, especially since for_each is often used to modify the elements of a container, or observing, which means passing by reference.
 
 I’m still not an expert on Concepts Lite, but in my understanding (which could be wrong!), when you say, “requires Foo<T>“, then if T is a reference, it is checked exactly. If it’s not, it’s as if you had said T &. So in that sense, constraining for_each with Function<F, ValueType> doesn’t prohibit the use of functions that mutate the values.
 
 Maybe std::pair isn’t a good proxy. How about a type with an operator= defined such that, when moved, the underlying value gets moved, or with an implicit conversion operator declared with a && qualifier to move 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.
 
 Reply ↓
Max Lybbert on January 29, 2015 at 10:31 am said:

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.

Reply ↓
- Eric Niebler on January 29, 2015 at 10:36 am said:
 
 The semantics of sorting a zip view are clear. Imagine copying the view into a vector<pair<T,U>>, sorting that, and then copying the elements element-wise back into the zip 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>>. The zip view can be sorted directly. The primitive operations — operator<, move, swap — can all be defined for a zip view’s reference and value types. It just takes some thought.
 
 Reply ↓
Ben on January 29, 2015 at 10:56 am said:

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.

Reply ↓
- Eric Niebler on January 29, 2015 at 11:03 am said:
  
  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 besides reverse. 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.
  
  Reply ↓
Scott Prager on January 29, 2015 at 11:10 am said:

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> would not prohibit functions that pass by value. However, it defines the Function 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 since args... decays to references. Even an identity function wouldn’t conform since ResultType<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 the callable requirement if it accepts values by non-const reference and is passed a ValueType 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 be Function<F, ReferenceType> and the axiom should perfectly forward its arguments.

Reply ↓
- Scott Prager on January 29, 2015 at 11:11 am said:
 
 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
 
 Reply ↓
tkamin on January 30, 2015 at 1:19 pm said:

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?

Reply ↓
- Eric Niebler on January 30, 2015 at 1:28 pm said:
 Why ValueType for the zip iterator needs to be std::pair<int,int> insted of pair<int&, int&>?
 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 a zip 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 be pair<int,int>, not pair<int&,int&> or else the semantics come out all wrong.
 
 Aside: I know Boost’s zip_iterator uses pair<int&,int&> as the value type. That would be wrong if std::sort worked with proxy reference types. It doesn’t, so nobody is complaining.
 Could you provide us a link to Sean Parent proxy language change description if it is published?
 It’s not published anywhere, sorry.
 Reply ↓
 - tkamin on January 30, 2015 at 1:44 pm said:
 
 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>.
 
 Reply ↓
 - Eric Niebler on January 30, 2015 at 1:51 pm said:
 
 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:
 
 ValueType v = // move element; if( comp( v, *i ) ) // ...
 
 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, Ref>, see? The rabbit hole goes very deep…
 
 Reply ↓
 - tkamin on January 30, 2015 at 2:03 pm said:
 
 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.
 - tkamin on January 30, 2015 at 2:37 pm said:
 
 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
Peregringlk on April 7, 2017 at 8:43 pm said:

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?

“storage” => value_type
sequence => sequence_type (explicitely convertible to value_type)
iterator => reference (sequence_type or sequence_type&)

We don’t need the sequence_type actually (we don’t need a new member to iterator_trais).

If a STL algorithm needs local storage, it can assigns what *it returns to a new value_type object. It’s the only situation the value_type needs to be used. The reference must be explicitely convertible to value_type, and must allow assignments of value_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 to value_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 receive const remove_cv_t<reference>& objects, like the STL’s. The reference is what actually defines the type of the sequence type; what the user sees. The value_type is just for local storage!

About issue (3), the std::pair<T&, U&> isn’t a good reference type according to the semantics of zip, 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 of operator= to move the proxied objects.

In short view::zip?

value_type = pair<U, T>
reference => zip_reference_wrapper<U, T>

std::vector<bool>?

value_type => bool
reference => its proxy type, whatever it is

Reply ↓