I vantaggi di std :: string non memorizzare i dati in una posizione di memoria contigua (pre C++ 11)

In C++98 e C++03std::string potrebbe avere memorizzato i dati sottostanti in una memoria non contigua. Qual è stata la ragione di questo? Quale possibile ottimizzazione potrebbe essere stata raggiunta da questo requisito rilassato? Qualche compilatore/architettura ha effettivamente fatto uso di questo?I vantaggi di std :: string non memorizzare i dati in una posizione di memoria contigua (pre C++ 11)

Se alcune parti della stringa sono memorizzate in posizioni di memoria diverse, l'iteratore non sarebbe eccessivamente complicato? E anche la classe, in quanto avrebbe bisogno di sapere esattamente dove sono diverse parti della stringa.

fonte

2015-12-08 bolov

Non c'è alcun motivo per cui l'iteratore sarebbe eccessivamente complicato. Potrebbe essere implementato come 'pair ', con 'operator *' indicizzando la stringa, 'operator ++' incrementando l'indice e così via. La classe dovrebbe ovviamente sapere dove sono le diverse parti, ma può essere molto efficace se conservata in un albero bilanciato. Vedi [corda] (https://en.wikipedia.org/wiki/Rope_ (data_structure)). – user4815162342

Ecco un altro pro/contro per l'implementazione della corda (che - come ho capito - aveva in mente lo standard come qualcosa che dovrebbe essere possibile): http://www.sgi.com/tech/stl/Rope.html – peterchen

Il motivo principale era che la concatenazione di stringhe poteva avvenire senza ridistribuzione. Credo che le prime versioni di STLPort lo abbiano sfruttato.

Un altro motivo è che è stato possibile implementare la copia su scrittura o anche la copia su scrittura parziale. Sebbene altri requisiti richiesti da std::string (in particolare la semantica di spostamento di C++ 11) ora significano che questo non è più possibile.

fonte

2015-12-08 12:38:33 Bathsheba

wouldn ' l'iteratore sarebbe eccessivamente complicato? Anche la classe sarebbe complicata in quanto dovresti sapere esattamente dove sono le parti della tua stringa. – bolov

Senza pensarci troppo, avrei pensato che l'iterazione fosse un po 'più complicata di una semplice traversata per parti contigue accoppiata con un idioma di tipo lista collegata. – Bathsheba

@bolov: re iteratori: in modo sopportabile. Iterator conterrebbe un riferimento al segmento e un offset nel segmento. Se i segmenti sono tenuti in una lista doppiamente collegata o qualsiasi cosa bidirezionalmente iterabile, è * "un addizionale' se' "*. – peterchen

I vantaggi di std :: string non memorizzare i dati in una posizione di memoria contigua (pre C++ 11)

risposta

Problemi correlati