Newsgroup: it.comp.lang.c++
Titolo: Ancora set

Assumete di avere un set contenente n oggetti e di modificare ad un 
certo punto l'operatore usato in std::set per confrontare gli oggetti. 
La modifica è tale che cambia soltanto l'ordine tra k (k <= n) oggetti 
adiacenti (nel mio caso, l'ordine viene invertito).
Il modo più efficiente è senz'altro quello di modificare il contenuto 
degli oggetti ad insaputa di set (se sono grandi allora si useranno dei 
puntatori al posto degli oggetti stessi).
Secondo voi ci potrebbe essere qualche problema?
A meno che std::set non faccia cose particolari, la modifica dovrebbe 
passare del tutto inosservata.
Kiuhnm

 dovrebbe passare del tutto inosservata.
Anche se dovesse funzionare (e sono dell'avviso che non lo faccia
mai), non ci farei affidamento: dipende *molto* dall'implementazione.
--
Marco
 
-- 
I'm trying a new usenet client for Mac, Nemo OS X.
You can download it at 
http://www.malcom-mac.com/nemo

 mai), non ci farei affidamento: dipende *molto* dall'implementazione.
Non ti pare di essere un po' avventato nel trarre conclusioni? E' vero 
l'esatto contrario di quanto affermi.
L'unico modo che l'algoritmo ha per accorgersi del cambiamento è quello di
1) accedere al contenuto dei *miei* oggetti,
2) accedere al codice della *mia* funzione.
Kiuhnm

 adiacenti (nel mio caso, l'ordine viene invertito).
Fammi capire: a un certo punto, dopo aver inserito un certo numero di
elementi nel set, tu cambi qualcosa (un flag statico, mettiamo) e
l'operatore di confronto inizia a comportarsi diversamente?
E come pensi che 'set' possa, ad esempio, ritrovare gli elementi
precedetemente inseriti se il criterio di confronto non corrisponde più a
quello usato fino a quel momento per costruire e aggiornare la struttura
dati interna?
Forse sono io che non capito.
Max

 dati interna?
V. risposta a pan.
Kiuhnm

 V. risposta a pan.
Considera il seguente codice. Come vorresti che si comportasse? Sul mio
sistema stampa 1 e 0.
  bool abormal = false;
  struct Int
  {
        int i;
        Int(int i): i(i) { }; 
        bool operator<(const Int& b ) const
        {
                if( abormal ) return b.i < i;
                else return i < b.i;
        }
  };
 
  int main(int argc, char* argv[] )
  {
        std::set<Int> s;
        s.insert(1);
        s.insert(2);
        cerr << s.count(2) << endl;
        abormal = true;
        cerr << s.count(2) << endl;
 
  }
 

  2) accedere al codice della *mia* funzione.
Ribadisco che la struttura dell'albero (se il set e' implementato come
albero, com'e' nella maggioranza dei casi) e' creata
all'inserimento,non alla ricerca.
Se tu tra inserimento e ricerca modifichi i dati, rendi la
ricercaimpossibile in generale.


   }
Cosa pretendi? Hai modificato "<" senza invertire il contenuto degli 
elementi. Se rileggi il mio post originale, vedrai che la situazione è 
diversa.
Faccio un esempio concreto.
Se prendi la sequenza ordinata di oggetti
o_1 < o_2 < o_3 < o_4 < o_5 < o_6 < o_7
e la riscrivi come
o_1 < o_2 < o < o_6 < o_7        (1)
vedi chiaramente che qualsiasi modifica avvenga all'interno di "o" non 
altera la consistenza della sequenza purché "o" sia internamente 
consistente.
Allora puoi modificare "<" in modo che la (1) resti valida e si abbia
o_3 > o_4 > o_5
e puoi quindi scambiare il contenuto di o_5 con quello di o_3 in modo 
che si abbia nuovamente
o_3 < o_4 < o_5.
Se veramente std::set utilizza solo "<" per decidere l'ordine tra gli 
oggetti, allora la modifica passerà del tutto inosservata, in quanto le 
due sequenze sono "equivalenti" rispetto all'operatore "<".
Nota che modificando solo il contenuto degli oggetti, manteniamo 
consistenti anche tutti i puntatori.
Ho considerato una sequenza e non un albero, poiché è evidente che se la 
sequenza ordinata è consistente allora lo è anche l'albero.
Se questo non bastasse come esempio, immagina di moltiplicare le chiavi 
di tutti i tuoi elementi per 10. Il container si accorgerà della 
differenza, secondo te?
Ma a che serve tutto questo?
Immagina di avere una serie di oggetti disposti nel piano, e di avere un 
"oggetto" che passando sopra di essi ne altera la disposizione in modo 
prevedibile.
Ogni volta che l'oggetto esegue una modifica tra una serie di oggetti 
o_1, o_2, ..., o_k, si eliminano tali oggetti dalla struttura dati S, si 
modifica "<" in modo che tutti gli oggetti in S non risentano del 
cambiamento e quindi si reinseriscono gli oggetti in S.
Ma ammetti adesso di sapere già che l'oggetto non fa altro che invertire 
l'ordine della sequenza o_1, o_2, ..., o_k, dove, in S, non vi è alcun 
oggetto tra o_1, o_2, o_3, ecc... Perché non scambiare direttamente il 
contenuto di tali oggetti? L'effetto è il medesimo e il codice è di gran 
lunga più efficiente.
Kiuhnm

 ricerca impossibile in generale.
Sei in errore. Leggi la risposta a Max M. Se neanche questo basta, pazienza.
Kiuhnm

 elementi.
Vabbé, allora non avevo capito quello che intendevi.
A 'std:set' non importa nulla del contenuto degli oggetti. L'unica cosa che
utilizza è l'oggetto "funzionale" con cui effettua il confronto (che di
default è less<T>, che chiama operator<).
Tu puoi cambiare quello che vuoi dentro gli oggetti (beh, 'set' ti dà solo
dei rifeirmenti 'const', ma basta usare membri mutable). Se il confronto
tra due qualsiasi degli oggetti che 'set' controlla dà lo stesso risultato
che dava quando gli oggetti sono stati inseriti, dal punto di vista di
'set' non è cambiato assolutamente nulla.
Max

 'set' non è cambiato assolutamente nulla.
Oppure fai come Schildt e usi l'asm in linea ;-)
Kiuhnm

 prevedibile.
stai scrivendo algoritmi di elisione dei vertici nascosti ("in 
ombra") per l'ottimizzazione della reappresentazione 
tridimensionale di una scena ?
Soviet


 per l'ottimizzazione della reappresentazione tridimensionale di una scena ?
E' cosě, perň attualmente sto implementando la classe per trovare i 
punti d'intersezione tra un insieme di segmenti. L'algoritmo semplice 
(Bentley-Ottmann) č facilissimo da capire e ben piů difficile da 
implementare in modo robusto ed efficiente (snapping grid, floating 
point filters, ecc...). Purtroppo non si puň lavorare con i numeri 
reali, ma ci si deve accontentare dei floating point con tutti i 
problemi che ne seguono.
Fine dello sfogo.
Kiuhnm

 Kiuhnm <kiuhnm03_NO@SPAM_yahoo.it>
wrote:


rileggi: "in generale". Se ci sono casi specifici in cui
l'accrocchiofunziona, buon per te.
