Iterators++, Part 1

In the last post, I described the so-called proxy iterator problem: the fact that iterators that return proxy references instead of real references don’t sit comfortably within the STL’s framework. Real, interesting, and useful iterators fall foul of this line, iterators like vector<bool>‘s or like the iterator of the zip view I presented. In this post, I investigate what we could do to bring proxy iterators into the fold — what it means for both the iterator concepts and for the algorithms. Since I’m a library guy, I restrict myself to talking about pure library changes.

Recap

As in the last post, we’ll use the zip view to motivate the discussion. Given two sequences like:

vector<int> x{1,2,3,4};
vector<int> y{9,8,7,6};

…we can create a view by “zipping” the two into one, where each element of the view is a pair of corresponding elements from x and y:

using namespace ranges;
auto rng = view::zip(x, y);

assert(*rng.begin() == make_pair(1,9));

The type of the expression “*rng.begin()” — the range’s reference type — is pair<int&,int&>, and the range’s value type is pair<int,int>. The reference type is an example of a proxy: an object that stands in for another object, or in this case two other objects.

Since both x and y are random access, the resulting zip view should be random access, too. But here we run foul of STL’s “real reference” requirement: for iterators other than input iterators, the expression *it must return a real reference. Why? Good question! The requirement was added sometime while the STL was being standardized. I can only guess it was because the committee didn’t know what it meant to, say, sort or reverse elements that aren’t themselves persistent in memory, and they didn’t know how to communicate to the algorithms that a certain temporary object (the proxy) is a stand-in for a persistent object. (Maybe someone who was around then can confirm or deny.)

The real-reference requirement is quite restrictive. Not only does it mean the zip view can’t be a random access sequence, it also means that you can’t sort or reverse elements through a zip view. It’s also the reason why vector<bool> is not a real container.

But simply dropping the real-reference requirement isn’t enough. We also need to say what it means to sort and reverse sequences that don’t yield real references. In the last post, I described three specific problems relating to constraining and implementing algorithms in the presence of proxy references.

  1. What, if anything, can we say about the relationship between an iterator’s value type and its reference type?
  2. How do we constrain higher-order algorithms like for_each and find_if that take functions that operate on a sequence’s elements?
  3. How do we implement algorithms that must swap and move elements around, like sort?

Let’s take the last one first.

Swapping and Moving Elements

If somebody asked you in a job interview to implement std::reverse, you might write something like this:

template< class BidiIter >
void reverse( BidiIter begin, BidiIter end )
{
    using std::swap;
    for(; begin != end && begin != --end; ++begin)
        swap(*begin, *end);
}

Congratulations, you’re hired. Now, if the interviewer asked you whether this algorithm works on the zip view I just described, what would you say? The answer, as you may have guessed, is no. There is no overload of swap that accepts pair rvalues. Even if there were, we’re on thin ice here with the zip view’s proxy reference type. The default swap implementation looks like this:

template< class T >
void swap( T & t, T & u )
{
    T tmp = move(u);
    u = move(t);
    t = move(tmp);
}

Imagine what happens when T is pair<int&,int&>. The first line doesn’t move any values; tmp just aliases the values referred to by u. The next line stomps the values in u, which mutates tmp because it’s an alias. Then we copy those stomped values back to t. Rather than swapping values, this makes them both equal to t. Oops.

If at this point you’re smugly saying to yourself that pair has its own swap overload that (almost) does the right thing, you’re very smart. Shut up. But if you’re saying that the above is not a standard-conforming reverse implementation because, unlike all the other algorithms, reverse is required to use iter_swap, then very good! That’s the clue to unraveling this whole mess.

iter_swap

iter_swap is a thin wrapper around swap that takes iterators instead of values and swaps the elements they refer to. It’s an exceedingly useless function, since iter_swap(a,b) is pretty much required to just call swap(*a,*b). But what if we allowed it to be a bit smarter? What if iter_swap were a full-fledged customization point that allowed proxied sequences to communicate to the algorithms how their elements should be swapped?

Imagine the zip view’s iterators provided an iter_swap that knew how to truly swap the elements in the underlying sequences. It might look like this:

template< class It1, class It2 >
struct zip_iterator
{
    It1 it1;
    It2 it2;

    /* ... iterator interface here... */

    friend void iter_swap(zip_iterator a, zip_iterator b)
    {
        using std::iter_swap;
        iter_swap(a.it1, b.it1);
        iter_swap(a.it2, b.it2);
    }
};

Now we would implement reverse like this:

template< class BidiIter >
void reverse( BidiIter begin, BidiIter end )
{
    using std::iter_swap;
    for(; begin != end && begin != --end; ++begin)
        iter_swap(begin, end);
}

Voilà! Now reverse works with zip views. That was easy. All that is required is (a) to advertise iter_swap as a customization point, and (b) use iter_swap consistently throughout the standard library, not just in reverse.

iter_move

We haven’t fixed the problem yet. Some algorithms don’t just swap elements; they move them. For instance stable_sort might allocate a temporary buffer and move elements into it while it works. You can’t use iter_swap to move an element into raw storage. But we can use a play from the iter_swap playbook to solve this problem. Let’s make an iter_move customization point that gives iterators a way to communicate how to move values out of the sequence.

iter_move‘s default implementation is almost trivial:

template< class I,
    class R = typename iterator_traits< I >::reference >
conditional_t<
    is_reference< R >::value,
    remove_reference_t< R > &&,
    R >
iter_move( I it )
{
    return move(*it);
}

The only tricky bit is the declaration of the return type. If *it returns a temporary, we just want to return it by value. Otherwise, we want to return it by rvalue reference. If you pass a vector<string>::iterator to iter_move, you get back a string && as you might expect.

How does the zip view implement iter_move? It’s not hard at all:

template< class It1, class It2 >
struct zip_iterator
{
    It1 it1;
    It2 it2;

    /* ... iterator interface here... */

    friend auto iter_move(zip_iterator a)
    {
        using std::iter_move;
        using RRef1 = decltype(iter_move(a.it1));
        using RRef2 = decltype(iter_move(a.it2));
        return pair<RRef1, RRef2>{
            iter_move(a.it1),
            iter_move(a.it2)
        };
    }
};

The algorithms can use iter_move as follows:

// Move an element out of the sequence and into a temporary
using V = typename iterator_traits< I >::value_type;
V tmp = iter_move( it );
// Move the value back into the sequence
*it = move( tmp );

As an aside, this suggests a more general default implementation of iter_swap:

template< class I >
void iter_swap( I a, I b )
{
    using V = typename iterator_traits< I >::value_type;
    V tmp = iter_move( a );
    *a = iter_move( b );
    *b = move( tmp );
}

Now proxy sequences like zip only have to define iter_move and they gets a semantically correct iter_swap for free. It’s analogous to how the default std::swap is defined in terms of std::move. (Doing it this way doesn’t pick up user-defined overloads of swap. That’s bad. There’s a work-around, but it’s beyond the scope of this post.)

For a zip view that has value type pair<T,U> and reference type pair<T&,U&>, the return type of iter_move is pair<T&&,U&&>. Makes perfect sense. Take another look at the default implementation of iter_swap above and satisfy yourself that it correctly swaps zipped elements, even if the underlying sequences have move-only value types.

One final note about iter_move: the implication is that to support proxied sequences, iterators need an extra associated type: the return type of iter_move. We can call it rvalue_reference and put it in iterator_traits alongside value_type and reference.

Alternate Design

I find the above design clean and intuitive. But it raises an interesting question: is it OK that iter_swap(a,b) and swap(*a,*b) might mean different things? Personally I think that’s OK, but let’s imagine for a moment that it’s not. What else could we do?

An obvious alternate design is to overload swap for proxy references to swap the objects they refer to. Let’s imagine we add the following overload to namespace std:

template< class T, class U >
void swap( pair< T&, U& > && a, pair< T&, U& > && b )
{
    swap(a.first, b.first);
    swap(a.second, b.second);
}

With enough SFINAE magic we could further generalize this to support swapping pairs of proxy references, but let’s stick with this. I could live with it.

But as before, this isn’t enough; we would also need to overload move to take a pair<T&,U&> and return a pair<T&&,U&&>. And this is where I start getting uncomfortable, because move is used everywhere and it’s currently not a customization point. How much code is out there that assumes the type of a move expression is &&? What breaks when that’s no longer true?

Purely as a matter of library evolution, overloading move that way for pairs of references is a non-starter because it would be changing the meaning of existing code. We could avoid the problem by changing zip‘s reference type from pair<T&,U&> to magic_proxy_pair< T&, U& > and overloading swap and move on that. magic_proxy_pair would inherit from pair, so most code would be none the wiser. Totally valid design.

Summary, For Now

I’ve run long at the mouth, and I still have two more issues to deal with, so I’ll save them for another post. We’ve covered a lot of ground. With the design suggested above, algorithms can permute elements in proxied sequences with the help of iter_swap and iter_move, and iterators get a brand new associated type called rvalue_reference.

Whether you prefer this design or the other depends on which you find more distasteful:

  1. iter_swap(a,b) can be semantically different than swap(*a,*b), or
  2. move is a customization point that is allowed to return some proxy rvalue reference type.

In the next installment, I’ll describe what we can say about the relationship between an iterator’s value type and its reference type (and now its rvalue reference type), and how we can constrain higher-order algorithms like for_each and find_if.

As always, you can find all code described here in my range-v3 repo on github.

"\e"

27 Replies to “Iterators++, Part 1”

  1. In connection to the problem of putting the requirments on the comparators for the STL that supports proxy iterators. You have mentonied that the requirements of the comparators get really complex because they are required to be callable with the combiation of ValueType const& and LValueReferenceType and RValueRereferenceType for the iterator. I think such complicated requirement is not needed.

    I think that the right solution would be to treat ConstReferenceType as the ViewType for the iterator – that allows you to access the value of the element pointed by the Iterator. This ViewType shall be implictly construtible from ValueType const&, LValueReferenceType and RvalueReferenceType. Within this addition, the requirments of the comparators will again be simple: must be callable with pair of ConstReferenceType. Note that this actually above asumptions are true for TrivalIterators, where above typedefs are references.

      • I dont not think that requirement of common_type for EqualityComparable is right think to do. Lets consider a commong example of comparing a Employee with it SocialSecurityNumber. There is a bijection between this two domains, and the comparision between such objects in domain of SocialSecurityNumbers is mathematically well-sound. Hoever nor Employee shall not be implicity construtible from SocialSecurityNumber (needs additional informat), nor there should be implict conversion from Employee to SocialSecurityNumber (loss of information). I think that this concpet should require an axion that thre is transformation f from T and U commaind domain d. And t < u is equivalent to f(t) < f(u), where < in U is total order.

        Also you would need to somehow provide a common_type for a ValueType and ReferenceType for the iterators, where it cannot be deduced. This may be done via use of common_type, but will impact non iterator related context. Or the ConstReferenceType (ViewType) may be used to provide this type. In the STL algorithms comparators shall not modify the objects, so you need only a view for a value.

        • I mean that for comparator it makes sense that common type of pair(T,U) const& and pair(T&, U&) is pair(T const&, U const&). But in other context returning pair(T,U) would be more fitting, but such solution for STL sort would be not accetable (copy of object for every comparision).

        • Lets consider a commong example of comparing a Employee with it SocialSecurityNumber. There is a bijection between this two domains, and the comparision between such objects in domain of SocialSecurityNumbers is mathematically well-sound.

          Comparing them with a predicate is sound. Comparing them with op== is not sound, because an employee is not a social security number. (Ask one. She’ll tell you!)

          It’s also not practical to hypothesize a domain transformation that make the comparison sound. This constraint needs to be checked by a computer. It needs a procedure. The procedure can’t be: imagine a domain transformation…

          • As I said, the requirment (that is checked by compler) of common type, should be transformed to axiom (that is not checked).

            But there is matter of perspective. I find it usefull to be able to use op== on objects that represents the same entity: I mean that that there is unambiguus one to one mapping between them.

          • Also both Employee and SocialSecurityNumber is reprensentation of real life entity (person). There both artificial, so argument about asking is one is out of place.

            If I have to ways to represent the same real life entity (int and double when in range of both) I should be able to compare them using just ==.

  2. Also I think that the iter_swap shall be required to use a user provided swap, not be impleneted by the with the iter_move. Of course iter_move would still be needed. For some type the customized swap algorithm is much more faster than the one implemented as the three moves, and usually the swap is noxcept in such situations, while move may throw.

    The obvious example: list container from STL that uses a allocated sentinel (do not invalidate the end iterator on move). Two such container may be swapped by swaping pointers to begin and end of the list. But move operations on such container, requires allocation, as the moved-from object must again perform allocation for sentinel node to be in valid state. So moving from custom swap to use of three moves, incurs cost of 3 alloactions, which is not accetable.

    This is acutlly the reason why iter_swap in C++11 was required to use ADL swap. And you zip_iterator may iterate over two vectors of list.

    • Yes, I noted above that implementing iter_swap in terms of iter_move unconditionally would miss user overloads of swap, and that would be bad. The default implementation of iter_swap in range-v3 is more refined. It implements iter_swap in terms of iter_move only if swap(*a,*b) is not a valid expression. You can see that logic is all its awfulness here. (It’s called indirect_swap in range-v3 to avoid accidentally picking up the unconstrained iter_swap in namespace std.)

      • What about the algorithms like sort, that may create a copy of element pointed by iterator into ValueType to create a pivot. In such algorihtms it may be more optional to swap such stored element with element pointed by iterator. It is no problem with TrivialIterators, but in case of ProxyIterators you would need to have ability to use iter_swap on ValueType* and ReferenceType. Otherwise you would need to fallback to less optimal implementation.

        • Fair point, but I’ve implemented all the algorithms in the STL using iter_swap and iter_move, and I’ve never needed to swap a value with a reference. That’s not to say it could never happen, but I don’t design for hypotheticals.

          • Of course, you can use iter_move to move out from iterator to stored value, and move from stored value to assign the iterator, so you can implement all STL algorithms using iter_swap, iter_move. The question is if there was a point when you need to exchange this values (not move it) and swap would be more efficient.

          • The answer is no. I have found no place where the code needs to do iter_swap(&tmp, it). It wouldn’t be hard to add that expression as a requirement for the IndirectlySwappable concept. Satisfying the requirement would require nothing more than a couple of extra overloads of iter_swap.

            There are places where you have a choice about whether to do *a = iter_move(it) or iter_swap(a, it). But here the answer is not cut and dry. For many types, swapping is more expensive than moving, like int. To me, sorting a vector of ints seems like a more important case than sorting a vector of lists. Library design is full of trade-offs.

  3. Pingback: 1p – Eric Niebler: Iterators++, Part 1 – blog.offeryour.com

  4. At some point you also need language support. E.g. if you have both a proxy iterator and a proxy reference with a user-defined value type, you want *it<T> to return a ref<T> and &ref<T> to return an it<T>. This is what libc++ does with vector<bool>.

    But while the language supports constructs like it<T>->fun() to access T‘s member fun(), the equivalent ref<T>.fun() will not compile, unless you implement the full T class interface inside of ref<T>, which is what vector<bool> does.

    However, there are some subtle snags having to do with the fact that if ref<T> has an implicit conversion operator to T, you can run into the limitation that only 1 user-defined conversion is allowed in expressions, so you can’t quite get the ref<T> to behave identically to a true T&.

    To avoid all that, the ideal way out is to overload operator. (IIRC, Sebastian Redl had a proposal for it).

    • Bjarne had a proposal at the last meeting for overloading operator.. It was just a sketch of an idea, but it looked promising. I’m not sure if he or somebody else is planning to follow up.

      The other approach is one suggested to me in private by Sean Parent: allow a type to inherit from T&, thereby making it a true proxy reference. Again, just a sketch of an idea. We haven’t found anybody yet to flesh it out.

      • Bjarne and Gabe’s proposal is extremely similar to the 1991 paper. The same issues are discussed. This time they actually make a few specific choices, but I feel that they do not sufficiently explore the consequences of these choices. Maybe there was more at the meeting itself than there is in the paper. But the examples presented in the paper do not convince me in the least.

        6.1, Pimpl, fails almost completely. It is not a compilation barrier, because the user of the class still needs to see the definition of the Impl object. The trick preserves binary compatibility (except when virtual function calls are involved). It does not prevent the need for recompilation.

        6.2 looks kinda interesting, but would be much better served by a proper mixin feature.

        6.4 scares me and is more an example of how to abuse the operator. Also, when did auto deduction rules change?

        Sean’s idea sounds much more interesting. I’d love to elaborate on that.

  5. correct me if’m wrong, but I don’t think that swapping and moving is the only reason why forward iterators are required to refer to real objects. For example, not much in standard algorithms, but in user code you may still see code expecting a “referential consistency” property , ie that *biter, *++–biter, etc… refer to exactly the same object in a way or the other ( whenever well defined, and provided the originating container, if any, has not mutated ).

    Now, zip_iterator is not a problem here, but there are useful proxy use cases ( like any iterator view based on some bijection with the underlying sequence, or non mutable iterators generating its own sequence, like counting_iterator ) that cannot satisfy such a property as of now, even with a properly implemented iter_swap/move.
    May I ask you to take a look at my comment in your previous blog post concerning an alternative “transactional” iterator concept ? what do you think ?

  6. I tried to make swap(*it, a) (or the equivalent) work in my range library. It was a disaster.

    I like iter_swap and iter_move. It’s a simple approach and should be sufficient, with some smart concept definitions. I didn’t have that simple option in my range library because I had range primitives, so I’d need swap_fronts, swap_backs, and swap_front_back, and that’s not taking into account random-access ranges.

    One incarnation of my library used positions (similar to the cursor/property_map abstraction), where this would have worked, but that library had other issues (like trying to define a filter_range that isn’t a nightmare of usability).

  7. Pingback: Непросмотренные ссылки – 12 | Откомпилируй Это

  8. For std::list::iterator, would you implement iter_move as actually moving the data, or just linking the new node in and destroying the old node (similar question for iter_swap). Or, put another way, will a reference to the target value of iter_move be guaranteed to remain valid and point at the new data?

    • No overloads of iter_move and iter_swap can violate the functions’ post-conditions. They do not invalidate iterators. So they would not try to be clever with manipulating list nodes. They would manipulate the values only. Good question, BTW.

  9. How much code is out there that assumes the type of a move expression is &&?

    Sorry, can you please explain what this means? Are you referring to the parameters? If so, what else would it be and how is this relivant?

    • Given an lvalue o of type T, the type of std::move(o) is T&&. If we were to make std::move a customization point, then the return type could be something else. That is a breaking change that is likely to surprise some users.

  10. About:

    The requirement was added sometime while the STL was being standardized. I can only guess it was because the committee didn’t know what it meant to

    In the famous article of Herb Sutter that you link, in one of the paragraphs it says that:

    Further, both the original STL’s container requirements and the C++ standard’s container requirements are based on the implicit assumption (among others) that dereferencing an iterator both is a constant-time operation and requires negligible time compared to other operations. […] neither of these assumptions is true for a disk-based container or a packed-representation container. […] Further, whenever the proxy object construction and destruction can’t be completely optimized away by the compiler, managing the proxies themselves adds further overhead.

    So, it seems that the main reasons was about the dislike of possible inneficiences when using proxy iterators, and not about its conceptual problems.

  11. Hi Eric,
    Really great work on Ranges library.
    Excellent work Eric !. I really liked it.
    I saw your video on cppcon it was mind-blowing.
    I need your help. I am beginner in C++ with less than 4 years of
    experience. I wanted to learn more about template meta-programming(TMP),
    so that someday I could build a library others can use like Ranges-v3.
    Could you tell me how you started with TMP as a beginner.?
    Any suggestions on books to read ?
    Any online source to practice the same ?
    How to write readable TMP ?
    I find it hard to do TMP!.
    Last question,
    Out of curiosity will modules be part of C++20 ?
    Thanks
    Nithish

Leave a Reply to tkamin Cancel reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.