Esercizio C++ accelerato 11-6

Question

Rimanere bloccato nella funzione di cancellazione su ch 11 esercizio 11-6. Ho distrutto gli oggetti ma non ho idea di come utilizzare deallocazione dalla libreria di allocatori per restituire lo spazio.

Si prega di salvarmi. PS: non è compito a casa ma mi sto esercitando a casa

Di seguito è riportato il codice da C++ accelerato e successivamente la funzione di cancellazione modificata. Grazie `

template <class T> class Vec 
{ 
public: 
    typedef T* iterator; 
    typedef const T* const_iterator; 
    typedef size_t size_type; 
    typedef T value_type; 
    typedef T& reference; 
    typedef const T& const_reference; 

    Vec() { create(); } 
    explicit Vec(size_type n, const T& t = T()) { create(n, t); } 
    Vec(const Vec& v) { create(v.begin(), v.end()); } 
    Vec& operator=(const Vec&); 
    ~Vec() { uncreate(); } 

    T& operator[](size_type i) { return data[i]; } 
    const T& operator[](size_type i) const { return data[i]; } 

    void push_back(const T& t) 
    { 
     if (avail == limit) 
     { 
      grow(); 
     } 

     unchecked_append(t); 
    } 

    iterator erase(iterator); 
    iterator erase(iterator, iterator); 
    void clear(); 

    size_type size() const { return avail - data; } 

    iterator begin() { return data; } 
    const iterator begin() const { return data; } 

    iterator end() { return avail; } 
    const iterator end() const { return avail; } 

private: 
    iterator data; 
    iterator avail; 
    iterator limit; 

    std::allocator<T> alloc; 

    void create(); 
    void create(size_type, const T&); 
    void create(const_iterator, const_iterator); 

    void uncreate(); 

    void grow(); 
    void unchecked_append(const T&); 
}; 

mio codice

template <class T> typename Vec<T>::iterator Vec<T>::erase(iterator first, iterator second) 
{ 
    if(second < first) 
    { 
     throw std::out_of_range("Iterator out of bounds."); 
    } 
    if(first < data || second >= avail) 
    { 
     throw std::out_of_range("Iterator out of bounds."); 
    } 
    iterator last = avail -1 ; 
    iterator i = first ; 
    iterator j = second ; 
    while(j <= last) 
    { 
     *i++ = *j++ ; 

    } 
    // destroy each initilsed space 
    iterator new_avail = avail - first + second ; 

    std::cout << " end " << end() << std::endl; 

    while(avail != new_avail) 
    { 
     alloc.destroy(--avail) ; 
    } 


    // dellocate space how to do that ? 
    alloc.deallocate(avail -1, ); // not sure what to do here 
    return first ; 

} 

Answer 1

Non è possibile deallocare una parte della memoria allocata. che

alloc.deallocate (disponibile -1,);

non va bene.

Modifica

Non si dovrebbe cercare di mangage assegnazione in cancellazione. Un'opzione che hai è di riallocarla, il che renderà la cancellazione ancora più costosa. Una seconda funzione potrebbe fare:

iterator shrink(iterator first, iterator last) { 

    size_type capacity = (limit - data) - (last - first); 

    iterator new_data = alloc.allocate(capacity); 
    iterator new_avail = new_data; 
    iterator source = data; 
    while(source < first) 
     // C++11 
     alloc.construct(new_avail++, std::move(*source++)); 
    source = last; 
    iterator result = new_avail; 
    while(source < avail) 
     // C++11 
     alloc.construct(new_avail++, std::move(*source++)); 
    while(data < avail) 
     alloc.destroy(--avail); 
    data = new_data; 
    avail = new_avail; 
    limit = new_data + capacity; 

    return result; 
} 

Un'opzione migliore è questa modalità standard. Aggiungere un costruttore aggiuntivo, swap e shrink_to_fit:

Vec(const_iterator first, const_iterator last) { 
    create(first, last); 
} 

void swap(Vec& other) { 
    std::swap(data, other.data); 
    ... 
} 

bool shrink_to_fit() { 
    try 
    { 
     Vec(begin(), end()).swap(*this); 
     return true; 
    } 
    catch(...) {} 
    return false; 
} 

Ora è possibile applicare le operazioni sul vettore e ridurre il consumo di memoria, infine.

v.erase(a, b); 
v.erase(c, d); 
... 
v.shrink_to_fit(); 

Answer 2

suppongo, che una delle soluzioni è quello di creare un nuovo vettore con il seguente formato:

new_size = old_size - number_of_elements_to_delete 

Poi si copiano oggetti dall'inizio al primo oggetto di cancellazione, dall'ultimo oggetto che cancella fino alla fine e quindi rilascia il vecchio vettore.

Non è la soluzione migliore, ma il più semplice come suppongo.

Answer 3

Ecco cosa un reference page for std::allocator::deallocate ha avuto modo di dire:

void deallocate(pointer p, size_type n);

rilascia l'archiviazione a cui fa riferimento il puntatore p, che deve essere un puntatore ottenuto da una precedente chiamata a allocate(). L'argomento n deve essere uguale al secondo argomento della chiamata a allocate() che ha originariamente prodotto p.

Cioè, non è possibile deallocare una parte dello spazio di archiviazione che è stato assegnato, ma solo l'intero blocco.

La soluzione sarebbe quella di non restituire lo spazio di archiviazione reso gratuito dalla chiamata a erase. È sufficiente aggiornare gli iteratori dei membri di conseguenza in modo da mantenere questo spazio disponibile per le chiamate successive a create. Questo è anche il contenitore standard vector.

Se si desidera veramente restituire spazio in eccesso, allocare un blocco temporaneo più piccolo, copiare gli elementi che rimangono nel contenitore, rilasciare il vecchio archivio e aggiornare gli iteratori.

La cosa da tenere a mente qui è la sicurezza delle eccezioni. Una volta assegnato un buffer temporaneo, è necessario assicurarsi di non averlo perso nel caso in cui si verifichi un'eccezione durante la copia degli elementi.

Answer 4

Come jrok e gli altri hanno menzionato, non è possibile deallocare parte della memoria: è necessario deallocare lo entire referenced storage.

C'è una cosa più importante - se si guarda attraverso capitolo 11 (in particolare, sotto 11.4, dinamico VECS), noterete che l'implementazione per push_back() raddoppia la dimensione della matrice sottostante, una volta raggiunta la massima corrente dimensione.

Su linee simili, che ci si vuole dimezzare la dimensione della matrice sottostante quando la dimensione del vettore diventa un quarto della dimensione massima corrente. Questo è quando avresti bisogno di riallocare la memoria e chiamare std::allocator::deallocate per rilasciare la memoria in eccesso.