std :: string e il suo ridimensionamento automatico della memoria

Question

Sono abbastanza nuovo a C ++, ma so che non si può semplicemente usare la memoria volenti o nolenti come la classe std :: string sembra farvi fare. Per esempio:

std::string f = "asdf";
f += "fdsa";

In che modo la maniglia classe string sempre più grandi e più piccoli? Presumo che alloca una quantità predefinita di memoria e se ha bisogno di più, news un blocco più grande di memoria e si replica oltre a quella. Ma non sarebbe che essere piuttosto inefficiente di dover copiare l'intera stringa ogni volta che aveva bisogno di ridimensionare? Non posso davvero pensare ad un altro modo in cui potrebbe essere fatto (ma ovviamente qualcuno ha fatto).

E del resto, come fanno tutte le classi stdlib come vettore, coda, pila, ecc manico in crescita e contrazione in modo trasparente?

Answer 1

Di solito, c'è un algoritmo di raddoppio. In altre parole, quando si riempie il buffer corrente, si alloca un nuovo buffer che è due volte più grande, e quindi copia i dati correnti sopra. Ciò comporta minori allocano / operazioni di copia rispetto all'alternativa di crescere da un unico blocco di allocazione.

Answer 2

La tua analisi è corretta - è è inefficiente per copiare la stringa ogni volta che ha bisogno di ridimensionare. Ecco perché scoraggia consiglio comune che tipo di impiego. Utilizzare reserve funzione della stringa di chiedere ad allocare memoria sufficiente per quello che intenzione per memorizzare in esso. Poi ulteriori operazioni riempiranno quel ricordo. (Ma se il tuo suggerimento risulta essere troppo piccola, la stringa sarà ancora crescere automaticamente, anche.)

Container sarà anche di solito cercare di mitigare gli effetti di frequente ri-allocazione assegnando più memoria di cui hanno bisogno. Un algoritmo comune è che quando una stringa reperti che è fuori di spazio, doppie le dimensioni del buffer invece di allocare il minimo necessario per contenere il nuovo valore. Se la stringa viene cresciuto un carattere per volta, questo algoritmo raddoppiando riduce la complessità temporale di tempo lineare ammortizzato (invece di tempo quadratico). Si riduce anche la suscettibilità del programma per la frammentazione della memoria.

Answer 3

Anche se non so esattamente realizzazione di std :: string, la maggior parte delle strutture di dati che hanno bisogno per gestire la crescita memoria dinamica farlo facendo esattamente quello che dici - allocare una quantità predefinita di memoria, e se più è necessario quindi creare un blocco più grande e copia te stesso più.

Il modo in cui si ottiene intorno al problema dell'inefficienza ovvia è quella di allocare più memoria del necessario. Il rapporto di memoria utilizzata: la memoria totale di un vettore / string / list / etc è spesso chiamato il fattore di Carica (utilizzato anche per le tabelle hash in un significato leggermente diverso). Di solito si tratta di un rapporto di 1: 2 - che è, si assegna il doppio della memoria si ha bisogno. Quando si esaurisce lo spazio, si assegna una nuova quantità di memoria due volte l'importo attuale e usare quella. Ciò significa che nel corso del tempo, se si continua ad aggiungere le cose al vettore / string / etc, è necessario copiare la voce sempre meno (come la creazione di memoria è esponenziale, e il vostro inserimento di nuovi elementi è naturalmente lineare), e così il tempo impiegato per questo metodo di gestione della memoria non è così grande come si potrebbe pensare. Con i principi di analisi ammortizzata , si può quindi vedere che l'inserimento di elementi m in un vettore / string / lista usando questo metodo è solo Big-Theta di m, non m ² .