Ownership y templates

La semana pasada usaron std::string y std::vector sin pensar en su memoria. Un vector se crea, crece, se copia, y al salir de la función desaparece, sin un solo free. Esa comodidad no es magia: alguien escribió una clase que hace por ustedes lo que en Introducción a la Programación hacían a mano.

Este semestre vamos a construir esas clases, así que hoy abrimos la caja. Veremos cómo una clase se vuelve owner de un bloque de memoria, qué pasa cuando alguien la copia sin que ella esté preparada, y qué significan exactamente copiar y mover un objeto. Después haremos que el código sirva para cualquier tipo, con templates. Y terminaremos con una distinción que usaremos todo el curso: una cosa es lo que una estructura promete, y otra cómo está hecha. La pila será el primer ejemplo.

Al terminar, tendrán lo necesario para escribir, en el laboratorio, una pila genérica sin fugas.

Ruta de lectura.

• Antes de clase (15 a 20 minutos, obligatorio): Del owner por convención al owner en el tipo, RAII y La copia superficial.
• En clase: La regla de cinco, Copiar de verdad, Mover, Templates, Tipo abstracto e implementación y Invariantes.
• Después de clase: repasen con el Resumen y los Ejercicios, y lean El código de esta semana. Opcional: Open Data Structures, secs. 1.2 (Interfaces) y 2.1 (ArrayStack). El ArrayStack de esa sección crece cuando se llena; el nuestro todavía no, y el crecimiento llega en la semana 4.

Código. Los programas de este capítulo están en code/week-02. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. Los programas de errors/ tienen errores a propósito y se compilan a mano, como se muestra en cada caso.

Del owner por convención al owner en el tipo

En C, el owner de un bloque es quien debe liberarlo, y el ownership es esa responsabilidad. Es una regla que ustedes acordaron consigo mismos. El lenguaje no sabe nada de ella:

struct int_array numbers = int_array_new(4);
if (numbers.data == NULL) {
    return 1;
}
numbers.data[0] = 7;
printf("%d\n", numbers.data[0]);
int_array_free(&numbers);

Si se olvidan de int_array_free, hay una fuga. Si la función tiene tres return, hay que liberar en los tres. Y si dos variables guardan el mismo struct, nada indica cuál de las dos libera. Todo eso depende de la disciplina de quien escribe, y por eso necesitaban ASan y valgrind.

C++ permite algo mejor: que la responsabilidad de liberar sea parte del tipo. Para eso hacen falta dos piezas.

new y delete

new crea un objeto en el heap y devuelve su dirección. delete lo destruye y libera su memoria. Para un arreglo se escriben new[] y delete[].

int* one = new int(7);
std::string* name = new std::string("pila");
std::cout << *one << " " << *name << " " << name->size() << "\n";
delete one;
delete name;

std::size_t n = 4;
int* zeros = new int[n]();
std::string* words = new std::string[n];
words[1] = "hola";
std::cout << zeros[3] << " [" << words[0] << "] [" << words[1] << "]\n";
delete[] zeros;
delete[] words;

$ build/new_basics
7 pila 4
0 [] [hola]
delete de nullptr: no hace nada

La diferencia con malloc y free es de fondo. malloc reserva bytes. new reserva y construye:

Cuatro detalles que conviene fijar desde ahora:

• new std::string[n] construye n cadenas vacías, porque std::string tiene un constructor sin argumentos.
• new int[n] no inicializa nada: un int no tiene constructor, y los valores son basura, como con malloc. Con paréntesis, new int[n](), quedan en cero.
• No hace falta revisar si new devolvió nullptr. Si no hay memoria, lanza una excepción: un mecanismo que corta la ejecución normal y va saliendo de las funciones, una tras otra, hasta que alguien la atrape. En este curso casi no las atraparemos, pero sí importa que existan, y veremos por qué.
• delete de un nullptr no hace nada, igual que free(NULL).

Error común. Lo que se pidió con new[] se libera con delete[], y lo que se pidió con new se libera con delete. Mezclarlos es comportamiento indefinido. Aquí g++ da un aviso porque el caso es muy directo, pero no siempre podrá verlo, y ASan lo detecta al ejecutar:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/new_delete_mismatch.cpp -o build/new_delete_mismatch
errors/new_delete_mismatch.cpp:5:12: warning: 'void operator delete(void*, long unsigned int)' called on pointer returned from a mismatched allocation function [-Wmismatched-new-delete]
$ build/new_delete_mismatch
=================================================================
==1333==ERROR: AddressSanitizer: alloc-dealloc-mismatch (operator new [] vs operator delete) on 0x502000000010
...
    #1 0xaaaadfcd10a8 in main errors/new_delete_mismatch.cpp:5
...
allocated by thread T0 here:
    #0 0xffff9714b090 in operator new[](unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:98
    #1 0xaaaadfcd0efc in main errors/new_delete_mismatch.cpp:3

El destructor

El destructor (destructor) es el método que corre cuando un objeto muere. Se llama como la clase, con ~ delante, no recibe argumentos y no devuelve nada. Una clase tiene exactamente uno.

La clave es cuándo corre. Lo decide el lenguaje, no ustedes:

• Una variable local muere al salir de su alcance (scope), es decir, al cerrar la llave del bloque donde se declaró. Da igual si se sale por el final, por un return o por una excepción que alguien atrape.
• Las locales de un mismo bloque mueren en el orden inverso al de su creación.
• Un objeto creado con new muere cuando alguien hace delete, y solo entonces.

Esta clase avisa cuando nace y cuando muere:

class Noisy {
public:
    explicit Noisy(const std::string& name) : name_(name) {
        std::cout << "  crea " << name_ << "\n";
    }
    ~Noisy() {
        std::cout << "  destruye " << name_ << "\n";
    }

private:
    std::string name_;
};

La palabra explicit impide que el compilador convierta un std::string en un Noisy sin que nadie lo pida. La pondremos en todo constructor de un solo argumento. Veamos a Noisy en tres situaciones:

int first_positive(int a, int b) {
    Noisy guard("guard");
    if (a > 0) {
        return a;
    }
    return b;
}

std::cout << "bloque:\n";
{
    Noisy x("x");
    Noisy y("y");
    std::cout << "  fin del bloque\n";
}
std::cout << "retorno temprano:\n";
int result = first_positive(5, 6);
std::cout << "  resultado " << result << "\n";
std::cout << "new y delete:\n";
Noisy* z = new Noisy("z");
std::cout << "  z sigue vivo\n";
delete z;
std::cout << "fin de main\n";

$ build/scope_trace
bloque:
  crea x
  crea y
  fin del bloque
  destruye y
  destruye x
retorno temprano:
  crea guard
  destruye guard
  resultado 5
new y delete:
  crea z
  z sigue vivo
  destruye z
fin de main

Lean la salida despacio. y muere antes que x, porque nació después. guard muere aunque la función salió por un return en medio de un if, y lo hace antes de que main escriba el resultado. Y z no murió al cerrar nada: murió en el delete.

Idea clave. El destructor de una variable local corre por cualquier camino de salida del bloque. Lo que se escribe en un destructor no se puede olvidar.

RAII

Juntemos las dos piezas. Si el constructor pide la memoria y el destructor la libera, y el destructor corre solo, entonces el problema de la fuga desaparece. Esa idea tiene un nombre poco afortunado, que se quedó:

RAII (resource acquisition is initialization) es la técnica de adquirir un recurso en el constructor de un objeto y liberarlo en su destructor. El tiempo de vida del recurso queda atado al del objeto.

Un recurso es cualquier cosa que se pide y se tiene que devolver: un bloque de memoria, un archivo abierto, una conexión. En este curso casi siempre será memoria.

Este es nuestro ejemplo para todo el capítulo: un arreglo de enteros de tamaño fijo, owner de su bloque. Por ahora solo tiene lo necesario para RAII:

class IntBuffer {
public:
    explicit IntBuffer(std::size_t size) : data_(new int[size]()), size_(size) {}
    ~IntBuffer() {
        delete[] data_;
    }
    int& at(std::size_t index) {
        return data_[index];
    }
    std::size_t size() const {
        return size_;
    }

private:
    int* data_;
    std::size_t size_;
};

Quien usa esta clase ya no piensa en memoria:

void f() {
    IntBuffer numbers(4);       // reserva
    numbers.at(0) = 7;
    if (numbers.at(0) > 5) {
        return;                 // libera
    }
    numbers.at(1) = 8;
}                               // libera

Comparen con lo que hacían en CS201:

El owner es el mismo de CS201. Lo que cambió es quién se encarga de cumplir la regla.

Hay otra ganancia, que solo se nota con el tiempo. Si una función lanza una excepción y alguien la atrapa, las locales de todas las funciones que va abandonando corren su destructor. Una clase con RAII no pierde memoria ni en ese caso, y no hay que escribir nada especial para eso. Si nadie la atrapa, el estándar deja a cada implementación decidir si se abandonan las funciones de esa forma: con g++, el programa termina sin correr esos destructores. std::exit y abort tampoco los corren para las locales.

En la biblioteca. std::string y std::vector son clases con RAII. También std::ifstream, que abre un archivo en el constructor y lo cierra en el destructor. Por eso no hizo falta liberar nada la semana pasada. La biblioteca también tiene std::unique_ptr, un puntero que es owner de lo que apunta, y es lo normal en un programa de verdad. Aquí no lo usaremos, porque el tema del curso es construir estas clases. Por eso la regla de la guía de estilo: new y delete solo dentro de una clase con RAII.

La copia superficial

Nuestra IntBuffer parece terminada. Compila, no tiene fugas, y funciona. Hasta que alguien la copia.

Si una clase no dice cómo copiarse, el compilador escribe una copia por ella. Esa copia por defecto copia cada campo, uno por uno. Para un int es lo correcto. Para un puntero, copia la dirección, no el bloque. A esto se le llama copia superficial (shallow copy). El programa completo está en errors/shallow_copy.cpp:

int main() {
    IntBuffer a(3);
    a.at(0) = 10;
    IntBuffer b = a;
    b.at(0) = 99;
    std::cout << "a.at(0) = " << a.at(0) << "\n";
    return 0;
}

Así corre el programa, hasta la llave que cierra main:

Dos objetos, y cada uno cree ser el único owner del mismo bloque. Eso rompe el programa de dos maneras. La primera es que b.at(0) = 99 también cambia a. La segunda llega al cerrar main: b muere primero y libera el bloque, y después a muere y lo libera otra vez.

Compilemos y corramos. Fíjense en que el compilador no dice nada, ni siquiera con -Wall -Wextra:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/shallow_copy.cpp -o build/shallow_copy
$ build/shallow_copy
a.at(0) = 99
=================================================================
==1341==ERROR: AddressSanitizer: attempting double-free on 0x502000000010 in thread T0:
    #0 0xffff9a79b9c0 in operator delete[](void*) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:155
    #1 0xaaaaca672634 in IntBuffer::~IntBuffer() errors/shallow_copy.cpp:9
    #2 0xaaaaca672294 in main errors/shallow_copy.cpp:30
...
0x502000000010 is located 0 bytes inside of 12-byte region [0x502000000010,0x50200000001c)
freed by thread T0 here:
    #0 0xffff9a79b9c0 in operator delete[](void*) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:155
    #1 0xaaaaca672634 in IntBuffer::~IntBuffer() errors/shallow_copy.cpp:9
    #2 0xaaaaca67228c in main errors/shallow_copy.cpp:30
...
previously allocated by thread T0 here:
    #0 0xffff9a79b090 in operator new[](unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:98
    #1 0xaaaaca67239c in IntBuffer::IntBuffer(unsigned long) errors/shallow_copy.cpp:7
    #2 0xaaaaca671f04 in main errors/shallow_copy.cpp:24
...
SUMMARY: AddressSanitizer: double-free ../../../../src/libsanitizer/asan/asan_new_delete.cpp:155 in operator delete[](void*)

Las direcciones y los números de proceso cambian en cada corrida. Lo demás se lee igual que en CS201, por bloques:

1. Qué pasó. attempting double-free. La pila de llamadas dice dónde: en el destructor, línea 9, llamado desde main, línea 30. Esa línea 30 es la llave que cierra main. Ningún delete aparece escrito en main, y aun así el error ocurre ahí, porque ahí corren los destructores.
2. Quién lo liberó antes. freed by: el mismo destructor, desde la misma línea 30. Es el otro objeto.
3. Quién lo reservó. previously allocated by: el constructor, llamado desde la línea 24. Un solo bloque, reservado una vez, en IntBuffer a(3). La línea 26, la copia, no aparece en ninguna parte, porque esa copia no reservó nada. Esa ausencia es la pista.

La región es de 12 bytes: tres enteros de 4 bytes. La primera línea de la salida, a.at(0) = 99, ya mostraba el problema antes del informe.

La asignación por defecto hace algo parecido, y es un poco peor. Aquí b ya tenía su propio bloque:

IntBuffer a(3);
IntBuffer b(5);
b = a;

Son dos errores en una línea: la misma doble liberación de antes, más una fuga, porque ya nadie puede liberar el bloque de 5 enteros. ASan solo reporta el primero, porque se detiene en la doble liberación, antes de buscar fugas:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/shallow_assign.cpp -o build/shallow_assign
$ build/shallow_assign
=================================================================
==1347==ERROR: AddressSanitizer: attempting double-free on 0x502000000010 in thread T0:
...
SUMMARY: AddressSanitizer: double-free ../../../../src/libsanitizer/asan/asan_new_delete.cpp:155 in operator delete[](void*)

Valgrind no se detiene, así que muestra los dos. Recuerden compilar sin sanitizers para usarlo:

$ g++ -Wall -Wextra -std=c++20 -g -O0 errors/shallow_assign.cpp -o build/shallow_assign_vg
$ valgrind --leak-check=full build/shallow_assign_vg
==1891== Invalid free() / delete / delete[] / realloc()
...
==1891== 20 bytes in 1 blocks are definitely lost in loss record 1 of 1
...
==1891==    by 0x1089CB: main (shallow_assign.cpp:18)

La línea 18 es IntBuffer b(5);. Esos 20 bytes son los cinco enteros que perdió b.

Error común. Escribir el destructor y olvidar la copia. Es el error de esta semana. El programa compila sin avisos y falla al final, en una llave de cierre, lejos de la línea que causó el problema. La causa no está en lo que escribieron, sino en lo que el compilador escribió por ustedes. Con la opción -Wdeprecated-copy-dtor, que no viene incluida en -Wall -Wextra, g++ sí avisa, pero no contamos con ella.

La regla de cinco

Hay cinco funciones que dicen qué pasa cuando un objeto nace a partir de otro, cuando recibe el valor de otro, o cuando muere. Se les llama funciones miembro especiales:

El signo = engaña. IntBuffer b = a; no es una asignación: b no existía, así que es el constructor de copia. Solo b = a;, con b ya creado, es una asignación. El compilador las distingue, y ustedes también deben hacerlo. La diferencia importa porque el constructor empieza de la nada, mientras que la asignación debe encargarse de lo que el objeto ya tenía.

Regla de cinco (rule of five): si una clase necesita escribir una de estas cinco funciones, casi seguro necesita escribir las cinco.

¿Por qué aparecen juntas? Porque las cinco hablan de lo mismo: quién es owner del recurso, y qué pasa con él. Si el destructor libera un bloque, es porque el objeto es owner de ese bloque, y entonces copiar campo por campo ya no sirve: la copia necesitaría su propio bloque. Una clase que necesita el destructor es una clase que necesita las otras cuatro.

Qué función elige el compilador

Traced es una clase que escribe el nombre de cada función especial cuando corre. El nombre del objeto nuevo agrega +c si nació de una copia, y +m si nació de un movimiento. El programa escribe cada línea antes de ejecutarla:

$ build/special_members
Traced a("a");
  constructor a
Traced b = a;
  constructor de copia, desde a
Traced c = std::move(a);
  constructor de movimiento, desde a
b = c;
  asignación de copia, a+c = a+m
b = std::move(c);
  asignación de movimiento, a+c = a+m
Traced d = make_traced();
  constructor local
fin de main
  destructor local
  destructor a+m
  destructor a+c
  destructor a

std::move y make_traced los explicaremos más adelante. Por ahora, noten que los cuatro destructores del final corren en el orden inverso de creación, y que la asignación no creó ningún objeto nuevo.

Qué escribe el compilador por su cuenta

Lo que ustedes declaran cambia lo que el compilador genera. Estas son las reglas de C++20 para lo que nos interesa:

La segunda fila es la trampa. Con un destructor declarado, no hay movimiento implícito, pero la copia sigue ahí. Lo vemos con una clase que tiene un campo Traced, con destructor y sin él:

class OnlyMember {
public:
    Traced member{"m"};
};

class WithDestructor {
public:
    ~WithDestructor() {}
    Traced member{"m"};
};

$ build/implicit_moves
sin destructor declarado:
  constructor m
  constructor de movimiento, desde m
con destructor declarado:
  constructor m
  constructor de copia, desde m
fin de main
  destructor m+c
  destructor m
  destructor m+m
  destructor m

En las dos clases se escribió std::move(...). Sin destructor, el campo se mueve. Con destructor, el campo se copia. Por eso una clase con solo destructor falla igual aunque intenten moverla: errors/shallow_move.cpp usa IntBuffer b = std::move(a); y da la misma doble liberación, otra vez sin ningún aviso:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/shallow_move.cpp -o build/shallow_move
$ build/shallow_move
=================================================================
==1353==ERROR: AddressSanitizer: attempting double-free on 0x502000000010 in thread T0:

La última fila de la tabla, en cambio, sí se nota al compilar: si declaran un constructor de movimiento, la copia queda borrada, y usarla es un error.

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/move_deletes_copy.cpp -o build/move_deletes_copy
errors/move_deletes_copy.cpp:12:19: error: use of deleted function 'constexpr OnlyMoves::OnlyMoves(const OnlyMoves&)'

En C++. = default pide la versión que el compilador escribiría, y = delete prohíbe la función. Si una clase no tiene por qué copiarse, lo más simple es escribir MyClass(const MyClass&) = delete;, y el error aparece al compilar, en la línea de quien intentó copiar.

La regla de cero

Hay una salida más cómoda: no ser owner de nada de forma directa. Si los campos de una clase ya se administran solos, las cinco funciones que genera el compilador son correctas, porque copiar cada campo copia de verdad, y destruir cada campo libera de verdad. Esa es la regla de cero (rule of zero): una clase que no administra un recurso directamente no declara ninguna de las cinco.

template <typename T>
class VectorStack {

Esta pila, que veremos completa más adelante, solo tiene un std::vector como campo, y no declara ninguna función especial. Se copia, se mueve y se destruye bien, porque std::vector ya lo hace.

Entonces, la regla práctica para el curso:

• Si su clase usa un new, es owner de un recurso: escriban las cinco.
• Si no, no escriban ninguna.

Una clase que es owner de algo debería ser owner de una sola cosa. Veamos ahora las cuatro que nos faltan.

Copiar de verdad

El programa de antes se llama errors/shallow_copy.cpp, y su IntBuffer tiene solo el destructor. A partir de aquí usamos la versión completa, en int_buffer.h e int_buffer.cpp, que declara las cinco funciones. Su encabezado también promete que data_ es nullptr si y solo si size_ es 0.

Y el constructor respeta el primer invariante. No pide bloques vacíos:

IntBuffer::IntBuffer(std::size_t size)
    : data_(size == 0 ? nullptr : new int[size]()), size_(size) {}

El constructor de copia

Lo que queremos se llama copia profunda (deep copy): un bloque nuevo, con los mismos valores.

IntBuffer::IntBuffer(const IntBuffer& other) : IntBuffer(other.size_) {
    for (std::size_t i = 0; i < size_; i++) {
        data_[i] = other.data_[i];
    }
}

: IntBuffer(other.size_) es un constructor delegado: primero corre el otro constructor, que reserva el bloque, y después el cuerpo copia los valores. También puede leer other.data_, aunque sea privado, porque en C++ private es por clase, no por objeto.

Con esto, la memoria queda como debe:

La asignación, escrita de la forma ingenua

La asignación tiene más trabajo: b ya tiene un bloque, y hay que soltarlo. El primer intento casi siempre es este:

IntBuffer& operator=(const IntBuffer& other) {
    delete[] data_;
    data_ = new int[other.size_];
    size_ = other.size_;
    for (std::size_t i = 0; i < size_; i++) {
        data_[i] = other.data_[i];
    }
    return *this;
}

Devuelve *this, el propio objeto, para que a = b = c funcione como con los enteros. Y parece correcta. En efecto, para b = a lo es, salvo por un caso que aún no se ve. El problema aparece con la autoasignación: un objeto que se asigna a sí mismo.

¿Quién escribiría a = a? Nadie, a propósito. Pero sí items[i] = items[j] cuando i vale lo mismo que j, o first = second cuando dos referencias apuntan al mismo objeto. Con other y *this siendo lo mismo, sigan el código paso a paso:

El programa pierde sus datos. Y aquí viene algo que deben ver, porque contradice lo que uno esperaría:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/self_assign.cpp -o build/self_assign
$ build/self_assign
antes: 10
después: -1094795586

ASan no reporta nada. El valor exacto después de la asignación depende del sistema, porque es basura, pero el programa termina sin un solo informe. No hay acceso a memoria liberada: other.data_ ya apunta al bloque nuevo cuando el ciclo lo lee. Es memoria válida, solo que con basura. Un sanitizer encuentra accesos inválidos, no valores equivocados. Este error solo lo encuentra una prueba que asigne un objeto a sí mismo y revise el resultado.

Se podría parchar con if (this == &other) return *this; al inicio, y mucho código antiguo lo hace. Eso arregla la autoasignación, pero queda el caso que dejamos pendiente. Si new lanza una excepción por falta de memoria, ya hicimos delete[] data_. El objeto queda con un puntero colgante, y cuando corra su destructor habrá una doble liberación.

El orden correcto es primero conseguir lo nuevo, y solo después soltar lo viejo.

Copy and swap

Copy and swap es una forma de escribir la asignación que sigue ese orden sin esfuerzo. Tiene tres líneas:

IntBuffer& IntBuffer::operator=(const IntBuffer& other) {
    IntBuffer copy(other);
    swap(copy);
    return *this;
}

void IntBuffer::swap(IntBuffer& other) noexcept {
    std::swap(data_, other.data_);
    std::swap(size_, other.size_);
}

Para b = c, con b de tamaño 3 y c de tamaño 5:

Observen lo que no hay: no hay ningún delete, ni ninguna copia a mano. El constructor de copia ya sabe copiar, y el destructor ya sabe liberar. La asignación solo los combina, sin repetir código. Revisemos los dos problemas:

• Autoasignación. copy es un bloque aparte con los mismos valores. Después del swap, el objeto tiene el bloque nuevo con los datos correctos, y el viejo se libera. Funciona sin ningún if.
• Una falla. Si no hay memoria, la excepción sale en la primera línea, cuando todavía no se ha tocado nada. El objeto queda exactamente como estaba. A esto se le llama garantía fuerte (strong guarantee): la operación termina bien, o es como si no hubiera empezado.

Lo comprobamos con el programa copy_demo.cpp, que escribe cuántos new[] y delete[] lleva todo el programa. Los cuenta alloc_count.h, que reemplaza esos dos operadores globales por versiones con contador. El programa crea a, copia a b, cambia b, hace b = c con un c de tamaño 5, y al final b = b:

$ build/copy_demo
copia: a.at(0)=10 b.at(0)=10 | new[]=2 delete[]=0
cambio b: a.at(0)=10 b.at(0)=99 | new[]=2 delete[]=0
b = c: a.at(0)=10 b.at(0)=7 | new[]=4 delete[]=1
b.size()=5
b = b: a.at(0)=10 b.at(0)=7 | new[]=5 delete[]=2
b.size()=5

Sigamos los números. La copia reservó un bloque, y cambiar b no toca a a: la copia ya es independiente. En b = c hubo dos new[], el de IntBuffer c(5) y el de copy, y un delete[]: el bloque viejo de b, que se fue con copy. Y b = b conservó los datos, a cambio de un new[] y un delete[]. Ese es el precio de no tener un if: una autoasignación, que casi nunca pasa, cuesta una copia entera. Es un buen trato.

La garantía fuerte la comprueba buffer_test.cpp, con un tipo cuya copia lanza una excepción a propósito. Después de la falla, el destino de la asignación sigue con su tamaño y sus valores, y ASan no encuentra fugas.

En C++. Un constructor delegado también evita una fuga poco visible. Si un constructor lanza una excepción, el destructor de ese objeto no corre, porque el objeto nunca terminó de nacer. Pero si delega en otro constructor y este ya terminó, el objeto ya existe y el destructor sí corre. Por eso nuestro constructor de copia no pierde el bloque si copiar un elemento falla. Con enteros no puede fallar; con Buffer<T>, más adelante, sí.

Mover

Copiar 1000 enteros para que el original se destruya en la línea siguiente es trabajo perdido. Pasa más de lo que parece: al devolver un resultado, al meter un temporal en un vector, al reacomodar elementos. Si el original ya no se va a usar, se le puede quitar el bloque en vez de duplicarlo.

Mover (move) es pasar los recursos de un objeto a otro, sin copiarlos, dejando al original en un estado válido.

Mover cuesta copiar dos campos, sin importar el tamaño del bloque.

Referencias a un valor que se va

¿Cómo sabe el compilador cuándo mover? Por el tipo del argumento. En C++, una expresión es un lvalue si nombra algo que sigue existiendo y se puede volver a usar (a, items[i]), y un rvalue si es un valor a punto de desaparecer (un temporal como IntBuffer(4), o el resultado de x + y).

Un T&& es una referencia a rvalue: una referencia que solo se une a algo que nadie más va a usar. Con eso, las dos versiones de cada operación se distinguen como cualquier sobrecarga:

IntBuffer(const IntBuffer& other);   // recibe lvalues y rvalues: copia
IntBuffer(IntBuffer&& other);        // recibe solo rvalues: se prefiere para ellos

El constructor y la asignación de movimiento

IntBuffer::IntBuffer(IntBuffer&& other) noexcept
    : data_(other.data_), size_(other.size_) {
    other.data_ = nullptr;
    other.size_ = 0;
}

IntBuffer& IntBuffer::operator=(IntBuffer&& other) noexcept {
    IntBuffer taken(std::move(other));
    swap(taken);
    return *this;
}

En el constructor, las dos últimas líneas son la parte esencial. Sin ellas, los dos objetos apuntarían al mismo bloque y volvería la doble liberación. Dejar other.data_ en nullptr hace que su destructor no libere nada, porque delete[] de un nullptr no hace nada.

La asignación sigue la misma idea de copy and swap. taken le quita todo a other. Después, el objeto intercambia con taken, que se lleva el bloque viejo y lo libera al morir. Funciona incluso para a = std::move(a): taken le quita todo a a, el swap se lo devuelve, y taken muere vacío. La prueba automovimiento de int_buffer_test.cpp lo revisa.

std::move no mueve nada

Este es el malentendido más común de C++. A pesar del nombre, std::move no mueve, no reserva, no copia y no cambia nada al ejecutar. Es un cast: toma una expresión y la presenta como un rvalue. Por dentro hace static_cast<T&&>(x), y nada más. Quien mueve es la función que se elige después, gracias a ese cast.

move_demo.cpp lo muestra con contadores. Este es el inicio, y las demás partes siguen igual:

IntBuffer a(1000);
a.at(0) = 42;
report("a creado");

IntBuffer&& same = std::move(a);
report("solo std::move(a)");

$ build/move_demo
a creado: new[]=1 delete[]=0
solo std::move(a): new[]=1 delete[]=0
same.size()=1000 a.size()=1000 a.at(0)=42
constructor de movimiento: new[]=1 delete[]=0
a.size()=0 b.size()=1000 b.at(0)=42
c creado: new[]=2 delete[]=0
asignación de movimiento: new[]=2 delete[]=1
b.size()=0 c.size()=1000 c.at(0)=42
se reutiliza b, con una copia: new[]=3 delete[]=1
b.size()=1000 b.at(0)=42
d creado, const: new[]=4 delete[]=1
std::move de un const: new[]=5 delete[]=1
d.size()=20 e.size()=20

Vamos por partes:

1. Solo std::move(a). Después de IntBuffer&& same = std::move(a);, a sigue intacto, con sus 1000 elementos. Nadie lo movió. same solo es otro nombre para a.
2. Constructor de movimiento. new[] sigue en 1: mover 1000 enteros no reservó nada. a quedó vacío, y b tiene el bloque con el 42.
3. Asignación de movimiento. c tenía su propio bloque de 10. new[] no cambia, y delete[] sube a 1: se liberó el bloque viejo de c.
4. Volver a usar b. Se puede asignar a un objeto movido. La copia sí reserva: new[] sube a 3.
5. std::move de un const. new[] sube de 4 a 5, y d sigue con sus 20 elementos. Fue una copia. Un const IntBuffer&& no se puede unir a IntBuffer&&, porque mover modifica el original, así que el compilador elige el constructor de copia, sin avisar. El código dice “mover”, y copia.

Idea clave. std::move(x) significa “a partir de aquí, trátenme a x como algo que ya no se va a usar”. Si existe una función que aproveche eso, se mueve. Si no, se copia. Nada falla ni avisa en ese caso.

Qué queda en el objeto movido

Después de mover, el original sigue existiendo: su destructor correrá de todas formas. Así que debe quedar en un estado válido, es decir, uno que al menos se pueda destruir y al que se le pueda asignar. Qué más se puede esperar de él depende de quién escribió la clase:

• Sus clases. Ustedes lo deciden, y lo escriben. IntBuffer promete que el original queda vacío, con size() == 0, y ese estado cumple sus invariantes. Por eso move_demo.cpp llama a a.check_invariants() justo después de mover.
• La biblioteca estándar. El estándar solo promete válido pero no especificado (valid but unspecified): se cumplen los invariantes del tipo, y funciona cualquier operación que no tenga precondiciones, como size(), clear(), o asignarle un valor. Pero no se puede suponer cuál es su contenido.

std::string text = "un texto bastante largo para no caber en el objeto";
std::string other = std::move(text);
std::cout << "text.size()=" << text.size() << " other.size()=" << other.size() << "\n";

text = "de nuevo";
std::cout << text << "\n";

$ build/library_moved_from
text.size()=0 other.size()=50
de nuevo
numbers.size()=1 taken.size()=3

En este entorno, text quedó vacía. Eso no es una promesa, sino lo que hace esta versión de la biblioteca. Otra podría dejar otra cosa. Lo correcto es asignarle un valor antes de volver a leerla, como hace el programa.

Leer un objeto movido sin revisar es un bug, aunque compile. Con IntBuffer lo detecta el assert de at, porque el objeto tiene tamaño 0:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/use_after_move.cpp int_buffer.cpp -o build/use_after_move
$ build/use_after_move
b.size() = 3
use_after_move: int_buffer.cpp:42: int& IntBuffer::at(std::size_t): Assertion `index < size_' failed.

Devolver un objeto local

Una duda frecuente: al devolver un objeto de una función, ¿hay que escribir std::move? No. Miren make_traced en la salida de special_members:

Traced make_traced() {
    Traced local("local");
    return local;
}

Corrió un solo constructor, y ningún movimiento. El compilador construyó local directamente en el lugar de d. A esto se le llama elisión de copia (copy elision). Para un objeto con nombre como local, el estándar la permite pero no la exige. g++ la aplica incluso sin optimizaciones. Si no pudiera aplicarla, el return movería por su cuenta, porque el lenguaje trata como rvalue a una local que se devuelve así.

Si agregan std::move, el resultado es peor. Ya no es la misma variable, así que la elisión no se puede aplicar, y -Wall lo avisa:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/pessimizing_move.cpp -o build/pessimizing_move
errors/pessimizing_move.cpp:8:21: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
$ build/pessimizing_move
  constructor local
  constructor de movimiento, desde local
  destructor local
  destructor local+m

Por qué noexcept

Las dos funciones de movimiento llevan noexcept: la promesa de que no lanzan excepciones. Si una lanzara de todos modos, el programa terminaría de inmediato. La promesa no solo documenta. Cambia lo que hace la biblioteca.

Cuando un std::vector se queda sin espacio, reserva un bloque más grande y pasa sus elementos allí, algo que estudiaremos en la semana 4. Supongan que std::vector lleva movidos 500 de 1000 elementos, y el siguiente movimiento lanza una excepción. Los primeros 500 ya no están en el bloque viejo, y devolverlos podría fallar también. No hay vuelta atrás, y std::vector promete la garantía fuerte en ese caso. Por eso usa std::move_if_noexcept: mueve si el movimiento es noexcept, y si no, copia, porque al copiar el original sigue intacto y solo hay que descartar lo nuevo. La única excepción es un tipo que no se pueda copiar: ahí no le queda más que mover.

Lo medimos con dos clases iguales, con un contador de copias y movimientos. La única diferencia es esta palabra:

SafeMove(SafeMove&& other) noexcept : counts_(other.counts_) {

RiskyMove(RiskyMove&& other) : counts_(other.counts_) {

$ build/vector_growth
SafeMove nothrow=1 antes de crecer: copias=0 movimientos=0
SafeMove después de crecer: copias=0 movimientos=1000
RiskyMove nothrow=0 antes de crecer: copias=0 movimientos=0
RiskyMove después de crecer: copias=1000 movimientos=0

Son 1000 elementos, y con solo quitar noexcept se pasa de 1000 movimientos a 1000 copias. Por eso las funciones de movimiento, y swap, llevan noexcept siempre que puedan cumplirlo. Las nuestras pueden, porque solo intercambian punteros y enteros.

En C++. Existe una forma de escribir copy and swap con una sola asignación: operator=(IntBuffer other), que recibe por valor. El parámetro se construye copiando o moviendo, según lo que le pasen, y el cuerpo solo hace swap. Es válida y se ve mucho. Pero reemplaza a las dos asignaciones. Si se escribe junto a una asignación de movimiento, b = std::move(a) no compila, porque las dos sirven por igual:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/ambiguous_assign.cpp -o build/ambiguous_assign
errors/ambiguous_assign.cpp:20:20: error: ambiguous overload for 'operator=' (operand types are 'Both' and 'std::remove_reference<Both&>::type' {aka 'Both'})

En este curso escribimos las dos por separado, porque así se ven las cinco funciones.

Templates

IntBuffer guarda enteros. Si mañana necesitan cadenas, ¿copian la clase entera y cambian int por std::string? En C, ya conocen la respuesta genérica: void *, tamaños en bytes y punteros a función.

typedef int (*compare_fn)(const void *, const void *);

const void *max_of(const void *items, size_t count, size_t size, compare_fn compare) {
    const char *bytes = items;
    const void *best = items;
    for (size_t i = 1; i < count; i++) {
        const void *item = bytes + i * size;
        if (compare(item, best) > 0) {
            best = item;
        }
    }
    return best;
}

const int *best = max_of(numbers, 3, sizeof numbers[0], compare_int);

Funciona, y qsort está escrita así. Pero el compilador borró toda la información de tipos: confía en que ustedes pasen la comparación correcta. Si no lo hacen, no se entera:

double prices[] = {1.5, 0.25, 7.75};
const double *top = max_of(prices, 3, sizeof prices[0], compare_int);
printf("%.2f\n", *top);

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/void_wrong_compare.c -o build/void_wrong_compare
$ build/void_wrong_compare
1.50

Compila sin avisos, los sanitizers callan, y dice que el máximo de 1.5, 0.25 y 7.75 es 1.50. Además, leer un double como int es comportamiento indefinido, así que este resultado ni siquiera está garantizado.

Funciones template

Un template es código con un hueco para un tipo. No es una función, sino una receta para generar funciones. El compilador la completa con el tipo que haga falta:

template <typename T>
const T& max_of(const std::vector<T>& items) {
    assert(!items.empty());
    const T* best = &items[0];
    for (std::size_t i = 1; i < items.size(); i++) {
        if (items[i] > *best) {
            best = &items[i];
        }
    }
    return *best;
}

std::vector<int> numbers{3, 9, 4};
std::vector<std::string> names{"Ana", "Zoila", "Beto"};
std::cout << max_of(numbers) << "\n";
std::cout << max_of(names) << "\n";

$ build/max_of
9
Zoila

template <typename T> declara el hueco. T es un nombre como cualquier otro, y se elige por costumbre. En la llamada, el compilador deduce T del argumento: un std::vector<int> significa que T es int.

Crear una versión concreta del template se llama instanciar. Y es literal: el compilador genera una función por cada tipo usado. Se puede comprobar en el archivo objeto, con nm, que lista lo que contiene:

$ g++ -std=c++20 -O0 -c max_of.cpp -o build/max_of.o
$ nm -C build/max_of.o | /usr/bin/grep 'max_of<int>'
0000000000000000 W int const& max_of<int>(std::vector<int, std::allocator<int> > const&)

La otra versión también está, con un nombre mucho más largo, porque el nombre real de std::string es largo:

$ nm -C build/max_of.o | /usr/bin/grep -c 'max_of<'
2

Son dos funciones distintas, compiladas por separado. La W significa que el símbolo es débil (weak): si varios archivos generan la misma versión, el enlazador se queda con una sin reclamar.

Templates contra void *

Con el error de antes, el template no llega ni a compilar:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/template_wrong_type.cpp -o build/template_wrong_type
errors/template_wrong_type.cpp:20:22: error: cannot convert 'const double*' to 'const int*' in initialization

El template también tiene requisitos, solo que no están escritos en ninguna parte: son lo que el cuerpo use. max_of usa >. Con un tipo que no lo tenga, el error sale al instanciar, y el mensaje apunta dentro del template:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/no_operator.cpp -o build/no_operator
errors/no_operator.cpp: In instantiation of 'const T& max_of(const std::vector<T>&) [with T = Point]':
errors/no_operator.cpp:25:11:   required from here

Estos mensajes se leen buscando dos cosas: la línea required from here, que dice qué línea suya pidió la instancia, y el with T = ..., que dice con qué tipo.

Por qué un template va en el encabezado

Recuerden cómo se compila: cada .cpp se compila solo, sin ver los demás, y al final el enlazador junta los resultados. Para una función común eso basta. main.cpp ve la declaración, y el cuerpo se compila aparte, una sola vez.

Con un template no alcanza, porque el compilador necesita el cuerpo y el tipo al mismo tiempo para generar la versión. Veamos qué pasa si se separa como de costumbre, con esta clase pequeña:

template <typename T>
class Box {
public:
    explicit Box(T value);
    const T& value() const;

private:
    T value_;
};

template <typename T>
Box<T>::Box(T value) : value_(value) {}

template <typename T>
const T& Box<T>::value() const {
    return value_;
}

Box<int> box(5);
std::cout << box.value() << "\n";

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/split_template/main.cpp errors/split_template/box.cpp -o build/split_template
/work/code/week-02/errors/split_template/main.cpp:7:(.text+0x94): undefined reference to `Box<int>::Box(int)'
/usr/bin/ld: /work/code/week-02/errors/split_template/main.cpp:8:(.text+0x180): undefined reference to `Box<int>::value() const'
collect2: error: ld returned 1 exit status

Cada archivo compiló bien, y lo que falló fue el enlace. Sigan el razonamiento:

• Al compilar main.cpp, el compilador sabe que hace falta Box<int>, pero solo ve las declaraciones de box.h. Deja un pendiente para el enlazador.
• Al compilar box.cpp, ve los cuerpos, pero nadie le pidió Box<int>. Un template que nadie usa no genera nada.
• El enlazador busca Box<int>::Box(int), y no existe en ninguna parte.

La solución normal es poner el cuerpo en el encabezado, para que todo .cpp que use el template lo vea. Por eso IntBuffer tiene int_buffer.h e int_buffer.cpp, y Buffer<T> solo tiene buffer.h. Y por eso en <vector> está todo el código de std::vector. Existe otra salida, la instanciación explícita, que obliga a generar ciertos tipos desde un .cpp, pero exige conocer de antemano todos los tipos, y no la usaremos.

Clases template

Una clase también puede ser template. Buffer<T> es IntBuffer con un hueco. Las cinco funciones cambian poco:

template <typename T>
class Buffer {
public:
    explicit Buffer(std::size_t size) : data_(size == 0 ? nullptr : new T[size]()), size_(size) {}

    ~Buffer() {
        delete[] data_;
    }

    Buffer(const Buffer& other) : Buffer(other.size_) {
        for (std::size_t i = 0; i < size_; i++) {
            data_[i] = other.data_[i];
        }
    }

    Buffer& operator=(const Buffer& other) {
        Buffer copy(other);
        swap(copy);
        return *this;
    }

Con las clases, el tipo se escribe al declarar: Buffer<int>, Buffer<std::string>. Son dos tipos sin relación, y un Buffer<int> no se puede asignar a un Buffer<std::string>. Dentro de la clase, Buffer a secas significa Buffer<T>. Los métodos de una clase template solo se instancian si alguien los usa, así que un método que no compilaría con cierto T no estorba mientras nadie lo llame.

Qué le exigimos a T

Mirando el cuerpo, Buffer<T> necesita dos cosas de T:

• Un constructor sin argumentos, porque new T[size]() construye todos los elementos al reservar.
• Que se pueda asignar, porque la copia hace data_[i] = other.data_[i].

Lo primero es una limitación seria, y conviene decirlo sin rodeos: una clase que no se pueda construir sin argumentos no se puede guardar en Buffer<T>. Y como la pila del laboratorio también pide su arreglo con new T[capacity], tiene la misma limitación: por ahora, T debe tener un constructor sin argumentos. Por ejemplo, con un Student cuyo único constructor recibe un nombre:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/no_default.cpp -o build/no_default
errors/no_default.cpp:15:31:   required from here
errors/../buffer.h:16:69: error: no matching function for call to 'Student::Student()'

Además, new T[capacity] construye todos los elementos de una vez, aunque aún no se usen. Lo pueden ver contando:

$ build/array_constructs
después de new[]: construidos=1000 destruidos=0
después de delete[]: construidos=1000 destruidos=1000

Para int no cuesta nada, pero con T caro, una pila de capacidad 1000 corre 1000 constructores aunque solo guarde un elemento.

std::vector no tiene esta limitación: no_default_vector.cpp guarda ese mismo Student con push_back, sin problema. Lo logra porque separa reservar memoria de construir objetos en ella, y construye cada elemento recién cuando hace falta. Es una técnica más delicada, que aquí no usamos. Por ahora escogemos lo simple, y sabemos lo que cuesta.

Tipo abstracto e implementación

Hasta ahora hablamos de cómo está hecha una clase. Cambiemos de pregunta: ¿qué ofrece?

Un tipo abstracto de datos (abstract data type) es un conjunto de operaciones, junto con lo que cada una promete, sin decir cómo se logra. La implementación es una forma concreta de cumplir esas promesas.

Es la separación que conocen de CS201 entre interfaz e implementación, llevada a un nivel más alto. Y el contrato (contract) es esa promesa, escrita con precisión: qué debe cumplirse antes de llamar a una operación (precondición), y qué será cierto después (poscondición).

La pila

La pila (stack) es el tipo abstracto más simple que hay. Ya conocen una, la de los marcos de llamada. Guarda elementos, y solo se puede acceder al último que entró: el último en entrar es el primero en salir.

Unas propiedades escritas con precisión son el contrato. Para toda pila s y valor x:

• Después de s.push(x), s.top() devuelve x y s.empty() es falso.
• s.push(x) seguido de s.pop() deja a s como estaba.

Noten lo que no dice: ni arreglos, ni punteros, ni tope. Por eso, la pregunta de qué es parte de qué tiene respuesta clara:

Un uso: la notación postfija

Lo valioso de un tipo abstracto es que quien lo usa no necesita saber cómo está hecho. En notación postfija el operador va después de sus operandos: 3 4 + 2 * significa (3 + 4) * 2, sin paréntesis. Se evalúa con una pila: un número se apila, y un operador saca dos, opera y apila el resultado.

int eval_postfix(const std::vector<std::string>& tokens) {
    VectorStack<int> values;
    for (const std::string& token : tokens) {
        if (token == "+" || token == "-" || token == "*") {
            assert(values.size() >= 2);
            int right = values.top();
            values.pop();
            int left = values.top();
            values.pop();

$ build/postfix
14
4

El segundo resultado es de 10 2 3 * -, que es 10 - 2 * 3. Esa función nunca menciona un arreglo, ni un std::vector.

Dos implementaciones del mismo tipo

La forma más directa de implementar una pila es sobre std::vector: push llama a push_back, pop a pop_back y top a back. Es la VectorStack de vector_stack.h, de unas pocas líneas.

Y aquí tienen la otra, la del laboratorio: un arreglo y un tope. Se reserva un arreglo de capacidad casillas, y el tope dice cuántas se están usando:

Las operaciones, en pseudocódigo:

algoritmo push(datos, tope, valor)
    datos[tope] ← valor
    devolver tope + 1
fin algoritmo

algoritmo pop(tope)
    devolver tope - 1
fin algoritmo

algoritmo top(datos, tope)
    devolver datos[tope - 1]
fin algoritmo

Sigamos unas operaciones sobre un arreglo de capacidad 3:

Fíjense en la quinta fila. pop no borra nada: el 8 sigue en el arreglo, y simplemente ya no cuenta como parte de la pila. En Stack<T>, eso tiene una consecuencia concreta: el elemento sacado sigue vivo como objeto, hasta que otro push lo reemplace o la pila se destruya. Si es un std::string grande, su memoria sigue ocupada todo ese tiempo.

Tampoco crece. Si se llena, se llenó: push tiene como precondición que haya espacio. El crecimiento, que es lo que hace el ArrayStack de la lectura, tiene su propio costo y su propio análisis, y llega en la semana 4.

Esta es la interfaz que escribirán en el laboratorio. Es la de lab/stack.h, que trae también size y capacity:

void push(T) {  // Requiere !full().
void pop() {  // Requiere !empty().
T& top() {  // Requiere !empty().

Las dos implementaciones cumplen el mismo contrato. Por eso, en vector_stack_test.cpp, las pruebas están escritas como templates que reciben el tipo de la pila, y no saben cuál es.

Idea clave. El tipo abstracto dice qué. La implementación dice cómo. Un programa escrito contra el qué no se entera si cambia el cómo. En este curso veremos varias implementaciones del mismo tipo, y la diferencia entre ellas será el costo de cada operación.

En la biblioteca. std::stack es la pila de la biblioteca, en <stack>, con push, pop, top, empty y size. Por defecto usa un std::deque por dentro, pero se puede cambiar, y se ve igual desde afuera. Su pop tampoco devuelve el elemento: si lo devolviera por valor, y copiarlo lanzara una excepción, el elemento ya se habría sacado y se perdería. Por eso top y pop están separadas, en esa biblioteca y en nuestra pila. No necesita un T con constructor sin argumentos.

Invariantes

Un contrato habla desde afuera. Desde adentro, lo que mantiene todo en pie son los invariantes.

Un invariante (invariant) de una estructura es una condición sobre sus campos que se cumple siempre entre dos operaciones: al terminar el constructor, y al terminar cada método.

“Entre dos operaciones” es importante. Dentro de un método, el invariante se puede romper por un momento, como en el swap, donde un objeto tiene el data_ nuevo y el size_ viejo. Lo que importa es que esté restablecido antes de que nadie más pueda mirar. Por eso los campos son privados: si cualquiera pudiera cambiar size_, no se podría prometer nada.

Los invariantes de una pila sobre un arreglo son estos, y son los que trae lab/stack.h:

//   1. size_ <= capacity_.
//   2. data_ == nullptr si y solo si capacity_ == 0.
//   3. Los elementos están en data_[0], ..., data_[size_ - 1]. El tope es data_[size_ - 1].

Si se cumplen, todo método puede confiar en ellos. pop no necesita revisar si size_ tiene sentido: el invariante se lo garantiza. El razonamiento es local: cada método supone el invariante al entrar, y debe dejarlo cierto al salir.

Estos invariantes deben cumplirse también en un objeto movido. Por eso el constructor de movimiento no puede dejar size_ como estaba. Si solo pusiera data_ en nullptr, un size_ mayor que cero rompería el primer invariante en la siguiente comprobación. Y hay una precondición que recordar: un objeto movido tiene capacidad 0, así que push sobre él viola !full(). Hay que asignarle algo antes.

check_invariants

Una regla de este curso: cada estructura declara sus invariantes en un comentario y los comprueba en un método check_invariants, que usan las pruebas.

Las condiciones de IntBuffer son pocas. Para ver para qué sirve de verdad, tomemos una clase cuyo invariante sí cuesta comprobar: una lista de enteros que siempre está ordenada. Es de sorted_ints.h, y como solo tiene un std::vector, sigue la regla de cero:

// Invariante: items_[i - 1] <= items_[i] para todo i válido.
class SortedInts {
public:
    void insert(int value) {
        items_.push_back(value);
        std::size_t i = items_.size() - 1;
        while (i > 0 && items_[i - 1] > value) {
            items_[i] = items_[i - 1];
            i--;
        }
        items_[i] = value;
    }

void check_invariants() const {
    for (std::size_t i = 1; i < items_.size(); i++) {
        assert(items_[i - 1] <= items_[i]);
    }
}

La prueba, en sorted_ints_test.cpp, hace operaciones al azar y llama a check_invariants después de cada una. Usa una semilla fija, así que repite siempre la misma secuencia, y un error que aparezca se puede volver a ver.

Ahora introduzcamos un bug. En errors/broken_sorted.cpp, el ciclo se detiene una casilla antes:

while (i > 1 && items_[i - 1] > value) {

La inserción de 5 funciona. La de 3 deja 5 3, y el invariante lo detecta de inmediato, justo después de la operación culpable:

$ g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined errors/broken_sorted.cpp -o build/broken_sorted
$ build/broken_sorted
broken_sorted: errors/broken_sorted.cpp:25: void SortedInts::check_invariants() const: Assertion `items_[i - 1] <= items_[i]' failed.

Sin check_invariants, ese error aparecería más tarde, quizá en una búsqueda que dé un resultado equivocado, y lejos de la causa. Por eso conviene el método. Tres precisiones:

• check_invariants no reemplaza a las pruebas. Una lista ordenada con el valor equivocado cumple su invariante. Por eso las pruebas también comparan contra una referencia de la biblioteca estándar.
• Puede costar. check_invariants de SortedInts recorre toda la lista. Se llama desde las pruebas, no desde insert.
• assert se puede apagar. Compilando con -DNDEBUG desaparece, y por eso no sirve para validar datos del usuario. Sirve para atrapar errores del programador: un invariante roto o una precondición violada, como pop sobre una pila vacía.

El código de esta semana

Las pruebas de C++ usan assert y una pequeña ayuda, run_test, que escribe el nombre de cada prueba terminada:

$ build/int_buffer_test
ok copia independiente
ok asignación de copia reserva una vez
ok autoasignación
ok mover no reserva y deja vacío
ok automovimiento
ok un objeto movido se puede volver a usar
ok reservas y liberaciones se emparejan

make test corre todas, compila los programas de errors/, y comprueba que cada comando y cada salida de este capítulo sigan siendo ciertos. Debe terminar con OK.

El laboratorio

La guía de la semana tiene los pasos. El código inicial está en lab/, con funciones que escriben falta implementar y detienen el programa. Por eso, al principio, make test-lab falla. Tiene una clase de prueba por paso, en orden, así que vayan viendo cómo pasa cada una.

• Pasos 1 a 4. IntStack, en lab/int_stack.h y lab/int_stack.cpp. Después del paso 1, make copy-demo corre la prueba del paso 2 y les muestra el informe de ASan. Lo que aprendieron con IntBuffer se aplica, con una diferencia: ahora hay dos números, size_ y capacity_, y deben decidir qué copiar de cada uno.
• Paso 4. La prueba cuenta los new[] con la misma técnica de alloc_count.h. Antes de que escriban el movimiento, esa prueba falla, porque std::move termina copiando.
• Paso 5. Stack<T>, en lab/stack.h. Recuerden que T debe tener un constructor sin argumentos.
• Paso 6. El verificador de lab/brackets.cpp. El comentario de lab/brackets.h da los mensajes exactos. Los comentarios y las cadenas ya vienen blanqueados por blank_comments_and_literals, de lab/code_text.cpp, así que solo se ocupan de la pila.

Resumen

• new reserva y construye. delete destruye y libera. Con arreglos, new[] y delete[], sin mezclarlos.
• El destructor corre solo, al salir del alcance, en orden inverso de creación.
• RAII: adquirir en el constructor y liberar en el destructor. El owner ahora está en el tipo.
• La copia por defecto copia campos. Para un puntero, eso es una copia superficial: dos owners del mismo bloque, doble liberación, y ningún aviso al compilar.
• Regla de cinco: destructor, constructor de copia, asignación de copia, constructor de movimiento y asignación de movimiento. Aparecen juntas porque las cinco tratan del mismo recurso. Con un destructor declarado, no hay movimiento implícito.
• Regla de cero: una clase que no administra un recurso directamente no declara ninguna.
• Copy and swap: copiar primero, intercambiar después, y dejar que el destructor libere lo viejo. Soporta la autoasignación y da la garantía fuerte. La versión ingenua pierde los datos, y ASan no lo nota.
• Mover toma los recursos sin reservar. std::move es solo un cast: si no hay función de movimiento que aplique, como con un const, se copia sin avisar.
• Un objeto movido queda válido. En sus clases, ustedes dicen en qué estado. En la biblioteca, es válido pero no especificado.
• noexcept en el movimiento decide si std::vector mueve o copia al crecer.
• Un template genera una versión por tipo, por eso su cuerpo va en el encabezado. Da la comprobación de tipos que void * no da, a cambio de una copia del código por cada tipo.
• new T[n] exige un constructor sin argumentos y construye los n elementos al reservar. Es una limitación nuestra por ahora.
• Un tipo abstracto dice qué operaciones hay y qué prometen. La implementación dice cómo. Pila: push, pop, top, empty.
• Un invariante es lo que siempre se cumple entre dos operaciones. check_invariants lo comprueba en las pruebas.

Ejercicios

Los ejercicios de programación se resuelven dentro del entorno del curso, compilando con -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined.

1. Dibujen la memoria, antes de que cierre la llave de main, para este código, con la IntBuffer que solo tiene destructor. ¿Cuántos bloques hay? ¿Cuántos owners cree tener cada uno? ¿Qué reporta ASan?

   IntBuffer a(2);
   IntBuffer b(a);
   IntBuffer c(4);
   c = a;

2. Para cada línea, digan qué función especial corre, si es que corre alguna. Luego compruébenlo con la clase Traced.

   Traced a("a");
   Traced b(a);
   Traced c = b;
   c = a;
   Traced d = std::move(c);
   const Traced e("e");
   Traced f = std::move(e);
   Traced& g = a;

3. Clasifiquen como parte del tipo abstracto o de la implementación: top, un std::vector usado por dentro, “pop requiere que la pila no esté vacía”, capacity_, “después de push(x), top() devuelve x”.

4. Sigan con una tabla la evaluación de 5 1 2 + 4 * + 3 - con la pila de postfix.cpp. Comprueben el resultado agregando la llamada al programa.

5. Escriban el método void resize(std::size_t new_size) de IntBuffer. Debe conservar los primeros valores, rellenar con ceros lo nuevo, y dar la garantía fuerte. Escriban una prueba que use array_news() para contar las reservas.

6. Escriban la función template count_equal(const std::vector<T>& items, const T& value). Pruébenla con int y con std::string. Después pruébenla con un struct sin ==, y encuentren en el mensaje de error la línea suya y el tipo.

7. Agreguen a errors/shallow_copy.cpp el constructor de copia, pero no la asignación. Escriban un main que todavía falle. ¿Qué reporta ASan? Esta vez -Wextra sí da un aviso. ¿Cuál, y por qué no lo daba cuando la clase solo tenía destructor?

8. Una clase LineLog tiene dos campos: un std::string con su nombre y un std::vector<std::string> con sus líneas. ¿Cuántas de las cinco funciones especiales debe escribir? Escriban la clase, y comprueben con una prueba que se puede copiar y mover.

9. Quiten noexcept del constructor de movimiento de SafeMove, en vector_growth.cpp, y digan qué cambia. Después, en RiskyMove, borren el constructor de copia con = delete, y corran de nuevo. ¿Qué hace ahora std::vector, y por qué ya no da la garantía fuerte?

10. Escriban la clase IntRange, que guarda dos enteros low y high, con low <= high como invariante, y los métodos shift(int d), widen(int d) y check_invariants. ¿Qué valores de d debe rechazar widen? Escriban la precondición con assert.

11. Alguien propone escribir la pila con un Buffer<T> y un std::size_t size_, sin declarar ninguna función especial, siguiendo la regla de cero. Copiar funciona bien. Pero ¿qué pasa con size_ en el objeto original después de mover? ¿Qué invariante se rompe? Escriban una prueba que lo demuestre, y digan cómo lo arreglarían.

12. Desafío. La asignación de movimiento por swap libera el bloque viejo al morir taken. Otra forma común es intercambiar directamente con other, sin taken, y dejar que other se lleve el bloque viejo. Escríbanla. ¿Cumple lo que promete IntBuffer sobre el estado del objeto movido? ¿Cuándo se libera el bloque viejo? Decidan cuál prefieren y justifiquen.