Newsgroup: it.comp.lang.c++
Titolo: Ancora liste standard C++ ...

(Il titolo cosě va bene, Alex?!)
Ho un dubbio sulle liste standard: io avrei bisogno di mantenere una
lista di classi costantemente ordinata, anche dopo un inserimento. Io
non ho trovato altro modo che chiamare il metodo sort() dopo ogni
inserimento. Questo metodo perň non mi soddisfa granchč, perchč io non
ho la minima idea di come sia implementata sort(), ma in ogni caso
credo sia troppo oneroso come algoritmo da chiamare ad ogni
inserimento. Sarebbe forse meglio un contenitore ordinato che va
subito ad inserire la classe al posto giusto...
Esiste un altro metodo?
GRAZIE
Daniele.


Puoi usare set, che e` un Sorted Associative Container.
Ecco un piccolo esempio preso dalla documentazione della STL
di SGI :
#include <set>
struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};
int main()
{
  const int N = 6;
  const char* a[N] = {"isomer", "ephemeral", "prosaic",
                      "nugatory", "artichoke", "serif"};
  const char* b[N] = {"flat", "this", "artichoke",
                      "frigate", "prosaic", "isomer"};
  set<const char*, ltstr> A(a, a + N);
  set<const char*, ltstr> B(b, b + N);
  set<const char*, ltstr> C;
  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
}
_________________________________________
Roberto Gerola
e-mail: 
roge...@tin.it
www: 
http://space.tin.it/computer/rgerola

Esiste un altro metodo?
Si`, c'e` un approccio generale, decisamente MOLTO
sofisticato, basato sull'osservazione che, nel 99% dei
casi in cui un analista ingenuo potrebbe pensare che
un dato contenitore "deve essere sortato in qualsiasi
momento", esso, in realta`, deve esserlo solo in certi
SPECIFICI momenti di "osservabilita`" -- i momenti
in cui quel contenitore viene "percorso" (e deve fornire
i suoi elementi in quel momento nel giusto ordine)
ovvero "frugato" (ricerca di un elemento, ad esempio
con binary_search).  A questo si unisce il fatto che, nel
mondo reale, molto spesso i contenitori "alternano"
FASI di "inserimento", in cui la grande maggioranza
delle operazioni sono appunto inserimenti di nuovi
elementi (o, in certi casi, cancellazione o alterazione
di elementi esistenti), e FASI di "percorso/fruga", in
cui la grande maggioranza delle operazioni non alterano
il contenitore.  I "contenitori bifasici" sono basati
sull'idea di trarre tutto il vantaggio da questo tipo di
"alternanza"; per chiarire, un modello semplificato
della completa pattern "contenitore bifasico" potrebbe
essere semplicemente:
    -- se arrivano nuovi elementi o altri "editing"
        (alterazioni/cancellazioni), entrare in "fase
        di alterazione" se gia` il contenitore non vi
        si trovava, e NON apportare modifiche al
        "corpo principale del contenitore" (che e`
        sortato), bensi` accumulare le richieste di
        editing in un buffer separato;
    -- se arriva una richiesta di "percorso" o "fruga",
        entrare in "fase di percorso" se gia` il contenitore
        non vi era, e quindi apportare tutti gli editing
        "pending" ripristinando il "corpo principale"
        del contenitore prima di concedere l'accesso
        "di fruga" (percorso o ricerca che sia)
Con questo approccio semplificato, la prima richiesta
"di fruga" dopo una sequenza di richieste "di editing"
puo` subire un notevole rallentamento, anche se il
"costo ammortizzato" resta potenzialmente molto buono;
fra i raffinamenti che portano da questo approccio piu`
semplice, a quello "completo" del pattern, vi e` lo
sfruttamento delle caratteristiche delle "heap" per
ammortizzare piu` uniformemente il costo (migliora
il ritardo di caso peggiore, con un lieve appesantimento
del ritardo medio e quindi lieve peggioramento del
throughput); inoltre, questo raffinamento permette di
"irrobustire" il passaggio di fase ("introdurre una
isteresi"), cosi` che una OCCASIONALE richiesta "di
fruga" ad un contenitore "in fase di editing", o viceversa,
non forza ancora la commutazione di fase, bensi` puo`
venire soddisfatta pur essendo "nella fase sbagliata".
Naturalmente, questa enorme complessita` implementativa
va giustificata NEI FATTI, verificando, anzitutto, che un
approccio piu` semplice ed elementare non sia gia` del
tutto soddisfacente.
L'approccio piu` semplice in assoluto e` usare un multiset
(std::multiset, naturalmente): questo e` mantenuto in
ordine ad ogni insert (ogni insert costa log K, quindi il
costo di mantenimento e` l'"imbattibile in astratto" N log N,
o meglio somma per i da 1 a N di log N, leggermente
inferiore ma asintoticamente equivalente), esattamente
come da specifiche.  Qualsiasi approccio piu` sofisticato
puo` battere questo se e solo se e` in grado di trarre
vantaggio, anche solo "euristicamente", da caratteristiche
di non-ergodicita` degli inserimenti (v. sopra ad esempio
il concetto di "fasi"), o da altri trucchi (radix sort, ecc).
[A volte, inoltre, il semplice fatto di poter passare a
multiset::insert un iteratore di "hint", se si ha gia` una
idea di dove probabilmente si inserira` il nuovo elemento,
puo` bastare per battere NlogN con un multiset: infatti,
se "ci prendo sempre" con l'iteratore che passo, allora il
costo di inserimento e` ammortizzato costante, invece
che log K...!  Naturalmente, se l'iteratore di "hint" e`
"sbagliato", il tempo rischia di _peggiorare_, invece che
di _migliorare_].
Non ho sotto mano in questo momento un riferimento
bibliografico per i "contenitori bifasici" (ricordo vagamente
che e` stata pubblicata nel C++ Report nel 97 o 98, ma,
pur essendo abbonato a C++ Report "da sempre", sono
sufficientemente disordinato che trovare il numero esatto
non e` un problema banale).  Ti consiglierei di provare
anzitutto con un semplice multiset, con o senza hint, e
vedere un poco se le caratteristiche di prestazioni che
ottieni cosi` sono gia` soddisfacenti; se no, puoi provare
anzitutto ad analizzare le pattern (in senso statistico!) di
inserimenti e "frughe" cui e` soggetto il tuo contenitore,
e su questa base vedere se una qualche versione abbastanza
semplice dei "contenitori bifasici" non possa gia` bastarti
(se VERAMENTE l'ordinamento DEVE essere garantito ad
ogni pie` sospinto, allora, scorda i contenitori bifasici, NON
PUOI fare meglio del multiset...!).
Alex

Puoi usare set, che e` un Sorted Associative Container.
std::set va benissimo, naturalmente, se non possono
mai essere in lista due elementi equivalenti (cioe` tali
che, per l'ordinamento debole D usato, x D y e` falso
e y D x e` pur esso falso); io suggerivo std::multiset
in quanto, in generale, non si puo` escludere che
interessi anche tenere nel contenitore elementi fra
loro equivalenti.  In questo caso e` da notare che
l'ordinamento imposto da multiset NON e` "stabile"
(elementi equivalenti possono trovarsi in qualsiasi
ordine fra loro), quindi puo` darsi che convenga in
ogni caso (se interessa la "stabilita`") usare un set,
_arricchendo_ gli elementi di un identificatore unico
(ad esempio, l'ordine progressivo di arrivo nel
contenitore) in modo da escludere l'equivalenza.
Alex