¿Cómo puedo escribir un asignador con estado en C++ 11, dados los requisitos en la construcción de copias?

c++11 stl

Question

Por lo que puedo decir, los requisitos de un asignador para ser utilizado con contenedores STL se establecen en la Tabla 28 de la sección 17.6.3.5 de la norma C ++ 11.

Estoy un poco confundido acerca de la interacción entre algunos de estos requisitos. Dado un tipo X que es un asignador para el tipo T , un tipo Y que es "la clase asignadora correspondiente" para el tipo U , las instancias a , a1 y a2 de X , y la instancia b de Y , la tabla dice:

1. La expresión a1 == a2 evalúa como true solo si el almacenamiento asignado desde a1 puede ser desasignado por a2 , y viceversa.

2. La expresión X a1(a); está bien formado, no sale a través de una excepción, y luego a1 == a es verdadero.

3. La expresión X a(b) está bien formada, no sale a través de una excepción, y luego a == b .

Leí esto diciendo que todos los asignadores deben ser construibles con copia de tal manera que las copias sean intercambiables con los originales. Peor aún, la misma verdad a través de los límites de tipo. Esto parece ser un requisito bastante oneroso; por lo que puedo decir, hace imposible un gran número de tipos de asignadores.

Por ejemplo, digamos que tenía una clase de lista libre que quería usar en mi asignador para almacenar en caché los objetos liberados. A menos que me esté faltando algo, no podría incluir una instancia de esa clase en el asignador, porque los tamaños o alineamientos de T y U pueden diferir y, por lo tanto, las entradas de las listas de consulta no son compatibles.

Mis preguntas:

1. ¿Son correctas mis interpretaciones anteriores?

2. He leído en algunos lugares que C ++ 11 mejoró el soporte para "asignadores de estado". ¿Cómo es ese el caso, dadas estas restricciones?

3. ¿Tiene alguna sugerencia sobre cómo hacer el tipo de cosas que estoy tratando de hacer? Es decir, ¿cómo incluyo el estado específico de tipo asignado en mi asignador?

4. En general, el lenguaje en torno a los asignadores parece descuidado. (Por ejemplo, el prólogo de la Tabla 28 dice que debe asumir que a es de tipo X& , pero algunas de las expresiones redefinen a ). Además, al menos el soporte de GCC no es conforme. ¿Qué explica esta rareza alrededor de los asignadores? ¿Es solo una característica poco utilizada?

Answer 1

1) ¿Son correctas mis interpretaciones anteriores?

Tiene razón en que su lista gratuita podría no ser una buena opción para los asignadores, debe ser capaz de manejar múltiples tamaños (y alineaciones) para adaptarse. Ese es un problema para la lista libre de resolver.

2) He leído en algunos lugares que C ++ 11 mejoró el soporte para "asignadores con estado". ¿Cómo es ese el caso, dadas estas restricciones?

No se mejora tanto, que nacido. En C ++ 03, el estándar solo impulsó a los implementadores a proporcionar asignadores que pudieran admitir instancias e implementadores no iguales, lo que hace que los asignadores con estado no sean portables.

3) ¿Tiene alguna sugerencia sobre cómo hacer el tipo de cosas que estoy tratando de hacer? Es decir, ¿cómo incluyo el estado específico de tipo asignado en mi asignador?

Es posible que su asignador tenga que ser flexible , ya que se supone que no debe saber exactamente qué memoria (y qué tipos) se supone que debe asignar. Este requisito es necesario para aislarlo (al usuario) de las partes internas de algunos de los contenedores que utilizan el asignador, como std::list , std::set o std::map .

Aún puede usar dichos asignadores con contenedores simples como std::vector o std::deque .

Sí, es un requisito costoso.

4) En general, el lenguaje alrededor de los asignadores parece descuidado. (Por ejemplo, el prólogo de la Tabla 28 dice que debe asumir que a es de tipo X &, pero algunas de las expresiones redefinen a). Además, al menos el soporte de GCC no es conforme. ¿Qué explica esta rareza alrededor de los asignadores? ¿Es solo una característica poco utilizada?

El estándar en general no es exactamente fácil de leer, no solo los asignadores. Tienes que tener cuidado.

Para ser pedante, gcc no admite asignadores (es un compilador). Supongo que está hablando de libstdc ++ (la implementación de la biblioteca estándar incluida con gcc). libstdc ++ es antiguo y, por lo tanto, se adaptó a C ++ 03. Se ha adaptado a C ++ 11, pero aún no es totalmente conforme (por ejemplo, todavía utiliza Copia en escritura para cadenas). La razón es que libstdc ++ tiene un gran enfoque en la compatibilidad binaria, y una serie de cambios requeridos por C ++ 11 romperían esta compatibilidad; Por lo tanto, deben introducirse con cuidado.

Answer 2

Leí esto diciendo que todos los asignadores deben ser construibles con copia de tal manera que las copias sean intercambiables con los originales. Peor aún, la misma verdad a través de los límites de tipo. Esto parece ser un requisito bastante oneroso; por lo que puedo decir, hace imposible un gran número de tipos de asignadores.

Es trivial cumplir con los requisitos si los asignadores son un controlador liviano en algún recurso de memoria. Simplemente no intente incrustar el recurso dentro de objetos asignadores individuales.

Por ejemplo, digamos que tenía una clase de lista libre que quería usar en mi asignador para almacenar en caché los objetos liberados. A menos que me esté faltando algo, no podría incluir una instancia de esa clase en el asignador, porque los tamaños o alineamientos de T y U pueden diferir y, por lo tanto, las entradas de las listas de consulta no son compatibles.

[allocator.requirements] párrafo 9:

Un asignador puede restringir los tipos en los que se puede crear una instancia y los argumentos para los que se puede llamar a su miembro de construct . Si no se puede usar un tipo con un asignador en particular, la clase del asignador o la llamada a construct pueden fallar en la instanciación.

Está bien que su asignador se niegue a asignar memoria para cualquier cosa excepto un tipo T dado. Eso evitará que se use en contenedores basados ​​en nodos, como std::list que necesitan asignar sus propios tipos de nodos internos (no solo el value_type del value_type ) pero funcionará bien para std::vector .

Esto se puede hacer evitando que el asignador rebote a otros tipos:

class T;

template<typename ValueType>
class Alloc {
  static_assert(std::is_same<ValueType, T>::value,
    "this allocator can only be used for type T");
  // ...
};

std::vector<T, Alloc<T>> v; // OK
std::list<T, Alloc<T>> l;   // Fails

O solo puede admitir tipos que pueden caber en sizeof(T) :

template<typename ValueType>
class Alloc {
  static_assert(sizeof(ValueType) <= sizeof(T),
    "this allocator can only be used for types not larger than sizeof(T)");
  static_assert(alignof(ValueType) <= alignof(T),
    "this allocator can only be used for types with alignment not larger than alignof(T)");

  // ...
};

1. ¿Son correctas mis interpretaciones anteriores?

No completamente.

2. He leído en algunos lugares que C ++ 11 mejoró el soporte para "asignadores de estado". ¿Cómo es ese el caso, dadas estas restricciones?

¡Las restricciones antes de C ++ 11 eran aún peores!

Ahora se especifica claramente cómo los asignadores se propagan entre los contenedores cuando se copian y mueven, y cómo se comportan varias operaciones de contenedores cuando su instancia del asignador se reemplaza por una instancia diferente que podría no ser igual a la original. Sin esas aclaraciones, no estaba claro qué se suponía que pasaría si, por ejemplo, intercambiaba dos contenedores con asignadores con estado.

3. ¿Tiene alguna sugerencia sobre cómo hacer el tipo de cosas que estoy tratando de hacer? Es decir, ¿cómo incluyo el estado específico de tipo asignado en mi asignador?

No lo incruste directamente en el asignador, guárdelo por separado y haga que el asignador se refiera a él mediante un puntero (posiblemente un puntero inteligente, dependiendo de cómo diseñe la administración de por vida del recurso). El objeto de asignación real debe ser un identificador liviano en alguna fuente externa de memoria (por ejemplo, una arena o grupo, o algo que administre una lista libre). Los objetos de asignación que comparten la misma fuente deben ser iguales, esto es cierto incluso para los asignadores con diferentes tipos de valores (ver más abajo).

También sugiero que no intente admitir la asignación para todos los tipos si solo necesita admitirla para uno.

4. En general, el lenguaje en torno a los asignadores parece descuidado. (Por ejemplo, el prólogo de la Tabla 28 dice que debe asumir que a es de tipo X &, pero algunas de las expresiones redefinen a).

Sí, como informaste en https://github.com/cplusplus/draft/pull/334 (gracias).

Además, al menos el soporte de GCC no es conforme.

No es 100%, pero estará en la próxima versión.

¿Qué explica esta rareza alrededor de los asignadores? ¿Es solo una característica poco utilizada?

Sí. Y hay una gran cantidad de equipaje histórico, y es difícil especificar que sea ampliamente útil. Mi presentación de ACCU 2012 tiene algunos detalles, me sorprendería mucho si después de leerlo crees que puedes hacerlo más simple ;-)

Con respecto a cuando los asignadores se comparan iguales, considere:

MemoryArena m;
Alloc<T> t_alloc(&m);
Alloc<T> t_alloc_copy(t_alloc);
assert( t_alloc_copy == t_alloc ); // share same arena
Alloc<U> u_alloc(t_alloc);
assert( t_alloc == u_alloc ); // share same arena
MemoryArena m2
Alloc<T> a2(&m2);
assert( a2 != t_alloc ); // using different arenas

El significado de la igualdad de asignador es que los objetos pueden liberar la memoria de cada uno, por lo que si asigna algo de memoria desde t_alloc y (t_alloc == u_alloc) es true , entonces significa que puede desasignar esa memoria usando u_alloc . Si no son iguales, u_alloc no puede desasignar la memoria que proviene de t_alloc .

Si solo tiene una lista de libre distribución donde cualquier memoria puede agregarse a cualquier otra lista de consulta, entonces tal vez todos los objetos de su asignador se comparen de la misma manera.

Answer 3

La igualdad de los asignadores no implica que deban tener exactamente el mismo estado interno, solo que ambos deben poder desasignar la memoria asignada con cualquiera de los asignadores. La igualdad cruzada de los asignadores a == b para un asignador a de tipo X y el asignador b de tipo Y se define en la tabla 28 como "igual que a == Y::template rebind<T>::other(b) " . En otras palabras, a == b si la memoria asignada por a puede ser desasignada por un asignador instanciado por rebinding b al value_type .

Sus asignadores de listas libres no necesitan poder desasignar nodos de tipo arbitrario, solo necesita asegurarse de que la memoria asignada por FreelistAllocator<T> pueda ser desasignada por FreelistAllocator<U>::template rebind<T>::other . Dado que FreelistAllocator<U>::template rebind<T>::other es del mismo tipo que FreelistAllocator<T> en la mayoría de las implementaciones sanas, esto es bastante fácil de lograr.

Ejemplo simple ( demostración en vivo en Coliru ):

template <typename T>
class FreelistAllocator {
    union node {
        node* next;
        typename std::aligned_storage<sizeof(T), alignof(T)>::type storage;
    };

    node* list = nullptr;

    void clear() noexcept {
        auto p = list;
        while (p) {
            auto tmp = p;
            p = p->next;
            delete tmp;
        }
        list = nullptr;
    }

public:
    using value_type = T;
    using size_type = std::size_t;
    using propagate_on_container_move_assignment = std::true_type;

    FreelistAllocator() noexcept = default;
    FreelistAllocator(const FreelistAllocator&) noexcept {}
    template <typename U>
    FreelistAllocator(const FreelistAllocator<U>&) noexcept {}
    FreelistAllocator(FreelistAllocator&& other) noexcept :  list(other.list) {
        other.list = nullptr;
    }

    FreelistAllocator& operator = (const FreelistAllocator&) noexcept {
        // noop
        return *this;
    }

    FreelistAllocator& operator = (FreelistAllocator&& other) noexcept {
        clear();
        list = other.list;
        other.list = nullptr;
        return *this;
    }

    ~FreelistAllocator() noexcept { clear(); }

    T* allocate(size_type n) {
        std::cout << "Allocate(" << n << ") from ";
        if (n == 1) {
            auto ptr = list;
            if (ptr) {
                std::cout << "freelist/n";
                list = list->next;
            } else {
                std::cout << "new node/n";
                ptr = new node;
            }
            return reinterpret_cast<T*>(ptr);
        }

        std::cout << "::operator new/n";
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }

    void deallocate(T* ptr, size_type n) noexcept {
        std::cout << "Deallocate(" << static_cast<void*>(ptr) << ", " << n << ") to ";
        if (n == 1) {
            std::cout << "freelist/n";
            auto node_ptr = reinterpret_cast<node*>(ptr);
            node_ptr->next = list;
            list = node_ptr;
        } else {
            std::cout << "::operator delete/n";
            ::operator delete(ptr);
        }
    }
};

template <typename T, typename U>
inline bool operator == (const FreelistAllocator<T>&, const FreelistAllocator<U>&) {
    return true;
}

template <typename T, typename U>
inline bool operator != (const FreelistAllocator<T>&, const FreelistAllocator<U>&) {
    return false;
}