Newsgroup: it.comp.lang.c++
Titolo: Specializzazione di elementi di std

Ciao,
Nel corso della recente "pizzata" e' stato espresso un dubbio circa la
legittimita' di specializzare i template della libreria standard. Il
seguente paragrafo specifica cosa e' consentito fare:
  [lib.reserved.names] 17.4.3.1 Reserved names
1 It is undefined for a C++ program to add declarations or definitions
  to namespace std or namespaces within namespace std unless otherwise
  specified. A program may add template specializations for any standard
  library template to namespace std. Such a specialization (complete or
  partial) of a standard library template results in undefined behavior
  unless the declaration depends on a user-defined name of external
  linkage and unless the specialization meets the standard library
  requirements for the original template. 163)
E' interessante anche la nota:
163) Any library code that instantiates other library templates must be
     prepared to work adequately with any user-supplied specialization
     that meets the minimum requirements of the Standard.
Ciao,
Nicola

 seguente paragrafo specifica cosa e' consentito fare:
Piò precisamente la domanda di Andrea era relativa alla possibilità di
non usare la specializzazione di default per std::swap relativa a una
sua classe.
Come previsto è possibile (purchè si tratti di una SUA classe, e non di
una tipo predefinito o di una classe fornita con la libreria standard)
specializzare std::swap con del codice appropriato e specifico.
Ovviamente l'assunto che un dato algoritmo (per esempio di sort) faccia
uso della std::swap è errato. Non è detto che la std::swap venga
chiamata. Però SE viene chiamata e SE la specializzazione è visibile
PRIMA della specializzazione dell'algoritmo in TUTTE le T.U. che
chiamano l'algoritmo, allora verrà chiamata la tua versione.
--
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

legittimita' di specializzare i template della libreria standard.
Posso fare una domanda ? vi siete seduti a mangiare una
pizza per parlare di C++ ?
Programmatori, gente strana !!
-- 
Andrea Laforgia - walkietalkie(at)
libero.it
Spostare "Windows" nel cestino ?

Programmatori, gente strana !!
La pizza non era male, soprattutto come rapporto qualita'/prezzo
(ps... me la pagherete!!! ... anzi ... no, la prossima ve la
paghero' io :) )
Poi una pizza e' una pizza
Io avevo preventivato che ci sarebbero stati solo grandi silenzi
surreali e sguardi sperduti (in fondo qui non siamo su IRC :) )
e invece sembrava (quasi) una cena sensata :D
Solo i giovani mi sono sembrati un po' spaesati :/
Andrea
PS:
  Tu eri impegnato in una festa con tutte le altre
  diverse identita' che usi qui su usenet ?

chiamano l'algoritmo, allora verrà chiamata la tua versione.
Non potrebbe anche essere che std::sort chiama std::swap solo per
alcune classi della libreria standard (scelte dagli implementatori
di std::sort) ?
Comunque in C++ manca in effetti secondo me la distinzione fra
oggetti "pesanti" e "leggeri"... come ho gia' detto anche
cose come std::vector::erase sono state scritte pensando solo ad
oggetti "leggeri" e risultano poco adatte in altri casi (anche
semplicemente per std::string).
Andrea

Solo i giovani mi sono sembrati un po' spaesati :/
I giovani non hanno tutte le conoscenze che avete voi! Comunque è
stato interessante.
-- 
                    Marco Barisione (ICQ 84277092)
Se sei interessato alla creazione di un newsgroup generico in cui si
possa parlare di quei linguaggi di programmazione senza un gruppo
apposito vota per it.comp.lang su it.news.votazioni.

 e invece sembrava (quasi) una cena sensata :D
Un pochino lo temevo. Ma non č andata cosě. Per fortuna.


 di std::sort) ?
Ovviamente std::sort può essere specializzata per ciascun oggetto. Più
precisamente la libreria standard deve fornire una versione template (e
quindi generale) di std::sort la quale potrebbe fare uso di std::swap o
non farne uso. Indipendentemente da questo la libreria può fornire
specializzazioni particolari per i tipi predefiniti e per i tipi
definiti nella libreria, se non lo fa verrà usata la versione template.
Non può, ovviamente, fornire specializzazioni particolari per i tipi
definiti dall'utente.
L'utente può invece fornire specializzazione particolari per i suoi
tipi, e anche in questo caso se non lo fa verrà usata la versione
template. Nota che l'utente NON PUO' (almeno non in maniera standard e
portabile) definire specializzazioni particolari per i tipi predefiniti
e per i tipi della libreria.


e per i tipi della libreria.
Ora forse comprendo quali sono i problemi di std::swap.
Lo standard parla della *possibilita'* di definire
specializzazioni, ma se non vengono dichiarate esplicitamente
le *richieste* per queste implementazioni std::sort
*non puo'* chiamare std::swap sui tipi utente perche' non
potrebbe garantire nulla sul risultato. Provo a spiegarmi
meglio...
Cosa deve fare una specializzazione di std::swap ?
Che complessita' deve avere ?
Che limitazioni puo' presentare (es. invalidazione
di iteratori) ?
Puo' lanciare exceptions ? Di che tipo ? Con che
tipo di guarantee ?
Visto che queste cose non vengono richieste esplicitamente
dallo standard risulta impossibile che std::sort chiami
funzioni dal significato, costo e implicazioni ignote;
se lo facesse non sarebbe in grado di garantire nulla.
Lo standard e' chiaro su cosa fa il metodo x.swap(y)
per i container standard, ma non dice nulla riguardo a
cosa fa il metodo swap se presente per una classe utente o
cosa deve fare std::swap specializzato su classi utente.
Quindi std::sort non ha il permesso di chiamare std::swap
per scambiare elementi definiti dall'utente; per gli
ordinamenti si possono quindi definire i criteri, ma lo
scambio avviene nell'unico modo "safe" consentito, ovvero
con duplicazioni e assegnazioni. Questa cosa sarebbe
superabile credo solo passando un *altro parametro* al
template relativo all'operazione di scambio oppure
aggiungendo ipotesi aggiuntive sulle specializzazioni
di std::swap.
Condividete ?
Andrea

 Un pochino lo temevo. Ma non č andata cosě. Per fortuna.
Che centra IRC? C'č gente piů intelligente lě? :)
--
Luigi
http://web.tiscali.it/luigi_web
byte...@hotmail.com
ICQ 46240443

 Condividete ?
No. Per nulla. std::sort chiama (o meglio potrebbe chiamare, dipende da
quanto è lunga sequenza da ordinare) std::partition e questa a sua volta
chiama (o meglio potrebbe chiamare, dipende dai valori che trova)
std::swap. Nota che std::partition DEVE chiamare std::swap se gli
elementi non soddisfano già la condizione di partizione: è specificato
nello standard!
Questo semplice programma dovrebbe dimostrartelo:
#include <iostream>
#include <algorithm>
#include <vector>
struct Item {
 int i;
 Item(int _i):i(_i){}
 operator int() const { return i; }
 bool operator<( const Item&r ) const
 {
  std::cout << "<";
  return i < r.i;
 }
};
template<> void std::swap<Item>( Item& l, Item& r )
{
 std::cout << "x";
 std::swap(l.i,r.i);
}
int main()
{
 std::vector<Item> v;
 for ( int i=0; i<35; i++ )
  v.push_back(i);
 std::random_shuffle( v.begin(), v.end() );
 std::cout << "Begin" << std::endl;
 std::sort( v.begin(), v.end() );
 std::cout << std::endl << "End" << std::endl;
}
naturalmente perchè la cosa funzioni bisogna che il compilatore sia
conforme. Se provi a dare in pasto il suddetto codice al Comeau (puoi
usare anche il compilatore "online" via web) vedrai che è corretto.
Non so cosa succeda con il VC6 ne con il VC7 beta 2, ma so che il VC7
beta 1 ha qualche problema.
Il problema sta nel fatto che non accetta la forma:
template<> void std::swap<Item>( Item& l, Item& r )
e in particolare non accetta lo std::
Se provi con una using peggiori solo le cose. Però puoi risolvere
inserendo tutto nel namspace:
namespace std {
template<> void swap<Item>( Item& l, Item& r )
{
 std::cout << "x";
 std::swap(l.i,r.i);
}
}
con questa modifica il VC7 beta 1 mi da questo output (ovviamente gli a
capi sono aggiunti da me tranne che dopo "Begin" e "End":
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxBegin
<x<x<<<<<<<<<<<x<<<<<<<<x<<<<x<<<<<x<<<<x<<<<x<
<<<<<xx<<xx<<xx<<xx<<xx<<xx<<<xx<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<
End
Ovviamente le x che compaiono prima di Begin sono quelle relative alle
chiamate a std::swap fatte dalla random_shuffle (vi prego, non saltate
fuori con considerazioni sulla randomicità della random_shuffle usata
con il generatore random di default e senza neppure un seed! Per quel
che mi serviva va bene così!).
Nota anche che la sequenza di sort termina con una lunga sfilza di
paragoni senza nessuno swap. Questo per un motivo molto semplice: quando
il numero di elementi della partizione è al di sotto di un certo livello
il quick-sort non è l'algoritmo migliore. Un heap sort o un selection
sort risultano molto più veloci. E vengono fatti senza uso dello swap.
Nel caso specifico della Dinkumware distribuita con VC7 questo limite è
32. Pertanto vettori con meno di 32 elementi verranno sortati senza uso
dello swap. Il nostro vettore di 35 elementi viene inizialmente sortato
con l'algoritmo quick-sort e pertanto tramite std::partition che usa,
come previsto, la std::swap.


come previsto, la std::swap.
Non e' affatto detto che swap debba essere chiamata.
Questo ha implicazioni in alcuni casi... ad esempio
se volessi fare il sort di un vector di lock la
cosa potrebbe non funzionare anche se io ho fornito
un modo per fare lo swap di due lock. In questi casi
dovrei necessariamente aggiungere un livello di
indirezione... la cosa invece non accade con partition.
Andrea

 indirezione... la cosa invece non accade con partition.
Accade se segui le regole. Puoi anche specializzare std::swap in modo
che swappi oggetti che non soddisfano Assignable. Ma è una mezza
forzatura perchè il fatto che l'oggetto da swappare deve essere
Assignable come prerequisito perchè abbia senso specializzare std::swap.


draft man mano che cambiavano).
Mi riferivo esattamente a quello... ma mi spieghero' meglio in
un altro messaggio visto che sto ancora rimuginando su un paio
di cosette...
Fra l'altro ho trovato leggendo il draft una citazione di "equivalent"
riferita a due istanze... in particolare:
       lib.container.requirements
       ...
       Assignable requirements:
       Expression: t=u
       Return type: T&
       Post-condition: t is equivalent to u
Che significa "equivalente" in questo contesto ?
Ho posto la domanda anche in comp.std.c++... qualcuno
ha qualche idea in proposito ?
Equivalente utilizzato per frammenti di codice e' qualcosa
che mi e' chiaro (la famosa regola "as if" che secondo me
lascia in un linguaggio come il C++ ben poca liberta') ma
su cosa possa mai significare l'equivalenza di oggetti
user-defined senza un contesto specifico (es. un criterio
di ordinamento) non mi vengono idee ragionevoli...
Andrea

 Che significa "equivalente" in questo contesto ?
Il concetto di equivalence si basa sull' operator< :
t e u hanno equivalent value se la seguente espressione
risulta vera:
!(t<u) && !(u<t)
cio dipende quindi da come implementi l'operatore<.
--
Ciao
Gaetano
--
#exclude <windows>
printf("\t\t\b\b\b\b\b\b");.
printf("\t\t\b\b\b\b\b\b");

 cio dipende quindi da come implementi l'operatore<.
Laddove conta il concetto di ordinamento, quello che dici è corretto in
quanto in tali ordinamenti due elementi non vengono mai considerati
uguali ma appunto solo equivalenti. Ma nel contesto degli "Assignable
requirements" l'equivalenza è molto più stretta.
Sono curioso di sapere cosa rispondono gli esperti. Ma credo che
l'equivalenza sia da intendersi nel contesto dell'oggetto stesso
intendendo che le due copie sono, appunto, due copie identiche. Ovvero
che, come minimo, qualunque chiamata ad un membro debba dare lo stesso
risultato indipendentemente da quale delle due copie dell'oggetto è
coinvolta. E che la cosa si debba estendere anche a "qualunque sequenza
di chiamate". Naturalmente se il membro in questione ha una qualche
dipendenza dal tempo le chiamate dovranno dare lo stesso responso solo
se "eseguite nello stesso istante", cosa impossibile in pratica ma
valida logicamente se intesa che "eseguire la chiamata in un dato
istante da lo stesso risultato indipendentemente da quale è l'oggetto su
cui viene eseguita".
Insomma, i due oggetti sono equivalenti nel senso che sono una "copia
propria l'uno dell'altro" qualunque cosa questo significhi nel contesto
della classe in questione.
Ovviamente non tutte le classi ammettono la possibilità di una copia
propriamente detta.


della classe in questione.
...
Da un primo paio di risposte che ho avuto sembra che la
questione sia spinosa... ad esempio std::vector e std::string
non trasferiscono capacity() quando fai una assegnazione
e questo porta sicuramente a differenze misurabili; questo
esclude secondo me la possibilita' che citi (a meno che si
voglia dire che e' illegale mettere std::string in un
container standard!)
Il problema inoltre ha implicazioni pesanti... cosa significhi
"uguaglianza" per due tipi user-defined e' qualcosa che sa
solo il programmatore e che potrebbe addirittura cambiare
a seconda del contesto o del momento. Pretendere una fantomatica
"uguaglianza" senza fornire un contesto e' decisamente troppo
restrittivo.
Credo che la soluzione migliore sarebbe eliminare dallo
standard sia il concetto di CopyConstructible che quello di
Assignable per rimpiazzare la cosa citando quando e come
le funzioni di libreria possono usare assegnazioni, copy
constructor (o std::swap) per spostare o copiare gli
elementi. Tentare di associare una semantica a queste
operazioni e' complesso, limitante, e secondo me inutile.
Ci sono alcuni casi in cui sarebbe necessario aggiungere
qualche cautela (es. sorting e altri algoritmi in cui
confronti e spostamenti/copie sono usati contestualmente)
ma sono convinto che la definizione ottenuta di linguaggio
sarebbe meno confusa.
Per chi e' interessato alla cosa c'e' un thread su
comp.std.c++ in cui si discute di questo (what is
object "equivalence" ?)
Andrea