Estoy practicando el uso de plantillas y clases en C ++. Mi objetivo es escribir una clase de plantilla para un deque. Tendrá funciones para "insert_head", "insert_tail", "remove_tail" y "remove head", junto con la capacidad de imprimirse usando "cout". Además, el operador '=' debe poder usarse para copiar una instancia de la clase en otra instancia. Aquí está mi código actual:

#ifndef DEQUE_H
#define DEQUE_H

template <typename T>
class Deque {
public:
    Deque(int size = 0, int capacity = 1000) : size_(size), capacity_(capacity) 
    {}
    Deque(Deque & d) : x_(d.x()), size_(d.size()), capacity_(d.capacity()) {}


std::ostream & operator<<(std::ostream & cout) {
    cout << '[';

    if (size_ > 0) {
        for (int i = 0; i < (size_ - 1)* sizeof(T); i += sizeof(T)) {
            std::cout << *(x_ + i) << ',';
        }
        cout << *(x_ + (size_ - 1)* sizeof(T));
    }
    cout << ']';
    return cout;
}

Deque operator=(Deque d) {
    Deque dq(d);
    return dq;
}

void print_test() {
    std::cout << '[';

    if (size_ > 0) {
        for (int i = 0; i < (size_ - 1)* sizeof(T); i += sizeof(T)) {
            std::cout << *(x_ + i) << ',';
        }
        std::cout << *(x_ + (size_ - 1)* sizeof(T));
    }
    std::cout << ']';
}

int * x() {
    return x_;
}
int size() {
    return size_;
}
int capacity() {
    return capacity_;
}

bool is_empty() {
    return size_ == 0;
}

void insert_tail(T tail) {
    if (size_ < capacity_) {
        *(x_ + sizeof(T) * size_) = tail;
        size_++;
    } else {
        // throw overflow
    }
}
T remove_tail() {
    if (size_ > 0) {
        T ret = *(x_ + sizeof(T) * (size_ - 1));
        std::cout << ret;
        size_--;
        return ret;
    } else {
        // throw underflow
    }
}

void insert_head(T head) {
    if (size_ > 0 && size_ < capacity_) {
        for (int i = (size_ - 1) * sizeof(T); i < 0; i -= sizeof(T)) {
            *(x_ + i + sizeof(T)) = *(x_ + i);
        }
    }
    if (size_ < capacity_) {
        *x_ = head;
        size_++;
    } else {
        // throw overflow
    }
}

T remove_head() {

    if (size_ > 0) {
        T ret = *x_;
        for (int i = sizeof(T); i < size_* sizeof(T); i += sizeof(T)) {
            *(x_ + i - sizeof(T)) = *(x_ + i);
        }   
        size_--;
        return ret;
    } else {
        // throw underflow
    }
}

private:
    T * x_;
    int size_;
    int capacity_;
};

#endif

Aquí está mi código de prueba usando esa clase:

#include <iostream>
#include "Deque.h"

int main(int argc, char const *argv[])
{
    Deque< int > dq;


    dq.insert_head(1);

    // dq.insert_head(2); // adding head when not empty causes bug

    dq.insert_tail(3);
    dq.insert_tail(4);
    dq.insert_tail(5);
    dq.print_test(); std::cout << std::endl;

    // std::cout << dq; // '<<' not overloaded properly'

    std::cout << dq.remove_head() << " head removed\n";

    // int x = dq.remove_head(); // seg faults when assigning returned value to a variable 

    dq.insert_tail(2);
    dq.print_test();
    std::cout << std::endl;

    Deque< int > dq1(dq);
    Deque< int > dq2;

    // dq2 = dq1; // '=' not overloaded properly

    return 0;
}

Cada uno de mis cuatro problemas está en una línea de código comentada en mi archivo de prueba, aquí hay una explicación adicional:

  1. Cuando se llama "dq.insert_head (2)" y dq no está vacío (tamaño> 0), trato de cambiar todos los demás elementos de la deque en una posición para poder insertar el nuevo valor allí, hay un problema y el los elementos no se mueven.

  2. "std :: cout << dq" no imprime dq como debería. El código es muy similar al método "print_test ()", sin embargo, cuando ejecuto el programa, aparece el error "no coincide con el operador <<". ¿Es esto porque es una clase de plantilla? ¿O estoy haciendo algo completamente incorrecto?

  3. Al intentar quitar la cabeza o la cola del deque, estoy tratando de devolver el valor eliminado. En la línea de código no comentada, el valor devuelto se imprime como debería, pero la siguiente línea de código provoca una falla seg. ¿Es porque estoy tratando de asignar un varabale de plantilla a una variable entera?

  4. Mi último problema es que el operador '=' no está copiando una instancia de la clase a otra. Mi objetivo era crear una nueva instancia de la clase y luego devolver esa instancia (como puede ver en el "Operador Deque = (Deque d)") pero eso no funciona como esperaba. ¿Cuál es la mejor manera de sobrecargar la función '=' usando clases de plantilla?

Gracias por su ayuda, la respuesta a cualquiera de estas preguntas es muy apreciada.

1
Schnagl 12 dic. 2017 a las 03:05

2 respuestas

La mejor respuesta

La respuesta a su primer problema es eliminar el sizeof(T) para que termine con este

    for (int i = (size_ - 1); i > 0; i --) {
        *(x_ + i + 1) = *(x_ + i);
    }

La respuesta a su segundo problema es cambiar su declaración para su sobrecarga << a friend std::ostream & operator<<(std::ostream & x, Deque n) e inicializar el cuerpo fuera de la clase.

La respuesta al tercer problema es que no puede devolver un puntero int que puede apuntar a un bloque de ubicación de memoria diferente al que podría ser T.

La respuesta a la cuarta pregunta es hacer lo siguiente:

Deque& operator=(const Deque& d) {
    x_ = d.x_; // Deep copy
    size_ = d.size_;
    capacity_ = d.capacity_;
    return *this;
}
1
Jake Freeman 12 dic. 2017 a las 01:30

Todas sus funciones tienen problemas:

 Deque(int size = 0, int capacity = 1000) : size_(size), capacity_(capacity) {}
  • Si permite especificar un tamaño, tendrá que asignar e inicializar memoria para esos elementos. Solo debe especificar la capacidad.
  • x_ no está inicializado.

Suponiendo que desea una capacidad fija, entonces su constructor debería ser:

Deque(int capacity = 1000) 
    : size_(0)
    , x_(new T[capacity])
    , capacity_(capacity) 
{
}

E incluso esa es una versión simplificada, ya que llamaría al constructor para todos los elementos que podrían ser ineficientes y requerirían que T tenga un constructor predeterminado accesible.

Y ahora para el constructor de copias:

  • El constructor de copia debería hacer una copia profunda. De lo contrario, su programa (probablemente) se bloqueará después de eliminar la primera Deque para la que ha hecho copias, ya que eliminar un elemento dos veces es un comportamiento indefinido.
  • El prototipo debe tener una referencia constante como en: Deque(const Deque &other);

El código se vería similar a esto:

Deque(const Deque &other)
    : capacity_(other.capacity_)
    , x_(new T[other.capacity_])
    , size_(other.size_)
{
    for (int i = 0; i != size_; ++i)
    {
        x_[i] = other.x_[i];
    }
}

Para la <<, el prototipo debe ser:

friend std::ostream & operator<<(std::ostream &cout, const T &data)

Asumiendo que se declara dentro de la clase para acceder a campos privados. Debe pasar los datos en los que trabaja el operador.

Para el operador de asignación, algo como esto podría funcionar:

Deque& operator=(const Deque &other)
{
    // Use swap idiom...
    Deque tmp(other);

    // Swap pointers so old x_ get destroyed...
    T *old_x = x_;
    x_ = tmp.x_;
    tmp.x_ = old_x;

    // Usually one would use std::swap. 
    // Here as tmp get destroyed, it is not strictly to swap capacity_ and size_.
    capacity_ = tmp.capacity_;
    size_ = tmp.size_;
}

Ahora para la función x(): - Si hace una cola, probablemente no desee exponer datos, por lo que la función debería eliminarse. - Si se mantuvo, la función debe ser constante y devolver un puntero a T: T *x() const; para la funcionalidad esperada.

size, capacity y is_empty deberían ser funciones miembro de const.

Los problemas de insert_tail y remove_tail se han explicado en los comentarios de otras personas (en particular, los sizeof extraños).

Problemas similares para insert_head y remove_head también. Además, el código que copia los elementos existentes podría refactorizarse dentro de una función privada para seguir el principio DRY y evitar la duplicación de código.

2
Phil1970 12 dic. 2017 a las 02:45