Newsgroup: it.comp.lang.c++
Titolo: Manuale c++ (libreria standard)

Dove posso trovare qualche manuale sul c++ standard? sui nuovi "tipi"
string, vector, list, ecc. e su come usare gli iteratori, ecc.???
Tutto nasce da un problema semplice semplice: scansire un vettore alla
ricerca di elementi da eliminare... qual č il modo piů giusto per
farlo?
Pensavo di scansirlo da end() - 1 fino a begin(), perché altirmenti
quando elimino un elemento non riesco a scansirli tutti...
dico bene?
me lo scrivete 'sto ciclo come lo fareste voi?
e mi dite dove posso trovare le risposte a queste domande troppo
facili per essere chieste qui? :-DD
-- 
]\/[ad]\/[age
"Un Maestro insegue semplicemente la sua visione di Eccellenza in
qualunque cosa sta facendo e lascia agli altri decidere se sta 
lavorando o giocando. A lui sembra sempre di fare entrambe." - Anonimo

 farlo?
Esistono funzioni apposite nella libreria standard. In
www.dinkumware.com/htm_cpl/index.html
 clicca su <algorithm> per aprire
la pagina relativa a questo header e poi clicca sulla funzione remove_if
(o se vuoi una copia del vettore dove mancano alcuni elementi clicca su
remove_copy_if).
(nota: se accedi alla documentazione online di DinkumWare ogni tanto ti
esce una pagina dove ti propongono di comperare una copia della
documentazione stessa. Clicca sul pulsantino in basso per continuare a
navigare).
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 me lo scrivete 'sto ciclo come lo fareste voi?
Tutti i container della libreria standard dipongono di un metodo erase()
con la seguente signature:
        iterator erase(iterator it);
erase() rimuove l'elemento identificato dall'iteratore passato come
argomento e restituisce un iteratore che punta al primo degli elementi che
rimangono dopo quello rimosso (oppure end() se non ci sono elementi
residui). Ad esempio, per rimuovere progressivamente tutti gli elementi:
   while( i != container.end() )
   {
       i = container.erase(i);
   }
Max

 me lo scrivete 'sto ciclo come lo fareste voi?
Se devi eliminare un valore che conosci:
std::vector<int> v;
v.erase(std::remove(v.begin(), v.end(), valore_da_eliminare), v.end());
se hai una funzione che prende un intero e ti dice se va eliminato o no:
bool elimina(int x);
v.erase( remove_if(v.begin(), v.end(), elimina), v.end());
lo puoi anche fare con un tradizionale for di iteratori tenendo conto
che quando elimini un elemento invalidi l'iteratore, insomma non puoi
scrivere qualche cosa del tipo:
typedef std::vector<int> V;
V v;
.....
V::iterator it  v.begin();
for ( ; it ! v.end(); ++it)
{
    if ( devo_cancellare(*it) )  v.erase(it);
}
 infatti dopo la erase hai invalidato l'operatore e non
puoi piu' incrementarlo. L'approccio corretto:
typedef std::vector<int> V;
V v;
.....
V::iterator it  v.begin();
for ( ; it ! v.end(); )
{
    if ( devo_cancellare(*it) )  it  v.erase(it);
    else ++it;
}
Spero di non aver detto troppe cavolate.
Nota che tutto quello che ti ho detto vale per i vettori,
per liste e associative container le cose cambiano.
Ciao
Gaetano.
-- 
Posted from 
nts-03.mm.eutelsat.org
 [194.214.173.15] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Spero di non aver detto troppe cavolate.
Non troppe. Però ti propongo un piccolo quiz.
Supponiamo di avere una sequenza di interi (nel mio esempio un vector ma
potrebbe essere deque o list):
    typedef vector<int> MySequence;
    typedef MySequence::iterator SeqIt;
    MySequence seq;
e supponiamo che contenga qualche migliaio di interi a caso sia positivi
che negativi (e non in ordine).
Secondo te c'è differenza (a parte questioni di leggibilità e
manutenibilità) fra il fare:
    for ( SeqIt it=seq.begin(); it != seq.end(); ) {
        if ( *it < 0 )
            it = seq.erase(it);
        else
            ++it;
    }
ed il fare invece
    SeqIt it = remove_if(seq.begin(), seq.end(),
bind2nd(less<int>(),0));
    seq.erase( it, seq.end() );
Ovviamente invito Maurizio, Nicola e gli altri esperti a non dare subito
la risposta (ma se non ci avete mai pensato e non lo avete letto da
qualche parte ... pensateci).


 qualche parte ... pensateci).
Io la posso dare subito ?


 Non troppe.
Quali?


}
ti sei sistematicamente dimenticato dell'operando sinistro per
l'operatore '.'.
In altre parole mancano le 'v' prima dei '.'.
Inoltre hai proposto due soluzioni diverse ma che non sono del tutto
equivalenti e ti sei dimenticato di spiegare le differenze fra le due
(vedi quiz e relativo subtrhead).


 Io la posso dare subito ?
Beh, il quiz l'ho posto a te. Più che altro perchè hai proposto due
soluzioni diverse ma che non sono del tutto equivalenti e ti sei
dimenticato di spiegare le differenze fra le due. Quindi sei
direttamente chiamato in causa.


 In altre parole mancano le 'v' prima dei '.'.
In realta io l'ho messa, ma non so perche' ma mailgate le toglie !!!!!
Secondo te posso scrivere .erase() ? (qui non l'ho messa di 
proposito).
Ci riprovo:
    v.erase();   // <-- Se qui manca la v allora e' stata tolta.
Ciao
Gaetano.


     v.erase();   // <-- Se qui manca la v allora e' stata tolta.
ROTFL
Io dico che mailgate ti sta pigliando per il c..o ;-P


 In altre parole mancano le 'v' prima dei '.'.
Strano, io le "v" le leggo tutte :-) 
-- 
FUSION (fyu zh & n) n: 
1) the Act or Process of Fusing or Melting Together... 
2) the State of being Fused... 
3) to Join or become Combined...

Io dico che mailgate ti sta pigliando per il c..o ;-P
Eh eh, invece è OE che sta pigliando per il culo te! <g>
(Hint: il messaggio di Gaetano è in quoted printable...)
-- 
Ciao, Marvin

 wrote in message
news:9srf9i.3...@marvin.gpp.despammed.com...

Per nulla. Io la v la vedo benissimo. Proprio per questo ridevo. Gaetano
ha postato quel messaggio per dimostrare che se anche se lui la v la
mette, poi mailgate gliela toglie. E mailgate non l'ha tolta proprio per
nulla.


 Strano, io le "v" le leggo tutte :-)
Anche nel messaggio originale di Gaetano? Mo vado a controllare. Può
essere l'ennesima cappellata di OL. Ma non vedo perchè togliere delle v!
(e soprattutto perchè solo a volte).


 nulla.
Credo che Marvin intendesse che anche nel messaggio originale di Gaetano
sei l'unico che non vede le v. In effetti io le vedo nel suo messaggio,
ma non dove tu lo quoti. Cambia newsreader!
Ciao,
Nicola

 Strano, io le "v" le leggo tutte :-)
Si hai ragione. Maledetto OL.


 (Hint: il messaggio di Gaetano è in quoted printable...)
Azz. Hai ragione. Porca puzzola.


 wrote in message
news:3BF13B02...@divalsim.it...

Si, va be. Sei stato troppo veloce! Ho postato quel messaggio, poi l'ho
ritirato ... e tu già avevi replicato. Quando ti servono i tempi di
latenza delle news ... latitano.
Purtroppo non posso cambiare reader su questa macchina (potrei usare
mailgare ma diventa scomodissimo).
Magari in un futuro prossimo venturo ...
Ma porca puzzola, possibile che OL non ne faccia una giusta. Manco 'na
cagata come il QP gestisce correttamente :-(


 direttamente chiamato in causa.
Ho fatto un semplice programma di test.
Container da 10000 elementi e ho provato a
ad eliminare i numeri negativi con entrambi i metodi,
un numero di volte pari a "cicles".
Il risultato e' stato il seguente (tempi mediati sulle prove):
30.1      deque (erase-remove_if)  -> 513 ms (100 cicles)
30.2      deque (for)                       -> 18.840 sec [18840 ms] (100
cicles)
40.1      list (erase-remove_if)        -> 5.869 sec [5869 ms] (1000 cicles)
40.2      list (for)                             -> 6.294 sec [6294 ms]
(1000 cicles)
50.1      vector (erase-remove_if)   -> 244 ms (50 cicles)
50.2      vector (for)                        -> 9.642 sec [9642 ms] (50
cicles)
Da quello che posso evincere:
    List: quasi indipendente il metodo scelto.
            Credo che il for e' piu' lento a causa della chiamata end() ad
ogni ciclo.
    Vector: e' meglio l'idioma "erase-remove_if".
    Deque: come per i vector.
PS. Se vuoi sapere anche perche', dovrei guardare esattamente cosa fa la STL
dentro.
Ciao
Gaetano.


 
Visto che siamo in vena di quiz, sono curioso di vedere se qualcuno riesce
a svelare... 
   l' enigma delle 'v' mancanti 
Vi do un piccolo indizio:  tutte le 'v' "scomparse" seguivano
immediatamente il segno '='.
Max

 immediatamente il segno '='.
Come puoi evincere dai miei replay a Nicola e a Davide il problema era
mio con quella schifezza di OL che non sa neppure gestire decentemente
il QP (in pratica si pappa i due caratteri successivi agli = a meno che
non siano effettivamente delle sequenze QP).
Il fatto è che non sempre uso OL per leggere i NG, ma per i NG ai quali
partecipo (qulli in cui scrivo) praticamente lo devo usare dato che lo
faccio da una postazione che ho al lavoro nei momenti di attesa
(encoding di un film, multiplexing di un file VOB o cose simili).
E su questa postazione ho qualche limite di policy amministrativa (il
SysOp sono io, ma mica posso imporre una filosofia diversa alle macchine
solo perchè mi va di postare cose personali! Care e grazie che posso
farlo sfruttando gli strumenti presenti per altri motivi!).


 (encoding di un film, multiplexing di un file VOB o cose simili).
Allora cambia lavoro!!!!!!!
8-PPPPP
-- 
Luc.

 non siano effettivamente delle sequenze QP).
Credo, però, che un testo marcato come quoted-printable non possa
contenere sequenze =?? non valide e il testo iniziale inviato da Gaetano
(tramite Mailgate) contiene in effetti caratteri '=' non seguiti da codici
esadecimali. 
Pine (4.10) si rifiuta proprio di visualizzarlo quel messaggio, segnalando
errori nella codifica.
In realtà, sembra che Mailgate marchi come quoted-printable i messaggi
senza di fatto effettuare alcun tipo di encoding. Forse, sarebbe il caso
di segnalarlo.
Max

 di segnalarlo.
Mumble. Salvo prima fare qualche prova in it.test per verificare direi
di si.


 di Gaetano è effettivamente non conforme.
Ora la colpa e' mia!


 la STL dentro.
No. Se ogni volta che usi la STL devi andarti a studiare il sorgente sei
fritto!
Quello che ti serve sapere č solo quello che ti riporto e che, piů o
meno, dovrebbe stare anche nel tuo reference della STL (il testo sotto č
tratto in parte dal reference online di SGI e in parte da quello di
Dinkumware):
Per la remove if ti serve sapere:
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(  ForwardIterator first,
                            ForwardIterator last,
                            Predicate pred );
Remove_if removes from the range [first, last) every element x such that
pred(x) is true. That is, remove_if returns an iterator new_last such
that the range [first, new_last) contains no elements for which pred is
true. The iterators in the range [new_last, last) are all still
dereferenceable, but the elements that they point to are unspecified.
Remove_if is stable, meaning that the relative order of elements that
are not removed is unchanged. It executes in linear time. Remove_if
performs exactly last - first applications of pred.
Per i metodi erase ti serve sapere:
iterator erase(iterator where);
iterator erase(iterator first, iterator last);
The first member function removes the element of the controlled sequence
pointed to by where. The second member function removes the elements of
the controlled sequence in the range [first, last). Both return an
iterator that designates the first element remaining beyond any elements
removed, or end() if no such element exists.
Quanto sopra vale sia per list che per vector che per deque. Sempre
sulle erase valgono poi queste (che cambiano da classe a classe):
list::erase
Erasing N elements causes N destructor calls. No reallocation occurs, so
iterators and references become invalid only for the erased elements.
vector::erase
Erasing N elements causes N destructor calls and an assignment for each
of the elements between the insertion point and the end of the sequence.
No reallocation occurs, so iterators and references become invalid only
from the first element erased through the end of the sequence.
deque::erase
Removing N elements causes N destructor calls and an assignment for each
of the elements between the insertion point and the nearer end of the
sequence. Removing an element at either end invalidates only iterators
and references that designate the erased elements. Otherwise, erasing an
element invalidates all iterators and references.


Ora la colpa e' mia!
Ho detto che è non conforme il tuo post. Il post non conforme è il tuo.
La colpa non so (penso di mailgate).


 fritto!
Non ho detto di andare a guardare il codice, ma gli "internals" che sono
quelli che
hai postato tu.


     seq.erase( it, seq.end() );
Su un vettore la erase e' piuttosto pesante, infatti, essendo gli elementi
del contenitore memorizzati in memoria contigua, per rimuovere l' i-esimo
elemento, tutti gli n-i elementi che lo seguono vanno spostati di un posto:
quoesto implica n-i copie , n-i distruttori eccetera.
in caso di O(n) cancellazioni, si hanno almeno O(n^2) operazioni.
(La cosa potrebbe essere ancora piu' pesante se gli elementi del vettore non
sono tipi primitivi ma oggetti complessi)
Usando la erase_if, invece gli elementi che non verificano la condizione di 
test vengono copiati in testa al vettore, lasciando indeterminati gli altri
oggetti. Questo comporta una complessita' O(n).
Per la deque il discorso e' analogo (anche se la erase dovrebbe essere un
po' piu' efficiente)
Nel caso di liste il discorso cambia, e conviene usare il primo metodo.
Infatti in questo caso i vari elementi vengono eliminati "in loco" 
senza coinvolgere inutili copie. (La questione diventa piu' evidente, 
di nuovo, se si tratta di oggetti piu' complessi, dove le copie hanno
un costo non indifferente).
Saluti
Fabio
-- 
Posted from 
flopiano.mm.eutelsat.org
 [194.214.173.28] 


hai postato tu.
Non li sai ancora a memoria? :-)


un costo non indifferente).
Esatto.


    seq.erase( it, seq.end() );
Uuhm, provo a rispondere io.
Mi pare che la remove_if non elimini gli elementi che soddisfano la
condizione, ma li sposti semplicemente in fondo alla lista( li rimuovi
poi tu con la erase).
L'operazione di cancellazione tramite il for quindi , almeno per
quanto riguarda strutture dati come il 'vector' dovrebbe quindi
risultare molto più lenta perché ad ogni cancellazione é obbligatorio
fare la reallocazione, mentre per strutture come list( ottimizzata per
le operazioni di cancellazione/inserimento piuttosto che su quelle di
estrazione dei dati) non dovrebbe esserci una grande differenza.
Il Ghenio
-----
These are my parting words to you:
those who give up are doomed!
-----

 estrazione dei dati) non dovrebbe esserci una grande differenza.
Ancora più o meno. In realtà vector non fa nessuna riallocazione (la
riallocazione corrisponde a una resize) ma si limita a fare una cosa
simile a quella che avviene con remove_if, salvo che gli elementi
eccedenti vengono distrutti (ne viene chiamato il distruttore). Ma non
viene liberata la memoria che li conteneva. Solo che mentre facendo il
tutto con il remove_if seguito da erase in pratica gli elementi vengono
copiati una sola volta e alla fine viene chiamato il distruttore dei
"residui", nell'algoritmo con il for ogni volta che fai l'erase di un
elemento tutti quelli successivi vengono copiati. Quindi la sostanza di
quello che hai detto è corretta.


 
Non è tua, certo. Ci sono buone ragioni per credere si tratti di un
problema di Mailgate. Penso che se tu e gli altri utenti di Mailgate
provaste a scrivere "=3D" anichè "=" il problema sarebbe, per così dire,
risolto. (Beh, non proprio, a pensarci bene: resterebbero fregati tutti
quelli che usano Free Agent, che, come è noto, non riconosce il
quoted-printable.)
Max

 provaste a scrivere "=3D" anichč "=" il problema sarebbe, per cosě
dire,
Ho fatto qualche prova e il problema sembra essere effettivamente di
MailGate. Ho segnalato la cosa. Ora non resta che aspettare Dario e/o i
suoi collaboratori.


Spero di non aver detto troppe cavolate.
Secondo me ne hai detta una abbastanza grossa parlando di
questo loop. Nel caso di un vector il sistema proposto e'
decisamente "terribile"; in particolare ad esempio ha un
tempo di esecuzione O(N^2) sul numero di elementi del
vettore nel caso che tu li debba cancellare tutti.
Io personalmente credo che nessuno che si sia fermato a
pensare un secondo a come puo' essere implementato
erase per un std::vector potrebbe mai aver scritto codice
simile; chiaro che non aver mai pensato a cosa c'e' dietro
e sperare di ricordarsi "a memoria" il costo dei vari
algoritmi per i vari container senza averne compreso i
motivi e' molto piu' complesso (e non e' secondo me la
strada maestra per imparare a utilizzare STL).
Se vuoi fare un loop esplicito conviene usare un'altra
strada (che e' anche utile quando vuoi eliminare degli
elementi da un array nativo):
   std::vector<int>::iterator rp,wp,ep;
   for (rp=v.begin(),wp=rp,ep=v.end(); rp!=ep; ++rp)
     if (!devo_cancellare(*rp))
       *wp++=*rp;
   v.erase(wp,ep);
sostanzialmente usi un puntatore di "lettura" e uno di
"scrittura": quello di lettura si incrementa sempre
mentre quello di scrittura lo incrementi solo dopo aver
fatto la copia degli elementi che *non* vuoi eliminare.
In questo caso l'algoritmo e' O(N) ed e' quello che
fa anche "remove_if".
Se gli elementi contenuti sono complessi il discorso
sull'efficienza si complica un poco. Anche per rimuovere
ad esempio il primo elemento non e' affatto detto che
scrivere la naturale
  v.erase(v.begin());
sia il sistema piu' veloce; infatti le specifiche di
erase dicono che devono essere fatte n-1 assegnazioni.
Se l'elemento contenuto e' "pesante" (ad esempio un
altro std::vector di qualcosa, oppure una stringa o
cose ancora piu' grosse e complesse) allora una
alternativa potrebbe essere usare std::swap per far
"galleggiare" la vittima predestinata verso l'ultima
posizione prima di effettuare il resize del vector.
Gia' con std::vector<std::string> ho visto differenze
di 20:1 nei tempi di esecuzione. Questo per dire che
non c'e' solo l'ordine O(...) degli algoritmi che conta,
ma anche le costanti coinvolte. E pensando a cosa
succede "dietro le quinte" diventa naturale accorgersi
anche di questi problemi.
Andrea

 del vettore e M il numero di elementi da rimuovere.
Adesso il pignolo lo faccio io ;-)
  M < N  > O(N+M)  O(N+N)  O(2N)  O( N )
[snip]


 vettore nel caso che tu li debba cancellare tutti.
Non puoi parlare di tempo di esecuzione quando ti
riferisci alla complessita' di un algoritmo e con la 
notazione O(N^2) ci si riferisce ad un indice di 
complessita non di tempo.
Quando si parla di complessita' in oltre ci si riferisce 
sempre al WC (Worst Case).
NB. Non ho mai parlato di efficienza nel mio post.
Ciao
Gaetano.
-- 
Posted from 
nts-03.mm.eutelsat.org
 [194.214.173.15] 


 
[snip]
Accidenti! mi sono spariti 5 uguali su una riga sola!
volevo scrivere:
M minore o uguale N  implica O(N+M) uguale O(N+N) uguale O(2N) uguale O(N)
Non so cosa e' cambiato ma fino a qualche giorno fa funzionava...
Saluti da un programmatore senza uguali ;-)


 Non li sai ancora a memoria? :-)
Ci sto lavorando :-)


  M <=  = O(N+M) =(N+N) =(2N) =( N )
Si hai ragione. Mi era sfuggita chissà come. (ma con i calcoli degli
ordini di complessità sono sempre stato superdistratto. Magari dovrei
farmi una "seduta di ripasso". Solo che non trovo più i testi! Magari
quando trovo tempo provo a cercare online).


 sempre al WC (Worst Case).
Per la verità la frase di Andrea era "ha tempo di esecuzione O(N^2)" che
in virtù del significato della big-O-notation io leggerei: "ha tempo di
esecuzione che cresce proporzionalmente al crescere del quadrato del
numero degli elementi". E a me questo sembra corretto.
Anche se hai ragione a dire che non ha senso parlare di tempo di
esecuzione *assoluto* quando si parla di complessità. Ma per come la
leggo io andrea parlava di tempo di esecuzione *relativo*.
Sul discorso del worst case non sono del tutto d'accordo. Un conto è la
semplificazione della "formula", un'altra il calcolo dei singoli
elementi. Secondo il tuo ragionamento il quick-sort dovrebbe essere
O(N^2) invece che O(N log N).


e Xi e la posizione (zero based) dell'elemento i-esimo da eliminare.
giusto (ma non facevi prima a scrivere {sommatoria[su i](N-Xi)} e
definire Xi come posizione (non zero based)) ?
--
Posted from 
nts-03.mm.eutelsat.org
 [194.214.173.15]
via Mailgate.ORG Server - 
http://www.Mailgate.ORG
--


 definire Xi come posizione (non zero based)) ?
si ma parlando di vettori in cui gli elementi sono ad indice
"zero based" mi sembrava piu' conforme.
Ciao
Gaetano.


Saluti da un programmatore senza uguali ;-)
LOL!
-- 
Ciao, Marvin

 string, vector, list, ecc. e su come usare gli iteratori, ecc.???
su 
cpp.programmazione.it
 trovi le prime puntate di un mio tutorial (che 
non ho ancora finito di scrivere) che tratta proprio questo argomento; 
occhio che e' piu' una introduzione panoramica che non un reference, 
quindi non aspettarti ti trovare tutto.
ciao anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

     seq.erase( it, seq.end() );
qua invece prima sposta tutti gli elementi da eliminare alla fine e poi 
esegue una sola cancellazione; nel caso di un vector e' ovviamente piu' 
efficiente.
Detto in termini un po' piu' formali: detta Oe la complessita' 
computazionale di MySequence::erase() e Or la complessita' di 
std::remove_if<MySeqIt, ...>, nel primo caso la compessita' totale del 
codice e' n*Oe, mentre nel secondo e' Or+Oe.
Ho indovinato?
ciao Anto


 che pesasse.
In termini di complessità ovviamente non conta nulla (tra l'altro 1
rimozione è un fattore costante che nella complessità sparisce in ogni
caso).
Ma stavamo parlando di cosa fa il codice, non della complessità. Nel
caso di un vettore la "rimozione" degli elementi in coda è
effettivamente un assegnamento (al membro che tiene conto del numero di
elementi presenti). Per una lista doppiamente linkata invece le cose
sono leggermente più complicate. La rimozione di un elemento significa
il riassegnamento dei link presenti nel nodo precedente e in quello
successivo il che richiede alcune dereferenziazioni e assegnazioni.
Quello che volevo sottolineare è che se le distruzioni restano sempre M
il lavoro di riassegnare i link (almeno in teoria, poi dipende
dall'implementazione) viene fatto una sola volta usando la remove di un
"range" mentre viene eseguito più volte se rimuovi gli elementi uno ad
uno.


 Ho indovinato?
Hai fatto praticamente meglio di me. Non resta che risolvere Oe e Or per
i vari casi e semplificare ove possibile (non come feci io!). Risultato:
se è vero che in termini di tempo assoluto per la lista conviene il
ciclo rispetto al remove_if+erase, in termini di complessità l'algoritmo
con remove_if+erase è sempre O(N) mentre il ciclo è O(N) per le liste ma
O(N^2) per vettori e deque.


 codice e' n*Oe, mentre nel secondo e' Or+Oe.
un appunto: per le caratteristiche della notazione O, Or + Oe = max(Or, 
Oe)

 suoi collaboratori.
Nelle prossime ore provvederemo a fare dei controlli, poi ti relaziono in
privato e/o sul newsgroup.
Grazie comunque della segnalazione.
Un saluto
-- 
Dario Centofanti
-- 
Posted from 
relay.mailgate.org
 [151.38.159.199] 


 suoi collaboratori.
Aggiornamento: Cinzia Benedetti di Mailgate mi conferma che Dario
Centofanti (suppongo sappiate chi è) sta verificando il problema. Mi
faranno sapere presumibilmente domani. Vi aggiornerò.


 elementi presenti).
La lista non ha e non puo contenere un membro che dice quanti elementi
ci sono presenti.


 efficiente.
Sbagliato. Qui vengono spostati solo gli elementi da non rimuovere
soltanto quelli dopo il primo da rimuovere, che e' diverso da quello che
dici tu, anzi quello che dici tu e' quasi quello che fa il for.


 faranno sapere presumibilmente domani. Vi aggiornerò.
Assolutamente no (non si chi sia).


Assolutamente no (non si chi sia).
Tra l'altro ho visto che è intervenuto egli stesso nel NG.
Comunque non sei un utente MailGate molto attento dato che su un sacco
di schermate mailgate c'è scritto il suo nome. E' quello che ha di fatto
inventato (e sviluppato) mailgate e che tuttora (anche se non da solo)
lo gestisce.


ci sono presenti.
A parte il fatto che stavo parlando del vettore, mi spieghi perchè dici
questo (che tra l'altro non è vero ma anzi è *quasi* vero il contrario)?



Il +1 che io ti contesto e' presente soltanto nel caso della lista non
del vettore.
Ti dico che una lista non contiene e non puo contenere un membro
che dice quanti elementi contiene perche' se std::list<>::size()
avesse un tempo costante (con il membro che tiene memoria
del numero di elementi) allora la
std::list<>::splice() non sarebbe piu' a tempo constante come
invece richiede lo standard.
Imagina una operazione del genere:
list1.splice( list1.end(), list2,
                 find(list2.begin(), list2.end(), 5),
                 find(list2.rbegin(), list2.rend(),10));
come fai ad implementare splice in tempo costante,
con un membro dentro che tiene conto di quanti elementi
contiene list1?
ciao
Gaetano


                 find(list2.rbegin(), list2.rend(),10));
Ho scordato di dire che: lo standard richiede solo questa forma 
di slice a tempo costante.
Ciao
Gaetano.


NB. Non ho mai parlato di efficienza nel mio post.
Io ho visto una richiesta di un newbie su come si scrive
un loop per rimuovere degli elementi e ho visto la
tua risposta che, dopo aver dato indicazioni corrette,
ha scritto quel codice orribile.
  NOTA BENE:
    *NON* sto dicendo che tu sia un fesso
    o che tutto il codice che scrivi sia
    orribile. E nemmeno che in genere il
    codice che scrivi tu sia orribile.
Quel codice e' pero' secondo me orribile.
Orribile al punto che chi ha pensato al C++ ha deciso ad
esempio di rimuovere l'operatore [] dal container di lista
per evitare che chi ha le idee confuse (o chi semplcemente
si distrae) lo utilizzasse.
Io credo che dare quell'esempio a qualcuno sia stato
un errore grave. Non vuoi fare il discorso di efficienza ?
Benissimo. Allora evita quel loop e mostrane comunque uno
esplicito ma decente senza discuterne l'efficienza.
L'aggiunta su eventuali inefficienze nascoste anche
in un sigolo "v.erase()" su strutture complesse e' stata
una aggiunta che ho deciso di fare perche' ritenevo la
cosa interessante per chi usa STL sul campo (e non solo su
libri in cui la complessita' computazionale non e' legata
al tempo di esecuzione - se questi libri esistono).
E' un discorso sicuramente poco adatto a chi sta imparando
le basi di C++ e della libreria standard, ma ho creduto
che fosse qualcosa di interessante per chi e' un po' piu'
avanti. Di cosa faccia esattamente vector::erase dietro le
quinte e delle implicazioni che questo comporta si e'
discusso in comp.std.c++, e' un argomento che ho trovato
interessante e che si riaggancia all'idea di "copy destructor"
o di "rilocazione" che avevo visto citata da Nicola Musatti
e di cui ho discusso anche con dei guru. Ho anche saputo
che boost si occupa dell'argomento.
Tu non hai mai parlato di efficienza nel tuo post. Vero.
Questa e' secondo me una cosa preoccupante. Se tu non ne
avessi parlato ma avessi fatto solo esempi ragionevoli
non avrei avuto nulla da ridire. Non parlarne e scrivere
codice orribile mi ha fatto pensare ad un errore di
distrazione (una "grossa cavolata" come l'hai chiamata tu)
e te l'ho fatto notare.
Andrea

 invece richiede lo standard.
Questo ragionamento e' capovolto: il fatto di avere un membro che
memorizza la dimensione (cosa che hanno svariate implementazioni di
std::list) *non* implica un requisito di tempo costante per
list<>::size() .
Lo standard *non* impedisce ottimizzazioni :-)
Ciao,
Nicola

Non e' che spostate la discussione su meriti e demeriti di OE e Mailgate
altrove?
Ciao,
Nicola



Pero' un requisito di tempo costante per la size
implica la presenza di un membro che tiene conto della dimensione
o come nel caso dei vettori il poter fare
( end() - begin() ).
Lo standard *non* impedisce ottimizzazioni
ma ti da delle specifiche di complessita', in questo
caso la splice che ti ho mostrato ha una richiesta di essere
a tempo costante e non lo potrebbe essere se la 
lista avesse un membro che tiene memoria degli
elementi presenti in lista.
dal g++:
Per le liste:
size_type size() const 
{
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
}
Ciao
Gaetano.


 elementi presenti in lista.
Perche' no? Dipende dalla politica di aggiornamento del contatore.
Potrebbe esserci un membro booleano che indica se il contatore e'
valido; all'interno di size() si potrebbe allora controllare il flag e
se necessario ricalcolare la lunghezza.
Ciao,
Nicola

 messaggi corretti con [alt+enter dettagli originale].
Purtroppo il campo 'Content-Transfer-Encoding' non e' generato autonomamente da
Mailgate ma viene preso dall'header dall'email originale.
La cosa migliore per postare attraverso Mailgate sarebbe comunque non
utilizzare il gateway email ma il piu' nuovo gateway web.
Stiamo comunque cercando di risolvere il problema.
Un saluto
-- 
Dario Centofanti
-- 
Posted from 
relay.mailgate.org
 [151.38.159.199] 


 se necessario ricalcolare la lunghezza.
come ho detto prima sarebbe un "ammortized costant time".


Riparto da capo perche' non capisco le tue obiezioni. STL pone come
requisito che list<>::splice(iter,list,iter,iter) richieda tempo
indipendente dal numero degli elementi aggiunti (ovvero non li puo'
contare) e che list<>::size() sia lineare nel numero di elementi
correnti.
Un'implementazione che mantenga un contatore della dimensione corrente,
che venga aggiornato direttamente nel corso delle operazioni almeno
lineari nel numero di elementi inseriti o tolti e che venga invalidato
nell'esecuzione di splice(), per essere ricalcolato eventualmente
durante l'esecuzione di size() e' conforme allo standard. Infatti splice
resta indipendente dal numero di elementi inseriti e size() e' al piu'
lineare in n.
Ciao,
Nicola

 wrote:
- Riparto da capo perche' non capisco le tue obiezioni. STL pone come
- requisito che list<>::splice(iter,list,iter,iter) richieda tempo
- indipendente dal numero degli elementi aggiunti (ovvero non li puo'
- contare) e che list<>::size() sia lineare nel numero di elementi
- correnti.
- Un'implementazione che mantenga un contatore della dimensione corrente,
- che venga aggiornato direttamente nel corso delle operazioni almeno
- lineari nel numero di elementi inseriti o tolti e che venga invalidato
- nell'esecuzione di splice(), per essere ricalcolato eventualmente
- durante l'esecuzione di size() e' conforme allo standard. Infatti splice
- resta indipendente dal numero di elementi inseriti e size() e' al piu'
- lineare in n.
Hai ragione tu.
Quelli in torto siamo io, Meyers quelli che hanno
implementato STL per la GNU e M$ che si e' fatta
fregare dal non avere una splice non conforme allo
standard.


 standard.
No, ad avere torto siete solo tu e Microsoft. Microsoft per avere
un'implementazione non conforme, tu per continuare a non riconoscere
come conforme l'ottimizzazione che ho suggerito. GNU ha scelto di non
applicarla e quindi non c'entra.
Meyers invece si limita a dire che non e' possibile avere sia splice che
size costanti rispetto al numero di elementi, e su questo siamo tutti
d'accordo.
Ciao,
Nicola

 applicarla e quindi non c'entra.
Io non ho mai detto che non e' conforme. Io ho detto che non puoi avere
la size costante e la splice costante allo stesso momento  perche' sono
due cose che cozzano tra di loro. Io non ho mai detto che non e' conforme
il tuo suggerimento e se per caso avessi dato l'impressione opposta me ne
scuso.
Mi permetto di attirare la tua attenzione alla seguente:
Sbaglio o eri tu a cui non piacevano membri mutable e/o funzioni friend ?
Pensa ad una implementazione di list<>::size() const; che deve rivalidare
il booleano dentro.
Per non parlare degli algoritmi che lavorano sulle liste.....
Ad ogni modo puoi proporre la tua modifica alla GNU.
Non appena ho tempo do un'occhiata all'implementazione di altre parti
per vedere che hanno combinato.


 per vedere che hanno combinato.
Ho dato un'occhiata all'implementazione di RogueWave su BCB 5 e ad
occhio mi pare che abbia lo stesso problema di Microsoft.
Ciao,
Nicola

 wrote in message
news:3BF38BB6...@divalsim.it...

Giusto, siamo OT.
[CC di questo a Dario in E-Mail.]
Quindi chiudiamo questa discussione sul NG salvo, eventualmente, un
unico post quando il problema verrà risolto. Giusto per notificare la
cosa al NG (che è quello nel quale il problema è stato rilevato).
Per il resto (incluso il caso di inviti di Dario a fare delle prove)
limitiamoci a E-Mail (e it.test).


std::list<>::splice() non sarebbe piu' a tempo constante come
invece richiede lo standard.
Imagina una operazione del genere:
list1.splice( list1.end(), list2,
                 find(list2.begin(), list2.end(), 5),
                 find(list2.rbegin(), list2.rend(),10));
come fai ad implementare splice in tempo costante,
con un membro dentro che tiene conto di quanti elementi
contiene list1?
ciao
Gaetano
--
Posted from 
nts-03.mm.eutelsat.org
 [194.214.173.15]
via Mailgate.ORG Server - 
http://www.Mailgate.ORG
--


contiene list1?
Non lo fai. E non è richiesto dallo standard.
Questi sono i requirement dello standard per i membri di list:
// should be constant
size_type size() const;
quindi non obbligatorio constant ma fortemente consigliato (per questo
dicevo che "è *quasi* vero il contrario"). Per farlo constant il modo
più semplice è mantenere la dimensione in un membro (per esempio
_MySize).
// constant
void splice(iterator position, list<T,Allocator>& x);
Questa è facile: se this==&x non fai nulla. Altrimenti _MySize+=x.size()
e in x la dimensione va a zero.
// constant
void splice(iterator position, list<T,Allocator>& x, iterator i);
Anche questa è facile: se this==&x non fai nulla. Altrimenti ++_MySize e
in x la dimensione verrà diminuita di uno dalla rimozione dell'elemento.
// constant if this==&x altrimenti linear
void splice(iterator position, list<T,Allocator>& x, iterator first,
                  iterator last);
E questa è facile. Se this==&x la size non cambia, altrimenti la
ricalcoli ed esegui in linear time.


 wrote in message
news:3bf3637e...@news.interbusiness.it...


 non avrei avuto nulla da ridire.
In sostanza lo penso anche io. Se proponi una soluzione e questa è
efficiente, puoi non entrare del merito dell'efficienza. Ma se proponi
due soluzioni e una è genericamente efficiente ma resta inefficiente in
un caso mentre l'altra è efficiente in quel caso ma terribilmente
inefficiente in tutti gli altri, allora DEVI entrare nel merito
dell'efficienza. Per questo ho posto il "quiz".


 size_type size() const;
Lo standard non dice nulla circa la complessita' di size().


 standard.
mi sembra che in questa discussione non vi state capendo. La proposta 
di Nicola e':
- esiste un membro che tiene in cache il valore di list::size()
- esiste un membro che determina se il valore in cache e' valido
- se esegui splice() invalidi la cache (cosa che si puo' fare in tempo 
costante); quindi la complessita' di splice() e' ancora costante.
- quando esegui size() se la cache e' valida allora hai un tempo di 
esecuzione costante; se la cache non e' valida occorre ricalcolarsela 
(complessita' lineare).
In pratica size() e' lineare nel caso peggiore ma costante nel caso 
(frequente) medio. splice e' costante, quindi lo standard e' rispettato.
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 di Nicola e':
Ci siamo gia chiariti.
Rimane comunque il fatto che si devono comunque fare dei
salti mortali tipo:
    "Il booleano che invalida la size cache 
    e il membro che tengono in cache il valore del size
    devono essere dichiarate mutable"
per non parlare degli algoritmi che lavorano
sugli iteratori delle liste che cambiano la lunghezza
della lista e devono quindi invalidare il membro?
Funzioni friend? Orrore.


Lo standard non dice nulla circa la complessita' di size().
Non "richiede" niente, sarebbe corretto. Non "dice" niente è falso. Per
il metodo size lo standard non dice "constant time" o "must be constant
time" ma dice "complexity should be constant time".
Quindi "dovrebbe" essere costante. Ma se non lo è, sei comunque
compliant. Ovviamente in una buona implementazione la size ha
complessita costante, dato che la cosa è sia possibile che conveniente.
Tra l'altro c'è anche chi vorrebbe interpretare quel "should" in modo
più stringente e dichiarare che una implementazione in cui la size non è
di complessità costante è non conforming. Io penso che una
implementazione in cui la size non è di complessità costante sia
comunque conforming, anche se non è una buona implementazione.
--
Posted from 
nts-03.mm.eutelsat.org
 [194.214.173.15]
via Mailgate.ORG Server - 
http://www.Mailgate.ORG
--


 (frequente) medio. splice e' costante, quindi lo standard e'
rispettato.
La mia impressione è che non si sia capita una cosa: può esistere un
membro che mantiene il valore di list<>::size() in una implementazione
conforme. In tutti i casi in cui c'è bisogno di ricalcolarlo, lo
standard ammette esecuzione lineare. Pertanto il problema non esiste.


 Funzioni friend? Orrore.
No. Se cambiano la lunghezza della lista useranno un metodo non costante
della lista e sarà questo a cambiare (non invalidare) i membri di
questa.


 davanti alla crescita esponenziale). 
solo una precisazione: x^2 e' quadratica, non certo esponenziale!


 standard ammette esecuzione lineare. Pertanto il problema non esiste.
No, l'intoppo e' la versione di splice che prende quattro parametri:
questa prevede di eseguire in tempo costante, ma inserisce un range
arbitrario preso da un'altra lista, di cui ovviamente non conosce la
lunghezza. In questo caso il ricontare gli elementi viola il vincolo
temporale.
Ciao,
Nicola


Postato troppo in fretta. Ho letto il tuo altro messaggio (e lo
standard). Direi a questo punto che memorizzare la dimensione della
lista non solo e' possibile, ma e' l'implementazione piu' ragionevole.
Ciao,
Nicola

 lista non solo e' possibile, ma e' l'implementazione piu' ragionevole.
Infatti ho letto lo standard e per quella maledetta pslice dice:
void splice(iterator position, list<T,Allocator>& x, iterator first,
    iterator last);
    Complexity: Constant time if &x =this; otherwise, linear time.
quindi si puo fare tenersi dentro la size. Non capisco perche'
non l'hanno fatto.
Tra le altre cose per chi avesse letto l'Item 4 di 
Effective STL di Meyers ho scritto al medesimo:
"Hi,
I found on Effective Stl, second printing page 23
the example:
    list1<int> list1;
    list2<int> list2;
    .....
    list1.splice( list1.end(), list2,
                 find(list2.begin(), list2.end(), 5),
                 find(list2.rbegin(), list2.rend(),10)
   );
and you wrote that this should be a costant time operation.
The standard say:
    void splice(iterator position, list<T,Allocator>& x, iterator first,
    iterator last);
    Complexity: Constant time if &x =this; otherwise, linear time.
in your example &x != this 
so in your example the complexity required is linear not constant."
ecco la sua risposta:
"Not exactly.  I wrote that it can be implemented in constant time and it
would not be unreasonable for a client to expect it to be done that way.  I
also go on to point out that the Standard does not require this behavior.
Scott"
Ma io dico: "ma puoi scrivere un Item e basarlo sul fatto che l'utente
potrebbe aspettarsi che sia scritta in tempo costante?"


 solo una precisazione: x^2 e' quadratica, non certo esponenziale!
Si. Infatti. Ma in questi giorni sono anche più impallato del solito.
Scrivo poco ... e male. Ma il concetto era chiaro.


 wrote in message
news:3BF8CCC9...@divalsim.it...

NO! Prevede l'esecuzione in tempo costante solo se gli elementi sono
presi dalla stessa lista. Altrimenti prevede l'esecuzione in tempo
lineare. E non potrebbe essere altrimenti dato che è persino possibile
che gli elementi debbano non solo essere contati ma anche copiati e
distrutti gli originali (per esempio se gli allocator non sono
compatibili).


 potrebbe aspettarsi che sia scritta in tempo costante?"
IMO no. Soprattutto perchè è certamente più facile che l'utente usi size
che non splice e che si aspetti questa come O(1) e quella O(N). Ammesso
che degli utenti si aspettino splice con implementazione O(1) come dice
Meyers, quanti fra questi, pur aspettandosi la splice in O(1), sono
coscenti che la loro aspettativa è sensata solo alle seguenti due
condizioni:
1) la size è O(N) o al massimo amortized O(1)
2) la splice è si O(1) ma SOLO se gli allocator sono compatibili
Tutti quelli che si aspettano la splice in O(1) ma non sono coscenti dei
due vincoli suddetti, è molto meglio che si accorgano fin da subito che
la splice in realtà non è affatto detto che sia O(1) se le liste sono
diverse.


 diverse.
void splice(iterator  position , list<T,Allocator>&  x );
-3- Requires: &x != this.
-4- Effects: Inserts the contents of x before position and x becomes empty.
Invalidates all iterators and references to the list x.
-5- Throws: Nothing
-6- Complexity: Constant time.
Sbaglio o dovrebbero esserne coscienti anche per questa.
ciao
Massimo

 IMO no.
Infatti.


 Sbaglio o dovrebbero esserne coscienti anche per questa.
Non mi ero accorto di questo particolare. Ho chiesto in giro e il
responso è ... che c'è in ballo un casino a livello di standard.
Da quello che ho capito il problema principale è l'esistenza di ben tre
diverse scuole di pensiero relativamente a cosa è un allocator e come va
usato. Una di queste scuole dice persino che nel caso due container
aventi allocators differenti vengono usati contmporaneamete ... il
risultato non riguarda lo standard.
Credo che questi problemi verranno risolti in futuro (ho guardato e non
sono al momento affrontati neppure a livello di "open issue").
Per come la vedo io questa versione di splice non può funzionare in
constant time se gli allocator sono diversi. Pertanto il requirement
dovrebbe diventare linear time o al massimo constant-time se gli
allocator sono compatibili e linear altrimenti.
In ogni caso hai ragione. I casi sono due: o la tua STL implementa
questa versione della splice in linear time (almeno nel caso di
allocator non compatibili, e viola lo standard per questo specifico
caso) oppure ti impalla il sistema senza warning se la usi per liste con
allocators diversi. Fra le due preferisco pensare che lo standard è
errato in questo punto.


 risultato non riguarda lo standard.
All'inizio ero daccordo con te sul fatto degli allocator diversi..... ma ora
ripensandoci nel caso della lista con gli splice non viene fatta nessuna
copia quindi gli allocator non entrano in gioco in tutto questo discorso.
Tra le altre cose una classe lista (secondo lo standard) e' fatta cosi' :
template <class T, class Allocator  allocator<T> >
class list {  ........ }
e lo standard parla della splice (prendiamo quella + semplice) in questi
termini:
void splice(iterator position, list<T,Allocator>& x);
quindi il metodo splice e definito solo se x e' dello stesso
tipo della lista su cui stai chiamando la splice.
Quindi secondo lo standard se tenti di fare una splice tra due
liste che hanno due allocator non deve compilare essendo a
tutti gli effetti due tipi diversi.
Mi sono perso qualche cosa?


Mi sono perso qualche cosa?
No. Hai perfettamente ragione.
Ma da questo si deduce che lo standard non è sbagliato in nessun punto,
che le operazioni di splice sono ammesse solo fra liste omogenee (in
temini di allocator), che il discorso di Meyers sull'aspettarsi che la
splice esegua in tempo costante potrebbe avere qualche senso (in realtà
non molto perchè lo standard dice che se la terza splice non avviene con
LA STESSA LISTA la complessità è lineare), che lo standard ammette
esplicitamente l'implementazione di size() in tempo costante (non c'è
alcun altro motivo per permettere l'esecuzione con complessità lineare
della splice del terzo tipo se non appunto permettere O(1) per la size)
e che pertanto l'implementazione di GNU non è affatto buona da questo
punto di vista.


 
Vista l'ora tarda di ieri, ho scordato di dire che lo
standard richiede agli allocator da usare negli 
standard container anche il seguente operatore:
bool operator==(const allocator& a1, const allocator& a2);
che deve tornare true se i due allocator sono intercambili
(cio significa che la memoria (o storage) allocata da uno
puo essere deallocata dall'altro)
e per allocator dello stesso tipo questa deve tornare sempre
true.
Tutte queste precisazioni per dire che lo standard e' abbastanza 
conservativo, nel senso che se fai le cose come dice lui non 
puoi incorrere in problemi visto che li elimina alla base.


Ricordate il progetto di traduzione del famigerato libro THINKING IN C++ di
Bruce Eckel, mica sapreste darmi l'indirizzo del sito?

 puoi incorrere in problemi visto che li elimina alla base.
Questo e' il punto centrale di tutto il discorso. Lo standard consente
di assumere che tutti gli allocatori dello stesso tipo coincidono.
Questo tra l'altro e' fondamentale proprio per lo splice tra liste,
altrimenti l'unico modo per evitare disastri alla distruzione della
lista risultante sarebbe far si' che ogni nodo si porti dietro un
riferimento al proprio allocatore.
Ciao,
Nicola

 riferimento al proprio allocatore.
Infatti
Ciao
Gaetano.
PS. Ma questi thread immensi vengono alla fine raccolti in una 
FAQ, in maniera tale da non ripeterli? Altro thread che ricordo
immenso fu quello della classe base senza distruttore virtuale.


immenso fu quello della classe base senza distruttore virtuale.
Google raccoglie tutto, peccato che poi quando uno ne ha bisogno non
riesce piů a ritrovare niente.
-- 
Marco Barisione (ICQ 84277092)

 riesce più a ritrovare niente.
Be basta includere nei mess anche parole tipo: "bomb",
"been laden", "new york", "antrax", "TNT", "USA President",
"DES" e stai certo che il mess viene anche salvato da un'altra parte.
Io dicevo raccolte in maniera + organica.
Ciao
Gaetano.
-- 
Posted from 
nts-03.mm.eutelsat.org
 [194.214.173.15] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 bool operator==(const allocator& a1, const allocator& a2);
Si. Fa perte dell'interfaccia di allocator. Ma occhio che per poter fare
una splice fra due liste non basta che i due allocatori siano
compatibili (ovvero non basta che paragonandoli con operator== si abbia
true). Serve proprio che siano identici (ovvero istanze della stessa
classe).
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556