Do C++'s iterator categories forbid writing a UTF-8 iterator adapter?

Question

I've been working on a UTF-8 iterator adapter. By which, I mean an adapter that turns an iterator to a char or unsigned char sequence into an iterator to a char32_t sequence. My work here was inspired by this iterator I found online.

However, as I looked through the standard when I was beginning my own implementation, I came to a realization: it does not appear to be possible to implement such an adaptor while still conforming to the requirements that C++ places on iterators.

For example, could you create a UTF-8 iterator that satisfies the InputIterator requirements? Yes, but only so long as the iterator you are given is not itself an InputIterator. Why?

Because InputIterator requires the ability to dereference the same iterator more than once. You can also dereference multiple copies of that iterator, so long as they all compare equal.

Of course, dereferencing a UTF-8 iterator adaptor requires both dereferencing and potentially incrementing the base iterator. And if that iterator is an InputIterator, then you can't get the original value back after you increment it. And the fact that copies have to work means that you can't locally store a char32_t that represents the previously-decoded value. You could have done this:

auto it = ...
auto it2 = it; //Copies an empty `char32_t`.
*it;           //Accesses base iterator, storing `it.ch`.
*it;           //Doesn't access the base iterator; simply returns `it.ch`.
*it2;          //Cannot access `it.ch`, so must access base iterator.

OK, fine, so you can't use InputIterators. But what about ForwardIterator? Is it possible to create a ForwardIterator adaptor that can adapt ForwardIterators over UTF-8 character sequences?

That is problematic as well, because the operation *it is required to produce value_type& or const value_type&. InputIterators can spit out anything which is convertible to value_type, but a ForwardIterator is required to provide an actual reference [forward.iterators]/1.3:

if X is a mutable iterator, reference is a reference to T ; if X is a constant iterator, reference is a reference to const T

The only recourse here is for every such iterator to carry around a char32_t, which exists solely to provide the storage for that reference. And even then, that value will have to be updated every time the the iterator instance is incremented and dereferenced. This effectively invalidates the old reference, and the standard doesn't explicitly permit that (invalidation can only happen when an iterator is destroyed, or if the container says so).

The aforementioned code I found online isn't valid due to this, as it returns a uint32_t (written pre-C++11) by value rather than a proper reference.

Is there any recourse here? Have I overlooked something in the standard, or some implementation technique I could use to bypass these issues? Or is this simply not possible with the current wording of the standard?

Note: the odd thing is that it seems to be possible to write a conforming OutputIterator for UTF-8 conversion. That is, a type which takes char32_t and writes UTF-8 to a char or unsigned char OutputIterator.

Answer 1

I think the short answer is yes. An iterator adapter that decodes UTF-8 (and more generally, that potentially requires multiple input items to produce a single output item) has to be layered on top of an iterator that models (at least) BidirectionalIterator.

Note that this is assuming you only want a constant iterator (i.e., you only read UTF-8 from the input, not write UTF-8 to the underlying collection). If you want to support writing, things get much uglier in a hurry--changing from one value to another at the UTF-32 level could easily produce a UTF-8 encoding that has a different size, so you'd need to be prepared to insert/delete items in the middle of the underlying collection if you were going to support writing.