Newsgroup: it.comp.lang.c++
Titolo: cosa copia un copy constructor ?

Secondo voi il copy constructor per i container standard
deve copiare *tutto* lo stato di un container ?
Ad esempio:
   std::vector<int> v;
   v.reserve(10);
   std::vector<int> w(v); // Copia
   w.push_back(6502);
   std::vector<int>::iterator i=w.begin(); // Punta a 6502
   w.push_back(42);
   std::cout << *i; // Dereferencing. Lecito ?
Se il copy constructor ha copiato anche l'effetto
di reserve (capacity()>=10) allora il codice qui
sopra e' legale perche' la seconda aggiunta non ha
provocato riallocazioni. Se invece la capacity() non
e' stata copiata allora potrebbero essere guai...
Le implementazioni che ho visto non lo fanno (copiano
solo gli elementi e la capacity() del vector originale
viene ignorata) ... ma nello standard (draft) non si
accenna alla cosa.
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 deve copiare *tutto* lo stato di un container ?
Sono sicuro al 90% di no. Il copy constructor e' definito semplicemente
in base a:
X x1;
X x2(x1);
x1 == x2
Tra l'altro il trucco standard per ridurre le dimensioni di un container
e' fare lo swap con un container vuoto, e non si vede perche' swap
dovrebbe copiare solo il contenuto, mentre il copy constructor anche lo
stato interno. Hai gia' chiesto su comp.std.c++ ?
Ciao,
Nicola

Hai gia' chiesto su comp.std.c++ ?
No.


 Cosa in fondo ragionevole. Ma dove l'hai letta ?
Sullo standard, paragrafo 23.1, tabella 65, Container requirements.
Anzi, guardando meglio e' piuttosto chiaro, perche' x1 == x2 e' definito
come:
x1.size() == x2.size() && equal(x1.begin(),x1.end(),x2.begin())
 
Ciao,
Nicola

stato interno. Hai gia' chiesto su comp.std.c++ ?
Mi accorgo ora che cio' che mi dici su swap non quadra affatto.
A parte che swap non dovrebbe "copiare" ma scambiare, ma penso
proprio che swap scambi *tutto*, incluso capacity(): non farlo
significherebbe essere obbligati a copiare elemento per elemento.
Nella documentazione in mio possesso non sono pero' riuscito
a trovare una descrizione accurata di cosa deve fare swap()
(ma solo che l'algoritmo standard std::swap e' specializzato
per chiamare il metodo swap std::vector::swap).


 significherebbe essere obbligati a copiare elemento per elemento.
per il vector del gcc: 
size_type capacity() const
   { return size_type(const_iterator(_M_end_of_storage) - begin()); }
dove _M_end_of_storage e' gestito dall'Allocator
e la swap e' :
void swap(vector<_Tp, _Alloc>& __x) {
    std::swap(_M_start, __x._M_start);
    std::swap(_M_finish, __x._M_finish);
    std::swap(_M_end_of_storage, __x._M_end_of_storage);
}
in pratica si scambiano solo gli indirizzi delle porzioni di memoria 
gestite.
non so come si comportino altri compilatori

 accenna alla cosa.
Dubito che il draft non lo dicesse.
All'inizio del capitolo 23 c'e' una tabella con i "container requirements" da
cui si deduce chiaramente che devono supportare
X u(a);
X u=a;
con complessità lineare ed equivalenti a
X u; u=a;
e che la postcondizione e' u==a la quale a sua volta e' una operazione (di
complessita' lineare) che ha come condizione equivalente:
a.size()==u.size() && equal(a.begin(),a.end(),b.begin())
--
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

 wrote in message
news:3b84c578...@news.interbusiness.it...

IMO il fatto che copi *tutto* e' incidentale al fatto che tutto deve essere
copiato per garantire i requirement.
Nota che swap deve essere di complessita' constant time e che deve mantenere la
validità degli iteratori e dei riferimenti agli elementi swappati. L'unico modo
di fare questo con un vector e' di swappare i puntatori interni (e quindi i
buffer stessi) e, incidentalmente, le rispettive dimensioni (capacity).


x1.size() == x2.size() && equal(x1.begin(),x1.end(),x2.begin())
In effetti e' chiaro che se quello e' il requirement
allora l'effetto di reserve() non e' tenuto a essere
copiato con il copy constructor.
Ovviamente quella tabella non dice che con il copy
constructor copiare quell'effetto che e' vietato
(copiando *anche* l'effetto di reserve ovviamente il
requisito x1.size()==x2.size() && equal(...) e'
rispettato).
D'altra parte usando
  std::vector<int>(v.begin(),v.end()).swap(v);
il container v non viene passato al costruttore del
temporaneo e quindi il temporaneo non ha modo di
essere influenzato dal "reserve" fatto su v.
Il costruttore con quella coppia di iteratori garantisce
inoltre che nella costruzione non ci saranno riallocazioni
(visto che il costruttore puo' calcolare la distanza
fra v.begin() e v.end()) e il calcolo sara' efficiente.
Non concordi che usare questo sistema invece di
  std::vector<int>(v).swap(v);
sia piu' "sicuro" come effetti ?


X u; u=a;
Questa equivalenza dice che se capacity() viene
copiato dal copy constructor allora lo deve fare
anche l'assegnazione (e viceversa nel caso che
non venga copiato).
Personalmente avrei preferito una bella e semplice
frase chiara sulla cosa.
Guardando i sorgenti sia della implementazione
STL di g++ che di BCC55 si nota che il copy
constructor non copia capacity() e che l'operatore
di assegnazione non fa riallocazioni se la
capacita' di destinazione e' sufficiente... ovvero
  std::vector<int> x(100);
  std::vector<int> y(99);
  x = y;
comporta fare copy(y.begin(),y.end(),x.begin()) e
la distruzione del 100-esimo elemento (senza pero'
liberare memoria).


 sia piu' "sicuro" come effetti ?
Si, sono d'accordo.
 
Ciao,
Nicola

implementazioni di farsi concorrenza.
In alcuni punti lo standard mi stupisce per l'aver
fornito come descrizione una esplicita
implementazione, e  addirittura una implementazione
pessima (a mio parere).
Sto parlando ad esempio di operator[] per std::map
che e' definito come:
  T& operator[](const key_type& x);
  Returns:
    (*((insert(make_pair(x, T()))).first)).second.
Questa espressione e' secondo me una implementazione
terribile di quella che dovrebbe essere l'operazione
logica prodotta da operator[].
In particolare con il codice mostrato secondo me si
richiede per lo meno la costruzione di tre istanze
temporanee della class T e due copie della chiave
(senza contare una quarta istanza -- non temporanea
-- e la copia della chiave che devono essere inserite
nel container se non gia' presenti).
Tutte queste copie vengono create perche':
 - Una istanza di T e' creata esplicitamente
 - make_pair costruisce una istanza di pair che
   contiene una copia dell'istanza temporanea e
   una copia del valore della chiave
 - poiche' la deduzione implicita dei parametri
   di template fatta da make_pair porta alla
   costruzione di una istanza di pair<key_type,T>
   deve essere creata un'altra pair del tipo
   corretto per insert (in cui il primo membro
   sia "const key_type").
Personalmente non credo che nessuna di queste
copie inutili possa essere ottimizzata dal
compilatore (anche se su questo Scott Meyers
non concorda con me).
Ho chiesto in comp.std.c++ il motivo per cui lo
standard ha voluto essere cosi' vincolante (invece
di dire semplicemente che operator[] deve tornare
un reference a T  eventualmente creando una nuova
istanza nel container) e anche se quella descrizione
e' effettivamente un vincolo per chi implementa la
libreria; pero' non ho avuto nessuna risposta
specifica sulle due questioni.
Da prove che ho fatto ho visto che in realta'
nessuno usa l'espressione dello standard (in cui
make_pair deduce addirittura il tipo sbagliato) ma
tutte le implementazioni che ho visto si basano su
insert e richiedono quindi due costruzioni di
oggetti T temporanei e una duplicazione della chiave.
E' l'interfaccia stessa di insert che obbliga ad
essere inefficienti; la pair passata e' infatti
una pair contenente *valori* e anche se viene
passata per reference comporta delle duplicazioni
a meno che il chiamante abbia gia' una pair di
quel tipo fra le mani (cosa secondo me molto
improbabile, fra l'altro il fatto che il primo
membro sia const la rende secondo me una struttura
molto scomoda da utilizzare).
Piu' efficiente sarebbe stato passare separatamente
la chiave e il dato da inserire come due const
reference diversi.
Qualcuno comprende le ragioni di questa scelta ?


 sia piu' "sicuro" come effetti ?
Non del tutto. Come dicevo non so quale sia il motivo. Ma esiste un defect
report che dice che non e' possibile liberare la memoria un uso con vector e
deque (si puo' con le stringhe). La risposta del comitato e' che la cosa e'
irrilevante in quanto deque non prevede comunque reserve() o altri meccanismi
del genere e che e' possibile fare lo shrink_to_fit di un vector con la singola
linea di codice:
std::vector<int>(v).swap(v);
Ora questo e' vero se e solo se il copy constructor non puo' copiare l'effetto
di reserve(). Non so dove nello standard questo sia scritto. Ma il comitato
sembra sicuro dhe le cose stiano cosi'.
A questo punto diamo per scontato che il risultato finale sia lo stesso con
entrambe i metodi e poniamoci nuovamente la tua domanda: meglio il tuo metodo o
quello del comitato?
La mia risposta e' che quello del comitato, facendo riferimento a quello che di
fatto e' un copy constructor, ha molte piu' probabilitą di essere implementato
con qualche tipo di ottimizzazioni extra in termini di tempo di esecuzione
perche' ottimizzazioni superspinte (tipo memcpy per sequenze di POD) sono molto
piu' probabili all'interno di oggetti della stessa classe (e' possibile
verificare che gli iterator in ingresso nel tuo caso siano compatbili, ma e'
meno probabile che avvenga che non in un copy costructor.).
Ovviamente fermo restando che stiamo veramente depilando le uova e che e' meglio
non ottimizzare "a priori" ma solo dopo qualche giro di profiler.


 reference diversi.
Me lo sono sempre chiesto anch'io. In effetti le funzioni di inserimento
ragionano solo in termini di value_type (i.e. pair<>).
Mi chiedo però se, data quelle interfaccia, potrebbe essere possibile
creare un'implementazione diversa per operator[] che generi meno
temporanei.
Ho scritto questa.  Non genera temporanei quando la chiave già esiste e al
contempo non spreca il risultato della prima ricerca, in quanto passa
l'iteratore restituito da lower_bound() all'eventuale insert(), che a
questo punto dovrebbe (credo) garantire un costo di inserimento
ammortizzato costante.
 mapped_type& operator[]( const key_type & name )
 {
  iterator i = m.lower_bound( name );
  if( i != m.end() && name == (*i).first ) return (*i).second;
  else return (*m.insert( i, value_type(name,mapped_type() ) )).second;
 }
Max

 
Ehm, dopo aver letto l'ultimo post di Andrea su comp.std.c++, ho
verificato che la mia soluzione è perfettamente identica a quella adottata
nell'ultima release della libstdc++. Non lo sapevo. Devono averla cambiata
recentemente. Originariamente, coincideva con quella prevista dallo
standard.


standard.
Ti avrei risposto la stessa cosa stamattina :) ...
quella soluzione e' anche quella presentata in un
metodo "update-or-insert" mostrato in Effective STL.
Purtroppo la creazione di T temporanei e la duplicazione
della chiave e' insita nella creazione stessa della pair.
Quella creazione la puoi evitare solo se tu hai gia'
disponibile un oggetto del tipo value_type (ovvero
pair<const key_type,mapped_type>) e si tratta di una
cosa improbabile visto che oggetti di quel tipo sono
praticamente inutilizzabili.
Come avrai anche tu letto ci sono implementazioni
che hanno invece prestazioni di operator[] ottimali
ma che  di conseguenza non possono essere basate
su insert (MetroWerks).
Credo pero' che tutti questi miglioramenti non siano
conformi allo standard (la cui implementazione di
operator[] e' terribile ma non ho visto usata).


La definzione di operator[] e' quella dell'STL originale, ereditata
dallo standard. Tutti questi problemi derivano a mio avviso
dall'eccessiva brama di unificazione di chi ha disegnato l'STL, che ha
portato std::map ad essere definita in tutto e per tutto come una
sequenza di coppie chiave/valore. (Da qualche parte ho un abbozzo di
iteratore "sparificante", per evitare di dover scrivere i->second da
tutte le parti).
In questo contesto l'operator[] sembra quasi un aggiunta postuma,
certamente il parente povero della classe.
Ciao,
Nicola

 operator[] e' terribile ma non ho visto usata).
Mi sfugge comunque il motivo per cui si è sentita l'esigenza di
specificare nello standard l'implementazione di operator[] con un tale
livello di dettaglio.
Ad ogni modo, direi che sarebbe ragionevole se in una futura revisione
aggiungessero questi due metodi all'interfaccia di map e multimap:
 pair<iterator, bool> insert(const key_type& k );
 pair<iterator, bool> insert(const key_type& k, const mapped_type& v);
Se ci pensi bene, questi metodi renderebbero map<> e multimap<> delle
strutture peculiari e non banalmente riproducibili mediante set<> e
multiset<>. Al momento, mi pare si possa implementare una map con
pochissimo sforzo usando un set<> (con una coppia chiave/valore con valore
mutable e operator< che confronti solo la chiave) e ottenere qualcosa di
sostanzialmente equivalente a std::map come funzionalità e prestazioni.
Max

 
[snip]
Visto che la push_back() invalida gli iteratori, il dereferencing
di un iteratore dopo una push_back() non e' mai lecito (anche se
magari, sul primo vector, nella maggior parte delle implementazioni,
darebbe il risultato previsto).
O no ?
Fabio
-- 
Posted from [194.214.173.28] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 darebbe il risultato previsto).
No. push_back di per se non invalida gli iterator. Nel caso del vettore li
invalida se e solo se avviene una reallocation. L'effetto di reserve e' proprio
quello di garantire che la riallocation non avvenga (almeno non fino al
raggiungimento della dimensione indicata).
La domanda di andrea era proprio questa: l'effetto di reserve viene copiato o
no?
Che io sappia la risposta e' che non viene copiato ma viene swappato se usi
swap.
