library - Posibilidad de implementación de COW std:: string en C++ 11

string c++

Question

Hoy pasé por esta pregunta SO: Legalidad de COW std :: implementación de cadena en C ++ 11

La respuesta más votada (35 votos a favor) para esa pregunta dice:

No está permitido, porque según el estándar 21.4.1 p6, la invalidación de iteradores / referencias solo está permitida para

- como un argumento para cualquier función de biblioteca estándar que toma una referencia a non-const basic_string como un argumento.

- Llamando funciones no constantes, excepto el operador [], at, front, back, begin, rbegin, end y rend.

Para una cadena COW, llamar al operador no constante [] requeriría hacer una copia (y invalidar las referencias), lo cual no está permitido por el párrafo anterior. Por lo tanto, ya no es legal tener una cadena COW en C ++ 11.

Me pregunto si esa justificación es válida o no porque parece que C ++ 03 tiene requisitos similares para la invalidación del iterador de cadenas:

Las referencias, los punteros y los iteradores que se refieren a los elementos de una secuencia de cadena básica pueden ser invalidados por los siguientes usos de ese objeto cadena de cadena básica:

• Como un argumento a funciones no miembros swap () (21.3.7.8), operator >> () (21.3.7.9), y getline () (21.3.7.9).
• Como argumento a basic_string :: swap ().
• Llamando funciones de datos () y c_str ().
• Llamar a funciones no constantes, excepto el operador [] (), at (), begin (), rbegin (), end () y rend ().
• Posteriormente a cualquiera de los usos anteriores, excepto las formas de insert () y erase () que devuelven iteradores, la primera llamada al operador de funciones miembro no const [] (), at (), begin (), rbegin (), end (), o rend ().

Estos no son exactamente los mismos que los de C ++ 11, pero al menos lo mismo para la parte del operator[]() , que la respuesta original tomó como la justificación principal. Así que supongo que, para justificar la ilegalidad de la implementación de COW std :: string en C ++ 11, es necesario citar algunos otros requisitos estándar. Se necesita ayuda aquí.

Esa pregunta de SO ha estado inactiva por más de un año, por lo que he decidido plantear esto como una pregunta separada. Por favor, avíseme si esto es inapropiado y encontraré otra forma de aclarar mis dudas.

Answer 1

El punto clave es el último punto en el estándar C ++ 03. La redacción podría ser mucho más clara, pero la intención es que la primera llamada a [] , at , etc. (pero solo la primera llamada) después de algo que estableció nuevos iteradores (y por lo tanto invalidó los antiguos) podría invalidar a los iteradores, pero solo el primero. La redacción en C ++ 03 fue, de hecho, un truco rápido, insertado en respuesta a los comentarios del organismo nacional francés en el CD2 de C ++ 98. El problema original es simple: considere:

std::string a( "some text" );
std::string b( a );
char& rc = a[2];

En este punto, las modificaciones a través de rc deben afectar a , pero no a b . Sin embargo, si se usa COW, cuando se llama a a[2] , b comparten una representación; para que las escrituras a través de la referencia devuelta no afecten a b , a[2] debe considerarse una "escritura", y se le debe permitir invalidar la referencia. Que es lo que dijo CD2: cualquier llamada a un non-const [] , at , o una de las funciones de begin o end podría invalidar iteradores y referencias. Los comentarios del organismo nacional francés señalaron que esto hacía que a[i] == a[j] no fuera válida, ya que la referencia devuelta por uno de los [] sería invalidada por el otro. El último punto que cita de C ++ 03 se agregó para evitar esto: solo la primera llamada a [] et al. Podría invalidar los iteradores.

No creo que nadie estuviera totalmente feliz con los resultados. La redacción se hizo rápidamente, y si bien la intención fue clara para aquellos que conocían la historia y el problema original, no creo que fuera del todo clara. Además, algunos expertos comenzaron a cuestionar el valor de COW para comenzar, dada la relativa imposibilidad de la propia clase de cadena para detectar confiablemente todas las escrituras. (Si a[i] == a[j] es la expresión completa, no hay escritura. Pero la propia clase de cadena debe suponer que el valor de retorno de a[i] puede resultar en una escritura.) Y en una En el entorno de subprocesos, el costo de administrar el recuento de referencia necesario para copiar y escribir se consideró un costo relativamente alto para algo que normalmente no se necesita. El resultado es que la mayoría de las implementaciones (que admitían subprocesos mucho antes de C ++ 11) se han alejado de COW de todos modos; por lo que sé, la única implementación importante que todavía utiliza COW fue g ++ (pero hubo un error conocido en su implementación de multiproceso) y (quizás) Sun CC (que la última vez que lo miré, fue excesivamente lento, debido a la coste de gestión del contador). Creo que el comité simplemente tomó lo que les parecía la forma más simple de limpiar las cosas, prohibiendo el VAC.

EDITAR:

Algunas aclaraciones más con respecto a por qué una implementación de COW debe invalidar a los iteradores en la primera llamada a [] . Considere una implementación ingenua de VAC. (Simplemente lo llamaré Cadena e ignoraré todos los problemas relacionados con rasgos y asignadores, que no son realmente relevantes aquí. También ignoraré la seguridad de excepciones y subprocesos, solo para hacer las cosas lo más simples posible).

class String
{
    struct StringRep
    {
        int useCount;
        size_t size;
        char* data;
        StringRep( char const* text, size_t size )
            : useCount( 1 )
            , size( size )
            , data( ::operator new( size + 1 ) )
        {
            std::memcpy( data, text, size ):
            data[size] = ''/0'';
        }
        ~StringRep()
        {
            ::operator delete( data );
        }
    };

    StringRep* myRep;
public:
    String( char const* initial_text )
        : myRep( new StringRep( initial_text, strlen( initial_text ) ) )
    {
    }
    String( String const& other )
        : myRep( other.myRep )
    {
        ++ myRep->useCount;
    }
    ~String()
    {
        -- myRep->useCount;
        if ( myRep->useCount == 0 ) {
            delete myRep;
        }
    }
    char& operator[]( size_t index )
    {
        return myRep->data[index];
    }
};

Ahora imagina lo que pasa si escribo:

String a( "some text" );
String b( a );
a[4] = ''-'';

¿Cuál es el valor de b después de esto? (Ejecute el código a mano, si no está seguro).

Obviamente, esto no funciona. La solución es agregar una bandera, bool uncopyable; a StringRep , que se inicializa en false , y para modificar las siguientes funciones:

String::String( String const& other )
{
    if ( other.myRep->uncopyable ) {
        myRep = new StringRep( other.myRep->data, other.myRep->size );
    } else {
        myRep = other.myRep;
        ++ myRep->useCount;
    }
}

char& String::operator[]( size_t index )
{
    if ( myRep->useCount > 1 ) {
        -- myRep->useCount;
        myRep = new StringRep( myRep->data, myRep->size );
    }
    myRep->uncopyable = true;
    return myRep->data[index];
}

Esto significa, por supuesto, que [] invalidará los iteradores y las referencias, pero solo la primera vez que se llame a un objeto. La próxima vez, useCount será uno (y la imagen no podrá copiarse). Así que a[i] == a[j] funciona; independientemente de que el compilador realmente evalúe primero ( a[i] o a[j] ), el segundo encontrará un useCount de 1, y no tendrá que duplicar. Y por la bandera que no se puede uncopyable ,

String a( "some text" );
char& c = a[4];
String b( a );
c = ''-'';

También funcionará, y no modificará b .

Por supuesto, lo anterior se simplifica enormemente. Hacer que funcione en un entorno multiproceso es extremadamente difícil, a menos que simplemente tome un mutex para toda la función para cualquier función que pueda modificar cualquier cosa (en cuyo caso, la clase resultante es extremadamente lenta). G ++ probó y falló, hay un caso de uso particular donde se rompe. (Conseguir que maneje los otros problemas que he ignorado no es particularmente difícil, pero representa muchas líneas de código).