template - vector c++




Perché lo STL di C++ è così fortemente basato su modelli?(e non su*interfacce*) (9)

Voglio dire, a parte il suo nome obbligato (la libreria dei modelli standard) ...

Inizialmente, C ++ intendeva presentare i concetti OOP in C. Ovvero: si potrebbe dire cosa un'entità specifica potrebbe e non potrebbe fare (indipendentemente da come lo fa) in base alla sua gerarchia di classi e classi. Alcune composizioni di abilità sono più difficili da descrivere in questo modo a causa delle problematiche dell'ereditarietà multipla, e il fatto che C ++ supporti il ​​concetto di interfacce in un modo un po 'maldestro (rispetto a java, ecc.), Ma è lì (e potrebbe essere migliorata).

E poi i modelli sono entrati in gioco, insieme al STL. L'STL sembrava prendere i classici concetti di OOP e scovarli, usando invece i modelli.

Ci dovrebbe essere una distinzione tra i casi in cui i modelli sono usati per generalizzare i tipi in cui i tipi stessi non sono rilevanti per il funzionamento del modello (contenitori, per esempio). Avere un vector<int> ha perfettamente senso.

Tuttavia, in molti altri casi (iteratori e algoritmi), i tipi di modelli dovrebbero seguire un "concetto" (Input Iterator, Forward Iterator, ecc.) In cui i dettagli effettivi del concetto sono definiti interamente dall'implementazione del modello funzione / classe, e non dalla classe del tipo usato con il modello, che è un po 'anti-uso di OOP.

Ad esempio, puoi dire la funzione:

void MyFunc(ForwardIterator<...> *I);

Aggiornamento: Poichè non era chiaro nella domanda originale, ForwardIterator è ok per essere un modello per consentire qualsiasi tipo di ForwardIterator. Il contrario sta avendo ForwardIterator come un concetto.

si aspetta un Forward Iterator solo osservando la sua definizione, dove è necessario esaminare l'implementazione o la documentazione per:

template <typename Type> void MyFunc(Type *I);

Due affermazioni che posso fare a favore dell'utilizzo dei modelli: il codice compilato può essere reso più efficiente, compilando su misura il modello per ogni tipo utilizzato, invece di usare i vtables. E il fatto che i modelli possono essere utilizzati con tipi nativi.

Tuttavia, sto cercando una ragione più profonda per cui abbandonare l'OOP classico in favore del modello per la STL? (Supponendo che tu abbia letto fino a qui: P)


i tipi di modelli dovrebbero seguire un "concetto" (Input Iterator, Forward Iterator, ecc.) dove i dettagli reali del concetto sono definiti interamente dall'implementazione della funzione / classe template e non dalla classe del tipo usato con il modello, che è un po 'anti-utilizzo di OOP.

Penso che tu fraintenda l'uso previsto dei concetti da parte dei modelli. Forward Iterator, ad esempio, è un concetto molto ben definito. Per trovare le espressioni che devono essere valide affinché una classe sia un Forward Iterator, e la loro semantica compresa la complessità computazionale, si guarda lo standard o su http://www.sgi.com/tech/stl/ForwardIterator.html (devi seguire i link a Input, Output e Trivial Iterator per vederlo tutto).

Quel documento è un'interfaccia perfettamente valida e "i dettagli reali del concetto" sono definiti proprio lì. Non sono definiti dalle implementazioni di Forward Iterators e nemmeno sono definiti dagli algoritmi che usano Forward Iterators.

Le differenze nel modo in cui le interfacce sono gestite tra STL e Java sono triplici:

1) STL definisce espressioni valide usando l'oggetto, mentre Java definisce metodi che devono essere richiamabili sull'oggetto. Naturalmente un'espressione valida potrebbe essere una chiamata metodo (funzione membro), ma non deve essere.

2) Le interfacce Java sono oggetti runtime, mentre i concetti STL non sono visibili in fase di esecuzione anche con RTTI.

3) Se non si riesce a rendere valide le espressioni valide richieste per un concetto STL, si ottiene un errore di compilazione non specificato quando si crea un'istanza di un modello con il tipo. Se non si implementa un metodo richiesto di un'interfaccia Java, si ottiene un errore di compilazione specifico che lo dice.

Questa terza parte è se ti piace una sorta di "duck typing" (in fase di compilazione): le interfacce possono essere implicite. In Java, le interfacce sono piuttosto esplicite: una classe "è" Iterable se e solo se dice che implementa Iterable. Il compilatore può verificare che le firme dei suoi metodi siano tutte presenti e corrette, ma la semantica è ancora implicita (cioè sono documentate o meno, ma solo un numero maggiore di codici (test unitari) può dirti se l'implementazione è corretta).

In C ++, come in Python, sia la semantica che la sintassi sono implicite, anche se in C ++ (e in Python se si ottiene il preprocessore di tipizzazione forte) si ottiene un aiuto dal compilatore. Se un programmatore richiede una dichiarazione esplicita di interfacce Java simile alla classe di implementazione, l'approccio standard consiste nell'utilizzare i tratti di tipo (e l'ereditarietà multipla può impedire che questo sia troppo dettagliato). Quello che manca, rispetto a Java, è un singolo modello che posso istanziare con il mio tipo e che verrà compilato se e solo se tutte le espressioni richieste sono valide per il mio tipo. Questo mi direbbe se ho implementato tutti i bit necessari, "prima di usarlo". Questa è una comodità, ma non è il nucleo di OOP (e ancora non verifica la semantica, e il codice per testare la semantica dovrebbe naturalmente testare anche la validità delle espressioni in questione).

STL può o non può essere sufficientemente OO per i tuoi gusti, ma certamente separa l'interfaccia in modo pulito dall'implementazione. Manca la capacità di Java di fare riflessioni sulle interfacce e segnala le violazioni dei requisiti di interfaccia in modo diverso.

puoi dire alla funzione ... si aspetta un Forward Iterator solo guardando la sua definizione, dove avresti bisogno di guardare l'implementazione o la documentazione per ...

Personalmente penso che i tipi impliciti siano una forza, se usati in modo appropriato. L'algoritmo dice quello che fa con i suoi parametri del template, e l'implementatore si assicura che funzioni: è esattamente il denominatore comune di ciò che le "interfacce" dovrebbero fare. Inoltre con STL, è improbabile che tu stia usando, ad esempio, std::copy basato sulla ricerca della sua dichiarazione diretta in un file di intestazione. I programmatori dovrebbero capire cosa richiede una funzione in base alla sua documentazione, non solo sulla firma della funzione. Questo è vero in C ++, Python o Java. Ci sono limitazioni su cosa è possibile ottenere con la digitazione in qualsiasi lingua, e provare a usare la digitazione per fare qualcosa che non fa (controllare la semantica) sarebbe un errore.

Detto questo, gli algoritmi STL di solito nominano i loro parametri del modello in un modo che rende chiaro quale concetto è richiesto. Tuttavia, questo è di fornire utili informazioni supplementari nella prima riga della documentazione, non di rendere le dichiarazioni di inoltro più istruttive. Ci sono più cose che devi sapere che possono essere incapsulate nei tipi dei parametri, quindi devi leggere i documenti. (Ad esempio, in algoritmi che accettano un intervallo di input e un iteratore di output, è probabile che l'iteratore di output abbia bisogno di uno "spazio" sufficiente per un certo numero di output in base alle dimensioni dell'intervallo di input e forse ai valori in esso. )

Ecco Bjarne su interfacce esplicitamente dichiarate: http://www.artima.com/cppsource/cpp0xP.html

Nei generici, un argomento deve essere di una classe derivata da un'interfaccia (l'equivalente C ++ all'interfaccia è una classe astratta) specificato nella definizione del generico. Ciò significa che tutti i tipi di argomenti generici devono rientrare in una gerarchia. Ciò impone vincoli non necessari sui progetti richiede una previsione irragionevole da parte degli sviluppatori. Ad esempio, se scrivi un generico e definisco una classe, le persone non possono usare la mia classe come argomento per il tuo generico a meno che non conosca l'interfaccia che hai specificato e abbia derivato la mia classe da essa. È rigido

Guardando il contrario, digitando anatra è possibile implementare un'interfaccia senza sapere che l'interfaccia esiste. Oppure qualcuno può scrivere un'interfaccia deliberatamente tale che la tua classe lo implementa, dopo aver consultato i tuoi documenti per vedere che non chiedono nulla che tu già non faccia. È flessibile.


"OOP per me significa solo messaggistica, conservazione locale e protezione e occultamento del processo statale, e estremo legame tardivo di tutte le cose. Può essere fatto in Smalltalk e in LISP. Ci sono probabilmente altri sistemi in cui ciò è possibile, ma Non sono a conoscenza di loro. " - Alan Kay, creatore di Smalltalk.

C ++, Java e la maggior parte delle altre lingue sono abbastanza lontane dal classico OOP. Detto questo, discutere delle ideologie non è terribilmente produttivo. C ++ non è puro in alcun senso, quindi implementa funzionalità che sembrano avere un senso pragmatico al momento.


Il problema di base con

void MyFunc(ForwardIterator *I);

è come si ottiene in modo sicuro il tipo di cosa restituisce l'iteratore? Con i modelli, questo è fatto per te al momento della compilazione.


La mia comprensione è che in origine Stroustrup preferiva un design del contenitore "in stile OOP" e in effetti non vedeva nessun altro modo per farlo. Alexander Stepanov è il responsabile per la STL, e i suoi obiettivi non includevano "renderlo orientato agli oggetti" :

Questo è il punto fondamentale: gli algoritmi sono definiti su strutture algebriche. Mi ci sono voluti un altro paio di anni per capire che devi estendere la nozione di struttura aggiungendo requisiti di complessità a assiomi regolari. ... Credo che le teorie iteratrici siano al centro dell'informatica come le teorie di anelli o spazi di Banach sono centrali per la matematica. Ogni volta che guardo un algoritmo proverei a trovare una struttura su cui è definito. Quindi quello che volevo fare era descrivere gli algoritmi in modo generico. Questo è quello che mi piace fare. Posso passare un mese a lavorare su un algoritmo ben noto cercando di trovare la sua rappresentazione generica. ...

STL, almeno per me, rappresenta l'unico modo in cui la programmazione è possibile. È, infatti, abbastanza diverso dalla programmazione in C ++ come è stato presentato e viene ancora presentato nella maggior parte dei libri di testo. Ma, vedi, non stavo cercando di programmare in C ++, stavo cercando di trovare il modo giusto per gestire il software. ...

Ho avuto molte false partenze. Ad esempio, ho passato anni a cercare di trovare un uso per l'ereditarietà e i virtuals, prima di capire perché quel meccanismo era fondamentalmente difettoso e non dovrebbe essere usato. Sono molto felice che nessuno possa vedere tutti i passaggi intermedi - molti di loro erano molto stupidi.

(Spiega perché l'ereditarietà e il virtualismo - ovvero il design orientato agli oggetti "era fondamentalmente imperfetto e non dovrebbe essere usato" nel resto dell'intervista).

Una volta che Stepanov ha presentato la sua libreria a Stroustrup, Stroustrup e altri hanno intrapreso sforzi titanici per inserirlo nello standard ISO C ++ (stessa intervista):

Il supporto di Bjarne Stroustrup è stato fondamentale. Bjarne voleva davvero STL nello standard e se Bjarne voleva qualcosa, lo capiva. ... Mi ha anche costretto a fare dei cambiamenti in STL che non avrei mai fatto per nessun altro ... lui è la persona più single che conosca. Lui fa le cose. Gli ci volle un po 'per capire che cosa fosse STL, ma quando lo fece, era pronto a farcela. Ha inoltre contribuito alla STL sostenendo l'opinione che più di un modo di programmazione era valido - contro la fine di flak e hype per oltre un decennio, e perseguendo una combinazione di flessibilità, efficienza, sovraccarico e sicurezza del tipo in modelli che hanno reso possibile STL. Vorrei precisare abbastanza chiaramente che Bjarne è il preminente disegnatore di linguaggi della mia generazione.


La risposta più diretta a ciò che penso tu stia chiedendo / lamentando è questa: l'assunto che C ++ sia un linguaggio OOP è un falso assunto.

C ++ è un linguaggio multi-paradigma. Può essere programmato usando i principi OOP, può essere programmato proceduralmente, può essere programmato genericamente (modelli) e con C ++ 11 (precedentemente noto come C ++ 0x) alcune cose possono anche essere programmate funzionalmente.

I progettisti di C ++ vedono questo come un vantaggio, quindi sostengono che costringendo il C ++ ad agire come un puro linguaggio OOP quando la programmazione generica risolve meglio il problema e, beh, più genericamente , sarebbe un passo indietro.


La risposta si trova in questa intervista con Stepanov, l'autore della STL:

Sì. STL non è orientato agli oggetti. Penso che l'orientazione degli oggetti sia quasi una burla come l'Intelligenza Artificiale. Devo ancora vedere un pezzo interessante di codice che proviene da queste persone OO.


Perché un design OOP puro in una libreria Data Structure & Algorithms sarebbe meglio ?! OOP non è la soluzione per ogni cosa.

IMHO, STL è la libreria più elegante che abbia mai visto :)

per la tua domanda,

non è necessario il polimorfismo di runtime, è un vantaggio per STL implementare effettivamente la libreria utilizzando il polimorfismo statico, ovvero l'efficienza. Prova a scrivere un ordinamento o distanza generico o quale algoritmo si applica a TUTTI i contenitori! il tuo Sort in Java chiamerebbe le funzioni che sono dinamiche attraverso n livelli da eseguire!

Hai bisogno di cose stupide come Boxing e Unboxing per nascondere le brutte supposizioni dei cosiddetti linguaggi Pure OOP.

L'unico problema che vedo con STL e i modelli in generale sono i messaggi di errore terribili. Che sarà risolto usando Concepts in C ++ 0X.

Confrontando STL con le collezioni in Java è come confrontare Taj Mahal nella mia casa :)


Questa domanda ha molte ottime risposte. Va anche detto che i modelli supportano un design aperto. Con lo stato attuale dei linguaggi di programmazione orientati agli oggetti, è necessario utilizzare lo schema del visitatore quando si affrontano tali problemi e il vero OOP dovrebbe supportare più associazioni dinamiche. Vedi Open Multi-Methods per C ++, P. Pirkelbauer, et.al. per una lettura molto interessante.

Un altro punto interessante di modelli è che possono essere utilizzati anche per il polimorfismo di runtime. Per esempio

template<class Value,class T>
Value euler_fwd(size_t N,double t_0,double t_end,Value y_0,const T& func)
    {
    auto dt=(t_end-t_0)/N;
    for(size_t k=0;k<N;++k)
        {y_0+=func(t_0 + k*dt,y_0)*dt;}
    return y_0;
    }

Nota che questa funzione funzionerà anche se Value è un vettore di qualche tipo ( non std :: vector, che dovrebbe essere chiamato std::dynamic_array per evitare confusione)

Se func è piccola, questa funzione guadagnerà molto dall'inlining. Esempio di utilizzo

auto result=euler_fwd(10000,0.0,1.0,1.0,[](double x,double y)
    {return y;});

In questo caso, dovresti conoscere la risposta esatta (2.718 ...), ma è facile costruire un semplice ODE senza soluzione elementare (Suggerimento: usa un polinomio in y).

Ora, hai una grande espressione in func , e usi il solutore ODE in molti posti, così il tuo eseguibile viene inquinato con istanze di template ovunque. Cosa fare? La prima cosa da notare è che un puntatore a funzioni regolari funziona. Quindi vuoi aggiungere currying in modo da scrivere un'interfaccia e un'istanza esplicita

class OdeFunction
    {
    public:
        virtual double operator()(double t,double y) const=0;
    };

template
double euler_fwd(size_t N,double t_0,double t_end,double y_0,const OdeFunction& func);

Ma l'istanziazione di cui sopra funziona solo per il double , perché non scrivere l'interfaccia come modello:

template<class Value=double>
class OdeFunction
    {
    public:
        virtual Value operator()(double t,const Value& y) const=0;
    };

e specializzati per alcuni tipi di valori comuni:

template double euler_fwd(size_t N,double t_0,double t_end,double y_0,const OdeFunction<double>& func);

template vec4_t<double> euler_fwd(size_t N,double t_0,double t_end,vec4_t<double> y_0,const OdeFunction< vec4_t<double> >& func); // (Native AVX vector with four components)

template vec8_t<float> euler_fwd(size_t N,double t_0,double t_end,vec8_t<float> y_0,const OdeFunction< vec8_t<float> >& func); // (Native AVX vector with 8 components)

template Vector<double> euler_fwd(size_t N,double t_0,double t_end,Vector<double> y_0,const OdeFunction< Vector<double> >& func); // (A N-dimensional real vector, *not* `std::vector`, see above)

If the function had been designed around an interface first, then you would have been forced to inherit from that ABC. Now you have this option, as well as function pointer, lambda, or any other function object. The key here is that we must have operator()() , and we must be able to do use some arithmetic operators on its return type. Thus, the template machinery would break in this case if C++ did not have operator overloading.


The concept of separating interface from interface and being able to swap out the implementations is not intrinsic to Object-Oriented Programming. I believe it's an idea that was hatched in Component-Based Development like Microsoft COM. (See my answer on What is Component-Driven Development?) Growing up and learning C++, people were hyped out inheritance and polymorphism. It wasn't until 90s people started to say "Program to an 'interface', not an 'implementation'" and "Favor 'object composition' over 'class inheritance'." (both of which quoted from GoF by the way).

Poi Java è arrivato con un garbage collector e una interfaceparola chiave incorporati , e all'improvviso è diventato pratico separare interfaccia e implementazione. Prima che tu lo sai, l'idea è diventata parte della OO. C ++, modelli e STL sono precedenti a tutto questo.







stl