Sarebbe questo l'ottimizzazione nella realizzazione di std :: string essere permesso?

Question

Stavo solo pensando alla realizzazione di std::string::substr. Esso restituisce un nuovo oggetto std::string, che sembra un po 'uno spreco per me. Perché non restituire un oggetto che si riferisce al contenuto della stringa originale e può essere implicitamente assegnato a un std::string? Una sorta di valutazione pigra della copia reale. Tale Classe A potrebbe essere simile a questa:

template <class Ch, class Tr, class A>
class string_ref {
public:
    // not important yet, but *looks* like basic_string's for the most part

private:
    const basic_string<Ch, Tr, A> &s_;
    const size_type pos_;
    const size_type len_;    
};

L'interfaccia pubblica di questa classe sarebbe imitare tutte le operazioni di sola lettura di un vero e proprio std::string, quindi l'utilizzo sarebbe senza soluzione di continuità. std::string potrebbe quindi avere un nuovo costruttore che prende un string_ref modo che l'utente non sarebbe mai stato il più saggio. Nel momento in cui si cerca di "store" il risultato, si finisce per creare una copia, le questioni in modo che nessun reali con il riferimento indicando i dati e quindi averlo modificato dietro la schiena.

L'idea è che il codice come questo:

std::string s1 = "hello world";
std::string s2 = "world";
if(s1.substr(6) == s2) {
    std::cout << "match!" << std::endl;
}

avrebbe non più di 2 std::string oggetti costruiti in totale. Questo mi sembra un utile per l'ottimizzazione del codice che che esegue un sacco di manipolazioni di stringhe. Naturalmente, questo non vale solo per std::string, ma a qualsiasi tipo che può restituire un sottoinsieme del suo contenuto.

Per quanto ne so, non implementazioni farlo.

I supponiamo che il nocciolo della questione è:

Data una classe che può essere convertito in modo implicito un std::string se necessario, sarebbe conforme allo standard per uno scrittore libreria per cambiare il prototipo di tipo a ritorno di un membro? O più in generale, fare gli scrittori della biblioteca hanno il margine di manovra per tornare "oggetti proxy" invece di oggetti normali in questo tipo di casi come un'ottimizzazione?

Il mio intestino è che questo non è consentito e che i prototipi deve corrispondere esattamente. Dato che non si può sovraccaricare il tipo di ritorno da solo, che lascerebbe spazio a scrittori biblioteca di approfittare di questi tipi di situazioni. Come ho detto, credo che la risposta è no, ma ho pensato di chiedere: -).

Answer 1

Questa idea è copy-on-write , ma invece di COW'ing l'intero buffer, a tenere traccia di quale sottoinsieme del buffer è la stringa "reale". (COW, nella sua forma normale, era (è?) Utilizzato in alcune implementazioni di libreria.)

Quindi, non hai bisogno di un oggetto proxy o un cambiamento di interfaccia a tutti perché questi dettagli possono essere realizzati completamente interna. Concettualmente, è necessario tenere traccia delle quattro cose: un buffer di origine, un conteggio di riferimento per il buffer, e l'inizio e la fine della stringa all'interno di questo buffer

.

Sempre un funzionamento modifica il buffer affatto, crea la propria copia ( dai inizio e fine delimitatori ), diminuisce conteggio di riferimento del vecchio tampone per uno, e insiemi di riferimento del nuovo tampone conteggio a uno. Il resto delle regole di conteggio di riferimento sono gli stessi: la copia e il numero di aumento per uno, Destruct un conteggio di stringa e il decremento di una, raggiungono lo zero ed eliminare, etc

.

substr fa solo una nuova istanza di stringa, se non con i delimitatori di inizio e fine esplicitamente specificato.

Answer 2

Questo è un ben noto ottimizzazione piuttosto che è relativamente ampiamente utilizzato, chiamato copy-on-write o di mucca. La cosa fondamentale non è nemmeno a che fare con sottostringhe, ma con qualcosa di semplice come

s1 = s2;

Ora, il problema con questa ottimizzazione è che per le librerie C ++ che si suppone possano essere utilizzati su obiettivi che supportano più thread, il conteggio dei riferimenti per la stringa deve essere accessibile tramite operazioni atomiche (o peggio, protetto con un mutex nel caso in cui la piattaforma di destinazione non fornisce operazioni atomiche). Questo è abbastanza costoso che nella maggior parte dei casi la semplice implementazione stringa non COW è più veloce.

Vedere GotW # 43-45:

http://www.gotw.ca/gotw/043.htm

http://www.gotw.ca/gotw/044.htm

http://www.gotw.ca/gotw/045.htm

A peggiorare le cose, le biblioteche che hanno COW utilizzati, come ad esempio la biblioteca di GNU C ++, non può semplicemente riversati alla semplice implementazione in quanto ciò rompere l'ABI. (Anche se, C ++ 0x in soccorso, come che richiederà un ABI urto comunque! :))

Answer 3

Dal momento che i rendimenti substr std::string, non v'è alcun modo per restituire un oggetto proxy, e non può semplicemente cambiare il tipo di ritorno o sovraccarico su di esso (per i motivi che lei ha citato).

Si potrebbe fare questo facendo string sé capace di essere un sub di un'altra stringa. Ciò significherebbe un rigore di memoria per tutti gli usi (per contenere una stringa supplementare e due size_types). Inoltre, ogni operazione avrebbe bisogno di controllo per vedere se ha i caratteri o è un proxy. Forse questo potrebbe essere fatto con un puntatore implementazione -. Il problema è, ora stiamo facendo una classe di uso generale più lento per un possibile caso limite

Se avete bisogno di questo, il modo migliore è quello di creare un'altra classe, substring, che costruisce da una stringa, pos, e la lunghezza, e ripari a stringa. Non è possibile utilizzare come s1.substr(6), ma si può fare

 substring sub(s1, 6);

Si sarebbe anche bisogno di creare operazioni comuni che prendono una stringa e la stringa per evitare la conversione (dal momento che è il punto).

Answer 4

Per quanto riguarda il tuo esempio specifico, questo ha funzionato per me:

if (&s1[6] == s2) {
    std::cout << "match!" << std::endl;
}

Questo non può rispondere alla tua domanda per una soluzione general-purpose. Per questo, avreste bisogno di sub-string mucca, come suggerisce @GMan.

Answer 5

Che cosa si sta parlando è (o era) uno dei core dotato di classe java.lang.String di Java ( http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/ ). In molti modi, i disegni di classe String di Java e C ++ 's basic_string modello sono simili, quindi mi immagino che scrivere un'implementazione del modello basic_string utilizzando questa 'ottimizzazione sottostringa' è possibile.

Una cosa che è necessario prendere in considerazione è come scrivere l'attuazione del membro c_str() const. A seconda della posizione di una stringa come una sottostringa di un altro, può essere necessario creare una nuova copia. E 'sicuramente avrebbe dovuto creare una nuova copia della matrice interna, se la stringa per la quale è stato richiesto il c_str non è una sottostringa finale. Credo che ciò richiede utilizzando la parola chiave mutable sulla maggior parte, se non tutti, i membri di dati di attuazione basic_string, complicando notevolmente l'attuazione di altri metodi const perché il compilatore non è più in grado di assistere il programmatore con const correttezza.

Modifica In realtà, per ospitare c_str() const e data() const, è possibile utilizzare un singolo campo mutabile di tipo const charT*. Inizialmente su NULL, potrebbe essere per-esempio, inizializzato un puntatore a una nuova matrice charT ogniqualvolta c_str() const o data() const sono chiamati, ed eliminati nel distruttore basic_string se non NULL.

Answer 6

Se e solo se si ha realmente bisogno di più prestazioni rispetto std :: string fornisce poi andare avanti e scrivere qualcosa che funziona il modo in cui avete bisogno di. Ho lavorato con varianti di stringhe prima.

La mia preferenza è quella di utilizzare stringhe non mutabili, piuttosto che copy-on-write, e di usare boost :: shared_ptr o equivalente, ma solo quando la stringa è in realtà al di là di 16 di lunghezza, quindi la classe String dispone anche di un privato tampone per brevi stringhe.

Questo significa che la classe string potrebbe portare un po 'di peso.

ho anche nella mia lista collezione un "fetta" di classe in grado di guardare un "sottoinsieme" di una classe che vive altrove fino a quando il ciclo di vita dell'oggetto originale è intatto. Quindi nel tuo caso ho potuto tagliare la corda per vedere una sottostringa. Naturalmente non sarebbe terminazione Null, né v'è alcun modo per renderlo tale senza copiandolo. E non è una classe stringa.