c++ - metodos - ordenamiento shell python

¿Hay alguna forma de implementar el método de inserción para un vector compatible con los estándares?

Question

En primer lugar, supongamos que A es un tipo con:

• Un constructor de copia potencialmente lanzado / operador de asignación.
• No mover constructor / asignación.

Este es un ejemplo común de un tipo C ++ 03 RAII. Ahora permítanme citar el estándar C ++ 14 (partes irrelevantes cortadas):

§23.2.1 Requisitos generales de contenedores

¹¹ A menos que se especifique lo contrario (ver ... y 23.3.6.5), todos los tipos de contenedores definidos en esta Cláusula cumplen con los siguientes requisitos adicionales:

• si una excepción es lanzada por una función insert() o emplace() al insertar un solo elemento, esa función no tiene efectos.

§23.3.6.5 modificadores vector

iterator insert(const_iterator position, const T& x);
...

¹ Observaciones: Provoca la reasignación si el nuevo tamaño es mayor que la capacidad anterior. Si no ocurre una reasignación, todos los iteradores y las referencias anteriores al punto de inserción seguirán siendo válidos. Si se produce una excepción distinta a la del constructor de copia, mueva el constructor, el operador de asignación o el operador de asignación de movimiento de T o mediante cualquier operación InputIterator , no hay efectos. Si se lanza una excepción al insertar un solo elemento al final y T es CopyInsertable o is_nothrow_move_constructible<T>::value es true , no hay efectos. De lo contrario, si el constructor de movimiento CopyInsertable una CopyInsertable no es CopyInsertable T , los efectos no se especifican.

² Complejidad: la complejidad es lineal en el número de elementos insertados más la distancia hasta el final del vector.

Ahora considera esto:

std::vector<A> v(5);
v.reserve(10);
v.insert(begin() + 2, A());

Claramente estamos insertando un solo elemento, por lo que se aplica §23.2.1 - 11 y la operación se realiza correctamente o v se modifica. §23.3.6.5 no cambia nada sobre esto. La excepción es lanzada por el constructor de copia. No estamos insertando al final. El constructor de movimiento no se utiliza.

Pero ahora considere este posible escenario durante la implementación del inserto suponiendo que no se produce una reasignación :

01234_____ initial state
0123_4____ making space by copying
012_34____ continued
012?34____ continued, but copy operation threw

En este punto, todas las futuras operaciones de copia podrían iniciarse, haciendo imposible restaurar el estado según sea necesario. Ups.

No puedo ver ninguna implementación sin reasignación que permita una seguridad de excepción fuerte. Esto significa que cualquier implementación siempre debe reasignarse cuando se inserta un tipo sin un constructor de movimiento y un constructor de copia de lanzamiento en el medio. Sin embargo:

1. insert(pos, value) vuelve insoportablemente lenta debido a las reasignaciones constantes.
2. El requisito de complejidad no se cumple (la reasignación siempre requiere n operaciones).

3. Se podría argumentar que "provoca la reasignación si el nuevo tamaño es mayor que la capacidad anterior". implica que no se permite la reasignación si el nuevo tamaño no es mayor que la capacidad anterior.

   Para apoyar esto, considere que si una implementación se puede reasignar en cualquier momento, el usuario no tiene forma de saberlo. Esto hace que la garantía de preservar los iteradores ( "Si no se realiza una reasignación, todos los iteradores y las referencias antes del punto de inserción sigan siendo válidos" ) es información inútil, y le hace preguntarse por qué ambas frases se insertaron en el estándar en primer lugar.

1 y 2 son observaciones bastante condenatorias, pero si 3 es cierto, entonces (hasta donde puedo ver) es totalmente imposible cumplir con el estándar.

Entonces, ¿hay alguna forma de implementar el método de inserción para un vector compatible con los estándares? ¿O es un defecto estándar?

Una demostración de este problema se puede ver aquí: http://coliru.stacked-crooked.com/a/afd2e838c34c8fcc

Answer 1

En lo que respecta a mi interpretación del estándar, aquí "A menos que se especifique lo contrario" significa que una vez que se especifique algo relacionado con las excepciones para insert en una cláusula correspondiente para un contenedor en particular, el punto de la lista en §23.2.1 ya no se aplica. .

Si se lanza una excepción distinta a la del constructor de copia [..] de T [..], no hay efectos.

Se indica lo contrario: cuando el constructor de copia de T lanza una excepción, no hay garantía de que la llamada no tenga ningún efecto. El requisito de que

si una excepción es lanzada por una función insert() o emplace() al insertar un solo elemento, esa función no tiene efectos

no es aplicable: §23.3.6.5 especifica "de lo contrario".