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.

  • 3
    It is well known that the wording of ForwardIterator did not fit well with any kind of proxy iterators, such as those that made vector<bool> possible. There was a well known article written in 1999 by Herb Sutter that explained why that determination was made. In modern times, there were a trend of rethinking this issue. I find one written by Eric Niebler. There might be more; there might even be some written by Herb Sutter himself, in some C++ proposals. – rwong Apr 1 '17 at 19:51
  • With InputIterator can't you read the cache in advance of dereferencing the iterator? – immibis Apr 5 '17 at 3:24
  • @immibis: Um, read what cache? Reading from the input iterator before the user actually dereferences it could cause me to access invalid iterators, since an iterator doesn't necessarily know where the end of the range is. So if you increment an iterator, that doesn't mean it's OK to dereference it. Also, remember the point I made about copying InputIterators: If you dereference two copies of the same input iterator, you're supposed to get the same value. – Nicol Bolas Apr 5 '17 at 13:32
up vote 3 down vote accepted

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.