c++ - operator - ¿Cómo puedo evitar el desperdicio de copias de claves en un mapa similar a STL basado en árbol B?

bitwise xor c++

Question

Estoy reemplazando el uso de std::map en una ruta de acceso con cpp-btree . Pero con la optimización habilitada, GCC y Clang se quejan de una violación estricta de alias. El problema se reduce a esto:

template <typename Key, typename Value>
class btree_map {
public:
    // In order to match the standard library''s container interfaces
    using value_type = std::pair<const Key, Value>;

private:
    using mutable_value_type = std::pair<Key, Value>;

    struct node_type {
        mutable_value_type values[N];
        // ...
    };

public:
    class iterator {
        // ...

        value_type& operator*() {
            // Here we cast from const std::pair<Key, Value>&
            // to const std::pair<const Key, Value>&
            return reinterpret_cast<value_type&>(node->values[i]);
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // ...
        // At this point, we have to insert into the middle of a node.
        // Here we rely on nodes containing mutable_value_type, because
        // value_type isn''t assignable due to the const Key member
        std::move_backward(node->values + i, node->values + j,
                           node->values + j + 1);
        node->values[i] = value;
        // ...
    }
};

Esto me hizo pensar: ¿hay una manera de hacer esto tan eficientemente que no dependa de un comportamiento indefinido? Las teclas que estoy usando se pueden mover eficientemente pero son bastante lentas de copiar, así que me encantaría evitar copiar muchas teclas en cada inserción. He considerado

• Utilizando value_type values[N] , luego const_cast<Key&>(values[i].first) = std::move(key) para mover la tecla, pero estoy bastante seguro de que todavía no está definido
• Devolviendo std::pair<const Key&, Value&> lugar de std::pair<const Key, Value>& cuando sea apropiado, pero no estoy seguro de que esto satisfaga los requisitos del contenedor (Oigo ...::reference es se supone que realmente es un tipo de referencia)
• No preocuparse. El código funciona como está, pero tengo curiosidad por poder hacerlo de una manera que cumpla con los estándares. También existe la posibilidad de que los compiladores futuros hagan cosas diferentes con la UB, y no conozco una forma de aplicar -fno-strict-aliasing a una sola clase.

¿Alguna otra idea?

Answer 1

Citando de estrictas reglas de alias ,

Si un programa intenta acceder al valor almacenado de un objeto a través de un lvalor distinto de uno de los siguientes tipos, el comportamiento no está definido:

• ...

• un tipo agregado o de unión que incluye uno de los tipos mencionados anteriormente entre sus miembros (incluido, recursivamente, un miembro de una subagregación o unión contenida), ...

Por lo tanto, pasar de std :: pair <Key, Value> a std :: pair <const Key, Value> a través de la conversión intermedia a una unión o una estructura que contenga ambos tipos como miembros no romperá las reglas estrictas de alias.

Advertencia: std :: pair en una unión no está permitido hasta que C ++ 11, puede usar una estructura en su lugar.

Advertencia: la suposición de que los dos tipos de pares tienen diseños compatibles puede no ser cierta. Imagine una implementación que ordene primero y segundo de manera diferente según la constancia del tipo de clave.

Answer 2

No usa BTREE como un árbol binario balanceado de reemplazo sin razón: generalmente, debido a que tiene un almacenamiento físico que es mucho más lento y funciona como dispositivo de bloque, necesita usar una matriz en un nodo que "algo" representa el Bloque de dispositivos. Por lo tanto, tratar de optimizar los ciclos empleados en el manejo de la matriz interna es bastante marginal.

Sin embargo, sospecho que N es el factor clave en:

struct node_type {
    mutable_value_type values[N];
    // ...
};

Si es lo suficientemente pequeño, es posible que no necesite insertar / buscar / eliminar un elemento en el orden de las claves. El rendimiento podría ser mejor que intentar ordenarlos en una pequeña matriz. Para evitar cualquier movimiento en la función Eliminar, también puede definir una ranura vacía para que Eliminar solo reemplace un elemento con una ranura vacía e Insertar reemplazará la primera ranura vacía con un elemento.

Para una matriz más grande, podría usar dos matrices: una contendrá como elemento un par que consiste en una clave y un índice / iterador que apunta al valor almacenado en la segunda matriz. De esa manera, aún puede ordenar la primera matriz rápidamente, independientemente del tipo de value_type . Dicho esto, aún es necesario manejar la segunda matriz al insertar o eliminar un elemento. La primera matriz también puede contener pares especiales con índices asignados previamente en la segunda matriz al crear un nodo. También se establece un par especial para eliminar un elemento (manteniendo el índice para la inserción posterior de otro elemento). Al ordenar la primera matriz, esos pares especiales se pondrán al final. Y conociendo el recuento de elementos insertados, puede usarlo como un índice para asignar el primer par especial para insertar un elemento (asignar en la segunda matriz) en O (1). Al eliminar un elemento, un par especial puede reemplazar el par normal (manteniendo el índice) en la primera matriz justo antes de ordenarlo. Y solo necesita usar una nueva llamada de ubicación o una llamada de destructor en el elemento actual (inserción o eliminación).

Answer 3

Modificado: se expandió move_backward(...) en for-loop con llamada de destructor explícita y ubicación nueva para evitar el error de asignación.

Se puede usar una nueva ubicación en lugar de una tarea simple.

Nota: esta implementación a continuación no es una excepción segura. Se requiere un código adicional para la excepción de seguridad.

template <typename Key, typename Value>
class btree_map {
// ...
private:
    struct node_type {
        // Declare as value_type, not mutable_value_type.
        value_type values[N];
        // ...
    };

    class iterator {
        // ...

        value_type& operator*() {
            // Simply return values[i].
            return node->values[i];
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // ...
        // expand move_backward(...)
        for(size_t k = j + 1; k > i; k--) {
            // Manually delete the previous value prior to assignment.
            node->values[k].~value_type();
            // Assign the new value by placement new.
            // Note: it goes wrong if an exception occurred at this point.
            new(&node->values[k]) value_type(node->values[k - 1]);
        }
        // Matual delete and placement new too.
        node->values[i].~value_type();
        // Note: it goes wrong if an exception occurred at this point.
        new (&node->values[i]) value_type(value);
        // ...
    }
};