Newsgroup: it.comp.lang.c++
Titolo: Ordinamento Lista

Saluti a tutti.
riprendo il thread sugli algoritmi di ordinamento qui, per non fare
confusione con altre domande.
Se io avessi una lista nella quale inserisco un solo elemento per volta,
volendo mantenere la lista ordinata DOPO OGNI inserimento, quale
strategia risulta più performante secondo voi?
Non conosco come è implementato l'algoritmo std sort(), ma dubito che la
cosa migliore sia inserire in fondo o in cima ed usare l'algoritmo std
sort();
Forse è meglio cercare la posizione di inserimento scorrendo ogni volta
la lista fino a che trovo un valore maggiore dell'elemento da inserire
(nel caso la lista sia ordinata in ordine crescente)?
Grazie
Saluti
Libra
--

 strategia risulta più performante secondo voi?
NON usare una lista.  Questo e' il caso tipico che richiede un albero
binario...  La stategia piu' performante e' uno std::set.
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Dept. of Physics, Univ. of Padova, Italy          loreti at pd dot infn dot it

 binario...  La stategia piu' performante e' uno std::set.
Ah!
Potresti indicarmi dove trovare qualche esempio per approfondire?
grazie mille
Libra
-- 

> Potresti indicarmi dove trovare qualche esempio per approfondire?
Ti rispondo io:
il set non consente di avere più volte lo stesso valore nell'insieme. Se tu
volevi usare le liste forse ti interessa avere elementi duplicati, per cui
il multiset mi sembra più appropriato.
Trovi molti esempi nella documentazione della stl sgi:
Multiset: 
http://www.sgi.com/tech/stl/multiset.html
Tutta la libreria: 
http://www.sgi.com/tech/stl/
Ti copio un esempio leggermente modificato da me:
#include <set>
#include <algorithm>
using namespace std;
int main()
{
  const int N = 10;
  int a[N] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};
  int b[N] = {4, 4, 2, 4, 2, 4, 0, 1, 5, 5};
  multiset<int> A(a, a + N);
  multiset<int> B(b, b + N);
  multiset<int> C;
  A.insert(11); // qui inserisco un nuovo elemento; con il cout vedrai che i
multiset sono ordinati
  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<int>(cout, " "));
  cout << endl;
  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<int>(cout, " "));
  cout << endl;
  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()));
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
}
Ciao!
--
"to mp3 or not to mp3; this is the question"
(un felice possessore di iRiver iMP-250; vedere 
www.iriver.com/english
 e
www.soluzionimp3.com
 )

 a écrit dans le message news:
abo814$do8$1...@dante.italia.com...
Ciao Mixer,
grazie per l'esempio.
Bisogna pero' aggiungere :
#include <iostream>
all'inizio, altrimenti il compilatore si arrabbia.
Maurus


Hai ragione, però il mio g++ non si arrabbia affatto: gcc version 2.96
20000731 (Red Hat Linux 7.1 2.96-98)
Forse era già incluso da set o algorithm.

ciao! ho visto ke ti hanno già risp ma un altra voce in capitolo non penso
sia male no!? 
beh ti dirò, secondo me non è complicato inserire ordinatamente in lista e
neanke "laborioso"...
bisognerebbe vedere ke tipo di ordinamento vuoi.. alfabetico? dal più
grande al più piccolo?
prendo ad esempio l ordinamento alfabetico con la "tipica" rubrica (poi te
lo modifiki te per le tue esigenze ;)
ti do parte del codice programmato con le classi... quindi se te lavori
con struct lo devi rivedere...
 (classe persona, funzione addANDdisposeName_by_RaffoZz ^_^ )
class persona {
 
  public: 
  void addANDdisposeName ( char [], char [], persona* & );
  private:
  char nome[20];
  char numero[10];
  persona* nextPtr;  
  };
void persona::addANDdisposeName ( char newName[], char newNumber[],
persona* &testaDiRubrica ) { 
  // inserimento e ordinamento nomi in lista: 
  // alla funzione arrivano il nome e numero della persona da inserire
(immessi nel main) 
  // e il collegamento al primo puntatore della lista 
              persona* prec = testaDiRubrica;  // creo un puntatore all
elemento precedente            
              persona* p;                      // e un puntatore di
ricerca (all elemento successivo)
 
for ( p = prec; p != NULL && strcmp ( p->nome, newName ) < 0; p =
p->nextPtr) 
  // ricerco la posizione dove poter inserire il nuovo dato con la
funzione strcmp ke mi confronta
  // il nuovo nome con quelli in lista: appena il nome confrontato risulta
<0 ho trovato la posizione
 
              prec = p;  // prec avanza una volta in meno di p, quindi ora
abbiamo questa situazione:
            ______          ______
     ----> | dato | -----> | dato | ---->
            ------          ------
               ^               ^
               |               |
               |               | 
           ptr.prec          ptr.p
    (fra i due ptr ci sarà il nostro nuovo dato (r) da inserire...)
 
              persona* r = new persona;  // creo il nuovo dato da
immettere in lista
 
  // e copio i dati:
              char tempName[20];  
              char tempNumber[10];
              strcpy( tempName, newName); 
              r->nome = tempName;              // copio  il nome    
              strcpy( tempNumber, newNumber);  
              r->numero = tempNumber;          // e il numero 
              r->nextPtr = p;             // (1) dico ke il suo ptr
punterà al ptr dell elemento successivo 
              if ( p != testaDiRubrica )  // e se la lista non è vuota
              prec->nextPtr = r;          // (2) lo inserisco nella
posizione in cui si trova
                                          // (prec potrebbe anke esser la
testa della lista
                                          // quindi p potrebbe diventare
primo elemento...)
              else                        // sennò inserisco all inizio   
 
              testaDiRubrica = r;         // e lo faccio diventare primo
elemento...
             }   
 // così si avrà:  
            ______                ___
     ----> | prec |              | p | ---->
            ------                ---
               |                   ^
               |                   |
               |                   | 
                \ (2)   ___   (1) /
                 \---> | r | ----/
                        ---
 // quindi:
            ______        ___        ______
     ----> | dato | ---> | r | ---> | dato | ---->
            ------        ---        ------
 //END ^_^  
spero sia stato cmq utile... semmai rimarrà un aiuto in più :)
cyacya!                               

 sia male no!?
Ciao
Ti ringrazio per la tua spiegazione. Il problema non è come farlo; il
problema è farlo nel modo più efficiente (nel minor tempo) dato che gli
inserimenti sono continui.
Ora però ti do io una dritta  ;-)
perché non usi le STL per le liste?
ti risparmi un bel pò di lavoro.
Ciao
Libra
--

 Tutta la libreria: 
http://www.sgi.com/tech/stl/
Ringrazio tutti per i consigli e i link.
Ciao
Libra