iterador - stl c++ español

¿Se permiten end+1 iteradores para std:: string?

Question

¿Es válido crear un iterador para end(str)+1 para std::string ?
Y si no lo es, ¿por qué no?

Esta pregunta está restringida a C ++ 11 y versiones posteriores, porque mientras los datos anteriores a C ++ 11 ya estaban almacenados en un bloque continuo en cualquiera de las implementaciones de juguetes de POC que no eran raras, los datos no tenían que ser almacenados de esa manera.
Y creo que eso podría hacer toda la diferencia.

La diferencia significativa entre std::string y cualquier otro contenedor estándar sobre el que especulo es que siempre contiene un elemento más que su size , el terminador cero, para cumplir los requisitos de .c_str() .

21.4.7.1 accesores de cadena básica [string.accessors]

const charT* c_str() const noexcept;
const charT* data() const noexcept;

1 Devuelve: un puntero p tal que p + i == &operator[](i) para cada i en [0,size()] .
2 Complejidad: tiempo constante.
3 Requiere: El programa no alterará ninguno de los valores almacenados en la matriz de caracteres.

Aún así, aunque debería garantizar que dicha expresión sea válida, por lo que respecta a la coherencia y la interoperabilidad con las cadenas terminadas en cero, el único párrafo que encontré arroja dudas al respecto:

21.4.1 requisitos generales de la cadena básica [string.require]

4 Los objetos de tipo char en un objeto basic_string se almacenarán de forma contigua. Es decir, para cualquier objeto basic_string s , la identidad &*(s.begin() + n) == &*s.begin() + n se mantendrá para todos los valores de n tales que 0 <= n < s.size() .

(Todas las citas son del borrador final de C ++ 14 (n3936)).

Relacionado: ¿ Legal para sobrescribir el terminador nulo de std :: string?

Answer 1

Devuelve: Un puntero p tal que p + i == &operator[](i) para cada i en [0,size()] .

std::string::operator[](size_type i) se especifica para devolver "una referencia a un objeto de tipo charT con el valor charT() cuando i == size() , por lo que sabemos que ese puntero apunta a un objeto.

5.7 indica que "Para los fines de [operadores + y -], un puntero a un objeto que no es una matriz se comporta igual que un puntero al primer elemento de una matriz de longitud uno con el tipo del objeto como su tipo de elemento".

Por lo tanto, tenemos un objeto que no es de matriz y la especificación garantiza que el puntero que se encuentre más allá de él será representable. Así que sabemos que std::addressof(*end(str)) + 1 tiene que ser representable.

Sin embargo, eso no es una garantía en std::string::iterator , y no existe tal garantía en ninguna parte de la especificación, lo que lo hace un comportamiento indefinido.

(Tenga en cuenta que esto no es lo mismo que ''mal formado''. *end(str) + 1 en realidad está bien formado).

Los iteradores pueden e implementan la lógica de verificación que produce varios errores cuando hace cosas como incrementar el iterador end() . De hecho, esto es lo que hacen los iteradores de depuración de Visual Studios con end(str) + 1 .

#define _ITERATOR_DEBUG_LEVEL 2
#include <string>
#include <iterator>
int main() {
std::string s = "ssssssss";
auto x = std::end(s) + 1; // produces debug dialog, aborts program if skipped
}

Y si no lo es, ¿por qué no?

por coherencia e interoperabilidad con cadenas terminadas en cero, si no más

C ++ especifica algunas cosas específicas para la compatibilidad con C, pero dicha compatibilidad hacia atrás se limita a admitir cosas que realmente pueden escribirse en C. C ++ no necesariamente intenta tomar la semántica de C y hacer que las nuevas construcciones se comporten de manera análoga. ¿Debería std::vector decay a un iterador solo para ser consistente con el comportamiento de decaimiento de la matriz de C?

Yo diría que end(std) + 1 se deja como comportamiento indefinido porque no tiene ningún valor intentar restringir std::string iteradores std::string esta manera. No hay un código C heredado que haga esto con lo que C ++ debe ser compatible y se debe evitar que el código nuevo lo haga.

Debe evitarse que el nuevo código confíe en él ... ¿por qué? [...] ¿Qué es lo que no te permite comprarte en teoría y cómo se ve eso en la práctica?

No permitirlo significa que las implementaciones no tienen que soportar la complejidad agregada, la complejidad que proporciona un valor demostrado cero.

De hecho, me parece que soportar end(str) + 1 tiene un valor negativo, ya que el código que intenta usarlo esencialmente creará el mismo problema que el código C que no puede determinar cuándo se debe tener en cuenta el terminador nulo o no. C tiene suficiente error de un tamaño de búfer para ambos idiomas.

Answer 2

A std::basic_string<???> es un contenedor sobre sus elementos. Sus elementos no incluyen el nulo final que se agrega implícitamente (puede incluir nulos incrustados).

Esto tiene mucho sentido: "para cada carácter en esta cadena" probablemente no debería devolver el ''/0'' , ya que es realmente un detalle de implementación para la compatibilidad con las API de estilo C.

Las reglas de iterador para contenedores se basaron en contenedores que no empujan un elemento adicional al final. Modificarlos para std::basic_string<???> sin motivación es cuestionable; uno solo debe romper un patrón de trabajo si hay una recompensa.

Hay muchas razones para pensar que los punteros a .data() y .data() + .size() + 1 están permitidos (podría imaginar una interpretación retorcida de la norma que haría que no esté permitido). Por lo tanto, si realmente necesita iteradores de solo lectura en el contenido de un std::string , puede usar los elementos de puntero a const (que, después de todo, son una especie de iterador).

Si quiere editables, entonces no, no hay manera de obtener un iterador válido hasta el último. Tampoco puede obtener una referencia no const al nulo final legalmente. De hecho, tal acceso es claramente una mala idea; Si cambia el valor de ese elemento, rompe la invariable terminación nula std::basic_string .

Para que haya un iterador a uno más allá del final, los iteradores const y non-const para el contenedor tendrían que tener un rango válido diferente, o un iterador no constante para el último elemento que puede ser referenciado pero no escrito a debe existir.

Me estremezco al hacer que estas palabras estándar sean estancas.

std::basic_string ya es un desastre. Hacerlo aún más extraño conduciría a errores estándar y tendría un costo no trivial. El beneficio es realmente bajo; en los pocos casos en los que quiera acceder a dicho nulo final en un rango de iteradores, puede usar .data() y usar los punteros resultantes como iteradores.

Answer 3

TL; DR: s.end() + 1 es un comportamiento indefinido.

std::string es una bestia extraña, principalmente por razones históricas:

1. Intenta traer compatibilidad con C, donde se sabe que existe un carácter /0 adicional más allá de la longitud informada por strlen .
2. Fue diseñado con una interfaz basada en índices.
3. Como una idea posterior, cuando se combinó en la biblioteca estándar con el resto del código STL, se agregó una interfaz basada en iteradores.

Esto llevó a std::string , en C ++ 03, al número 103 de funciones miembro , y desde entonces se agregaron algunas.

Por lo tanto, se deben esperar discrepancias entre los diferentes métodos.

Ya en la interfaz basada en índice aparecen discrepancias:

§21.4.5 [string.access]

const_reference operator[](size_type pos) const;
reference operator[](size_type pos);

1 / Requiere: pos <= size()

const_reference at(size_type pos) const; reference at(size_type pos);

5 / Lanza: out_of_range si pos >= size()

Sí, has leído este derecho, s[s.size()] devuelve una referencia a un carácter NUL mientras que s.at(s.size()) lanza una excepción out_of_range . Si alguien le dice que reemplace todos los usos del operator[] por at porque son más seguros, tenga cuidado con la trampa de string ...

Entonces, ¿qué pasa con los iteradores?

§21.4.3 [string.iterators]

iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cend() const noexcept;

2 / Devoluciones: Un iterador que es el valor pasado-final .

Maravillosamente sosa

Así que tenemos que referirnos a otros párrafos. Un puntero es ofrecido por

§21.4 [basic.string]

3 / Los iteradores admitidos por basic_string son iteradores de acceso aleatorio (24.2.7).

mientras que §17.6 [requisitos] parece carecer de cualquier cosa relacionada. Por lo tanto, los iteradores de cadenas son simples iteradores antiguos (probablemente puedas sentir a dónde va esto ... pero como hemos llegado hasta aquí, vamos hasta el final).

Esto nos lleva a:

24.2.1 [iterator.requirements.general]

5 / Así como un puntero regular a una matriz garantiza que hay un valor de puntero que apunta más allá del último elemento de la matriz, así para cualquier tipo de iterador hay un valor de iterador que apunta más allá del último elemento de una secuencia correspondiente. Estos valores se denominan valores pasados ​​al final . Los valores de un iterador i para los que se define la expresión *i se denominan inhabilitables. La biblioteca nunca asume que los valores pasados ​​al final son inhabilitables. [...]

Entonces, *s.end() está mal formado.

24.2.3 [input.iterators]

2 / Tabla 107 - Requisitos del iterador de entrada (además del iterador)

Enumere las condiciones previas a ++r y r++ que no pueda hacerse referencia.

Ni los iteradores hacia adelante, los iteradores bidireccionales ni el iterador aleatorio levantan esta restricción (y todos indican que heredan las restricciones de su predecesor).

Además, para completar, en 24.2.7 [random.access.iterators] , Tabla 111 - Requisitos del iterador de acceso aleatorio (además del iterador bidireccional) enumera la siguiente semántica operacional:

• r += n es equivalente a [inc | dec] rememting r n veces
• a + n y n + a son equivalentes a copiar a y luego aplicar += n a la copia

y de manera similar para -= n y - n .

Por s.end() + 1 tanto, s.end() + 1 es un comportamiento indefinido.