Implementazione di Matrix: std :: vector vs std :: unique_ptr []?

Question

Implementazione di Matrix: std :: vector vs std :: unique_ptr []?

#1 da (3 voti)

1

Come parte di un progetto di hobby, avevo bisogno di un oggetto Matrix rettangolare per mantenere lo stato di una griglia. Inizialmente, l'implementazione sembrava banale e indegna di ulteriori discussioni: (Non ho incluso tutto il codice, solo il codice pertinente)

template<typename T>
class Matrix {
    uint64_t rows, columns;
    std::vector<T> _data;

    uint64_t get_flat_index(uint64_t row, uint64_t column) const {
        return row * columns + column;
    }

public:
    Matrix(uint64_t rows, uint64_t columns) :
    rows(rows), columns(columns), _data(rows * columns, {}) {}

    //Auto-generated by compiler
    //Matrix(Matrix const&) = default;
    //Matrix(Matrix &&) = default;
    //Matrix & operator=(Matrix const&) = default;
    //Matrix & operator=(Matrix &&) = default;
    //~Matrix() = default;

    T & operator()(uint64_t row, uint64_t column) {
        return _data[get_flat_index(row, column)];
    }

    T const& operator()(uint64_t row, uint64_t column) const {
        return _data[get_flat_index(row, column)];
    }

    bool is_valid(uint64_t row, uint64_t column) const {
        return row < rows && column < columns;
    }

    T & at(uint64_t row, uint64_t column) {
        if(!is_valid(row, column)) throw std::runtime_error("row/column out of bounds!");
        return operator()(row, column);
    }

    T const& at(uint64_t row, uint64_t column) const {
        if(!is_valid(row, column)) throw std::runtime_error("row/column out of bounds!");
        return operator()(row, column);
    }

    uint64_t get_rows() const {return rows;}
    uint64_t get_columns() const {return columns;}

    void resize(uint64_t new_rows, uint64_t new_columns) {
        if (new_rows == rows && new_columns == columns) return;

        if (new_columns == columns) {
            _data.resize(new_rows * new_columns, {});
        }
        else {
            std::vector<T> new_data(new_rows * new_columns, {});
            for (uint64_t row = 0; row < std::min(rows, new_rows); row++) {
                auto beginning_of_row = _data.begin() + (row * columns);
                auto ending_of_row = beginning_of_row + std::min(columns, new_columns);
                auto beginning_of_new_row = new_data.begin() + (row * new_columns);
                std::copy(beginning_of_row, ending_of_row, beginning_of_new_row);
            }
            _data = std::move(new_data);
        }

        columns = new_columns;
        rows = new_rows;
    }

    //Other code, not related to this post
};

Quindi sembra tutto molto bello, vero? Posso scrivere cose come Matrix<int> m(50,50); , m(5, 10) = 17; , try {m.at(52, 47) = 99;} catch (std::runtime_error const& e) {std::cerr << "Whoops!" << std::endl;} , e tutto funziona, giusto?

Bene, risulta che c'è almeno una situazione in cui il codice si comporta in modo non corretto in modo sostanziale:

Matrix<bool> is_tested(60, 60); 
is_tested(30, 40) = true; //Does not compile! Whoops.

Sì. Si scopre che poiché std::vector<bool> è stato specializzato , compromette l'integrità del mio codice.

La mia soluzione iniziale era scrivere una specializzazione per Matrix<bool> .

template<>
class Matrix<bool> {
    uint64_t rows, columns;
    std::unique_ptr<bool[]> _data;

    //Duplicated: 
    uint64_t get_flat_index(uint64_t rows, uint64_t columns) {/*...*/}
public:
    Matrix(uint64_t rows, uint64_t columns) :
    rows(rows), columns(columns), _data(std::make_unique<bool[]>(rows * columns)) {}

    //I don't get this for free anymore!
    Matrix(Matrix const& m) : Matrix(m.rows, m.columns) {
        std::copy(m._data.get(), m._data.get() + rows * columns, _data.get());
    }

    //I have to include this manually now.
    Matrix(Matrix &&) = default;

    //More duplicated code...
    bool & operator()(uint64_t row, uint64_t column) {/*...*/}
    bool const& operator()(uint64_t row, uint64_t column) const {/*...*/}
    bool is_valid(uint64_t row, uint64_t column) const {/*...*/}
    bool & at(uint64_t row, uint64_t column) {/*...*/}
    bool const& at(uint64_t row, uint64_t column) const {/*...*/}
    uint64_t get_rows() const {/*...*/}
    uint64_t get_columns() const {/*...*/}

    void resize(uint64_t new_rows, uint64_t new_columns) {
        if (new_rows == rows && new_columns == columns) return;

        std::unique_ptr<bool[]> new_data{ std::make_unique<bool[]>(new_rows * new_columns) };

        if (new_columns == columns) {
            std::copy(
                begin(),
                begin() + ((new_rows < rows) ? new_rows * new_columns : rows * new_columns),
                new_data.get()
            );
        }
        else {
            for (uint64_t row = 0; row < std::min(rows, new_rows); row++) {
                auto beginning_of_row = _data.get() + (row * columns);
                auto ending_of_row = beginning_of_row + std::min(columns, new_columns);
                auto beginning_of_new_row = new_data.get() + (row * new_columns);
                std::copy(beginning_of_row, ending_of_row, beginning_of_new_row);
            }
        }

        _data = std::move(new_data);
        columns = new_columns;
        rows = new_rows;
    }

    //All the other code needs to be duplicated as well!
};

Questo è, ovviamente, frustrante, non ultimo dal momento che ogni volta che vedo un errore in una versione del codice, devo correggerlo nell'altra, e lo stesso vale se ridisegno qualcosa.

Quindi il mio prossimo pensiero è stato di abbandonare std::vector<T> interamente e solo specializzarmi attorno a std::unique_ptr<T[]> . Questo risolve il problema della duplicazione del codice, ma significa che non posso sfruttare alcun potenziale di ottimizzazione che std::vector<T> offre oltre std::unique_ptr<T[]> , come l'uso intelligente di allocatori e altri vantaggi, il tutto per garantire che Matrix<bool> funzioni correttamente. Ho provato una versione che separa il codice divergente in una superclasse chiamata _matrix_impl<T> che si specializza attorno a bool stesso, lasciando Matrix<T> a non dover specializzare nulla in sé, ma c'era ancora una quantità significativa di duplicazione del codice su cose come le dichiarazioni delle variabili e il codice get_flat_index (per non parlare di molti dei codici non elencati qui duplicati) e ha creato il suo incubo per la manutenibilità del codice, rispetto all'ereditarietà delle superclassi dei template.

Quindi alla fine, la mia domanda è: qual è la soluzione migliore per questa situazione? Poiché il mio codice non ha cose come insert , emplace , o altri costrutti simili, ha senso usare solo std::unique_ptr<T[]> per tutto, poiché molti dei benefici a cui altrimenti avrei accesso sono comunque moot ? Se invece utilizzo std::vector<T> , c'è un modo per gestire con garbo Matrix<bool> senza affrontare il mal di testa che è std::vector<bool> ? Esiste una terza / quarta opzione superiore che non ho nemmeno preso in considerazione?

c++ matrix

posta Xirema 19.06.2017 - 22:20

fonte

1 risposta

Leggi altre domande sui tag c++ matrix

Gli oggetti di servizio sono necessari in OOP? unique varchar (NNN) con un indice nel database e il relativo overhead

score 3 · Accepted Answer

Since my code doesn't have things like insert, emplace, or other similar constructs, does it make sense to just use std::unique_ptr<T[]> for everything, since many of the benefits I'd otherwise have access to are moot anyways?

Non è una cattiva idea dal punto di vista delle prestazioni; dato che la matrice è a dimensione fissa, puoi farla franca con un solo puntatore invece di tre, quindi i tuoi oggetti di matrice saranno leggermente più leggeri di quando utilizzi std::vector come backend di dati; inoltre, dato che quel puntatore ha ora modo di essere modificato al di fuori del costruttore, il compilatore può essere in grado di essere più intelligente ed evitare di rileggerlo dal tuo oggetto quando si eseguono manipolazioni combinate con chiamate di funzioni esterne (è una causa comune di lieve rallentamento con std::vector ).

OTOH, non stai ricevendo il materiale di copia / assegnazione gratuitamente, se è importante che tu lo giudichi.

If I use std::vector<T> instead, is there a way to gracefully handle Matrix<bool> without dealing with the headache that is std::vector<bool>?

Una possibilità che ho effettivamente usato è quella di usare std::vector<T>::reference typedef s per i tuoi accessors, inoltrando quindi qualsiasi oggetto proxy che std::vector<bool> voglia usare direttamente al tuo utente. Quindi, qualcosa del tipo:

typedef std::vector<T>::reference reference;
typedef std::vector<T>::const_reference const_reference;

reference operator()(uint64_t row, uint64_t column) {
    return _data[get_flat_index(row, column)];
}

const_reference operator()(uint64_t row, uint64_t column) const {
    return _data[get_flat_index(row, column)];
}

// ... same with at & co. ...

Per inciso, se devi implementare la tua classe Matrix utilizzando std::vector come back-end, puoi evitare di memorizzare il numero di righe: il std::vector memorizza già le dimensioni complete, quindi l'altezza è solo una divisione di distanza (ma come al solito, controlla se la riduzione della dimensione dell'oggetto Matrix vale il costo aggiuntivo della divisione profilando il codice rispetto a scenari comuni).