¿Las categorías de iterador de C ++ prohíben escribir un adaptador de iterador UTF-8?

8

He estado trabajando en un adaptador iterador UTF-8. Con lo cual, me refiero a un adaptador que convierte un iterador en una secuencia charo unsigned charen un iterador en una char32_tsecuencia. Mi trabajo aquí se inspiró en este iterador que encontré en línea .

Sin embargo, cuando miré a través del estándar cuando comencé mi propia implementación, llegué a una conclusión: no parece posible implementar dicho adaptador mientras sigo cumpliendo con los requisitos que C ++ impone a los iteradores.

Por ejemplo, ¿podría crear un iterador UTF-8 que satisfaga los requisitos de InputIterator? Sí, pero solo mientras el iterador que se le dé no sea en sí un InputIterator. ¿Por qué?

Porque InputIterator requiere la capacidad de desreferenciar el mismo iterador más de una vez. También puede desreferenciar varias copias de ese iterador, siempre que todas se comparen igual.

Por supuesto, la desreferenciación de un adaptador de iterador UTF-8 requiere tanto la desreferenciación como el incremento potencial del iterador base. Y si ese iterador es un InputIterator, entonces no puede recuperar el valor original después de incrementarlo. Y el hecho de que las copias tengan que funcionar significa que no puede almacenar localmente un char32_tque represente el valor previamente descodificado. Podrías haber hecho esto:

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, está bien, así que no puedes usar InputIterators. ¿Pero qué hay de ForwardIterator? ¿Es posible crear un adaptador ForwardIterator que pueda adaptar ForwardIterators sobre secuencias de caracteres UTF-8?

Eso también es problemático, porque *itse requiere la operación para producir value_type&o const value_type&. Los InputIterators pueden escupir cualquier cosa que sea convertible a value_type, pero ForwardIteratorse requiere a para proporcionar una referencia real [forward.iterators] /1.3:

si Xes un iterador mutable, referencees una referencia a T; si Xes un iterador constante, referencees una referencia aconst T

El único recurso aquí es que cada uno de estos iteradores lleve consigo a char32_t, que existe únicamente para proporcionar el almacenamiento para esa referencia. E incluso entonces, ese valor tendrá que actualizarse cada vez que la instancia del iterador se incremente y se desreferencia. Esto invalida efectivamente la referencia anterior, y el estándar no lo permite explícitamente (la invalidación solo puede ocurrir cuando se destruye un iterador, o si el contenedor lo dice).

El código mencionado anteriormente que encontré en línea no es válido debido a esto, ya que devuelve un uint32_t(escrito antes de C ++ 11) por valor en lugar de una referencia adecuada.

¿Hay algún recurso aquí? ¿He pasado por alto algo en el estándar o alguna técnica de implementación que podría usar para evitar estos problemas? ¿O simplemente esto no es posible con la redacción actual del estándar?

Nota: lo extraño es que parece posible escribir un OutputIterator conforme para la conversión UTF-8. Es decir, un tipo que toma char32_ty escribe UTF-8 en un charo unsigned charOutputIterator.

Nicol Bolas
fuente
3
Es bien sabido que la redacción de ForwardIteratorno encaja bien con ningún tipo de iteradores proxy , como los que hicieron vector<bool>posible. Hubo un artículo bien conocido escrito en 1999 por Herb Sutter que explicaba por qué se hizo esa determinación. En los tiempos modernos, hubo una tendencia a repensar este tema. Encuentro uno escrito por Eric Niebler . Puede haber más; incluso podría haber algunos escritos por el propio Herb Sutter, en algunas propuestas de C ++.
rwong
Con InputIterator, ¿no puede leer el caché antes de desreferenciar el iterador?
user253751
@immibis: Um, ¿qué caché lees? Leer desde el iterador de entrada antes de que el usuario realmente elimine las referencias podría hacer que acceda a iteradores no válidos, ya que un iterador no necesariamente sabe dónde está el final del rango. Entonces, si incrementa un iterador, eso no significa que esté bien desreferenciarlo. Además, recuerde el punto que hice al copiar InputIterators: si desreferencia dos copias del mismo iterador de entrada, se supone que debe obtener el mismo valor.
Nicol Bolas

Respuestas:

2

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.

Jerry Coffin
fuente